271
правка
Изменения
Нет описания правки
|statement= Пусть на натуральных числах задано отношение эквивалентности <tex>\equiv</tex>. Тогда следующие два утверждения не могут быть выполнены одновременно: <br>
# Пусть <tex>f</tex> {{---}} вычислимая функция. Тогда существует всюду определённое вычислимое <tex>\equiv</tex> {{---}} продолжение <tex>g</tex> функции <tex>f</tex>, то есть такая <tex>g</tex>, что <tex>D(g)=N</tex> и <tex>\forall x</tex> такого, что <tex>f(x) \ne \perp</tex>, выполнено <tex>f(x) \equiv g(x)</tex>.
# Найдётся такая всюду определенная вычислимая <tex>h</tex>, что <tex>\forall n </tex> выполнени <tex>h(n) \not\equiv n</tex>.
|proof=
Приведем доказательство от противного. Пусть оба утверждения выполнены. <br>
