Нумерація Геделя — це функція g , що зіставляє з кожним об'єктом деякої формальної мови її номер. З її допомогою можна явно пронумерувати наступні об'єкти мови: змінні, предметні константи, функціональні символи, предикатні символи і формули, побудовані з них.
Побудова нумерації Геделя для об'єктів теорії називається арифметизацією теорії — вона дозволяє переводити висловлювання, аксіоми, теореми чи теорії в об'єкти арифметики . При цьому потрібно, щоб нумерація g була ефективно обчислюваною і для будь-якого натурального числа можна було визначити, чи є воно номером чи ні, і якщо є, то побудувати відповідний йому об'єкт мови. Нумерація Геделя дуже схожа на посимвольне кодування рядків числами, але з тією різницею, що для кодування послідовностей номерів букв використовується не конкатенація номерів однакової довжини, а основна теорема арифметики.
Нумерація Геделя була ним застосована як інструмент для доказу неповноти формальної арифметики.
Варіант нумерації Геделя формальної теорії першого порядку
Нехай
— теорія першого порядку, що містить змінні
, предметні константи
, функціональні символи
і предикатні символи
, де
— номер, а
— арність функціонального або предикатного символу.
Кожному символу
довільній теорії першого порядку
поставимо у відповідність його Ґьоделя номер
наступним чином:
Номер Геделя довільної послідовності
виразів визначимо наступним чином:
.
Існують також інші нумерації Геделя формальної арифметики.
Приклад
Узагальнення
Взагалі, нумерацією множини
називають усюди повне сюр'єктивне відображення
. Якщо
, то
називають номером об'єкта
. Окремі випадки
— мови і теорії.
Див. також
Література