Изменения
йдется
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set''), если <tex>A</tex> — перечислимое, бесконечное и дополнение <tex>\overline{A}</tex> {{---}} иммунное.
}}
Рассмотрим все программы.
Для некоторого [[Перечислимые_языки | перечислимого языка ]] какая-то из них является его перечислителем.Рассмотрим программу <tex>q</tex>:
Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы.
===Лемма 1===
Необходимо, чтобы перечислимое множество <tex>E(q)</tex> имело иммунное дополнение. Это означает, что <tex>E(q)</tex> должно пересекаться с любым бесконечным перечислимым множеством.
{{Лемма
|id= ==lemma==
|about=1
|statement=Для любого бесконечного перечислимого множества <tex>B</tex> существует его элемент, принадлежащий <tex>E(q)</tex>.
|proof=
}}
===Лемма 2===
{{Лемма
|id= ==lemma==
|about=2
|statement=Для любого бесконечного перечислимого множества <tex>B</tex> верно, что <tex>B \not \subset \overline{E(q)}</tex>.
|proof=
}}
===Лемма 3==={{Лемма|id= ==lemma==|about=3
|statement=<tex>\overline{E(q)}</tex> {{---}} бесконечно.
|proof=
Среди чисел от <tex>1</tex> до <tex>k</tex> множеству <tex>E(q)</tex> принадлежат не более <tex>\fracdfrac{k}{2}</tex>.Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\fracdfrac{k}{2}</tex>.
}}
Теперь докажем теорему.
{{Теорема
|statement=Существует простое множество.
|proof=
}}Простые множества являются примерами перечислимых множеств, не являющихся <tex>\overline{E(q)}m</tex> {{-полными<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58. ISBN 5-900916-36-}} иммунно7]</ref>.Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы <tex>E(q)m</tex> {{-полным <ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012.c. 62. ISBN 5-900916-36-}} простое7]</ref>. .
== Литература Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
* [https://en.wikipedia.org/wiki/Simple_set Wikipedia {{---}} Simple set]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория:Разрешимые и перечислимые языки]]