Изменения
Нет описания правки
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''иммунным''', если <tex>A</tex> — бесконечное, для любого бесконечного перечислимого множества <tex>B</tex>, <tex>B \not \subset A</tex>.
}}
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''', если <tex>A</tex> — перечислимое, бесконечное, и дополнение <tex>A</tex> — иммунное.
}}
|proof=
Рассмотрим все программы.
Для некоторого перечислимого языка, какая-то из них является его перечислителем.
Рассмотрим программу <tex>q</tex>:
{{Лемма
|statement=Для любого перечислимого множества <tex>B</tex>, существует его элемент принадлежащий <tex>E(q)</tex>.
|proof=
В <tex>E(q)</tex> будет содержаться первый элемент множества <tex>B</tex> не превосходящий <tex>2 i</tex>, где <tex>i</tex> — номер перечислителя множества <tex>B</tex>
|statement=Для любого перечислимого множества <tex>B</tex> <tex>B \not \subset \overline{E(q)}</tex>.
|proof=
Cуществует элемент <tex>B</tex> , принадлежащий <tex>E(q)</tex>, и следовательно не принадлежащий <tex>\overline{E(q)}</tex>.
}}
|statement=<tex>\overline{E(q)}</tex> — бесконечно.
|proof=
Среди чисел от <tex>1</tex> до <tex>k</tex>, множеству <tex>E(q)</tex> принадлежат не более <tex>\frac{k}{2}</tex>.
Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\frac{k}{2}</tex>
}}
}}
== Литература ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
