Иммунные и простые множества — различия между версиями
Строка 65: | Строка 65: | ||
}} | }} | ||
− | Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост | + | Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы m-полным. |
== См. также == | == См. также == | ||
*[[Перечислимые языки]] | *[[Перечислимые языки]] |
Версия 15:44, 1 ноября 2016
Определение: |
Множество натуральных чисел | называется иммунным (англ. immune set), если оно бесконечно и не содержит бесконечных перечислимых подмножеств.
Определение: |
Множество натуральных чисел | называется простым (англ. simple set), если — перечислимое, бесконечное и дополнение — иммунное.
Содержание
Теорема о простом множестве
Теорема: | ||||||||||||||||||
Существует простое множество. | ||||||||||||||||||
Доказательство: | ||||||||||||||||||
Рассмотрим все программы. Для некоторого перечислимого языка какая-то из них является его перечислителем. Рассмотрим программу : главной нумерации программу на шагов напечатать первый , который вывела эта программа, такой что: for for запустить -ую в
Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы. Лемма 1Необходимо, чтобы перечислимое множество имело иммунное дополнение. Это означает, что должно пересекаться с любым бесконечным перечислимым множеством.
Лемма 2
Лемма 3
Вернемся к доказательству теоремы. Получаем: Из леммы (2) и из леммы (3) следует, что — иммунно. По построению перечислимо, его дополнение иммунно и, по лемме (3), бесконечно, а значит — оно простое. | ||||||||||||||||||
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы m-полным.
См. также
Источники информации
- Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
- Wikipedia — Simple set