stringtranslate.com

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

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

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

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

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

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

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

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

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

Чтобы закодировать целую формулу, которая является последовательностью символов, Гёдель использовал следующую систему. Учитывая последовательность положительных целых чисел, кодирование Гёделя последовательности представляет собой произведение первых 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. [i]

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

Рекурсия

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

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

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

затем

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

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

Обобщения

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

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

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

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

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

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

Примечания

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

    [ii]

    ...мы приходим к нашей нумерации — удобная функция.

  2. ^ (или, в биективной десятичной форме: )

Ссылки

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

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