Изменения

Перейти к: навигация, поиск

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

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

Навигация