Иммунные и простые множества

Определение:

Множество А называется имунным, если А - бесконечное, для любого бесконечного перечислимого B, [math]B \not \subset A[/math].

Определение:

Множество A называется простым, если A - перечислимое, бесконечное, и дополнение A - имунно.

Теорема:

Существует простое множество.

Доказательство:

[math]\triangleright[/math]

Рассмотрим все программы, каждая из них задает некоторый перечислимый язык, причем каждому перечислимому языку соответствует какая-то программа - его перечислитель. Напишем следующую программу q: q: for [math](TL = 1\ \ldots +\infty)[/math] for [math](i = 1\ \ldots TL)[/math] запустить [math]i[/math]-ую в главной нумерации программу на [math]TL[/math] шагов напечатать первый [math]x[/math], который вывела эта программа, такой что [math]x \geqslant 2 i[/math] Множество E(q), которое перечисляет эта программа: перечислимо; бесконечно (Существует бесконечное количество бесконечных множеств. В каждом из них есть элемент [math]x \geqslant 2 * i[/math], где i - номер программы перечисляющей это множество.) Дополнение этого множества [math]\overline{E(q)}[/math]: бесконечно. Для первых k слов, множеству E(q) принадлежат не более [math]\frac{k}{2}[/math]. для любого перечислимого множества B, существует его элемент принадлежащий [math]E(q)[/math], и следовательно не принадлежащий [math]\overline{E(q)}[/math], [math]\overline{E(q)} \not \subset A[/math] Таким образом [math]\overline{E(q)}[/math] --- имунно, а [math]E(q)[/math] --- простое.

[math]\triangleleft[/math]