Иммунные и простые множества — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (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> — перечислимое, бесконечное и дополнение <tex>A</tex> {{---}} иммунное.
+
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set''), если <tex>A</tex> — перечислимое, бесконечное и <tex>\overline{A}</tex> {{---}} иммунное.
 
}}
 
}}
  
{{Теорема
+
==Теорема о существовании простого множества==
|statement=Существует простое множество.
 
|proof=
 
 
Рассмотрим все программы.  
 
Рассмотрим все программы.  
 
Для некоторого [[Перечислимые_языки | перечислимого языка]] какая-то из них является его перечислителем.
 
Для некоторого [[Перечислимые_языки | перечислимого языка]] какая-то из них является его перечислителем.
 
Рассмотрим программу <tex>q</tex>:
 
Рассмотрим программу <tex>q</tex>:
  
  <tex>q</tex>:
+
  <tex>q</tex>():
  for <tex>(TL = 1\ \ldots +\infty)</tex>
+
    '''for''' <tex>TL = 1\ \ldots +\infty</tex>
  for <tex>(i = 1\ \ldots TL)</tex>
+
        '''for''' <tex>i = 1\ \ldots TL</tex>
    запустить <tex>i</tex>-ую в [[Главные нумерации|главной нумерации]] программу на <tex>TL</tex> шагов
+
            запустить <tex>i</tex>-ую в [[Главные нумерации|главной нумерации]] программу на <tex>TL</tex> шагов
    напечатать первый <tex>x</tex>, который вывела эта программа, такой что <tex>x \geqslant 2 i</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=
[[#lemma1 (1)|По первой лемме]] существует элемент <tex>B</tex>, принадлежащий <tex>E(q)</tex>, и, следовательно, не принадлежащий <tex>\overline{E(q)}</tex>.
+
[[#Лемма 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>\frac{k}{2}</tex>.
+
Среди чисел от <tex>1</tex> до <tex>k</tex> множеству <tex>E(q)</tex> принадлежат не более  
Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\frac{k}{2}</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>. .
  
[[Иммунные и простые множества#Лемма (2)|Из леммы (2)]] и [[Иммунные и простые множества#Лемма(3)|из леммы (3)]] следует, что <tex>\overline{E(q)}</tex> {{---}} иммунно.
+
== См. также ==
По построению <tex>E(q)</tex> перечислимо, его дополнение иммунно и, [[Иммунные и простые множества#Лемма(3)|по лемме (3)]], бесконечно, а значит {{---}} оно простое.
+
*[[Перечислимые языки]]
 +
*[[m-сводимость]]
 +
== Примечания ==
  
}}
+
<references />
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост  (англ. ''Post'' ) искал пример перечислимого неразрешимого множества, которое не было бы m-полным.
 
  
== Литература ==
+
== Источники информации ==
 
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 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

Определение:
Множество натуральных чисел [math]A[/math] называется иммунным (англ. immune set), если оно бесконечно и не содержит бесконечных перечислимых подмножеств.


Определение:
Множество натуральных чисел [math]A[/math] называется простым (англ. simple set), если [math]A[/math] — перечислимое, бесконечное и [math]\overline{A}[/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] — множество, которое перечисляет эта программа.

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

Лемма 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{E(q)}[/math].
Доказательство:
[math]\triangleright[/math]
По первой лемме существует элемент [math]B[/math], принадлежащий [math]E(q)[/math], и, следовательно, не принадлежащий [math]\overline{E(q)}[/math].
[math]\triangleleft[/math]

Лемма 3

Лемма (3):
[math]\overline{E(q)}[/math] — бесконечно.
Доказательство:
[math]\triangleright[/math]

Среди чисел от [math]1[/math] до [math]k[/math] множеству [math]E(q)[/math] принадлежат не более [math]\dfrac{k}{2}[/math].

Следовательно [math]\overline{E(q)}[/math] принадлежат не менее [math]\dfrac{k}{2}[/math].
[math]\triangleleft[/math]

Теперь докажем теорему.

Теорема:
Существует простое множество.
Доказательство:
[math]\triangleright[/math]

Из леммы (2) и из леммы (3) следует, что [math]\overline{E(q)}[/math] — иммунно.

По построению [math]E(q)[/math] перечислимо, его дополнение иммунно и, по лемме (3), бесконечно, а значит — оно простое.
[math]\triangleleft[/math]

Простые множества являются примерами перечислимых множеств, не являющихся [math]m[/math]-полными[1]. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы [math]m[/math]-полным [2]. .

См. также

Примечания

Источники информации

  • Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
  • Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972. С. 141-143.
  • Wikipedia — Simple set