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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 3 участников)
Строка 6: Строка 6:
 
Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод|универсальная функция]].
 
Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод|универсальная функция]].
  
−
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: g(n) \neq \bot </tex>.
+
Предположим, у нее существует всюду определенное продолжение <tex>g(n) \Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex> \forall n \in \mathbb{N} \ g(n) \neq \bot</tex>.
  
−
По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, определено значение <tex>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.
+
По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i \Rightarrow g(i) = U(i, i)</tex>.  
 +
 
 +
Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, определено значение <tex>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.
  
 
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
 
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
Строка 25: Строка 27:
 
\end{cases}</tex>
 
\end{cases}</tex>
  
−
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>.
+
Предположим, у нее существует всюду определенное продолжение <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>.
  
−
<tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>.
+
Поскольку <tex>g(n)</tex> всюду определена, то <tex>g(i) = U(i, i) \neq \bot</tex> и определено значение <tex>f(i)</tex>. Но по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.
−
 
 
−
<tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex> и определено значение <tex>f(i)</tex>. Но по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.
 
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \O</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми'''.
+
Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \varnothing</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').
 
|proof=
 
|proof=
−
Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> - функция из леммы 2.
+
Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> {{---}} функция из леммы 2.
  
−
Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам. Тогда вычислима характеристическая функция множества <tex>Y</tex>, то есть функция <tex>g(n) = \begin{cases}
+
Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция <tex>g(n) = \begin{cases}
−
   1 & n \in Y \\
+
   1, & n \in Y \\
−
   0 & n \notin Y (n \in X)
+
   0, & n \notin Y (n \in X)
−
\end{cases}</tex>
+
\end{cases}</tex>   множества <tex>Y</tex>.
  
 
Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.
 
Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.
 
}}
 
}}
 +
 +
Неотделимые множества используются в доказательстве других фактов<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 39, с. 63, c. 100. ISBN 5-900916-36-7]</ref>.
 +
 +
== Примечания ==
 +
 +
<references />
  
 
== Источники информации ==
 
== Источники информации ==
  
−
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7
+
* [http://en.wikipedia.org/wiki/Recursively_inseparable_sets Wikipedia {{---}} Recursively inseparable sets]
 +
* Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math. 139, Amsterdam: North-Holland, pp. 1041–1176, MR 1673598
 +
* Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория вычислимости]]
 
[[Категория: Теория вычислимости]]

Текущая версия на 19:41, 4 сентября 2022

Лемма (1):
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.
Доказательство:
[math]\triangleright[/math]

Рассмотрим функцию [math]f(n) = U(n, n) + 1[/math], где [math]U(n, n)[/math] — универсальная функция.

Предположим, у нее существует всюду определенное продолжение [math]g(n) \Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)[/math] и [math] \forall n \in \mathbb{N} \ g(n) \neq \bot[/math].

По определению универсальной функции [math]g(n) = U(i, n)[/math] для некоторого [math]i \Rightarrow g(i) = U(i, i)[/math].

Поскольку [math]g(n)[/math] всюду определена, то [math]U(i, i) \neq \bot[/math]. Значит, определено значение [math]f(i)[/math] и [math]g(i) = f(i) = U(i, i) + 1[/math]. Получили противоречие.

Таким образом, построенная функция [math]f(n)[/math] не имеет всюду определенного вычислимого продолжения.
[math]\triangleleft[/math]
Лемма (2):
Существует вычислимая функция, значения которой принадлежат множеству [math]\{0, 1, \bot\}[/math], не имеющая всюду определенного вычислимого продолжения.
Доказательство:
[math]\triangleright[/math]

Рассмотрим функцию [math]f(n) = \begin{cases} 0 & U(n, n) \neq 0 \text{, }U(n, n) \neq \bot \\ 1 & U(n, n) = 0 \\ \bot & U(n, n) = \bot \end{cases}[/math]

Предположим, у нее существует всюду определенное продолжение [math]g(n) = U(i, n)[/math] для некоторого [math]i[/math].

Поскольку [math]g(n)[/math] всюду определена, то [math]g(i) = U(i, i) \neq \bot[/math] и определено значение [math]f(i)[/math]. Но по построению функции [math]f(n)[/math] видим, что [math]f(i) \neq U(i, i)[/math]. Получили противоречие.
[math]\triangleleft[/math]
Теорема:
Существуют такие непересекающиеся перечислимые множества [math]X'[/math] и [math]Y'[/math], что не существует таких разрешимых множеств [math]X[/math] и [math]Y[/math], что [math]X' \subset X[/math], [math]Y' \subset Y[/math], [math]X \cap Y = \varnothing[/math], [math]X \cup Y = \mathbb{N}[/math]. Такие множества [math]X'[/math] и [math]Y'[/math] называют неотделимыми (англ. inseparable sets).
Доказательство:
[math]\triangleright[/math]

Рассмотрим множества [math]X' = \{n \mid f(n) = 0\}[/math] и [math]Y' = \{n \mid f(n) = 1\}[/math], где [math]f(n)[/math] — функция из леммы 2.

Пусть существуют [math]X[/math] и [math]Y[/math], удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция [math]g(n) = \begin{cases} 1, & n \in Y \\ 0, & n \notin Y (n \in X) \end{cases}[/math] множества [math]Y[/math].

Заметим, что [math]g(n)[/math] всюду определена и является продолжением [math]f(n)[/math], что противоречит лемме 2.
[math]\triangleleft[/math]

Неотделимые множества используются в доказательстве других фактов[1].

Примечания

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

  • Wikipedia — Recursively inseparable sets
  • Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math. 139, Amsterdam: North-Holland, pp. 1041–1176, MR 1673598
  • Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Неотделимые_множества&oldid=85822»