Нумерація Кантора

Ліву та праву компоненти пари з номером n позначають відповідно l(n) та r(n). Функції l(n) та r(n) називають відповідно лівою та правою координатними функціями.

Подібна нумерація застосовувалась при доведенні зліченності множини раціональних чисел, якщо їх вважати їх парами з цілих чисельника і знаменника.

Функції C, l та r зв'язані тотожностями:

C(l(n), r(n)) = n;
l(C(x, y)) = x;
r(C(x, y)) = y.

Маючи нумерацію пар натуральних чисел, можна ввести нумерацію n-ок натуральних чисел для довільного n>2:

Cn(x1, x2,..., xn) = Cn-1(C(x1, x2), x3,..., xn) = C(...С(C(x1, x2), x3),...), xn).

Обернена нумерація обчислюється так[2]:

def C_1(S):
	n = int((sqrt(1+8*S)-1)/2)
	k = S - (n+1)*n/2
	return (k, n-k)

Під кодуванням множини А на множині В будемо розуміти ін’єктивне та сюр’єктивне відображення φ: А→В таке, що існують алгоритми A та B:

• для кожного аєА A(а)єφ(а);
• для кожного bєB B(b)=φ^-1(b).

Нумерацiєю множини А називають сюр’єктивне функцiональне вiдображення ξ: N →А.

Однозначною нумерацiєю множини А називають бієктивне вiдображення ξ: N →А.

Нумерацiю ξ: N →А називають ефективною, якщо iснують алгоритми A та B такі:

• для кожного аєА A(а)єξ^-1(а);
• для кожного nєN B(n)=ξ(n).

Таким чином, ξ: N →А - ефективна нумерація ↔ коли ξ^-1: А→N - кодування А на N.

Введемо однозначні ефективні нумерацiї пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всi пари натуральних чисел розташуємо в послiдовнiсть так:

пара (x, y) передує парі (u, v)↔x+y<u+v або (x+y = u+v та x<y).

Номер пари (x, y) в такiй послiдовностi позначають C(x, y) та називають канторовим номером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)*(x+y)/2]+x

Лiву та праву компоненти пари з номером n позначають вiдповiдно l(n) та r(n). Функцiї l(n) та r(n) називають вiдповiдно лiвою та правою координатними функцiями.

Функцiя C(x, y) задає бiєкцiю N×N→N, пара функцiй (l(n), r(n)) задає бiєкцiю N→N×N.

При цьому функцiї C,l та r зв’язaнi такими тотожностями:

C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y.

Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2: Cn(x1, x2,..., xn)=C^n-1(C(x1, x2), x3,..., xn)=C(...С(C(x1, x2), x3),...), xn). Координатнi функцiї Cn1 , ..., Cnn вводимо так: Нехай Cn(x1, x2,..., xn)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn. Для функцiй Cп, Cn1 , ..., Cnn справджуються такi тотожностi:

Cп(Cn1(x), ..., Cnn(x))=x; Cnk(Cп(x1, x2,..., xn))=xk, 1≤k≤n.

Теорема 1.1.

1) Функцiї C(x, y), l(n) та r(n) є ПРФ.

2) Функцiї Cn, 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)≤2*207. Звідси р=19, звідки а=17 та v=2. Тепер маємо С(С(x,y),z)=17. Нехай С(x,y)=b, тоді C(b,z)=17. Нехай b+z=q. Тоді q є найбільшим натуральним числом, для якого q*(q+1)≤2*17. Звідси q=5, звідки b=2 та z=3. Маємо C(x,y)=2, звідки x=1 та y=0.

Приклад 3. Задамо однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел на основі наступного кодування k:Ų,k≥0,N^k→N таких послідовностей: k(Ø)=0; k(а1, ..., ап)= C(C^n(а1, ..., аn), n-1)+1. Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=k^-1 - шукана однозначна нумерацiя.

Приклад 4. Однозначну ефективну нумерацiю всiх скiнченних послiдовностей натуральних чисел можна задати на основі такого кодування ò:Ų,k≥0,N^k→N всіх скiнченних послiдовностей: k(Ø)=0; k(а1, ..., аn)=2^a1+2^A1+a2+...+2^a1+a2+...+an+n-1. Бiєктивнiсть вiдображення ò випливає iз однозначностi подання кожного натурального числа в двiйковiй системi числення. Обернене відображення α=ò^-1 -шукана однозначна нумерацiя.

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

ʋ(а1, ..., аn)=2^a1+2^a1+a2+1+...+2^a1+a2+...+an+n-1-1.

Обернене відображення ξ=ʋ^-1 - шукана однозначна нумерацiя.

Приклад 6. Ефективну нумерацiю Φ множини формул довiльної мови 1-го порядку із злiченним алфавiтом введемо таким чином. Занумеруємо множини предметних імен x0, x1, ..., константних символiв c0, c1, ... , функцiональних символiв f0, f1, ... та предикат-них символiв p0, p1,... .

Кодування k термiв та формул.задамо так: K(xk)=7-k ;

K(ck)=7-k+1;

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

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

K(ḷФ)=7-C(k,К(Ф))+4;

K(٧ФΨ)=7-C(К(Ф),К(Ψ))+5;

K(ЭxkФ)=7-C(k,К(Ф))+6.

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

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

Теорема 1.2 (про основну властивість функції Гьоделя). Для довiльної скiнченної послiдовностi натуральних чисел b0, b1, ..,bn існує натуральне число t таке, що Г(t, i)=bi для всiх i{0,...,n}.

Використання функції Гьоделя дає змогу промоделювати опера-цiю примiтивної рекурсiї операціями суперпозиції та мінімізації:

Теорема 1.3. Функцiя f=R(g, h) може бути отримана iз функцiй g, h, базових функцiй і функцiй +,× за допомогою скiнченної кiлькостi застосувань операцiй S^n+1 та М. Наслiдок. Клас ЧРФ спiвпадає з класом функцiй, отриманих із функцій о, s, I(m,n) , +, × за допомогою операцiй S^n+1 та M.

1. CybWiki - кодування і нумерації^{[недоступне посилання з липня 2019]}
2. CybWiki^{[недоступне посилання з вересня 2019]} джерело неавторитетне, але дані можна підтвердити експериментами