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

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


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

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

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

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

Нехай \mathrm{K} - теорія першого порядку , що містить змінні x_1,x_2,..., предметні константи a_1, a_2, ... , функціональні символи f_k^n і предикатні символи A_k^n , де k - номер , а n - арність функціонального або предикатного символу.

Кожному символу u довільній теорії першого порядку \mathrm{K} поставимо у відповідність його Ґьоделя номер g(u) наступним чином: g(()=3; \ g())=3; \ g(,)=3; \ g(\neg )=3; \ g(\to )=3;

g(x_k)=5+8k, \ k=1,2,...;

g(a_k)=7+8k, \ k=1,2,...;

g(f_k^n)=9+8\cdot 2^n3^k, \ k,n\geqslant 1;

g(A_k^n)=11+8\cdot 2^n3^k, \ k,n\geqslant 1.

Ґьоделя номер довільній послідовності e_0, ... ,e_r виразів визначимо наступним чином : g(e_0,...,e_r) =2^{g(e_0)}\cdot 3^{g(e_1)}\cdot...\cdot p_r^{g(e_r)}.

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

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

g(A_1^2(x_1, x_2))=2^{g(A_1^2)}\cdot 3^{g(()}\cdot 5^{g(x_1)}\cdot 7^{g(,)}\cdot 11^{g(x_2)}\cdot 13^{g())}=2^{107}\cdot 3^{3}\cdot 5^{13}\cdot 7^{7}\cdot 11^{21}\cdot 13^{5}

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

Взагалі , нумерацією безлічі F називають усюди певне сюрьектівное відображення\nu: \mathbb{N}\to F. Якщо \nu(n)=f, то n називають номером об'єкта f . Окремі випадки F - мови і теорії.

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

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