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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Георг Кантор

Нумерація — це бієкція між певною множиною об'єктів, та множиною натуральних чисел. Ге́орг Фердина́нд Лю́двіг Пили́п Ка́нтор (*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).

Нумерац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 - кодування і нумерації
  2. CybWiki джерело неавторитетне, але дані можна підтвердити експериментами