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

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

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

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

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

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

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

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

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

Приклад

Узагальнення

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

Див. також

Література

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.