Материал из Викиконспекты
| Определение: |
| Множество натуральных чисел [math]A[/math] называется иммунным (англ. immune set ), если оно бесконечно и не содержит бесконечных перечислимых подмножеств. |
| Определение: |
| Множество натуральных чисел [math]A[/math] называется простым (англ. simple set ), если [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] | |
Cуществует элемент [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] |
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост (англ. Post ) искал пример перечислимого неразрешимого множества, которое не было бы m-полным.
- Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
- Wikipedia — Simple set
