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

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

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

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

Содержание

• 1 Упрощенный обзор
• 2 Кодировка Гёделя
  • 2.1 Пример
• 3 Отсутствие уникальности
• 4 Применение к формальной арифметике
  • 4.1 Рекурсия
  • 4.2 Выражение утверждений и доказательств с помощью чисел
• 5 Обобщения
• 6 Геделевских множеств
• 7 См. Также
• 8 Ссылки
• 9 Дополнительная литература

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

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

Проще говоря, мы разрабатываем метод, с помощью которого каждая формула или утверждение, которое может быть сформулировано в нашей системе, получает уникальный номер, таким образом, мы можем механически преобразовывать туда и обратно формулы и числа Гёделя. Ясно, что есть много способов сделать это. Для любого оператора число, в которое оно преобразуется, называется его числом Гёделя. Простым примером является то, как английский язык хранится в виде последовательности чисел на компьютерах с использованием ASCII или Unicode :

• . Слово HELLO представлено 72-69- 76-76-79 с использованием десятичного числа ASCII.
• Логический оператор {{{1}}} представлен как 120-61-121-32-61-62-32- 121-61-120 с использованием десятичного кода ASCII.

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

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

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

$enc\; (x\; 1,\; x\; 2,\; x\; 3,\dots ,\; xn)\; знак\; равно\; 2\; x\; 1\; \cdot \; 3\; x\; 2\; \cdot \; 5\; x\; 3\; \cdots \; pnxn.\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{enc\}\; (x\_\; \{1\},\; x\_\; \{2\},\; x\_\; \{3\},\; \backslash \; dots,\; x\_\; \{n\})\; =\; 2\; ^\; \{x\_\; \{1\}\}\; \backslash \; cdot\; 3\; ^\; \{x\_\; \{2\}\; \}\; \backslash \; cdot\; 5\; ^\; \{x\_\; \{3\}\}\; \backslash \; cdots\; p\_\; \{n\}\; ^\; \{x\_\; \{n\}\}.\}$

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

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

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

Пример

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

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

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

$h\; (s\; 1)\; \times \; K\; (n\; -\; 1)\; +\; h\; (s\; 2)\; \times \; K\; (n\; -\; 2)\; +\; \cdots \; +\; h\; (sn\; -\; 1)\; \times \; K\; 1\; +\; h\; (sn)\; \times \; К\; 0.\; \{\backslash \; displaystyle\; h\; (s\_\; \{1\})\; \backslash \; times\; K\; ^\; \{(n-1)\}\; +\; h\; (s\_\; \{2\})\; \backslash \; times\; K\; ^\; \{(n-2)\}\; +\; \backslash \; cdots\; +\; h\; (s\_\; \{n-\; 1\})\; \backslash \; times\; K\; ^\; \{1\}\; +\; h\; (s\_\; \{n\})\; \backslash \; times\; K\; ^\; \{0\}.\}$

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

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

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

Рекурсия

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

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

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

$A,\; B\; ⊢\; р\; C,\; \{\backslash \; displaystyle\; A,\; B\; \backslash \; vdash\; \_\; \{r\}\; C,\}$

, затем

$gr\; (f\; (A),\; f\; (B))\; =\; f\; (C).\; \{\backslash \; displaystyle\; g\_\; \{r\}\; (f\; (A),\; f\; (B))\; =\; f\; (C).\}$

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

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

Обобщений

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

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

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

Гёделевские множества

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

См. Также

• Кодирование Чёрча
• Номер описания
• Нумерация Гёделя для последовательностей
• Теоремы Гёделя о неполноте
• Теорема Чейтина о неполноте 176>Ссылки
  • Гёдель, Курт (1931), «Über form unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I» (PDF), Monatshefte für Mathematik und Physik, 38: 173– 198, заархивировано из оригинала (PDF) 11.04.2018, извлечено 07.12.2013.
  • Доказательство Гёделя Эрнестом Нагелем и Джеймсом Р. Ньюманом (1959). Эта книга представляет собой хорошее введение и краткое изложение доказательства, с большим разделом, посвященным нумерации Гёделя.

  Дополнительная литература

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