Numerotare Gödel

Autor: Leandro Alegsa Data creării: 21 februarie 2022

În teoria formală a numerelor, o numerotare Gödel este o funcție care atribuie fiecărui simbol și fiecărei formule dintr-un limbaj formal un număr natural unic numit număr Gödel (GN). Conceptul a fost folosit pentru prima dată de Kurt Gödel pentru demonstrarea teoremei sale de incompletitudine.

O numerotare Gödel poate fi interpretată ca o codificare în care un număr este atribuit fiecărui simbol al unei notații matematice, iar un flux de numere naturale poate reprezenta o anumită formă sau funcție. O numerotare a setului de funcții calculabile poate fi reprezentată printr-un flux de numere Gödel (numite și numere efective). Teorema de echivalență a lui Rogers enunță criteriile pentru care acele numerotări ale ansamblului de funcții calculabile sunt numerotări Gödel.

Definiție

Dat fiind un ansamblu numărabil S, o numerotare Gödel este o funcție injectivă

f : S → N {\displaystyle f:S\to \mathbb {N} } $f:S\to \mathbb {N}$

atât cu f, cât și cu f - 1{\displaystyle f^{-1}} $f^{-1}$ (inversul lui f) fiind funcții calculabile.

Exemple

Notație de bază și șiruri de caractere

Una dintre cele mai simple scheme de numerotare Gödel este folosită în fiecare zi: Corespondența dintre numere întregi și reprezentările lor ca șiruri de simboluri. De exemplu, secvența 2 3 este înțeleasă, printr-un anumit set de reguli, să corespundă numărului douăzeci și trei. În mod similar, șirurile de simboluri dintr-un alfabet de N simboluri pot fi codificate prin identificarea fiecărui simbol cu un număr de la 0 la N și citirea șirului ca fiind reprezentarea în baza N+1 a unui număr întreg.

Întrebări și răspunsuri

Î: Ce este o numerotare Gödel?

R: O numerotare Gödel este o funcție care atribuie un număr natural unic fiecărui simbol și fiecărei formule dintr-un limbaj formal, numit număr Gödel (GN).

Î: Cine a folosit pentru prima dată conceptul de numerotare Gödel?

R: Kurt Gödel a folosit pentru prima dată conceptul de numerotare Gödel pentru demonstrarea teoremei sale de incompletitudine.

Î: Cum putem interpreta numerotarea Gödel?

R: Putem interpreta numerotarea Gödel ca pe o codificare în care fiecărui simbol al unei notații matematice i se atribuie un număr, iar un flux de numere naturale poate reprezenta o formă sau o funcție.

Î: Cum numim numerele naturale atribuite de o numerotare Gödel?

R: Numerele naturale atribuite de o numerotare Gödel se numesc numere Gödel sau numere efective.

Î: Ce afirmă teorema de echivalență a lui Rogers?

R: Teorema de echivalență a lui Rogers stabilește criteriile pentru care acele numerotări ale setului de funcții calculabile sunt numerotări Gödel.

Î: Ce reprezintă un flux de numere Gödel?

R: O numerotare a ansamblului de funcții calculabile poate fi reprezentată de un flux de numere Gödel.

Î: De ce este importantă numerotarea Gödel în teoria formală a numerelor?

R: Numerația Gödel este importantă în teoria formală a numerelor deoarece oferă o modalitate de a reprezenta formulele și funcțiile matematice sub formă de numere naturale, ceea ce permite demonstrarea unor teoreme importante, cum ar fi teorema incompletitudinii.