Иммунные и простые множества — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 22 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition = Множество натуральных чисел <tex>A</tex> называется '''иммунным''' (англ. ''immune set'' ), если оно бесконечно и не содержит бесконечных перечислимых подмножеств. | + | |definition = Множество натуральных чисел <tex>A</tex> называется '''иммунным''' (англ. ''immune set''), если оно бесконечно и не содержит бесконечных перечислимых подмножеств. |
}} | }} | ||
{{Определение | {{Определение | ||
− | |definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set'' ), если <tex>A</tex> — перечислимое, бесконечное и | + | |definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set''), если <tex>A</tex> — перечислимое, бесконечное и <tex>\overline{A}</tex> {{---}} иммунное. |
}} | }} | ||
− | + | ==Теорема о существовании простого множества== | |
− | |||
− | |||
Рассмотрим все программы. | Рассмотрим все программы. | ||
Для некоторого [[Перечислимые_языки | перечислимого языка]] какая-то из них является его перечислителем. | Для некоторого [[Перечислимые_языки | перечислимого языка]] какая-то из них является его перечислителем. | ||
Рассмотрим программу <tex>q</tex>: | Рассмотрим программу <tex>q</tex>: | ||
− | <tex>q</tex>: | + | <tex>q</tex>(): |
− | + | '''for''' <tex>TL = 1\ \ldots +\infty</tex> | |
− | + | '''for''' <tex>i = 1\ \ldots TL</tex> | |
− | + | запустить <tex>i</tex>-ую в [[Главные нумерации|главной нумерации]] программу на <tex>TL</tex> шагов | |
− | + | напечатать первый <tex>x</tex>, который вывела эта программа, такой что <tex>x \geqslant 2 i;</tex> | |
+ | ничего не печатать, если такого числа не найдется. | ||
+ | |||
Строка 24: | Строка 24: | ||
Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы. | Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы. | ||
+ | ===Лемма 1=== | ||
Необходимо, чтобы перечислимое множество <tex>E(q)</tex> имело иммунное дополнение. Это означает, что <tex>E(q)</tex> должно пересекаться с любым бесконечным перечислимым множеством. | Необходимо, чтобы перечислимое множество <tex>E(q)</tex> имело иммунное дополнение. Это означает, что <tex>E(q)</tex> должно пересекаться с любым бесконечным перечислимым множеством. | ||
Строка 36: | Строка 37: | ||
По построению, для любого множества <tex> B </tex> в <tex>E(q)</tex> будет содержаться первый его элемент не меньший <tex>2 i</tex>, где <tex>i</tex> {{---}} номер перечислителя множества <tex>B</tex>. | По построению, для любого множества <tex> B </tex> в <tex>E(q)</tex> будет содержаться первый его элемент не меньший <tex>2 i</tex>, где <tex>i</tex> {{---}} номер перечислителя множества <tex>B</tex>. | ||
}} | }} | ||
− | + | ===Лемма 2=== | |
{{Лемма | {{Лемма | ||
|id= ==lemma== | |id= ==lemma== | ||
Строка 42: | Строка 43: | ||
|statement=Для любого бесконечного перечислимого множества <tex>B</tex> верно, что <tex>B \not \subset \overline{E(q)}</tex>. | |statement=Для любого бесконечного перечислимого множества <tex>B</tex> верно, что <tex>B \not \subset \overline{E(q)}</tex>. | ||
|proof= | |proof= | ||
− | [[# | + | [[#Лемма 1|По первой лемме]] существует элемент <tex>B</tex>, принадлежащий <tex>E(q)</tex>, и, следовательно, не принадлежащий <tex>\overline{E(q)}</tex>. |
}} | }} | ||
− | + | ===Лемма 3=== | |
{{Лемма | {{Лемма | ||
|id= ==lemma== | |id= ==lemma== | ||
Строка 50: | Строка 51: | ||
|statement=<tex>\overline{E(q)}</tex> {{---}} бесконечно. | |statement=<tex>\overline{E(q)}</tex> {{---}} бесконечно. | ||
|proof= | |proof= | ||
− | Среди чисел от <tex>1</tex> до <tex>k</tex> множеству <tex>E(q)</tex> принадлежат не более <tex>\ | + | Среди чисел от <tex>1</tex> до <tex>k</tex> множеству <tex>E(q)</tex> принадлежат не более |
− | Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\ | + | <tex>\dfrac{k}{2}</tex>. |
+ | Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\dfrac{k}{2}</tex>. | ||
}} | }} | ||
+ | |||
+ | Теперь докажем теорему. | ||
+ | {{Теорема | ||
+ | |statement=Существует простое множество. | ||
+ | |proof= | ||
− | + | [[#Лемма 2|Из леммы (2)]] и [[#Лемма3|из леммы (3)]] следует, что <tex>\overline{E(q)}</tex> {{---}} иммунно. | |
+ | По построению <tex>E(q)</tex> перечислимо, его дополнение иммунно и, [[#Лемма 3|по лемме (3)]], бесконечно, а значит {{---}} оно простое. | ||
− | + | }} | |
+ | Простые множества являются примерами перечислимых множеств, не являющихся <tex>m</tex>-полными<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58. ISBN 5-900916-36-7]</ref>. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы <tex>m</tex>-полным <ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012.c. 62. ISBN 5-900916-36-7]</ref>. . | ||
− | [[ | + | == См. также == |
− | + | *[[Перечислимые языки]] | |
+ | *[[m-сводимость]] | ||
+ | == Примечания == | ||
− | + | <references /> | |
− | |||
− | == | + | == Источники информации == |
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7 | * Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7 | ||
* Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143. | * Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143. | ||
Строка 73: | Строка 83: | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
[[Категория: Теория вычислимости]] | [[Категория: Теория вычислимости]] | ||
+ | [[Категория:Разрешимые и перечислимые языки]] |
Текущая версия на 19:21, 4 сентября 2022
Определение: |
Множество натуральных чисел | называется иммунным (англ. immune set), если оно бесконечно и не содержит бесконечных перечислимых подмножеств.
Определение: |
Множество натуральных чисел | называется простым (англ. simple set), если — перечислимое, бесконечное и — иммунное.
Содержание
Теорема о существовании простого множества
Рассмотрим все программы. Для некоторого перечислимого языка какая-то из них является его перечислителем. Рассмотрим программу :
главной нумерации программу на шагов напечатать первый , который вывела эта программа, такой что ничего не печатать, если такого числа не найдется.(): for for запустить -ую в
Обозначим
— множество, которое перечисляет эта программа.Докажем несколько лемм, из которых будет очевидна правильность утверждения теоремы.
Лемма 1
Необходимо, чтобы перечислимое множество
имело иммунное дополнение. Это означает, что должно пересекаться с любым бесконечным перечислимым множеством.
Лемма (1): |
Для любого бесконечного перечислимого множества существует его элемент, принадлежащий . |
Доказательство: |
По построению, для любого множества | в будет содержаться первый его элемент не меньший , где — номер перечислителя множества .
Лемма 2
Лемма (2): |
Для любого бесконечного перечислимого множества верно, что . |
Доказательство: |
По первой лемме существует элемент , принадлежащий , и, следовательно, не принадлежащий . |
Лемма 3
Лемма (3): |
— бесконечно. |
Доказательство: |
Среди чисел от Следовательно до множеству принадлежат не более . принадлежат не менее . |
Теперь докажем теорему.
Теорема: |
Существует простое множество. |
Доказательство: |
Из леммы (2) и из леммы (3) следует, что — иммунно. По построению перечислимо, его дополнение иммунно и, по лемме (3), бесконечно, а значит — оно простое. |
Простые множества являются примерами перечислимых множеств, не являющихся [1]. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы -полным [2]. .
-полнымиСм. также
Примечания
- ↑ Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58. ISBN 5-900916-36-7
- ↑ Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012.c. 62. ISBN 5-900916-36-7
Источники информации
- Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
- Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
- Wikipedia — Simple set