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

Функция в математической логике

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

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

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

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

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

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

• Слово «лисица» представлено как102 111 120 121 .
• Логическая формула x=y => y=xпредставлена ​​следующим образом:120 061 121 032 061 062 032 121 061 120 .

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

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

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

${\displaystyle \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 символов , затем будет отображена на число ${\displaystyle s_{1}s_{2}s_{3}\dots s_{n}}$

${\displaystyle 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 основных символов в некотором фиксированном порядке, так что -й символ однозначно соответствует -й цифре биективной системы счисления с основанием K , каждая формула может служить просто цифрой своего собственного числа Гёделя. ${\displaystyle i}$ ${\displaystyle i}$

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

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

Рекурсия

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

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

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

${\displaystyle A,B\vdash _{r}C,}$

затем

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

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

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

Обобщения

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

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

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

Множества Гёделя

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

Смотрите также

• Церковное кодирование
• Номер описания
• Нумерация Гёделя для последовательностей
• Теоремы Гёделя о неполноте
• Теорема Хайтина о неполноте

Примечания

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

   ${\displaystyle (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]

   ...мы приходим к нашей нумерации — удобная функция. ${\displaystyle 123}$

2. (или, в биективной десятичной форме: ) ${\displaystyle 9A+1A+3}$

Ссылки

• Гёдель, Курт (1931), «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I» (PDF) , Monatshefte für Mathematik und Physik , 38 : 173–198, doi : 10.1007/BF01700692, S2CID  197663120, архив д из оригинала ( PDF) от 11 апреля 2018 г. , получено 7 декабря 2013 г..
• Gödel's Proof Эрнеста Нагеля и Джеймса Р. Ньюмана (1959). Эта книга содержит хорошее введение и краткое изложение доказательства, с большим разделом, посвященным нумерации Гёделя.

1. См. Gödel 1931, стр. 179; нотация Гёделя (см. стр. 176) была адаптирована к современной нотации.

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

• Гёдель, Эшер, Бах: вечная золотая коса , Дуглас Хофштадтер . В этой книге определяется и используется альтернативная нумерация Гёделя.
• I Am a Strange Loop Дугласа Хофштадтера . Это новая книга Хофштадтера, которая включает в себя историю нумерации Гёделя.
• Визуализация Turing Tarpit Джейсона Хеманна и Эрика Холка. Использует нумерацию Гёделя для кодирования программ.