Нумерації. Теореми про нерухому точку

Cnk(Cп(x1, x2,..., xп))=xk, 1kn.

Теорема 1.1. 1) Функцiї C(x, y), l(n) та r(n) є ПРФ.

2) Функцiї Cп, Cn1 , ..., Cnn є ПРФ.

Приклад 1. Знайдемо l(100) та r(100). Для х=l(100) та у=r(100) маємо рівняння С(х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р(р+1)2100. Звідси р=13. Маємо х+у=13, х=100-[(1314)/2]=9, y=13-9=4. Отже, l(100)=9 та r(100)=4.

Приклад 2. Розв'яжемо рівняння C4(x,y,z,v)=207. За визначенням маємо С(С(С(x,y),z),v)=207. Нехай С(С(x,y),z)=а, маємо C(а,v)=207. Нехай a+v=р. Тоді р є найбільшим натуральним числом, для якого р(р+1)2207. Звідси р=19, звідки а=17 та v=2. Тепер маємо С(С(x,y),z)=17. Нехай С(x,y)=b, тоді C(b,z)=17. Нехай b+z=q. Тоді q є найбільшим натуральним числом, для якого q(q+1)217. Звідси q=5, звідки b=2 та z=3. Маємо C(x,y)=2, звідки x=1 та y=0.

Приклад 3. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування : →N таких послідовностей:

(а1, ..., ап)= C(Cп(а1, ..., ап), п-1)+1.

Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=1 шукана однозначна нумерацiя.

Приклад 4. Однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел можна задати на основі такого кодування : →N всіх скiнченних послiдовностей:

Бiєктивнiсть вiдображення випливає iз однозначностi подання кожного натурального числа в двiйковiй системi числення. Обернене відображення 1 шукана однозначна нумерацiя.

Приклад 5. Однозначну ефективну нумерацiю всiх непорожніх скiнченних послiдовностей натуральних чисел задамо на основі кодування : →N, що є модифікацією кодування:

Обернене відображення шукана однозначна нумерацiя.

Приклад 6. Ефективну нумерацiю множини формул довiльної мови 1-го порядку із злiченним алфавiтом введемо таким чином.

Занумеруємо множини предметних імен x0, x1, ..., константних символiв c0, c1, ... , функцiональних символiв f0, f1, ... та предикат-них символiв p0, p1,... . Кодування  термiв та формул.задамо так:

(xk)=7k ;

(ck)=7k+1;

(fk t1...tn)=7C(Cn+1(k, (t1),...,(tn)), n1)+2;

(pk t1...tn)=7C(Cn+1(k, (t1),...,(tn)), n1)+3;

()=7C(k,())+4;

Номером (індексом) довiльної формули вважатимемо її код . Всi тi натуральнi числа, якi не є кодами формул, вважатимемо номером формули x0=x0 . Зрозуміло, що так введена нумерація  неоднозначна. Формулу з номером n позначатимемо n .

Кодувати довiльну скiнченну послiдовнiсть натуральних чисел. дозволяє також функція Гьоделя (x, y) = mod(l(x), 1+(y+1)r(x)).