Нумерація Геделя

Нумерація Геделя — це функція g , що зіставляє з кожним об'єктом деякої формальної мови її номер. З її допомогою можна явно пронумерувати наступні об'єкти мови: змінні, предметні константи, функціональні символи, предикатні символи і формули, побудовані з них.

Побудова нумерації Геделя для об'єктів теорії називається арифметизацією теорії — вона дозволяє переводити висловлювання, аксіоми, теореми чи теорії в об'єкти арифметики . При цьому потрібно, щоб нумерація g була ефективно обчислюваною і для будь-якого натурального числа можна було визначити, чи є воно номером чи ні, і якщо є, то побудувати відповідний йому об'єкт мови. Нумерація Геделя дуже схожа на посимвольне кодування рядків числами, але з тією різницею, що для кодування послідовностей номерів букв використовується не конкатенація номерів однакової довжини, а основна теорема арифметики.

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

Варіант нумерації Геделя формальної теорії першого порядкуРедагувати

Нехай   — теорія першого порядку, що містить змінні  , предметні константи  , функціональні символи   і предикатні символи   , де   — номер, а   — арність функціонального або предикатного символу.

Кожному символу   довільній теорії першого порядку   поставимо у відповідність його Ґьоделя номер   наступним чином:  

 

 

 

 

Номер Геделя довільної послідовності   виразів визначимо наступним чином:  .

Існують також інші нумерації Геделя формальної арифметики.

ПрикладРедагувати

 

УзагальненняРедагувати

Взагалі, нумерацією множини   називають усюди повне сюр'єктивне відображення . Якщо  , то   називають номером об'єкта  . Окремі випадки   — мови і теорії.

Див. такожРедагувати

ЛітератураРедагувати