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

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


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


Теорема:
Доказательство:
[math]\triangleright[/math]

Рассмотрим все программы в порядке нумерации, каждая из них задает некоторый перечислимый язык, причем каждому языку соответствует программа. Напишем следующую программу q:

q:
 for (TL = 1 .. [math]+\infty[/math])
  for (i = 1 .. TL)
   запустить [math]U(i, \varepsilon)[/math] на TL шагов (U - универсальная программа) 
   напечатать первый [math]x \ge 2 * i[/math], который вывела эта программа


Множество E(q), которое перечисляет эта программа - бесконечно - перечислимо

Дополнение этого множества [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]