Материал из Викиконспекты
|
|
| Строка 22: |
Строка 22: |
| | | | |
| | | | |
| − | Множество <tex>E(q)</tex>, которое перечисляет эта программа:
| |
| − | * перечислимо.
| |
| − | * бесконечно. Для любого <tex>i</tex> существует бесконечное множество с номером перечислителя большим <tex>i</tex>, и в этом множестве есть элемент <tex>x \geqslant 2 * i</tex>.
| |
| | | | |
| − | Дополнение этого множества <tex>\overline{E(q)}</tex>:
| + | Обозначим <tex>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)}</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=существует элемент <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>\overline{E(q)}</tex> принадлежат не менее <tex>\frac{k}{2}</tex> |
| | + | }} |
| | + | |
| | + | Получаем: |
| | + | <tex>\overline{E(q)}</tex> — иммунно. |
| | + | <tex>E(q)</tex> — простое. |
| | | | |
| − | Таким образом <tex>\overline{E(q)}</tex> — иммунно, а <tex>E(q)</tex> — простое.
| |
| | }} | | }} |
Версия 03:17, 10 декабря 2010
| Определение: |
| Множество натуральных чисел [math]A[/math] называется иммунным, если [math]A[/math] — бесконечное, для любого бесконечного перечислимого множества [math]B[/math], [math]B \not \subset A[/math]. |
| Определение: |
| Множество натуральных чисел [math]A[/math] называется простым, если [math]A[/math] — перечислимое, бесконечное, и дополнение [math]A[/math] — иммунное. |
| Теорема: |
Существует простое множество. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим все программы.
Для некоторого перечислимого языка, какая-то из них является его перечислителем.
Рассмотрим программу [math]q[/math]:
[math]q[/math]:
for [math](TL = 1\ \ldots +\infty)[/math]
for [math](i = 1\ \ldots TL)[/math]
запустить [math]i[/math]-ую в главной нумерации программу на [math]TL[/math] шагов
напечатать первый [math]x[/math], который вывела эта программа, такой что [math]x \geqslant 2 i[/math]
Обозначим [math]E(q)[/math] — множество, которое перечисляет эта программа.
| Лемма: |
Для любого перечислимого множества [math]B[/math], существует его элемент принадлежащий [math]E(q)[/math] |
| Доказательство: |
| [math]\triangleright[/math] | |
В [math]E(q)[/math] будет содержаться первый элемент множества [math]B[/math] не превосходящий [math]2 i[/math], где [math]i[/math] — номер перечислителя множества [math]B[/math] | | [math]\triangleleft[/math] |
| Лемма: |
для любого перечислимого множества [math]B[/math] [math]B \not \subset \overline{E(q)}[/math] |
| Доказательство: |
| [math]\triangleright[/math] | |
существует элемент [math]B[/math] принадлежащий [math]E(q)[/math], и следовательно не принадлежащий [math]\overline{E(q)}[/math]. | | [math]\triangleleft[/math] |
| Лемма: |
[math]\overline{E(q)}[/math] — бесконечно. |
| Доказательство: |
| [math]\triangleright[/math] | |
Для первых [math]k[/math] слов, множеству [math]E(q)[/math] принадлежат не более [math]\frac{k}{2}[/math].
Следовательно [math]\overline{E(q)}[/math] принадлежат не менее [math]\frac{k}{2}[/math] | | [math]\triangleleft[/math] |
Получаем:
[math]\overline{E(q)}[/math] — иммунно.
[math]E(q)[/math] — простое. |
| [math]\triangleleft[/math] |
