Изменения
→Главная нумерация
{{Теорема
|statement=Существует такая функция <tex>c</tex>, которая всюду определена и которая по номерам функций <tex>p</tex> и <tex>q</tex> дает номер <tex>c(p, q)</tex> их композиций. То есть выполняется свойство <tex>U(c(p,q),x) = U(p, U(q,x))</tex>
|proof=Для начала зафиксируем вычислимую нумерацию пар (взаимно однозначное соответствие <tex>\langle u, v \rangle \leftrightarrow [u, v]</tex> между <tex> N \times N </tex> и <tex>N</tex>; число <tex>[u, v]</tex> назовем номером этой пары. Возьмем некоторую функцию <tex>V([p,q],x)=U(p, U(q,x))</tex>. Исходя из определения главной нумерации существует такая вычислимая, всюду определенная функция <tex>S: V(n,x)=U(s(n),x)</tex> для всех <tex>n</tex> и <tex>x</tex>. А тогда <tex>V([p,q],x)=U(S[p,q], x)</tex>, что значит функция с, определяемая как <tex>c(p,q)=S([p,q])</tex>, будет искомой.
}}
Отметим, что при доказательстве существования функции-композиции мы пользуемся основным свойством главной нумерации, а значит для неглавных нумерации мы не сможем построить такую функций и не сможем найти номер функции-композиции двух функций.
