Імунні та прості множини

Визначення:
Безліч натуральних чисел [math]A[/math] називаєтьсяімунним(англ.immune set), якщо воно нескінченне і не містить нескінченних перелічуваних підмножин.

Визначення:
Безліч натуральних чисел [math]A[/math] називаєтьсяпростим(англ.simple set), якщо [math]A[/math] — перераховане, нескінченне і [math]\ overline[/math] - імунне.

Розглянемо усі програми. Для деякого перелічуваного мови якась із них є його перечислювачем. Розглянемо програму [math]q[/math]:

Позначимо [math]E(q)[/math] — множина, яку перераховує ця програма.

Доведемо кілька лем, у тому числі буде очевидна правильність утвердження теореми.

Лемма 1 [ред.]

Необхідно, щоб множина [math]E(q)[/math] мала імунне доповнення. Це означає, що [math]E(q)[/math] має перетинатися з будь-яким нескінченним переліченим безліччю.

Лемма (1):
Для будь-якої нескінченної множини [math]B[/math] існує його елемент, що належить [math]E(q)[/math] .
Доказ:
[math]\triangleright[/math]
За побудовою, для будь-якої множини [math] B [/math] в [math]E(q)[/math] буде утримуватися перший його елемент не менший [math]2 i[/math] , де [math]i[/ math] - номер перелічувача множини [math]B[/math].
[math]\triangleleft[/math]

Лемма 2 [ред.]

Лемма (2):
Для будь-якої нескінченної перелічуваної множини [math]B[/math] вірно, що [math]B \not \subset \overline[/math] .
Доказ:
[math]\triangleright[/math]
По першій лемі існує елемент [math]B[/math] , що належить [math]E(q)[/math] , і, отже, не належить [math]\overline[/math] .
[math]\triangleleft[/math]

Лемма 3 [ред.]

Серед чисел від [math]1[/math] до [math]k[/math] множині [math]E(q)[/math] належать не більше [math]\dfrac[/math] .

Отже [math]\overline[/math] належать не менше [math]\dfrac[/math] .

Лемма (3):
[math]\overline[/math] - нескінченно.
Доказ:
[math]\triangleright[/math]
[math]\triangleleft[/math]

Тепер доведемо теорему.

Теорема:

Доказ:[math]\triangleright[/math]

З леми (2) і леми (3) випливає, що [math]\overline[/math] - імунно.

За побудовою [math]E(q)[/math] перелічимо, його доповнення імунне і, по лемі (3), нескінченно, а значить, воно просте.

[math]\triangleleft[/math]

Прості множини є прикладами перелічуваних множин, що не є [math]m[/math]-повними [1] . Саме так і виникло поняття простої множини: Піст шукав приклад перелічуваної нерозв'язної множини, яка не була б [math] m [/math] -повним [2] . .