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

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

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

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

Множество натуральных чисел [math]A[/math] называется простым, если [math]A[/math] — перечислимое, бесконечное, и дополнение [math]A[/math] — иммунное.

Теорема:

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

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

[math]\triangleright[/math]

Рассмотрим все программы. Для некоторого перечислимого языка, какая-то из них является его перечислителем. Рассмотрим программу [math]q[/math]: [math]q[/math]: 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] Множество [math]E(q)[/math], которое перечисляет эта программа: перечислимо. бесконечно. Для любого [math]i[/math] существует бесконечное множество с номером перечислителя большим [math]i[/math], и в этом множестве есть элемент [math]x \geqslant 2 * i[/math]. Дополнение этого множества [math]\overline{E(q)}[/math]: бесконечно. Для первых [math]k[/math] слов, множеству [math]E(q)[/math] принадлежат не более [math]\frac{k}{2}[/math]. для любого перечислимого множества [math]B[/math], существует его элемент принадлежащий [math]E(q)[/math], и следовательно не принадлежащий [math]\overline{E(q)}[/math], отсюда следует [math]B \not \subset \overline{E(q)}[/math] Таким образом [math]\overline{E(q)}[/math] — иммунно, а [math]E(q)[/math] — простое.

[math]\triangleleft[/math]