Изменения
Нет описания правки
{{Определение
|definition = Множество <tex>A</tex> называется '''иммунным''', если <tex>A</tex> - — бесконечное, для любого бесконечного перечислимого <tex>B</tex>, <tex>B \not \subset A</tex>.
}}
{{Определение
|definition = Множество <tex>A</tex> называется '''простым''', если <tex>A</tex> - — перечислимое, бесконечное, и дополнение <tex>A</tex> - — иммунно.
}}
|statement=Существует простое множество.
|proof=
Рассмотрим все программы, каждая из них задает некоторый перечислимый язык, причем каждому перечислимому языку соответствует какая-то программа - — его перечислитель.
Напишем следующую программу <tex>q</tex>:
* для любого перечислимого множества <tex>B</tex>, существует его элемент принадлежащий <tex>E(q)</tex>, и следовательно не принадлежащий <tex>\overline{E(q)}</tex>, <tex>\overline{E(q)} \not \subset A</tex>
Таким образом <tex>\overline{E(q)}</tex> --- — иммунно, а <tex>E(q)</tex> --- — простое.
}}
