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

В математической логике нумерация Гёделя — это функция , которая присваивает каждому символу и правильно составленной формуле некоторого формального языка уникальное натуральное число , называемое числом Гёделя . Концепция была развита Куртом Гёделем для доказательства его теорем о неполноте . ( Гёдель 1931 )

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

С момента публикации статьи Гёделя в 1931 году термин «нумерация Гёделя» или «код Гёделя» использовался для обозначения более общих присвоений натуральных чисел математическим объектам.

Упрощенный обзор

Гёдель заметил, что каждое утверждение внутри системы может быть представлено натуральным числом (его числом Гёделя ). Значение этого заключалось в том, что свойства утверждения – такие как его истинность или ложность – были бы эквивалентны определению того, обладает ли его число Гёделя определенными свойствами. Число участников может быть действительно очень большим, но это не является препятствием; важно лишь то, что такие числа можно построить.

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

Слово фокси представлен номером 102 111 120 121 .
Логическая формула x=y => y=x представлен 120 061 121 032 061 062 032 121 061 120 .

Кодировка Гёделя

Оригинальная кодировка Гёделя ^{[ 1 ]}
								числовые переменные				переменные свойств			...
Символ	0	с	¬	∨	∀	(	)	х ₁	х ₂	х ₃	...	P_П1	П ₂	P_P3	...
Число	1	3	5	7	9	11	13	17	19	23	...	289	361	529	...

Гёдель использовал систему, основанную на факторизации простых чисел . Он впервые присвоил уникальное натуральное число каждому базовому символу формального языка арифметики, с которым он имел дело.

Чтобы закодировать целую формулу, представляющую собой последовательность символов, Гёдель использовал следующую систему. Учитывая последовательность $(x_{1},x_{2},x_{3},...,x_{n})$ положительных целых чисел, кодирование Гёделя последовательности представляет собой произведение первых n простых чисел, возведенных в соответствующие значения в последовательности:

\mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.

Согласно основной теореме арифметики , любое число (и, в частности, число, полученное таким способом) можно однозначно разложить на простые множители , поэтому можно восстановить исходную последовательность по ее числу Гёделя (для любого заданного числа n символов, подлежащих кодированию).

Гёдель специально использовал эту схему на двух уровнях: во-первых, для кодирования последовательностей символов, представляющих формулы, и, во-вторых, для кодирования последовательностей формул, представляющих доказательства. Это позволило ему показать соответствие между утверждениями о натуральных числах и утверждениями о доказуемости теорем о натуральных числах, что является ключевым наблюдением доказательства. ( Гёдель 1931 )

Существуют более сложные (и более краткие) способы построения нумерации Гёделя для последовательностей .

Пример

В конкретной нумерации Гёделя, используемой Нагелем и Ньюманом, число Гёделя для символа «0» равно 6, а число Гёделя для символа «=" равно 5. Таким образом, в их системе число Гёделя формулы «0 = 0" это 2 ⁶ × 3 ⁵ × 5 ⁶ = 243,000,000.

Отсутствие уникальности

Возможно бесконечно много различных нумераций Гёделя. Например, предположив, что существует K основных символов, альтернативная нумерация Гёделя может быть построена путем обратимого отображения этого набора символов (с помощью, скажем, обратимой функции h ) в набор цифр основанием K. биективной системы счисления с Формула, состоящая из строки из n символов. $s_{1}s_{2}s_{3}\dots s_{n}$ затем будет сопоставлен с числом

h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.

Другими словами, разместив набор из K базовых символов в некотором фиксированном порядке, так что $i$ -й символ однозначно соответствует $i$ -й цифре биективной системы счисления по основанию K , каждая формула может служить просто цифрой своего собственного числа Гёделя.

нумерация Например, описанная здесь имеет K=1000. ^{[ я ]}

Приложение к формальной арифметике

Рекурсия

Можно использовать нумерацию Гёделя, чтобы показать, как функции, определенные с помощью рекурсии хода значений, на самом деле являются примитивно-рекурсивными функциями .

Выражение утверждений и доказательств числами

После того как нумерация Гёделя для формальной теории установлена, каждое правило вывода теории можно выразить как функцию натуральных чисел. Если f — отображение Гёделя, а r — правило вывода, то должна существовать некоторая арифметическая функция g _r натуральных чисел такая, что если формула C выводится из формул A и B посредством правила вывода r , т.е.

A,B\vdash _{r}C,

затем

g_{r}(f(A),f(B))=f(C).

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

Таким образом, в формальной теории, такой как арифметика Пеано , в которой можно делать утверждения о числах и их арифметических отношениях друг с другом, можно использовать нумерацию Гёделя, чтобы косвенно делать утверждения о самой теории. Этот метод позволил Гёделю доказать результаты о свойствах непротиворечивости и полноты формальных систем .

Обобщения

В теории вычислимости термин «нумерация Гёделя» используется в более общих целях, чем описанный выше. Это может относиться к:

Любое присвоение элементов формального языка натуральным числам таким образом, чтобы числами можно было манипулировать с помощью алгоритма, имитирующего манипуляции с элементами формального языка. ^{[ нужна ссылка ]}
В более общем смысле, присвоение элементов счетного математического объекта, такого как счетная группа , натуральным числам, позволяющее алгоритмическое манипулирование математическим объектом. ^{[ нужна ссылка ]}

Кроме того, термин нумерация Гёделя иногда используется, когда присвоенные «числа» на самом деле являются строками, что необходимо при рассмотрении моделей вычислений, таких как машины Тьюринга , которые манипулируют строками, а не числами. ^{[ нужна ссылка ]}

наборы Гёделя

Множества Гёделя иногда используются в теории множеств для кодирования формул и похожи на числа Гёделя, за исключением того, что для кодирования используются множества, а не числа. В простых случаях, когда для кодирования формул используется наследственно конечный набор , это по существу эквивалентно использованию чисел Гёделя, но несколько легче определить, поскольку древовидная структура формул может быть смоделирована древовидной структурой множеств. Наборы Гёделя также можно использовать для кодирования формул на бесконечных языках .

См. также

Примечания

^ В качестве другого, возможно, более интуитивно понятного примера, предположим, что у вас есть три символа для кодирования и вы выбираете биективное основание 10 для знакомства (таким образом, перечисление начинается с 1, 10 представлено символом, например, A, а позиционное значение переносится в 11). вместо 10: десятичное 19 по-прежнему будет 19, и то же самое с 21, но десятичное 20 будет 1A ); С использованием $h(s_{n})=n$ и формула выше:

$(1\times 10^{(3-1)}+2\times 10^{(3-2)}+3\times 10^{(3-3)})=(1\times 10^{2}+2\times 10^{1}+3\times 10^{0})=(100+20+3)$ ^{[ ii ]}

... мы приходим к $123$ как наша нумерация — приятная особенность.
^ (или, в биективной форме по основанию 10: $9A+1A+3$ )

Ссылки

Гёдель, Курт (1931), «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» (PDF) , Monthly Books for Mathematics and Physics , 38 : 173–198, doi : 10.1007/BF01700692 , S2CID 197663120 , заархивировано из оригинал (PDF) на 11 апреля 2018 г. , получено 7 декабря 2013 г.
Гёделя Доказательство Эрнеста Нагеля и Джеймса Р. Ньюмана (1959). В этой книге содержится хорошее введение и краткое изложение доказательства, а большой раздел посвящен нумерации Гёделя.

^ См. Гёдель 1931, с. 179; Обозначения Гёделя (см. стр. 176) адаптированы к современным обозначениям.

Дальнейшее чтение

Гёдель, Эшер, Бах: вечная золотая коса , Дуглас Хофштадтер . В этой книге определяется и используется альтернативная нумерация Гёделя.
«Я — странная петля» , Дуглас Хофштадтер . Это новая книга Хофштадтера, включающая историю нумерации Гёделя.
Визуализация ямы Тьюринга Джейсона Хеманна и Эрика Холка. Использует нумерацию Гёделя для кодирования программ.

[fn1-2] В качестве другого, возможно, более интуитивно понятного примера, предположим, что у вас есть три символа для кодирования и вы выбираете биективное основание 10 для знакомства (таким образом, перечисление начинается с 1, 10 представлено символом, например, A, а позиционное значение переносится в 11). вместо 10: десятичное 19 по-прежнему будет 19, и то же самое с 21, но десятичное 20 будет 1A ); С использованием $h(s_{n})=n$ и формула выше:

$(1\times 10^{(3-1)}+2\times 10^{(3-2)}+3\times 10^{(3-3)})=(1\times 10^{2}+2\times 10^{1}+3\times 10^{0})=(100+20+3)$ ^{[ ii ]}

... мы приходим к $123$ как наша нумерация — приятная особенность.

[fn2-3] (или, в биективной форме по основанию 10: $9A+1A+3$ )

[1] См. Гёдель 1931, с. 179; Обозначения Гёделя (см. стр. 176) адаптированы к современным обозначениям.

[ 1 ]

[ я ]

[ ii ]