Лемма 8.3. Кусочное задание или разбор случаев. Пусть h1(x1,…,xn), …, hk(x1,…,xn)- произвольные ч.р.ф., а всюду определенные ч.р.ф. f1(x1,…,xn), …, fk(x1,…,xn) таковы, что на любом наборе аргументов (a1, …, an) одна и только одна из этих функций равна 0. Тогда функция g(x1,…, xn), определенная соотношениями:
является частично рекурсивной.
Доказательство Действительно, gn можно представить как сумму k произведений:
Следующий класс функций, который нас будет интересовать, - это функции для однозначной нумерации пар и n-ок целых чисел и обратные им. Определим для любой пары чисел (x,y) ее номер c2(x,y)=2x(2y+1) - 1. Например, c2(0,0)=0, c2(1,0)=1, c2(0,1)=2, c2(1,1)=5, c2(2,1)= 19. Из единственности разложения чисел на простые множители следует, что функция c2: N2
Из этих определений непосредственно следует, что для любого z выполнено равенство c2(c21(z), c22(z))=z.
Определим теперь по индукции функции cn нумерации n-ок чисел при n > 2 и обратные им координатные функции cni (1
Из этих определений также непосредственно следует, что для любого z имеет место равенство cn(cn1(z), cn2 (z),…, cnn (z))=z. (Проверьте это свойство индукцией по n.)
Лемма 8.4. Рекурсивность нумерационных функций. Для любых n
Доказательство Примитивная рекурсивность c2(x,y) устанавливается непосредственно (см.