Изменения
Нет описания правки
{{Определение
|definition = Множество А называется '''имунным''', если А - бесконечное, для любого бесконечного перечислимого B, <tex>B \not \subset A</tex>.
}}
{{Определение
|definition = Множество A называется '''простым''', если A - перечислимое, бесконечное, и дополнение A - имунно.
}}
{{Теорема
|statement=Существует простое множество.
|proof=
Рассмотрим все программы в порядке нумерации, каждая из них задает некоторый перечислимый язык, причем каждому языку соответствует программа.
Напишем следующую программу q:
for (TL = 1 .. <tex>+\infty</tex>)
for (i = 1 .. TL)
запустить <tex>U(i, \varepsilon)</tex> -ую программу на TL шагов (U - универсальная программа)
напечатать первый <tex>x \ge 2 * i</tex>, который вывела эта программа
Множество E(q), которое перечисляет эта программа:- * перечислимо;* бесконечно(Существует бесконечное количество бесконечных множеств. В каждом из них есть элемент <tex>x \ge 2 * i</tex>, где i - перечислимономер программы перечисляющей это множество.)
Дополнение этого множества <tex>\overline{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> --- простое.
}}
