Изменения

|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set''), если <tex>A</tex> — перечислимое, бесконечное и дополнение <tex>\overline{A}</tex> {{---}} иммунное.

{{==Теорема|statementо существовании простого множества=Существует простое множество.|proof=

Для некоторого [[Перечислимые_языки | перечислимого языка ]] какая-то из них является его перечислителем.Рассмотрим программу <tex>q</tex>:

Рассмотрим программу <tex>q</tex>(): '''for''' <tex>TL = 1\ \ldots +\infty</tex> '''for''' <tex>i = 1\ \ldots TL</tex> запустить <tex>i</tex>-ую в [[Главные нумерации|главной нумерации]] программу на <tex>TL</tex> шагов напечатать первый <tex>x</tex>, который вывела эта программа, такой что <tex>x \geqslant 2 i;</tex> ничего не печатать, если такого числа не найдется.

В По построению, для любого множества <tex> B </tex> в <tex>E(q)</tex> будет содержаться первый его элемент множества <tex>B</tex> не меньший <tex>2 i</tex>, где <tex>i</tex> {{---}} номер перечислителя множества <tex>B</tex>.

  ===Лемма 2===

Cуществует [[#Лемма 1|По первой лемме]] существует элемент <tex>B</tex>, принадлежащий <tex>E(q)</tex>, и, следовательно, не принадлежащий <tex>\overline{E(q)}</tex>.

  ===Лемма 3==={{Лемма|id= ==lemma==|about=3

Среди чисел от <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>.

}}Простые множества являются примерами перечислимых множеств, не являющихся <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>. .

}}== См. также ==*[[Перечислимые языки]]*[[m-сводимость]]== Примечания == <references />

== Литература Источники информации ==