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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 34: Строка 34:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Существуют такие перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что <tex>X' \cap Y' = \O</tex> и не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \in X</tex>, <tex>Y' \in 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 = \O</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми'''.
 
|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.

Версия 23:56, 16 сентября 2014

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

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

Предположим, у нее существует всюду определенное продолжение [math]g(n)[/math]. Это значит, что [math]f(n) \neq \bot \Rightarrow g(n) = f(n)[/math] и [math]\forall n: g(n) \neq \bot [/math].

По определению универсальной функции [math]g(n) = U(i, n)[/math] для некоторого [math]i[/math]. Тогда [math]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)[/math].

[math]g(n) = U(i, n)[/math] для некоторого [math]i[/math].

[math]g(i) = U(i, i)[/math]. Поскольку [math]g(n)[/math] всюду определена, то [math]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 = \O[/math], [math]X \cup Y = \mathbb{N}[/math]. Такие множества [math]X'[/math] и [math]Y'[/math] называют неотделимыми.
Доказательство:
[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]Y[/math], то есть функция [math]g(n) = \begin{cases} 1 & n \in Y \\ 0 & n \notin Y (n \in X) \end{cases}[/math]

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

Литература

  • Верещагин, Шень. Вычислимые функции.