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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о простом множестве)
Строка 14: Строка 14:
 
Рассмотрим программу <tex>q</tex>:
 
Рассмотрим программу <tex>q</tex>:
  
  <tex>q</tex>:
+
  '''function''' <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>
Строка 48: Строка 48:
 
}}
 
}}
 
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы m-полным <ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58, c. 62. ISBN 5-900916-36-7]</ref>. .
 
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы m-полным <ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58, c. 62. ISBN 5-900916-36-7]</ref>. .
 +
 
== См. также ==
 
== См. также ==
 
*[[Перечислимые языки]]
 
*[[Перечислимые языки]]

Версия 00:25, 2 ноября 2016

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


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

Теорема о простом множестве

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

Рассмотрим все программы. Для некоторого перечислимого языка какая-то из них является его перечислителем. Рассмотрим программу [math]q[/math]:

function [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]E(q)[/math] имело иммунное дополнение. Это означает, что [math]E(q)[/math] должно пересекаться с любым бесконечным перечислимым множеством.

1. Для любого бесконечного перечислимого множества [math]B[/math] существует его элемент, принадлежащий [math]E(q)[/math].

По построению, для любого множества [math] B [/math] в [math]E(q)[/math] будет содержаться первый его элемент не меньший [math]2 i[/math], где [math]i[/math] — номер перечислителя множества [math]B[/math].

2. Для любого бесконечного перечислимого множества [math]B[/math] верно, что [math]B \not \subset \overline{E(q)}[/math].

Из утверждения 1 следует, что существует элемент [math]B[/math], принадлежащий [math]E(q)[/math], и, следовательно, не принадлежащий [math]\overline{E(q)}[/math].

3. [math]\overline{E(q)}[/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].

Вернемся к доказательству теоремы.

Получаем:

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

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

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

См. также

Примечания

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

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