Godel, numero di

Godel, numero di

Gödel, numero di numero naturale associato a ciascuna formula di un sistema formale S secondo un procedimento dovuto a K. Gödel e detto pertanto gödelizzazione. Lo stesso procedimento permette anche di associare in modo univoco un numero naturale a ogni asserzione logica che coinvolga le formule in S. Poiché l’aritmetica è esprimibile in termini assiomatici come particolare sistema formale (→ aritmetica, sistema formale per la), è possibile rappresentare ogni affermazione espressa sui numeri naturali attraverso i numeri naturali stessi. Ciò si può esprimere dicendo che, con la gödelizzazione, l’aritmetica può “parlare di sé stessa” analogamente a quanto avviene in un libro di grammatica che spiega le regole della lingua italiana usando, a tale scopo, proprio la lingua italiana (funzione metalinguistica). Il procedimento di gödelizzazione si basa sulla definizione di una funzione, indicata con la lettera g, che associa a ogni formula aritmetica un numero naturale. Per far ciò bisogna innanzitutto associare a ciascun simbolo che può comparire in una formula aritmetica un numero naturale che costituisce il numero di Gödel di quel simbolo. In particolare, si può costruire una funzione g che associa:

• al simbolo 0 il numero naturale 3, in simboli g(0) = 3;

• al simbolo ′ il numero naturale 5, in simboli g(′) = 5;

• al simbolo ( il numero naturale 7, in simboli g(() = 7;

• al simbolo ) il numero naturale 9, in simboli g()) = 9;

• al simbolo + il numero naturale 11, in simboli g(+) = 11;

• al simbolo · il numero naturale 13, in simboli g(·) = 13;

• al simbolo = il numero naturale 15, in simboli g(=) = 15;

• al simbolo x_i il numero naturale 15 + 2i dove x_i è la i-esima variabile del linguaggio (per esempio g(x₁) = 15 + 2 = 17, g(x₂) = 15 + 4 = 19).

Si noti che a ogni simbolo dell’aritmetica viene così associato un numero dispari; la scelta dei numeri dispari viene operata per distinguere i simboli dalle formule. Infatti a ogni formula costituita da una stringa di simboli si attribuisce un numero naturale secondo la regola seguente: alla formula a₁a₂ ... a_n dove a₁, a₂, ..., a_n sono i simboli che compaiono in essa, si associa il numero

dove p_n è l’ennesimo numero primo. Il numero così ottenuto è, quindi, un numero pari, prodotto dei primi n numeri primi, ciascuno elevato al numero di Gödel associato al simbolo che occupa il posto corrispondente. La successione dei numeri primi 2, 3, 5, 7, ... indica il posto che il simbolo (codificato al suo esponente) occupa nella stringa a₁a₂ ... a_n. Per esempio, al numero naturale 4 che nella formalizzazione dell’aritmetica è scritto come stringa 0'''', essendo 5 = succ(succ(succ(succ(0)))) corrisponde il numero di Gödel g(4) = 3995822442167325000 che è il prodotto

Se invece si considera, per esempio, la formula x₁ + x₂ = 0, il suo numero di Gödel sarà

essendo

Seguendo questa procedura, ogni formula è, quindi, codificata da un numero pari, essendo il primo fattore una potenza di 2. Il numero di Gödel di ogni simbolo dell’alfabeto è invece, per la definizione data della corrispondenza g, un numero dispari; ciò esclude la possibilità di confondere simboli e formule. Inoltre il numero attribuito a una formula è unico perché unica è la scomposizione in fattori primi di un numero naturale (in base al teorema fondamentale dell’aritmetica): è dunque possibile risalire dal numero di Gödel alla formula da cui tale numero proviene. Si possono codificare in modo analogo anche le sequenze di formule; a una sequenza di espressioni formali e₁, e₂, e₃, ..., e_n si associa il numero di Gödel

Non è possibile che tale numero sia confuso con il numero di Gödel di una semplice formula: infatti, poiché g(e₁) è sicuramente un numero pari, gli esponenti del numero di Gödel di una sequenza di formule sono tutti pari, mentre quelli di una singola formula sono tutti dispari. Nella codifica così costruita si ha, quindi, che: a un simbolo è associato un numero di Gödel dispari; a una formula un numero pari che, scomposto in fattori primi, ha tutti i fattori con esponente dispari; a una sequenza di formule un numero pari che, scomposto in fattori primi, ha tutti i fattori con esponente dispari.

Come si vede anche negli esempi precedenti, i numeri di Gödel sono molto grandi anche in corrispondenza di formule elementari; tuttavia, l’importanza della codifica introdotta da Gödel non risiede nel calcolo effettivo dei numeri di Gödel, ma nella possibilità di scrivere una stringa di un linguaggio formale o anche una sequenza di stringhe come numero naturale in modo univoco (due formule diverse o due sequenze diverse di formule non possono infatti avere lo stesso numero di Gödel). In particolare, come nell’insieme delle stringhe di un linguaggio si distingue l’insieme L delle formule ben formate, così tra i numeri naturali si distinguono i numeri di Gödel relativi a formule ben formate; se è decidibile la proprietà di appartenenza a L, lo è anche quella di essere un numero di Gödel di una formula ben formata e viceversa.