Interested Article - Нумерация Гёделя
![](/images/007/200/7200060/1.jpg?rand=686753)
![](https://cdn.wafarin.com/avatars/70e42d83c1a00db8ab791df2b4844af4.jpg)
- 2020-09-04
- 1
Нумерация Гёделя — это функция g , сопоставляющая каждому объекту некоторого формального языка её номер. С её помощью можно явно пронумеровать следующие объекты языка: переменные, предметные константы, функциональные символы, предикатные символы и формулы, построенные из них. Построение нумерации Гёделя для объектов теории называется арифметизацией теории — оно позволяет переводить высказывания, аксиомы, теоремы, теории в объекты арифметики . При этом требуется, чтобы нумерация g была эффективно вычислимой и для любого натурального числа можно было определить, является ли оно номером или нет, и если является, то построить соответствующий ему объект языка. Нумерация Гёделя очень похожа на посимвольное кодирование строк числами, но с той разницей, что для кодирования последовательностей номеров букв используется не конкатенация номеров одинаковой длины, а основная теорема арифметики .
Данная нумерация была применена Гёделем в качестве инструмента для доказательства неполноты формальной арифметики .
Вариант нумерации Гёделя формальной теории первого порядка
Пусть — теория первого порядка , содержащая переменные , предметные константы , функциональные символы и предикатные символы , где — номер, а — арность функционального или предикатного символа.
Каждому символу произвольной теории первого порядка поставим в соответствие его гёделев номер следующим образом:
Гёделев номер произвольной последовательности выражений определим следующим образом: .
Существуют также другие нумерации Гёделя формальной арифметики.
Пример
Обобщения
Вообще, нумерацией множества называют всюду определенное сюръективное отображение . Если , то называют номером объекта . Частные случаи - языки и теории.
Примечания
- , §4.Арифметизация.Гёделевы номера., с. 151—152.
Литература
- Клини С.К. . — М. : ИЛ, 1957. — 526 с.
- Мендельсон Э. . — М. : «Наука», 1971. — 320 с.
См. также
![](https://cdn.wafarin.com/avatars/70e42d83c1a00db8ab791df2b4844af4.jpg)
- 2020-09-04
- 1