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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
−
|definition = Множество натуральных чисел <tex>A</tex> называется '''иммунным''', если <tex>A</tex> — бесконечное, для любого бесконечного перечислимого множества <tex>B</tex>, <tex>B \not \subset A</tex>.
+
|definition = Множество натуральных чисел <tex>A</tex> называется '''иммунным''', если <tex>A</tex> — бесконечное для любого бесконечного перечислимого множества <tex>B</tex>, <tex>B \not \subset A</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
−
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''', если <tex>A</tex> — перечислимое, бесконечное, и дополнение <tex>A</tex> — иммунное.
+
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''', если <tex>A</tex> — перечислимое, бесконечное и дополнение <tex>A</tex> — иммунное.
 
}}
 
}}
  
Строка 11: Строка 11:
 
|proof=
 
|proof=
 
Рассмотрим все программы.  
 
Рассмотрим все программы.  
−
Для некоторого перечислимого языка, какая-то из них является его перечислителем.
+
Для некоторого перечислимого языка какая-то из них является его перечислителем.
  
 
Рассмотрим программу <tex>q</tex>:
 
Рассмотрим программу <tex>q</tex>:
Строка 28: Строка 28:
  
 
{{Лемма
 
{{Лемма
−
|statement=Для любого перечислимого множества <tex>B</tex>, существует его элемент принадлежащий <tex>E(q)</tex>.
+
|statement=Для любого перечислимого множества <tex>B</tex> существует его элемент принадлежащий <tex>E(q)</tex>.
 
|proof=
 
|proof=
 
В <tex>E(q)</tex> будет содержаться первый элемент множества <tex>B</tex> не превосходящий <tex>2 i</tex>, где <tex>i</tex> — номер перечислителя множества <tex>B</tex>
 
В <tex>E(q)</tex> будет содержаться первый элемент множества <tex>B</tex> не превосходящий <tex>2 i</tex>, где <tex>i</tex> — номер перечислителя множества <tex>B</tex>
Строка 38: Строка 38:
 
|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=
−
Cуществует элемент <tex>B</tex> принадлежащий <tex>E(q)</tex>, и следовательно не принадлежащий <tex>\overline{E(q)}</tex>.
+
Cуществует элемент <tex>B</tex>, принадлежащий <tex>E(q)</tex>, и следовательно не принадлежащий <tex>\overline{E(q)}</tex>.
 
}}
 
}}
  
Строка 46: Строка 46:
 
|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>\frac{k}{2}</tex>.
 
Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\frac{k}{2}</tex>
 
Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\frac{k}{2}</tex>
 
}}
 
}}
Строка 60: Строка 60:
  
 
}}
 
}}
 +
 +
== Литература ==
 +
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7

Версия 21:32, 14 января 2012

Определение:
Множество натуральных чисел [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]
Cуществует элемент [math]B[/math], принадлежащий [math]E(q)[/math], и следовательно не принадлежащий [math]\overline{E(q)}[/math].
[math]\triangleleft[/math]


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

Среди чисел от [math]1[/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]

Литература

  • Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Иммунные_и_простые_множества&oldid=16680»