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

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

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

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

Множество натуральных чисел [math]A[/math] называется простым (англ. simple set), если [math]A[/math] — перечислимое, бесконечное и [math]\overline{A}[/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] — множество, которое перечисляет эта программа.

Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы.

Лемма 1

Необходимо, чтобы перечислимое множество [math]E(q)[/math] имело иммунное дополнение. Это означает, что [math]E(q)[/math] должно пересекаться с любым бесконечным перечислимым множеством.

Лемма (1):

Для любого бесконечного перечислимого множества [math]B[/math] существует его элемент, принадлежащий [math]E(q)[/math].

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

[math]\triangleright[/math]

По построению, для любого множества [math] B [/math] в [math]E(q)[/math] будет содержаться первый его элемент не меньший [math]2 i[/math], где [math]i[/math] — номер перечислителя множества [math]B[/math].

[math]\triangleleft[/math]

Лемма 2

Лемма (2):

Для любого бесконечного перечислимого множества [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]

Лемма 3

Лемма (3):

[math]\overline{E(q)}[/math] — бесконечно.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Теперь докажем теорему.

Теорема:

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

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

[math]\triangleright[/math]

Из леммы (2) и из леммы (3) следует, что [math]\overline{E(q)}[/math] — иммунно. По построению [math]E(q)[/math] перечислимо, его дополнение иммунно и, по лемме (3), бесконечно, а значит — оно простое.

[math]\triangleleft[/math]

Простые множества являются примерами перечислимых множеств, не являющихся [math]m[/math]-полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы [math]m[/math]-полным . .

См. также

• Перечислимые языки
• m-сводимость

Источники информации

• Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
• Wikipedia — Simple set