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