www.wikidata.uk-ua.nina.az

Нумерація Геделя це функція g що зіставляє з кожним об єктом деякої формальної мови її номер З її допомогою можна явно п

Нумерація Геделя

Нумерація Геделя — це функція g , що зіставляє з кожним об'єктом деякої формальної мови її номер. З її допомогою можна явно пронумерувати наступні об'єкти мови: змінні, предметні константи, функціональні символи, предикатні символи і формули, побудовані з них.

Побудова нумерації Геделя для об'єктів теорії називається арифметизацією теорії — вона дозволяє переводити висловлювання, аксіоми, теореми чи теорії в об'єкти арифметики . При цьому потрібно, щоб нумерація g була ефективно обчислюваною і для будь-якого натурального числа можна було визначити, чи є воно номером чи ні, і якщо є, то побудувати відповідний йому об'єкт мови. Нумерація Геделя дуже схожа на посимвольне кодування рядків числами, але з тією різницею, що для кодування послідовностей номерів букв використовується не конкатенація номерів однакової довжини, а основна теорема арифметики.

Нумерація Геделя була ним застосована як інструмент для доказу неповноти формальної арифметики.

Варіант нумерації Геделя формальної теорії першого порядку ред.

Нехай  — теорія першого порядку, що містить змінні , предметні константи , функціональні символи і предикатні символи , де  — номер, а  — арність функціонального або предикатного символу.

Кожному символу довільній теорії першого порядку поставимо у відповідність його Ґьоделя номер наступним чином:

Номер Геделя довільної послідовності виразів визначимо наступним чином: .

Існують також інші нумерації Геделя формальної арифметики.

Приклад ред.

Узагальнення ред.

Взагалі, нумерацією множини називають усюди повне сюр'єктивне відображення. Якщо , то називають номером об'єкта . Окремі випадки  — мови і теорії.

Див. також ред.

Література ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Numeraciya Gedelya ce funkciya g sho zistavlyaye z kozhnim ob yektom deyakoyi formalnoyi movi yiyi nomer Z yiyi dopomogoyu mozhna yavno pronumeruvati nastupni ob yekti movi zminni predmetni konstanti funkcionalni simvoli predikatni simvoli i formuli pobudovani z nih Pobudova numeraciyi Gedelya dlya ob yektiv teoriyi nazivayetsya arifmetizaciyeyu teoriyi vona dozvolyaye perevoditi vislovlyuvannya aksiomi teoremi chi teoriyi v ob yekti arifmetiki Pri comu potribno shob numeraciya g bula efektivno obchislyuvanoyu i dlya bud yakogo naturalnogo chisla mozhna bulo viznachiti chi ye vono nomerom chi ni i yaksho ye to pobuduvati vidpovidnij jomu ob yekt movi Numeraciya Gedelya duzhe shozha na posimvolne koduvannya ryadkiv chislami ale z tiyeyu rizniceyu sho dlya koduvannya poslidovnostej nomeriv bukv vikoristovuyetsya ne konkatenaciya nomeriv odnakovoyi dovzhini a osnovna teorema arifmetiki Numeraciya Gedelya bula nim zastosovana yak instrument dlya dokazu nepovnoti formalnoyi arifmetiki Zmist 1 Variant numeraciyi Gedelya formalnoyi teoriyi pershogo poryadku 1 1 Priklad 2 Uzagalnennya 3 Div takozh 4 LiteraturaVariant numeraciyi Gedelya formalnoyi teoriyi pershogo poryadku red Nehaj K displaystyle mathrm K nbsp teoriya pershogo poryadku sho mistit zminni x 1 x 2 displaystyle x 1 x 2 nbsp predmetni konstanti a 1 a 2 displaystyle a 1 a 2 nbsp funkcionalni simvoli f k n displaystyle f k n nbsp i predikatni simvoli A k n displaystyle A k n nbsp de k displaystyle k nbsp nomer a n displaystyle n nbsp arnist funkcionalnogo abo predikatnogo simvolu Kozhnomu simvolu u displaystyle u nbsp dovilnij teoriyi pershogo poryadku K displaystyle mathrm K nbsp postavimo u vidpovidnist jogo Godelya nomer g u displaystyle g u nbsp nastupnim chinom g 3 g 3 g 3 g 3 g 3 displaystyle g 3 g 3 g 3 g neg 3 g to 3 nbsp g x k 5 8 k k 1 2 displaystyle g x k 5 8k k 1 2 nbsp g a k 7 8 k k 1 2 displaystyle g a k 7 8k k 1 2 nbsp g f k n 9 8 2 n 3 k k n 1 displaystyle g f k n 9 8 cdot 2 n 3 k k n geqslant 1 nbsp g A k n 11 8 2 n 3 k k n 1 displaystyle g A k n 11 8 cdot 2 n 3 k k n geqslant 1 nbsp Nomer Gedelya dovilnoyi poslidovnosti e 0 e r displaystyle e 0 e r nbsp viraziv viznachimo nastupnim chinom g e 0 e r 2 g e 0 3 g e 1 p r g e r displaystyle g e 0 e r 2 g e 0 cdot 3 g e 1 cdot cdot p r g e r nbsp Isnuyut takozh inshi numeraciyi Gedelya formalnoyi arifmetiki Priklad red g A 1 2 x 1 x 2 2 g A 1 2 3 g 5 g x 1 7 g 11 g x 2 13 g 2 107 3 3 5 13 7 7 11 21 13 5 displaystyle g A 1 2 x 1 x 2 2 g A 1 2 cdot 3 g cdot 5 g x 1 cdot 7 g cdot 11 g x 2 cdot 13 g 2 107 cdot 3 3 cdot 5 13 cdot 7 7 cdot 11 21 cdot 13 5 nbsp Uzagalnennya red Vzagali numeraciyeyu mnozhini F displaystyle F nbsp nazivayut usyudi povne syur yektivne vidobrazhennyan N F displaystyle nu mathbb N to F nbsp Yaksho n n f displaystyle nu n f nbsp to n displaystyle n nbsp nazivayut nomerom ob yekta f displaystyle f nbsp Okremi vipadki F displaystyle F nbsp movi i teoriyi Div takozh red Teorema Gedelya pro nepovnotuLiteratura red Klini S K Vvedennya v metamatematiku M IL 1957 526 s Mendelson E Vvedennya v matematichnu logiku M Nauka 1971 320 s Otrimano z https uk wikipedia org w index php title Numeraciya Gedelya amp oldid 21349418