Nombre de Gödel

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ó.

Definició

Donat un conjunt contable S, una enumeració de Gödel és una funció

f:S\to \mathbb {N}

on f i la inversa de f són funcions computables.

Exemple

Pas 1

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")
$\forall$	2 ("per tots")
$\supset$	3 ("si, llavors")
$\vee$	4 ("o")
$\wedge$	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.

Pas 2

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 $\forall$ x, P(x) esdevé
2² × 3¹⁶ × 5¹² × 7⁶ × 11¹⁶ × 13⁷, 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.

Pas 3

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 2^GN1×3^GN2×5^GN3, 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).

Una demostració informal

L'argument central de la demostració fet per Gödel es basa en el fet que es pot escriure

$\forall$ x, ¬R(v,x)

que vol dir

cap sentència de tipus v es pot provar.

El nombre de Gödel per aquesta sentència seria

2² × 3¹⁶ × 5¹ × 7¹⁸ × 11⁶ × 13¹³ × 17¹⁶ × 19⁷

que es pot anomenar GN6. Ara, si es considera la sentència

$\forall$ x, ¬R(GN6,x),

que de fet està dient

cap sentència que digui 'cap sentència de tipus v es pot provar' es pot provar.

Que equival a

aquesta sentència no es pot provar.

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.

Vegeu també

Codificació de Church

Referències

Gödel, Kurt, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatsheft für Math. und Physik 38, 1931, S.173-198.