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

(перенаправлено с «Гёделевская нумерация»)

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

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

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

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

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

 

 

 

 

 

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

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

ПримерПравить

 

ОбобщенияПравить

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

ПримечанияПравить

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

ЛитератураПравить

См. такжеПравить