Изменения
→Главная нумерация
{{Теорема
|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>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>, будет искомой.
}}
Отметим, что при доказательстве существования функции-композиции мы пользуемся основным свойством главной нумерации, а значит для неглавных нумерации мы не сможем построить такую функций и не сможем найти номер функции-композиции двух функций.
