142
правки
Изменения
Нет описания правки
{{Лемма
|author=1
|statement=
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.
{{Лемма
|author=2
|statement=
Существует вычислимая функция, значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.
<tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Но тогда по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.
}}
{{Теорема
|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>.
|proof=
}}
