В математической логике нумерация Гёделя — это функция , которая присваивает каждому символу и правильно составленной формуле некоторого формального языка уникальное натуральное число , называемое числом Гёделя . Концепция была развита Куртом Гёделем для доказательства его теорем о неполноте . (Гедель, 1931)
Нумерацию Гёделя можно интерпретировать как кодировку , при которой каждому символу математической записи присваивается число , после чего последовательность натуральных чисел может затем представлять последовательность символов. Эти последовательности натуральных чисел снова могут быть представлены отдельными натуральными числами, что облегчает манипулирование ими в формальных теориях арифметики.
С момента публикации статьи Гёделя в 1931 году термин «нумерация Гёделя» или «код Гёделя» использовался для обозначения более общих присвоений натуральных чисел математическим объектам.
Гёдель заметил, что каждое утверждение внутри системы может быть представлено натуральным числом (его числом Гёделя ). Значение этого заключалось в том, что свойства утверждения – такие как его истинность или ложность – были бы эквивалентны определению того, обладает ли его число Гёделя определенными свойствами. Число участников может быть действительно очень большим, но это не является препятствием; важно лишь то, что такие числа можно построить.
Проще говоря, он разработал метод, с помощью которого каждая формула или утверждение, которое может быть сформулировано в системе, получает уникальный номер, таким образом, что формулы и числа Гёделя можно механически преобразовывать туда и обратно. Есть много способов сделать это. Простой пример — способ хранения английского языка в виде последовательности чисел в компьютерах с использованием ASCII . Поскольку коды ASCII находятся в диапазоне от 0 до 127, достаточно дополнить их тремя десятичными цифрами, а затем объединить их:
x=y => y=xпредставлена120 061 121 032 061 062 032 121 061 120 .Гёдель использовал систему, основанную на факторизации простых чисел . Он впервые присвоил уникальное натуральное число каждому базовому символу формального языка арифметики, с которым он имел дело.
Чтобы закодировать целую формулу, представляющую собой последовательность символов, Гёдель использовал следующую систему. Учитывая последовательность положительных целых чисел, гёделевское кодирование этой последовательности представляет собой произведение первых n простых чисел, возведенных до соответствующих им значений в последовательности:
Согласно основной теореме арифметики , любое число (и, в частности, число, полученное таким способом) можно однозначно разложить на простые множители , поэтому можно восстановить исходную последовательность по ее числу Гёделя (для любого заданного числа n символов, подлежащих кодированию).
Гёдель специально использовал эту схему на двух уровнях: во-первых, для кодирования последовательностей символов, представляющих формулы, и, во-вторых, для кодирования последовательностей формул, представляющих доказательства. Это позволило ему показать соответствие между утверждениями о натуральных числах и утверждениями о доказуемости теорем о натуральных числах, что является ключевым наблюдением доказательства. (Гедель, 1931)
Существуют более сложные (и более краткие) способы построения нумерации Гёделя для последовательностей .
В конкретной нумерации Гёделя, используемой Нагелем и Ньюманом, число Гёделя для символа «0» равно 6, а число Гёделя для символа «=" равно 5. Таким образом, в их системе число Гёделя формулы «0 = 0" это 2 6 × 3 5 × 5 6 = 243 000 000.
Возможно бесконечно много различных нумераций Гёделя. Например, предположив, что существует K основных символов, альтернативная нумерация Гёделя может быть построена путем обратимого отображения этого набора символов (с помощью, скажем, обратимой функции h ) в набор цифр биективной системы счисления с основанием K. Формула, состоящая из строки из n символов , будет затем сопоставлена числу
Другими словами, разместив набор K основных символов в некотором фиксированном порядке, так что -й символ однозначно соответствует -й цифре биективной системы счисления с основанием K , каждая формула может служить просто цифрой ее собственный номер Гёделя.
Например, описанная здесь нумерация имеет K=1000.
Можно использовать нумерацию Гёделя, чтобы показать, как функции, определенные с помощью рекурсии хода значений, на самом деле являются примитивно-рекурсивными функциями .
После того как нумерация Гёделя для формальной теории установлена, каждое правило вывода теории можно выразить как функцию натуральных чисел. Если f — отображение Гёделя, а r — правило вывода, то должна существовать некоторая арифметическая функция g r натуральных чисел такая, что если формула C выводится из формул A и B посредством правила вывода r , т.е.
затем
Это верно для нумерации, используемой Гёделем, и для любой другой нумерации, где закодированная формула может быть арифметически восстановлена из ее числа Гёделя.
Таким образом, в формальной теории, такой как арифметика Пеано , в которой можно делать утверждения о числах и их арифметических отношениях друг с другом, можно использовать нумерацию Гёделя, чтобы косвенно делать утверждения о самой теории. Этот метод позволил Гёделю доказать результаты о свойствах непротиворечивости и полноты формальных систем .
В теории вычислимости термин «нумерация Гёделя» используется в более общих целях, чем описанный выше. Это может относиться к:
Кроме того, термин нумерация Гёделя иногда используется, когда назначенные «числа» на самом деле являются строками, что необходимо при рассмотрении моделей вычислений, таких как машины Тьюринга , которые манипулируют строками, а не числами. [ нужна цитата ]
Множества Гёделя иногда используются в теории множеств для кодирования формул и похожи на числа Гёделя, за исключением того, что для кодирования используются множества, а не числа. В простых случаях, когда для кодирования формул используется наследственно конечный набор , это по существу эквивалентно использованию чисел Гёделя, но несколько легче определить, поскольку древовидная структура формул может быть смоделирована древовидной структурой множеств. Наборы Гёделя также можно использовать для кодирования формул на бесконечных языках .
