Материал из Викиконспекты
| Определение: |
| Множество А называется имунным, если А - бесконечное, для любого бесконечного перечислимого 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)
запустить i-ую программу на TL шагов (U - универсальная программа)
напечатать первый [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] |
