69
правок
Изменения
Нет описания правки
|proof=
Начнем с доказательства леммы.
{{ЛеммаУтверждение
|id=st1
|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следущие два утверждения не могут быть выполнены одновременно: <br>
Определим функцию <tex>f</tex> так: <tex>f(x)=U(x,x)</tex>. Заметим что никакая всюду вычислимая функция не отличается от <tex>f</tex> всюду. <br> Согласно первому утверждению найдется всюду определенное вычислимое <tex>\equiv</tex>-продолжение <tex>g</tex> функции <tex>f</tex>. <br> Определим функцию <tex>t</tex> так: <tex>t(x)=h(g(x))</tex>, где <tex>h</tex> - функция из второго утверждения. <br >Если <tex>f(x) \ne \perp</tex>, то <tex>f(x)=g(x) \ne h(g(x))=t(x)</tex>, т.е. <tex>f(x) \ne t(x)</tex>. Если <tex>f(x)= \perp</tex>, то <tex>f(x) \ne t(x)</tex>, т.к. <tex>t</tex> - всюду определена. Значит <tex>f</tex> всюду отлична от <tex>t</tex>, противоречие.
}}
Теперь определим отношение <tex>\equiv</tex> так: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex>. Покажем, что для него выполнено первое утверждение леммы. <br> Для заданной <tex>f</tex> определим <tex>V(n,x) = U(f(n), x)</tex>. <br> Так как <tex>U</tex> - универсальная функция, то найдется такая всюду определенная вычислимая <tex>s</tex>, что <tex>V(n,x) = U(s(n), x)</tex>. <br> Тогда <tex>\forall x, n </tex> <tex>U(f(n), x) = U(s(n), x)</tex>, значит <tex>\forall n </tex> <tex> s(n) \equiv f(n)</tex>, то есть <tex>s</tex> - всюду определенное <tex>\equiv</tex>-продолжение <tex>f</tex>.
Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое что <tex>U_{h(n)} = U_n</tex>
}}
