Изменения

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

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

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

Для некоторого [[Перечислимые_языки | перечислимого языка, ]] какая-то из них является его перечислителем. 

<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> ничего не печатать, если такого числа не найдется.

 Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы.===Лемма 1=== Необходимо, чтобы перечислимое множество <tex>E(q)</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>B</tex> не превосходящий меньший <tex>2 i</tex>, где <tex>i</tex> — {{---}} номер перечислителя множества <tex>B</tex>.

|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>\fracdfrac{k}{2}</tex>.Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\fracdfrac{k}{2}</tex>.

Получаем:Теперь докажем теорему.{{Теорема|statement=Существует простое множество.|proof=   [[#Лемма 2|Из леммы (2)]] и [[#Лемма3|из леммы (3)]] следует, что <tex>\overline{E(q)}</tex> — {{---}} иммунно.По построению <tex>E(q)</tex> — перечислимо, его дополнение иммунно и, [[#Лемма 3|по лемме (3)]], бесконечно, а значит {{---}} оно простое.