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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Нумерація Ґьоделя)
Перейти до: навігація, пошук

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

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

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

Варіант нумерації Геделя формальної теорії першого порядку[ред.ред. код]

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

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

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

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

Приклад[ред.ред. код]

Узагальнення[ред.ред. код]

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

Література[ред.ред. код]

Див. також[ред.ред. код]