From Wikipedia, the free encyclopedia
En teoria dels nombres un nombre de Gödel és una funció que assigna a cada símbol i fórmula d'un llenguatge formal un nombre únic, anomenat Nombre de Gödel (GN). El concepte va ser usat per primer cop per Kurt Gödel per a la demostració del teorema d'incomplitud de Gödel.
L'enumeració d'un conjunt de funcions computables s'anomena també enumeració de Gödel o enumeració efectiva. Una enumeració de Gödel es pot interpretar com un llenguatge de programació on els nombres de Gödel estan assignats a cada funció computable igual que els programes que calculen els valors per la funció en aquest llenguatge de programació.
Donat un conjunt contable S, una enumeració de Gödel és una funció
on f i la inversa de f són funcions computables.
Els nombres de Gödel es construeixen amb referència a símbols del càlcul proposicional i l'aritmètica formal. Cada símbol s'assigna primer a un nombre natural, per tant:
.
Símbols lògics | Nombres 1:12 |
---|---|
¬ | 1 ("no") |
2 ("per tots") | |
3 ("si, llavors") | |
4 ("o") | |
5 ("i") | |
( | 6 |
) | 7 |
S | 8 ("és el successor de") |
0 | 9 |
= | 10 |
. | 11 |
+ | 12 |
Símbols proposicionals | Nombres més grans de 10 i divisibles per 3 |
P | 12 |
Q | 15 |
R | 18 |
S | 21 |
Variables individuals | Nombres més grans de 10 amb residu 1 quan es divideixen per 3 |
v | 13 |
x | 16 |
y | 19 |
Símbols de predicat | Nombres més grans de 10 amb residu 2 quan es divideixen per 3 |
E | 14 |
F | 17 |
G | 20 |
I així per a tots els símbols possibles. La sintaxi del càlcul proposicional assegura que no hi ha ambigüitat entre el símbol "P" i el símbol "+" encara que estiguin assignats al nombre 12.
A cada enunciat aritmètic se li assigna un nombre de Gödel únic fent servir sèries de nombres primers. Es basa bàsicament en el següent codi:
1r primer caràcter × 2n primer caràcter × 3r primer caràcter, etc.
Per exemple l'enunciat
x, P(x) esdevé
2² × 3¹⁶ × 512 × 7⁶ × 11¹⁶ × 137, perquè {2, 3, 5, 7, 11, ...} és la sèrie de primers, i 2, 16, 12, 6, 16, 7 són els codis dels caràcters. Aquest és un nombre força gran, però perfectament determinat: 14259844433335185664666562849653536301757812500.
És important veure que, pel teorema fonamental de l'aritmètica, aquest nombre tan gran es pot descompondre en els seus factor primers, i per tant és possible convertir un nombre de Gödel a la seqüència de caràcters original.
Finalment, a les seqüències d'enunciats se'ls assigna un nombre de Gödel, de manera que la seqüència
Enunciat 1 (GN1)
Enunciat 2 (GN2)
Enunciat 3 (GN3)
(on GN vol dir nombre de Gödel)
té el nombre de Gödel 2GN1×3GN2×5GN3, que anomenarem GN4.
La demostració del teorema d'incomplitud de Gödel es basa en la demostració que, en aritmètica formal, alguns conjunts d'enunciats proven altres enunciats de forma lògica. Per exemple, es pot provar que GN1, GN2 i GN3 junts (és a dir GN4) proven GN5. Com que aquesta és una relació demostrable entre dos nombres, se li assigna el seu propi símbol, per exemple R. Llavors es pot escriure R(v,x) per expressar que "x demostra v. En el cas anterior on x i v són els nombres de Gödel GN4 i GN5, es podria escriure R(GN5, GN4).
L'argument central de la demostració fet per Gödel es basa en el fet que es pot escriure
que vol dir
El nombre de Gödel per aquesta sentència seria
que es pot anomenar GN6. Ara, si es considera la sentència
que de fet està dient
Que equival a
Si aquesta última sentència es pot provar, llavors el seu sistema formal és inconsistent perquè demostra una sentència que ella mateixa diu que no es pot demostrar (contradicció). Si la sentència no es pot provar dins del sistema formal, llavors el que diu la sentència és cert, i per tant la sentència és consistent, però com que el sistema conté una afirmació que és semànticament certa però que no es pot provar (sintàcticament), Llavors el sistema és incomplet.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.