Изменения
Нет описания правки
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set'' ), если <tex>A</tex> — перечислимое, бесконечное и дополнение <tex>A</tex> {{---}} иммунное.
}}
==Теорема о простом множестве==
{{Теорема
|statement=Существует простое множество.
Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы.
===Лемма 1===
Необходимо, чтобы перечислимое множество <tex>E(q)</tex> имело иммунное дополнение. Это означает, что <tex>E(q)</tex> должно пересекаться с любым бесконечным перечислимым множеством.
По построению, для любого множества <tex> B </tex> в <tex>E(q)</tex> будет содержаться первый его элемент не меньший <tex>2 i</tex>, где <tex>i</tex> {{---}} номер перечислителя множества <tex>B</tex>.
}}
===Лемма 2===
{{Лемма
|id= ==lemma==
[[#lemma (1)|По первой лемме]] существует элемент <tex>B</tex>, принадлежащий <tex>E(q)</tex>, и, следовательно, не принадлежащий <tex>\overline{E(q)}</tex>.
}}
===Лемма 3===
{{Лемма
|id= ==lemma==
Получаем:
[[Иммунные и простые множества#Лемма (2)|Из леммы (2)]] и [[Иммунные и простые множества#Лемма(3)Лемма3|из леммы (3)]] следует, что <tex>\overline{E(q)}</tex> {{---}} иммунно.По построению <tex>E(q)</tex> перечислимо, его дополнение иммунно и, [[Иммунные и простые множества#Лемма(3)|по лемме (3)]], бесконечно, а значит {{---}} оно простое.
}}
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост (англ. ''Post'' ) искал пример перечислимого неразрешимого множества, которое не было бы m-полным.
== Литература Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
