Множество <tex>E(q)</tex>, которое перечисляет эта программа:
* перечислимо.
* бесконечно. Для любого <tex>i</tex> существует бесконечное множество с номером перечислителя большим <tex>i</tex>, и в этом множестве есть элемент <tex>x \geqslant 2 * i</tex>.
Дополнение этого множества Обозначим <tex>\overline{E(q)}</tex>:— множество, которое перечисляет эта программа.{{Лемма* бесконечно. |statement=Для первых любого перечислимого множества <tex>kB</tex> слов, множеству существует его элемент принадлежащий <tex>E(q)</tex>|proof=В <tex>E(q)</tex> принадлежат будет содержаться первый элемент множества <tex>B</tex> не более превосходящий <tex>\frac{k}{2}i</tex>, где <tex>i</tex> — номер перечислителя множества <tex>B</tex>.* }} {{Лемма|statement=для любого перечислимого множества <tex>B</tex>, <tex>B \not \subset \overline{E(q)}</tex>|proof=существует его элемент <tex>B</tex> принадлежащий <tex>E(q)</tex>, и следовательно не принадлежащий <tex>\overline{E(q)}</tex>.}}{{Лемма|statement=<tex>\overline{E(q)}</tex> — бесконечно.|proof=Для первых <tex>k</tex> слов, отсюда следует множеству <tex>E(q)</tex> принадлежат не более <tex>\frac{k}{2}</tex>.Следовательно <tex>B \not overline{E(q)}</tex> принадлежат не менее <tex>\subset frac{k}{2}</tex>}} Получаем:<tex>\overline{E(q)}</tex>— иммунно.<tex>E(q)</tex> — простое.
Таким образом <tex>\overline{E(q)}</tex> — иммунно, а <tex>E(q)</tex> — простое.
}}
