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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Множество натуральных чисел [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]B[/math], существует его элемент принадлежащий [math]E(q)[/math]
Доказательство:
[math]\triangleright[/math]
В [math]E(q)[/math] будет содержаться первый элемент множества [math]B[/math] не превосходящий [math]2 i[/math], где [math]i[/math] — номер перечислителя множества [math]B[/math]
[math]\triangleleft[/math]


Лемма:
для любого перечислимого множества [math]B[/math] [math]B \not \subset \overline{E(q)}[/math]
Доказательство:
[math]\triangleright[/math]
существует элемент [math]B[/math] принадлежащий [math]E(q)[/math], и следовательно не принадлежащий [math]\overline{E(q)}[/math].
[math]\triangleleft[/math]


Лемма:
[math]\overline{E(q)}[/math] — бесконечно.
Доказательство:
[math]\triangleright[/math]

Среди чисел от [math]1[/math] до [math]k[/math], множеству [math]E(q)[/math] принадлежат не более [math]\frac{k}{2}[/math].

Следовательно [math]\overline{E(q)}[/math] принадлежат не менее [math]\frac{k}{2}[/math]
[math]\triangleleft[/math]


Получаем:

[math]\overline{E(q)}[/math] — иммунно.

[math]E(q)[/math] — простое.
[math]\triangleleft[/math]