Изменения
Нет описания правки
{{Определение|definition = Множество А называется имунным, если А - бесконечное, для любого бесконечного перечислимого B, <tex>B \not \subset A</tex>.}}
{{Определение
|definition = Множество A называется простым, если A - перечислимое, бесконечное, и дополнение A - имунно.
}}
{{Теорема|statement=|proof=Рассмотрим все перечислимые языки программы в лексикографическом порядке их перечислителей p_1нумерации,p_2каждая из них задает некоторый перечислимый язык,причем каждому языку соответствует программа...,p_nНапишем следующую программу q:
Множество E(q), которое перечисляет эта программа - бесконечно- перечислимо Дополнение этого множества <tex>\overline{E(q)}</tex>- бесконечно, для первых k слов, множеству E(q) принадлежат не более <tex>\frac{k}{2}</tex>- Для любого перечислимого множества B, существует его элемент принадлежащий <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> --- простое.}}
