Гёделевская нумерация - Gödel numbering

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

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

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

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

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

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

Слово HELLO представлено (72,69,76,76,79) в десятичном формате ASCII .
Логическая формула x=y => y=x представлена как (120,61,121,32,61,62,32,121,61,120) с использованием десятичного кода ASCII.

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

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

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

Чтобы закодировать всю формулу, которая представляет собой последовательность символов, Гёдель использовал следующую систему. Для данной последовательности положительных целых чисел гёделевское кодирование этой последовательности является произведением первых 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 основные символы, альтернативный Гедель нумерация может быть построена путем invertibly отображения этого набора символов (через, скажем, обратимую функцию ч ) к набору цифр в биективной базе - К системе счисления . Формула, состоящая из строки из 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.

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

Рекурсия

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

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

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

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

тогда

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

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

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

Обобщения

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

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

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

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

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

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

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

Гедель, Эшер, Бах: Вечный Золотой Шнурок , по Хофштадтеру . В этой книге определяется и используется альтернативная нумерация Гёделя.
I Am Странная Петля по Хофштадтеру . Это новая книга Хофштадтера, которая включает в себя историю нумерации Гёделя.
Визуализация брезента Тьюринга Джейсона Хеманна и Эрика Холка. Использует нумерацию Гёделя для кодирования программ.

Languages

In other projects