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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Гёделевская нумерация»)
Перейти к навигации Перейти к поиску

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

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

Вариант нумерации Гёделя формальной теории первого порядка

[править | править код]

Пусть  — теория первого порядка, содержащая переменные , предметные константы , функциональные символы и предикатные символы , где  — номер, а  — арность функционального или предикатного символа.

Каждому символу произвольной теории первого порядка поставим в соответствие его гёделев номер следующим образом:[1]

Гёделев номер произвольной последовательности выражений определим следующим образом: .

Существуют также другие нумерации Гёделя формальной арифметики.

Вообще, нумерацией множества называют всюду определенное сюръективное отображение . Если , то называют номером объекта . Частные случаи - языки и теории.

Примечания

[править | править код]
  1. Мендельсон, 1971, §4.Арифметизация.Гёделевы номера., с. 151—152.

Литература

[править | править код]
  • Клини С.К. Введение в метаматематику. — М.: ИЛ, 1957. — 526 с.
  • Мендельсон Э. Введение в математическую логику. — М.: «Наука», 1971. — 320 с.