Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Нумерація — це бієкція між певною множиною об'єктів, та множиною натуральних чисел. Ге́орг Фердина́нд Лю́двіг Пили́п Ка́нтор (*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.
Ось її табулювання:
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).
Обернена нумерація обчислюється так:
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.
Посилання
- . Архів оригіналу за 22 вересня 2020. Процитовано 1 липня 2022.
- CybWiki [ 22 вересня 2020 у Wayback Machine.] джерело неавторитетне, але дані можна підтвердити експериментами
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Numeraciya ce biyekciya mizh pevnoyu mnozhinoyu ob yektiv ta mnozhinoyu naturalnih chisel Ge org Ferdina nd Lyu dvig Pili p Ka ntor 3 bereznya 1845 Sankt Peterburg 6 sichnya 1918 Galle Zaale nimeckij matematik Georg Kantor Vvedemo odnoznachni efektivni numeraciyi par ta n ok naturalnih chisel yaki nazivayutsya kantorovimi numeraciyami Vsi pari naturalnih chisel roztashuyemo v poslidovnist tak para x y pereduye pari u v x y lt u v abo x y u v ta x lt u Nomer pari x y v takij poslidovnosti poznachayut C x y ta nazivayut kantorovim nomerom pari x y Nevazhko perekonatis sho C x y x y 1 x y 2 x Os yiyi tabulyuvannya Numeraciya racionalnih chisel 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 180KODUVANNYa TA NUMERACIYi KANTOROVI NUMERACIYiLivu ta pravu komponenti pari z nomerom n poznachayut vidpovidno l n ta r n Funkciyi l n ta r n nazivayut vidpovidno livoyu ta pravoyu koordinatnimi funkciyami Podibna numeraciya zastosovuvalas pri dovedenni zlichennosti mnozhini racionalnih chisel yaksho yih vvazhati yih parami z cilih chiselnika i znamennika Funkciyi C l ta r zv yazani totozhnostyami C l n r n n l C x y x r C x y y Mayuchi numeraciyu par naturalnih chisel mozhna vvesti numeraciyu n ok naturalnih chisel dlya dovilnogo n gt 2 Cn x1 x2 xn Cn 1 C x1 x2 x3 xn C S C x1 x2 x3 xn Obernena numeraciya obchislyuyetsya tak def C 1 S n int sqrt 1 8 S 1 2 k S n 1 n 2 return k n k Pid koduvannyam mnozhini A na mnozhini V budemo rozumiti in yektivne ta syur yektivne vidobrazhennya f A V take sho isnuyut algoritmi A ta B dlya kozhnogo ayeA A a yef a dlya kozhnogo byeB B b f 1 b Numeraciyeyu mnozhini A nazivayut syur yektivne funkcionalne vidobrazhennya 3 N A Odnoznachnoyu numeraciyeyu mnozhini A nazivayut biyektivne vidobrazhennya 3 N A Numeraciyu 3 N A nazivayut efektivnoyu yaksho isnuyut algoritmi A ta B taki dlya kozhnogo ayeA A a ye3 1 a dlya kozhnogo nyeN B n 3 n Takim chinom 3 N A efektivna numeraciya koli 3 1 A N koduvannya A na N Vvedemo odnoznachni efektivni numeraciyi par ta n ok naturalnih chisel yaki nazivayutsya kantorovimi numeraciyami Vsi pari naturalnih chisel roztashuyemo v poslidovnist tak para x y pereduye pari u v x y lt u v abo x y u v ta x lt y Nomer pari x y v takij poslidovnosti poznachayut C x y ta nazivayut kantorovim nomerom pari x y Nevazhko perekonatis sho C x y x y 1 x y 2 x Livu ta pravu komponenti pari z nomerom n poznachayut vidpovidno l n ta r n Funkciyi l n ta r n nazivayut vidpovidno livoyu ta pravoyu koordinatnimi funkciyami Funkciya C x y zadaye biyekciyu N N N para funkcij l n r n zadaye biyekciyu N N N Pri comu funkciyi C l ta r zv yazani takimi totozhnostyami C l n r n n l C x y x r C x y y Mayuchi numeraciyu par naturalnih chisel mozhna vvesti numeraciyu n ok naturalnih chisel dlya dovilnogo n gt 2 Cn x1 x2 xn C n 1 C x1 x2 x3 xn C S C x1 x2 x3 xn Koordinatni funkciyi Cn1 Cnn vvodimo tak Nehaj Cn x1 x2 xn m todi Cn1 m x1 Cn2 m x2 Cnn m xn Dlya funkcij Sp Cn1 Cnn spravdzhuyutsya taki totozhnosti Sp Cn1 x Cnn x x Cnk Sp x1 x2 xn xk 1 k n Teorema 1 1 1 Funkciyi C x y l n ta r n ye PRF 2 Funkciyi Cn Cn1 Cnn ye PRF Priklad 1 Znajdemo l 100 ta r 100 Dlya h l 100 ta u r 100 mayemo rivnyannya S h u 100 Nehaj h u r Todi r ye najbilshim naturalnim chislom dlya yakogo r r 1 2 100 Zvidsi r 13 Mayemo h u 13 h 100 13 14 2 9 y 13 9 4 Otzhe l 100 9 ta r 100 4 Priklad 2 Rozv yazhemo rivnyannya C4 x y z v 207 Za viznachennyam mayemo S S S x y z v 207 Nehaj S S x y z a mayemo C a v 207 Nehaj a v r Todi r ye najbilshim naturalnim chislom dlya yakogo r r 1 2 207 Zvidsi r 19 zvidki a 17 ta v 2 Teper mayemo S S x y z 17 Nehaj S x y b todi C b z 17 Nehaj b z q Todi q ye najbilshim naturalnim chislom dlya yakogo q q 1 2 17 Zvidsi q 5 zvidki b 2 ta z 3 Mayemo C x y 2 zvidki x 1 ta y 0 Priklad 3 Zadamo odnoznachnu efektivnu numeraciyu vsih skinchennih poslidovnostej naturalnih chisel na osnovi nastupnogo koduvannya k Ų k 0 N k N takih poslidovnostej k O 0 k a1 ap C C n a1 an n 1 1 Zrozumilo sho take vidobrazhennya biyektivne Teper obernene vidobrazhennya h k 1 shukana odnoznachna numeraciya Priklad 4 Odnoznachnu efektivnu numeraciyu vsih skinchennih poslidovnostej naturalnih chisel mozhna zadati na osnovi takogo koduvannya o Ų k 0 N k N vsih skinchennih poslidovnostej k O 0 k a1 an 2 a1 2 A1 a2 2 a1 a2 an n 1 Biyektivnist vidobrazhennya o viplivaye iz odnoznachnosti podannya kozhnogo naturalnogo chisla v dvijkovij sistemi chislennya Obernene vidobrazhennya a o 1 shukana odnoznachna numeraciya Priklad 5 Odnoznachnu efektivnu numeraciyu vsih neporozhnih skinchennih poslidovnostej naturalnih chisel zadamo na osnovi koduvannya ʋ Ų k 0 N k N sho ye modifikaciyeyu koduvannya o ʋ a1 an 2 a1 2 a1 a2 1 2 a1 a2 an n 1 1 Obernene vidobrazhennya 3 ʋ 1 shukana odnoznachna numeraciya Priklad 6 Efektivnu numeraciyu F mnozhini formul dovilnoyi movi 1 go poryadku iz zlichennim alfavitom vvedemo takim chinom Zanumeruyemo mnozhini predmetnih imen x0 x1 konstantnih simvoliv c0 c1 funkcionalnih simvoliv f0 f1 ta predikat nih simvoliv p0 p1 Koduvannya k termiv ta formul zadamo tak 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 ḷF 7 C k K F 4 K ٧FPS 7 C K F K PS 5 K ExkF 7 C k K F 6 Nomerom indeksom dovilnoyi formuli F vvazhatimemo yiyi kod K F Vsi ti naturalni chisla yaki ne ye kodami formul vvazhatimemo nomerom formuli x0 x0 Zrozumilo sho tak vvedena numeraciya F neodnoznachna Formulu z nomerom n poznachatimemo Fn Koduvati dovilnu skinchennu poslidovnist naturalnih chisel dozvolyaye takozh funkciya Godelya G x y mod l x 1 y 1 r x Z viznachennya viplivaye sho G x y ye PRF Teorema 1 2 pro osnovnu vlastivist funkciyi Godelya Dlya dovilnoyi skinchennoyi poslidovnosti naturalnih chisel b0 b1 bn isnuye naturalne chislo t take sho G t i bi dlya vsih i 0 n Vikoristannya funkciyi Godelya daye zmogu promodelyuvati opera ciyu primitivnoyi rekursiyi operaciyami superpoziciyi ta minimizaciyi Teorema 1 3 Funkciya f R g h mozhe buti otrimana iz funkcij g h bazovih funkcij i funkcij za dopomogoyu skinchennoyi kilkosti zastosuvan operacij S n 1 ta M Naslidok Klas ChRF spivpadaye z klasom funkcij otrimanih iz funkcij o s I m n za dopomogoyu operacij S n 1 ta M Posilannya Arhiv originalu za 22 veresnya 2020 Procitovano 1 lipnya 2022 CybWiki 22 veresnya 2020 u Wayback Machine dzherelo neavtoritetne ale dani mozhna pidtverditi eksperimentami