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