Numerotare Gödel
Î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} } 
atât cu f, cât și cu f - 1{\displaystyle 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.
