Нумерація Кантора
Нумерація — це бієкція між певною множиною об'єктів, та множиною натуральних чисел. Ге́орг Фердина́нд Лю́двіг Пили́п Ка́нтор (*3 березня 1845, Санкт-Петербург — †6 січня 1918, Галле (Заале)) — німецький математик.
Введемо однозначні ефективні нумерації пар та n-ок натуральних чисел, які називаються канторовими нумераціями.
Всі пари натуральних чисел розташуємо в послідовність так: пара (x, y) передує парі (u, v) ⇔ x+y<u+v або (x+y = u+v та x<u).
Номер пари (x, y) в такій послідовності позначають C(x, y) та називають канторовим номером пари (x, y). Неважко переконатись, що C(x, y) = [(x+y+1)⋅(x+y)/2]+x[1].
Ось її табулювання:
0 1 3 6 10 15 21 28 36 45 2 4 7 11 16 22 29 37 46 56 5 8 12 17 23 30 38 47 57 68 9 13 18 24 31 39 48 58 69 81 14 19 25 32 40 49 59 70 82 95 20 26 33 41 50 60 71 83 96 110 27 34 42 51 61 72 84 97 111 126 35 43 52 62 73 85 98 112 127 143 44 53 63 74 86 99 113 128 144 161 54 64 75 87 100 114 129 145 162 180
Ліву та праву компоненти пари з номером 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).
Нумерацією множини А називають сюр’єктивне функціональне відображення ξ: N →А.
Однозначною нумерацією множини А називають бієктивне відображення ξ: N →А.
Нумерацію ξ: N →А називають ефективною, якщо існують алгоритми A та B такі:
- для кожного аєА A(а)єξ^-1(а);
- для кожного nєN B(n)=ξ(n).
Таким чином, ξ: N →А - ефективна нумерація ↔ коли ξ^-1: А→N - кодування А на N.
Введемо однозначні ефективні нумерації пар та n-ок натуральних чисел, які називаються канторовими нумераціями.
Всі пари натуральних чисел розташуємо в послідовність так:
пара (x, y) передує парі (u, v)↔x+y<u+v або (x+y = u+v та x<y).
Номер пари (x, y) в такій послідовності позначають C(x, y) та називають канторовим номером пари (x, y).
Неважко переконатись, що C(x, y) = [(x+y+1)*(x+y)/2]+x
Ліву та праву компоненти пари з номером n позначають відповідно l(n) та r(n). Функції l(n) та r(n) називають відповідно лівою та правою координатними функціями.
Функція C(x, y) задає бієкцію N×N→N, пара функцій (l(n), r(n)) задає бієкцію N→N×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)=C^n-1(C(x1, x2), x3,..., xn)=C(...С(C(x1, x2), x3),...), xn). Координатні функції Cn1 , ..., Cnn вводимо так: Нехай Cn(x1, x2,..., xn)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn. Для функцій Сп, Cn1 , ..., Cnn справджуються такі тотожності:
Сп(Cn1(x), ..., Cnn(x))=x; Cnk(Сп(x1, x2,..., xn))=xk, 1≤k≤n.
Теорема 1.1.
1) Функції C(x, y), l(n) та r(n) є ПРФ.
2) Функції Cn, Cn1 , …, Cnn є ПРФ.
Приклад 1. Знайдемо l(100) та r(100). Для х=l(100) та у=r(100) маємо рівняння С(х, у)=100. Нехай х+у=р. Тоді р є найбільшим натуральним числом, для якого р*(р+1)≤2*100. Звідси р=13. Маємо х+у=13, х=100-[(1314)/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. Задамо однозначну ефективну нумерацію всіх скінченних послідовностей натуральних чисел на основі наступного кодування k:Ų,k≥0,N^k→N таких послідовностей: k(Ø)=0; k(а1, …, ап)= C(C^n(а1, …, аn), n-1)+1. Зрозуміло, що таке відображення бієктивне. Тепер обернене відображення η=k^-1 - шукана однозначна нумерація.
Приклад 4. Однозначну ефективну нумерацію всіх скінченних послідовностей натуральних чисел можна задати на основі такого кодування ò:Ų,k≥0,N^k→N всіх скінченних послідовностей: k(Ø)=0; k(а1, …, аn)=2^a1+2^A1+a2+...+2^a1+a2+...+an+n-1. Бієктивність відображення ò випливає із однозначності подання кожного натурального числа в двійковій системі числення. Обернене відображення α=ò^-1 -шукана однозначна нумерація.
Приклад 5. Однозначну ефективну нумерацію всіх непорожніх скінченних послідовностей натуральних чисел задамо на основі кодування ʋ:Ų,k≥0,N^k→N, що є модифікацією кодування ò:
ʋ(а1, …, аn)=2^a1+2^a1+a2+1+...+2^a1+a2+...+an+n-1-1.
Обернене відображення ξ=ʋ^-1 - шукана однозначна нумерація.
Приклад 6. Ефективну нумерацію Φ множини формул довільної мови 1-го порядку із зліченним алфавітом введемо таким чином. Занумеруємо множини предметних імен x0, x1, …, константних символів c0, c1, … , функціональних символів f0, f1, … та предикат-них символів p0, p1,... .
Кодування k термів та формул.задамо так:
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 натуральні числа, які не є кодами формул, вважатимемо номером формули x0=x0 . Зрозуміло, що так введена нумерація Ф неоднозначна.
Формулу з номером n позначатимемо Фn . Кодувати довільну скінченну послідовність натуральних чисел. дозволяє також функція Гьоделя Г(x, y) = mod(l(x), 1+(y+1)-r(x)). З визначення випливає, що Г(x, y) є ПРФ.
Теорема 1.2 (про основну властивість функції Гьоделя). Для довільної скінченної послідовності натуральних чисел b0, b1, ..,bn існує натуральне число t таке, що Г(t, i)=bi для всіх i{0,...,n}.
Використання функції Гьоделя дає змогу промоделювати опера-цію примітивної рекурсії операціями суперпозиції та мінімізації:
Теорема 1.3. Функція f=R(g, h) може бути отримана із функцій g, h, базових функцій і функцій +,× за допомогою скінченної кількості застосувань операцій S^n+1 та М. Наслідок. Клас ЧРФ співпадає з класом функцій, отриманих із функцій о, s, I(m,n) , +, × за допомогою операцій S^n+1 та M.
- ↑ CybWiki - кодування і нумерації. Архів оригіналу за 22 вересня 2020. Процитовано 1 липня 2022.
- ↑ CybWiki [Архівовано 22 вересня 2020 у Wayback Machine.] джерело неавторитетне, але дані можна підтвердити експериментами