Изменения
Нет описания правки
напечатать первый <tex>x</tex>, который вывела эта программа, такой что <tex>x \geqslant 2 i</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>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>
}}
Вернемся к доказательству теоремы.
Получаем:
