Нумерація Ґьоделя

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Курт Ге́дель (нім. Kurt Gödel)
Курт Гедель (1925 рік), австрійський логік і математик, приват-доцент Віденського університету (1933–1938)

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

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

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

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

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

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

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

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

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

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

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

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

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