Нумерация Гёделя

Поделись знанием:
(перенаправлено с «Гёделева нумерация»)
Перейти к: навигация, поиск

Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С её помощью можно явно пронумеровать следующие объекты языка: переменные, предметные константы, функциональные символы, предикатные символы и формулы, построенные из них. Построение нумерации Гёделя для объектов теории называется арифметизацией теории — оно позволяет переводить высказывания, аксиомы, теоремы, теории в объекты арифметики. При этом требуется, чтобы нумерация g была эффективно вычислимой и для любого натурального числа можно было определить, является ли оно номером или нет, и если является, то построить соответствующий ему объект языка. Нумерация Гёделя очень похожа на посимвольное кодирование строк числами, но с той разницей, что для кодирования последовательностей номеров букв используется не конкатенация номеров одинаковой длины, а основная теорема арифметики.

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





Вариант нумерации Гёделя формальной теории первого порядка

Пусть <math>\mathrm{K}</math> - теория первого порядка, содержащая переменные <math>x_1,x_2,...</math>, предметные константы <math>a_1, a_2, ... </math>, функциональные символы <math>f_k^n</math> и предикатные символы <math>A_k^n</math>, где <math>k</math> - номер, а <math>n</math> - арность функционального или предикатного символа.

Каждому символу <math>u</math> произвольной теории первого порядка <math>\mathrm{K}</math> поставим в соответствие его гёделев номер <math>g(u)</math> следующим образом:

<math>g(()=3; \ g())=5; \ g(,)=7; \ g(\neg )=9; \ g(\to )=11;</math>

<math>g(x_k)=5+8k, \ k=1,2,...;</math>

<math>g(a_k)=7+8k, \ k=1,2,...;</math>

<math>g(f_k^n)=9+8\cdot 2^n3^k, \ k,n\geqslant 1;</math>

<math>g(A_k^n)=11+8\cdot 2^n3^k, \ k,n\geqslant 1.</math>

Гёделев номер произвольной последовательности <math>e_0,...,e_r</math> выражений определим следующим образом: <math>g(e_0,...,e_r) =2^{g(e_0)}\cdot 3^{g(e_1)}\cdot...\cdot p_r^{g(e_r)}</math>.

Существуют также другие нумерации Гёделя формальной арифметики.

Пример

<math>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}</math>

Обобщения

Вообще, нумерацией множества <math>F</math> называют всюду определенное сюрьективное отображение <math>\nu: \mathbb{N}\to F</math>. Если <math>\nu(n)=f</math>, то <math>n</math> называют номером объекта <math>f</math>. Частные случаи <math>F</math> - языки и теории.

Напишите отзыв о статье "Нумерация Гёделя"

Литература

  • Клини С.К. [eqworld.ipmnet.ru/ru/library/books/Klini1957ru.djvu Введение в метаматематику]. — М.: ИЛ, 1957. — 526 с.
  • Мендельсон Э. [eqworld.ipmnet.ru/ru/library/books/Mendelson1971ru.djvu Введение в математическую логику]. — М.: «Наука», 1971. — 320 с.

См. также

Отрывок, характеризующий Нумерация Гёделя

– Ну, племянничек, на матерого становишься, – сказал дядюшка: чур не гладить (протравить).
– Как придется, отвечал Ростов. – Карай, фюит! – крикнул он, отвечая этим призывом на слова дядюшки. Карай был старый и уродливый, бурдастый кобель, известный тем, что он в одиночку бирал матерого волка. Все стали по местам.
Старый граф, зная охотничью горячность сына, поторопился не опоздать, и еще не успели доезжачие подъехать к месту, как Илья Андреич, веселый, румяный, с трясущимися щеками, на своих вороненьких подкатил по зеленям к оставленному ему лазу и, расправив шубку и надев охотничьи снаряды, влез на свою гладкую, сытую, смирную и добрую, поседевшую как и он, Вифлянку. Лошадей с дрожками отослали. Граф Илья Андреич, хотя и не охотник по душе, но знавший твердо охотничьи законы, въехал в опушку кустов, от которых он стоял, разобрал поводья, оправился на седле и, чувствуя себя готовым, оглянулся улыбаясь.
Подле него стоял его камердинер, старинный, но отяжелевший ездок, Семен Чекмарь. Чекмарь держал на своре трех лихих, но также зажиревших, как хозяин и лошадь, – волкодавов. Две собаки, умные, старые, улеглись без свор. Шагов на сто подальше в опушке стоял другой стремянной графа, Митька, отчаянный ездок и страстный охотник. Граф по старинной привычке выпил перед охотой серебряную чарку охотничьей запеканочки, закусил и запил полубутылкой своего любимого бордо.
Илья Андреич был немножко красен от вина и езды; глаза его, подернутые влагой, особенно блестели, и он, укутанный в шубку, сидя на седле, имел вид ребенка, которого собрали гулять. Худой, со втянутыми щеками Чекмарь, устроившись с своими делами, поглядывал на барина, с которым он жил 30 лет душа в душу, и, понимая его приятное расположение духа, ждал приятного разговора. Еще третье лицо подъехало осторожно (видно, уже оно было учено) из за леса и остановилось позади графа. Лицо это был старик в седой бороде, в женском капоте и высоком колпаке. Это был шут Настасья Ивановна.
– Ну, Настасья Ивановна, – подмигивая ему, шопотом сказал граф, – ты только оттопай зверя, тебе Данило задаст.
– Я сам… с усам, – сказал Настасья Ивановна.
– Шшшш! – зашикал граф и обратился к Семену.
– Наталью Ильиничну видел? – спросил он у Семена. – Где она?
– Они с Петром Ильичем от Жаровых бурьяно встали, – отвечал Семен улыбаясь. – Тоже дамы, а охоту большую имеют.
– А ты удивляешься, Семен, как она ездит… а? – сказал граф, хоть бы мужчине в пору!
– Как не дивиться? Смело, ловко.
– А Николаша где? Над Лядовским верхом что ль? – всё шопотом спрашивал граф.