Изменения
Нет описания правки
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''', если <tex>A</tex> — перечислимое, бесконечное и дополнение <tex>A</tex> — {{---}} иммунное.
}}
Обозначим <tex>E(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>\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>E(q)</tex> — {{---}} простое.
}}
