Teoremi di Gödel

Alessandro Berarducci

Versione molto preliminare, solo sulla parte tecnica, 1 giugno 2001, perdonate gli errori …

1 Algoritmi e funzioni calcolabili

1.1 Funzioni calcolabili

Una funzione f si dice calcolabile (o “algoritmicamente calcolabile”) se esiste un algoritmo che dato in ingresso x ∈ dom(f) fornisce in uscita il valore y = f(x).

Questa definizione ha bisogno di varie precisazioni. Innanzitutto la nozione di algoritmo è data per intuitivamente nota e non verrà definita. L’idea è che un algoritmo è un insieme finito di istruzioni che possono essere eseguite in modo del tutto meccanico senza che sia richiesta alcuna “creatività” da parte di chi esegue le istruzioni (che quindi può essere una macchina).

Poichè un algoritmo deve necessariamente operare su rappresentazioni finite, affinchè la definizione abbia senso assumiamo gli elementi del dominio e codominio di f siano rappresentati da stringhe finite di simboli presi da un alfabeto finito Σ. Questo implica che il dominio e il codominio di una funzione calcolabile è necessariamente un insieme finito o numerabile. Esempi di domini e codomini ammissibili sono i numeri naturali N con la usuale rappresentazione in notazione decimale^{1}, oppure i razionali Q dove q ∈ Q è rappresentato dando il numeratore e denominatore della frazione ridotta ai minimi termini che corrisponde a q ^{2}. Non considereremo invece funzioni su numeri reali in quanto non è possibile fissare una rappresentazione finita per i numeri reali^{3}.

1Un’altra notazione spesso usata in queste note è quella di rappresentare n ∈ N con l’espressione S(S(… S(0))) dove il simbolo S (successore) è ripetuto n volte.

2Ovviamente non è necessario che il dominio e codominio siano lo stesso insieme: possiamo ad esempio considerare funzioni da N^{5} ad Q.

A priori potrebbe capitare che una funzione sia calcolabile rispetto ad una data rappresentazione degli elementi del dominio e codominio e non calcolabile rispetto ad un’altra rappresentazione. Se però consideriamo due rappresentazioni tali che esiste un algoritmo per passare dall’una all’altra, ad esempio la rappresentazione in base decimale e quella in base due per i numeri naturali, allora è chiaro che una qualsiasi funzione è calcolabile rispetto alla prima rappresentazione se e solo se lo è rispetto alla seconda^{4}.

In genere tutte le rappresentazioni comunemente considerate hanno la proprietà che si può passare in modo algoritmico dall’una all’altra rappresentazione. Possiamo quindi parlare di funzioni calcolabili lasciando implicita la scelta della particolare rappresentazione usata.

Esempi classici di funzioni calcolabili sono i seguenti:

1) La funzione di divisione con resto sui numeri naturali (possiamo usare l’algoritmo delle sottrazioni successive).

2) La funzione da N^{2} a N che dati due numeri x e y fornisce il massimo comun divisore di x ed y (usiamo l’algoritmo di Euclide).

3) La funzione da N all’insieme di due elementi {SI, NO} che dato un numero x ∈ N stabilisce se x è primo (dato x calcoliamo il resto della divisione di x per tutti i numeri maggiori di uno e più piccoli di x e diamo risposta SI se tutti i resti sono diversi da zero).

4) La funzione da N ad N^{<ω} (sequenze finite di elementi di N) che dato un numero fornisce la sua scomposizione in fattori primi.

Chiaramente può esistere più di un algoritmo per calcolare la stessa funzione, alcuni più efficienti altri meno ^{5}.

3I reali possono essere rappresentati tramite i loro sviluppi decimali, ma in generale sono necessarie infinite cifre dopo la virgola, e quindi non si tratta di una rappresentazione finita. Sono stati fatti vari tentativi di estendere il concetto di funzione calcolabile ai numeri reali, ma non entreremo in questo argomento.

4Ad esempio se ho un algoritmo per scomporre in fattori primi in numero naturale scritto in base due, posso facilmente ottenere un secondo algoritmo per scomporre in fattori primi un numero scritto in base dieci. Il secondo algoritmo prende in ingresso un numero in base 10, ne trova la rappresentazione binaria, applica il primo algoritmo per scomporlo, e infine riscrive il risultato in base 10.

5La teoria della complessità si occupa del trovare algoritmi efficienti. La teoria della ricorsività, di cui ci occuperemo, si interessa solo all’esistenza di algoritmi indipendentemente dalla loro efficienza.

1.2 Funzioni calcolabili parziali

Alcuni algoritmi potrebbero non arrestarsi mai per alcuni valori in ingresso. Consideriamo il seguente esempio.

Esempio 1.1 E’ facile progettare un algoritmo che, ricevendo in ingresso una equazione polinomiale a coefficienti interi, passi in rassegna uno dopo l’altro tutti i possibili valori interi delle variabili arrestandosi qualora venga trovata una soluzione dell’equazione e fornendo in uscita la soluzione. Se l’equazione non ha soluzione, l’algoritmo continuerà la ricerca senza arrestarsi mai.

Sarebbe bello progettare un algoritmo che non solo trovi una soluzione quando essa esiste, ma sia anche in grado di determinare quando essa non esiste anziché andare avanti a cercarla senza fine. Ciò però non è possibile. Nel 1970 Y. Matijaseviç ha infatti dimostrato (assumendo la tesi di Church) che non esiste un metodo algoritmico per stabilire se una equazione polinomiale a coefficienti interi (in più variabili) ammetta una soluzione in numeri interi.

Diamo ora un esempio di un algoritmo di cui non è noto se la sua esecuzione termini per ogni valore in ingresso.

Esempio 1.2 Due numeri primi p, q ∈ N si dicono gemelli se q − p = 2. Mentre si sa che esistono infiniti numeri primi, non è noto se esistano infiniti numeri primi gemelli.

È facile costruire un algoritmo che dato x ∈ N, trova, se esistono, due numeri primi gemelli p, q ∈ N maggiori di x. L’algoritmo enumera uno dopo l’altro tutti i numeri dispari maggiori di x finchè trova, se esistono, due numeri dispari consecutivi che sono entrambi primi.

Se esistono infiniti numeri primi gemelli (cosa che a tutt’oggi è ignota) l’algoritmo si ferma sempre. Altrimenti si fermerà solo per valori x in ingresso non più grandi del più grande primo gemello.

Ad un algoritmo che non termina per alcuni valori in ingresso risulta naturale associare una “funzione parziale” nel senso seguente.

Una funzione parziale da A a B è una funzione da A a B ∪ {⊥} (unione disgiunta), dove f(a) =⊥ significa che f è indefinita su a.

Scriviamo f: A ⇝ B per indicare che f è una funzione parziale da A a B, cioè f: A → B ∪ {⊥}. Per funzioni parziali f: A ⇝ B esiste una distinzione tra l’insieme A dei possibili argomenti, e il dominio dom(f) ⊆ A consistente di quegli argomenti a ∈ A tali che f(n) ≠⊥. Ammettiamo come casi limite di funzioni parziali le funzioni totali, quelle cioè per cui dom(f) = A. Un altro caso limite di funzione parziale è la funzione indefinita per ogni input.

Possiamo associare ad ogni algoritmo M una funzione parziale f nel modo seguente. Supponiamo che l’algoritmo M prenda in ingresso elementi di un insieme A (in una fissata rappresentazione) e fornisca in uscita, nei casi in cui la computazione termina dopo un numero finito di passi, elementi di un insieme B (in una fissata rappresentazione).

La funzione calcolata da M è la funzione parziale f_{M}: A ⇝ B tale che: f_{M}(a) = b se M con input a fornisce in uscita b, f_{M}(a) =⊥ se M con input a non si ferma mai. Una funzione parziale f: X ⇝ Y si dice calcolabile parziale se esiste un

algoritmo M tale che f = f_{M}.

Qualche autore parla di semi-algoritmi per designare quegli algoritmi che potrebbero non fermarsi per alcuni input.

2 Macchine di Turing e tesi di Church

2.1 Macchine di Turing

Un tentativo di formalizzare il concetto di funzione calcolabile è stato compiuto da Alan Turing nel 1936. Una macchina di Turing può essere informalmente descritta come un calcolatore ideale fornito di due tipi di memoria: interna ed esterna. Ad ogni dato momento entrambi i tipi di memoria contengono una quantità finita di informazione, ma mentre la memoria esterna è potenzialmente illimitata (nel senso che il calcolatore può richiedere in ogni momento una sua espansione), la memoria interna ha una fissata capacità massima che non può essere superata nell’intero processo di elaborazione, cosicché essa può assumere solamente un insieme finito Q di stati. La memoria esterna è rappresentata da un nastro suddiviso in celle, dove ogni cella può contenere una quantità limitata di informazione, che senza perdita di generalità può essere rappresentata da un simbolo preso da un alfabeto finito Σ. La macchina è inoltre fornita di un puntatore che può scandire una cella alla volta della memoria esterna, e di un “programma” che determina il corso della elaborazione nel modo seguente. In funzione del contenuto della memoria interna e della parte della memoria esterna scandita dal puntatore, il programma specifica: 1) come deve essere modificato il contenuto della cella del nastro scandita in quel momento; 2) dove si deve spostare il puntatore (deve essere una cella contigua); 3) come deve essere alterata la memoria interna. A partire dalla configurazione iniziale della memoria la macchina esegue ripetutamente le operazioni specificate dal programma arrestandosi se, e quando, viene raggiunto un determinato stato della memoria interna, detto stato di arresto.

Diamo ora le definizioni formali. Una macchina di Turing è costituita da:

0. Un alfabeto finito Σ contenente almeno i simboli 0, 1, # (dove # è un simbolo speciale per lo spazio bianco).

1. Un nastro infinito diviso in celle. Ogni cella contiene uno dei simboli di Σ. In ogni dato momento il nastro conterrà solamente un numero finito di simboli diversi da #.

2. Un insieme finito Q di stati. Assumiamo che tra gli stati q ∈ Q vi siano due stati speciali di INIZIO ∈ Q e di ARRESTO ∈ Q

3. Un puntatore del nastro che ad ogni dato momento si trova in uno degli stati di Q e scandisce una cella del nastro. Esso può spostarsi lungo le celle del nastro, cambiare il contenuto delle celle stesse, e cambiare stato secondo delle regole che vedremo. Ad ogni movimento il puntatore scrive un simbolo di Σ nella cella che viene scandita, sostituendo ciò che vi era scritto, e poi si sposta di una cella a sinistra o a destra.

4. Le regole che governano il comportamento del puntatore sono date da un programma. Esso consiste di una funzione di transizione δ: Q × Σ → Q×Σ×{S, D} (dove S, D stanno per sinistra e destra)^{6}. Supponiamo che in un certo momento della computazione il puntatore si trovi nello stato q ∈ Q e stia scandendo una cella contenente il simbolo α ∈ Σ. Sia (q′, α′, i) = δ(q, α) (dove i ∈ {S, D}). In questa situazione il puntatore compie le seguenti azioni: scrive il simbolo α′ sulla cella che in quel momento sta scandendo (cancellando il simbolo α che vi si trovava), si porta nello stato q′, e se q′ ≠ ARREST O si sposta di una cella a sinistra o a destra a seconda che i = S, F. Nel caso q′ = ARREST O la macchina di Turing si arresta.

2.2 Funzione parziale calcolata da una macchina di Turing.

Fissiamo k ∈ N. Una macchina di Turing M con un alfabeto di inputoutput contenente i simboli 0, 1 calcola una funzione parziale f_{M}^{k}: N^{k} ⇝ N nel modo seguente.

Rappresentiamo x ∈ N con la parola 11 … 1 (x volte 1).

6Poichè Q×Σ è un insieme finito, la funzione di transizione può essere data sotto forma di una tabella finita

Se k > 1 rappresentiamo (x_{1}, x_{2}, …, x_{k}) ∈ N^{k} con la parola che contiene x_{1} volte il simbolo 1, seguita da uno 0, seguita dalla rappresentazione di (x_{2}, …, x_{k}).

Esempio: (4, 3, 5) è rappresentata dalla parola 11110111011111.

Diciamo che f_{M}^{k}(x_{1}, …, x_{k}) = y se e solo se, facendo partire la macchina M nello stato INIZIO con la parola che rappresenta (x_{1}, …, x_{n}) scritta inizialmente sul nastro e con il puntatore all’inizio della parola, abbiamo che dopo un certo numero finito di passi la macchina M si arresta con la parola rappresentante y scritta sul nastro e il puntatore all’inizio della parola.

Negli altri casi definiamo f_{M}^{k}(x_{1}, …, x_{k}) =⊥^{7}.

Chiaramente possiamo usare una macchina di Turing anche per calcolare funzioni parziali non numeriche f: A ⇝ B. Basta fissare una rappresentazione degli elementi di A e B come parole sull’alfabeto Σ.

2.3 Tesi di Church

Nella seconda metà degli anni trenta vari autori, tra cui Turing, Post, Church e Kleene, hanno indipendentemente cercato di rendere rigoroso il concetto di funzione calcolabile (si tenga presente che non esistevano ancora i calcolatori). A tal fine Turing ha introdotto il concetto di “macchina di Turing” (una sorta di calcolatore astratto il cui funzionamento può essere facilmente simulato con carta e penna). Una funzione si dice Turing-calcolabile se può essere calcolata da una macchina di Turing. Similmente Kleene ha definito le funzioni “μ-ricorsive”, e Church le funzioni “λ-calcolabili”. È stato successivamente dimostrato che le funzioni Turing calcolabili, μ-ricorsive, e λcalcolabili coincidono. Questi tre concetti individuano dunque una unica classe di funzioni, dette funzioni ricorsive parziali. La coincidenza di questi diversi tentativi di rendere rigoroso il concetto di funzione calcolabile ha portato all’accettazione della:

Tesi di Church Le funzioni algoritmicamente calcolabili parziali coincidono con le funzioni parziali Turing calcolabili.

Questa è una tesi che può essere giustificata e motivata in vari modi ma che ovviamente non può essere “dimostrata” in quanto il concetto di algoritmo è intuitivo e informale.

7È facile vedere che possiamo sempre modificare una macchina di Turing in modo da ottenerne un’altra che ha esattamente lo stesso comportamento della prima eccetto che, nel caso la prima si ferma senza fornire in uscita la rappresentazione di un intero, la seconda non si ferma mai.

L’accettazione della Tesi di Church rende possibile dimostrare la nonesistenza di algoritmi per calcolare determinate funzioni o risolvere determinati problemi.

3 Insiemi decidibili e semidecidibili

Consideriamo per semplicità sottoinsiemi di N sebbene le seguenti definizioni si applichino a sottoinsiemi di N^{k} ed anche ad insiemi non numerici, ad esempio sottoinsiemi di Σ^{∗}, ovvero insiemi i cui elementi siano rappresentati da stringhe finite di simboli da un certo alfabeto finito Σ.

Un insieme A ⊆ N si dice decidibile (come sottoinsieme di N) se esiste un algoritmo che, dato in ingresso x ∈ N (in una certa notazione fissata) stabilisce se x appartiene o non appartiene ad A (ad esempio fornendo in uscita 1 o 0 a seconda che x appartenga o non appartenga ad A).

In altre parole A è decidibile se la sua funzione caratteristica χ_{A}: U → {0, 1} (definita da χ_{A}(x) = 1 se x ∈ A, χ_{A}(x) = 0 se x ∉ A) è calcolabile.

Esempio: l’insieme dei numeri primi (come sottoinsieme dei numeri naturali) è decidibile. Dato x ∈ N possiamo stabilire se x è primo o no esaminando tutti i possibili divisori di x minori di x.

Un insieme A ⊆ N si dice semidecidibile se esiste un algoritmo tale che, se viene dato in ingresso un elemento x ∈ A, l’esecuzione dell’algoritmo termina dopo un numero finito di passi, mentre se in ingresso viene dato un elemento x ∈ U − A, l’esecuzione dell’algoritmo non termina mai.

Segue dalle definizioni che un insieme è semidecidibile se e solo se è il dominio di una funzione calcolabile parziale.

Chiaramente N e l’insieme vuoto e l’insieme sono (sia decidibili che) semidecidibili (come sottoinsiemi di N). Basta considerare un algoritmo che non si ferma per alcun input ed uno che si ferma per ogni input. Abbiamo:

Proposizione 3.1 Ogni insieme decidibile è anche semidecidibile.

Dim. Sia A ⊆ N decidibile. Ne segue, per definizione, che esiste un algoritmo M_{1} che dato x ∈ N stabilisce se x appartiene o no ad A (dando come uscita 1 o 0 rispettivamente). Consideriamo ora un algoritmo ausiliario M_{2} che avendo in ingresso 1 si ferma subito, ed avendo in ingresso 0 comincia un calcolo senza fine. Sia M_{3} l’algoritmo che si ottiene componendo M_{1} ed M_{2} in modo tale che l’uscita di M_{1} viene fornita in entrata ad M_{2}. Ne segue che se x ∈ A, l’algoritmo M_{3} si ferma dopo un numero finito di passi, e se x ∈ N − A, l’algoritmo M_{3} non si ferma mai. Quindi A è semidecidibile. QED

Teorema 3.2 (Teorema di Post) Supponiamo che sia A che il suo complemento N − A siano semidecidibili. Allora A è decidibile.

Dim. Dato x ∈ N possiamo dare x come ingresso ai due semi-algoritmi per A e N − A e eseguirli simultaneamente in modo alternato (eseguendo cioè un passo dell’uno ed uno dell’altro). Poichè x appartiene ad A oppure ad N − A, uno dei due semi-algoritmi si ferma dopo un numero finito di passi. Se è il primo a fermarsi, abbiamo stabilito che x ∈ A, se invece si ferma il secondo, x ∉ A. In questo modo abbiamo definito un algoritmo per stabilire se x appartiene o no ad A e quindi A è decidibile. QED

Ricordiamo che un insieme A è numerabile se è vuoto oppure esiste una lista a_{0}, a_{1}, a_{2}, … indiciata dai numeri naturali che esaurisce tutti e soli gli elementi di A (non è detto che nella lista non ci siano ripetizioni, e non escludiamo il caso in cui A sia finito).

Un insieme A ⊆ N si dice algoritmicamente enumerabile se A è vuoto oppure esiste una enumerazione a_{0}, a_{1}, a_{2}, … degli elementi di A che è effettiva, nel senso che la funzione n ↦ a_{n} (da N ad N) è calcolabile.

Quindi un insieme non-vuoto A è algoritmicamente enumerabile se e solo se è l’immagine di una funzione calcolabile con dominio N.

Esiste una importante differenza tra gli insiemi numerabili e quelli algoritmicamente numerabili: mentre ogni sottoinsieme di un insieme numerabilie è numerabile, un sottoinsieme di un insieme algoritmicamente enumerabile non è necessariamente algoritmicamente enumerabile. Ad esempio N è algoritmicamente enumerabile, ma vedremo (assumendo la “tesi di Church”) che N possiede sottoinsiemi non algoritmicamente enumerabili.

Teorema 3.3 Un insieme A ⊆ N è semidecidibile se e solo se è algoritmicamente enumerabile.

Dim. Se A è vuoto è sia semidecidibile che algoritmicamente enumerabile. Assumiamo che A non sia vuoto.

Supponiamo che A sia algoritmicamente enumerabile e fissiamo una funzione calcolabile f: N → A suriettiva. Definiamo ora un algoritmo H nel modo seguente. Avendo x ∈ N in ingresso H comincia a enumerare uno dopo l’altro f(0), f(1), f(2), … (usando un algoritmo per calcolare f) e si ferma solamente se nel corso di questa enumerazione trova un elemento f(n) uguale ad x. È chiaro che l’algoritmo H così definito si ferma su input x ∈ N se e solo se x ∈ A. Quindi A è semidecidibile.

Il viceversa è più complicato e richiede di fissare una funzione calcolabile suriettiva f: N → N × N (si usi una codifica delle coppie di numeri). Supponiamo che A sia semidecidibile. Esiste quindi un algoritmo H_{1} che si ferma su input x ∈ N se e solo se x ∈ A. Fissiamo un elemento a ∈ A e definiamo una funzione calcolabile g: N → N nel modo seguente: per calcolare g(n) calcoliamo dapprima f(n) = (a_{n}, b_{n}) ∈ N × N. Ora poniamo g(n) = a_{n} se l’algoritmo H_{1} su input a_{n} si ferma in al più b_{n} passi (questo può essere controllato algoritmicamente semplicemente eseguendo H_{1} per al più b_{n} passi), e g(n) = a nel caso contrario. È chiaro che i valori di g appartengono tutti ad A. Resta da vedere che ogni elemento u ∈ A è nell’insieme dei valori di g. Fissiamo dunque u ∈ A. Ne segue che H_{1} applicato ad u si ferma dopo un certo numero di passi, diciamo m passi. Poichè f: N → N × N è suriettiva, esiste n ∈ N tale che f(n) = (u, m). Per definizione di g, g(n) = u. Quindi g: N → A è suriettiva (e calcolabile) e A è algoritmicamente enumerabile. QED

Esercizio: l’unione, l’intersezione, e il prodotto cartesiano di insiemi algoritmicamente enumerabili è algoritmicamente enumerabile. Tutto ciò è vero a fortiori per gli insiemi decidibili che però hanno una proprietà in più: il complemento di un insieme decidibile è decidibile. Quindi i sottoinsiemi decidibili di N formano un algebra di Boole (rispetto a unioni, intersezioni e complementi).

Esercizio: Dimostrare il teorema precedente per insiemi non numerici A ⊆ Σ^{∗}. Cosa prende il posto della funzione calcolabile suriettiva f: N → N × N?

Esercizio: Siano A, B, C tre insiemi algoritmicamente enumerabili disgiunti la cui unione sia N. Dimostrare che A, B, C sono decidibili.

3.1 Enumerabilità algoritmica dei teoremi

Il teorema che segue fornisce l’esempio più importante di un insieme semidecidibile che non è in generale decidibile.

Teorema 3.4 L’insieme dei teoremi di una teoria formale con un numero finito di assiomi^{8} è semidecidibile.

Dim. Supponiamo di avere una teoria T con un insieme finito di assiomi Ax(T) ⊆ Σ^{∗} dove Σ è un alfabeto finito. Non è importante che T sia una teoria del primo ordine, l’unica cosa che conta è che abbiamo un insieme finito di regole di inferenza (o di schemi di regole) che a partire dagli assiomi permettono di dedurre nuovi teoremi^{9}. Sia T h(T) ⊆ Σ^{∗} l’insieme dei teoremi che si possono dedurre dagli assiomi usando un numero finito di volte le regole di inferenza. Mostreremo che T h(T) è semidecidibile (come sottoinsieme di Σ^{∗}).

A tal fine definiremo una procedura algoritmica che dato x ∈ Σ^{∗} cerca di dedurre x dagli assiomi applicando in modo sistematico le regole di inferenza in tutti i modi possibili. Questo può essere fatto nel seguente modo: dapprima controlliamo se x compare nella lista degli assiomi. Visto che gli assiomi sono in numero finito questo controllo termina dopo un numero finito di passi. Nel caso x compare nella lista degli assiomi ci fermiamo (in questo caso x è certamente un teorema). Se invece x non è un assioma generiamo l’insieme T_{1} di tutte quelle espressioni che si possono dedurre dagli assiomi usando al più una volta le regole di inferenza. Chiaramente T_{1} è un insieme finito ed è possibile generarlo in modo algoritmico in un numero finito di passi. Ora controlliamo se x appartiene a T_{1}. Se ci appartiene ci fermiamo, se no ripetiamo il procedimento ma partendo da T_{1} invece che dall’insieme degli assiomi. In questo modo generiamo l’insieme T_{2} di tutti i teoremi che si possono ottenere dagli assiomi usando al più due volte le regole di inferenza. Se x è in T_{2} ci fermiamo, se no ripetiamo il procedimento partendo da T_{2} invece che da T_{1} e così via.

È chiaro che se x è un teorema, prima o poi seguendo questa procedura una corretta derivazione di x dagli assiomi verrà trovata. Se però x non è un teorema, l’algoritmo che abbiamo dato non è in grado di accorgersene e andrà avanti a cercare possibili derivazioni di x di lunghezza sempre maggiore senza mai fermarsi. Questo mostra che l’insieme dei teoremi è in effetti semidecidibile^{10}. QED

8Questa ipotesi si può indebolire: basta avere un insieme decidibile o semidecidibile di assiomi.

9Assumiamo che ci sia un modo algoritmico per passare dalle premesse di una regola di inferenza alla sua conclusione, escludiamo quindi regole di inferenza che abbiano bisogno di infinite premesse

10Ovviamente l’argomentazione data non dimostra che l’insieme dei teoremi non è decidibile in quanto a priori potrebbero esserci algoritmi più ingegnosi di quello che abbiamo dato.

Chiaramente l’algoritmo che abbiamo sopra dato non è molto ingegnoso e certamente non corrisponde a ciò che un matematico farebbe nel tentare di stabilire se una certa espressione è un teorema di una certa teoria formale. Più verosimilmente il matematico farebbe la cosa seguente: prima cercherebbe di dimostrare x. Se dopo un ragionevole lasso di tempo questo tentativo fallisse, il matematico comincerebbe a dubitare della validità di x e cercherebbe di dare una dimostrazione della negazione di x. Se dopo vari tentativi anche questo tentativo non riuscisse, egli tornerebbe a cercare di dimostrare x percorrendo strade prima inesplorate. In questo modo, alternando la sua attenzione tra x e la sua negazione, il matematico può sperare di riuscire a trovare, avendo abbastanza tempo a disposizione, una dimostrazione di x o della negazione di x. Nel caso di teorie incomplete è tuttavia possibile che nè x nè la sua negazione siano derivabili dagli assiomi^{11} e in questo caso questa procedura fallisce. Chiaramente questa procedura ricorda molto da vicino il teorema di Post.

Teorema 3.5 Sia T una teoria formale coerente e completa con un numero finito di assiomi^{12}. Allora i teoremi di T sono un insieme decidibile.

Dim. Per teorie T coerenti e complete per ogni enunciato x nel linguaggio della teoria, o x o la sua negazione è dimostrabile in T ma non entrambi. Ne segue che la ricerca alternata sopra delineata (consistente nel cercare alternativamente dimostrazioni di x e della sua negazione) se organizzata in modo sistematico, definisce un algoritmo che riesce a dimostrare qualsiasi dato enunciato del linguaggio formale o la sua negazione. Questo fornisce un algoritmo per stabilire se x è un teorema. QED

Una dimosrazione alternativa si basa sul teorema di Post: l’insieme dei teoremi è semidecidibile, l’insieme degli enunciati refutabili (ciò gli enunciati la cui negazione è un teorema) è per lo stesso motivo semidecidibile. Per teorie coerenti e complete questi due insiemi sono l’uno il complemento dell’altro all’interno dell’insieme di tutti gli enunciati ben formati. Poichè gli enunciati ben formati sono un sottoinsieme decidibile di Σ^{∗}, una semplica applicazione del teorema di Post garantisce che entrambi questi insiemi sono decidibili.

11Questo capita ad esempio nella teoria dei gruppi: usando gli assiomi dei gruppi non si riesce a dimostrare nè la legge commutativa nè la sua negazione in quanto esistono sia gruppi commutativi che non.

12Anche qui si può indebolire l’ipotesi: basta che l’insieme degli assiomi sia algoritmicamente enumerabile

Resta da vedere se esistono interessanti teorie coerenti e complete complete. Gödel ha dimostrato che non è possibile avere una teoria coerente e completa nemmeno per quella parte della matematica che si occupa delle proprietà “elementari” (cioè esprimibili al primo ordine) dei numeri naturali. Tuttavia Tarski ha mostrato che esiste una teoria completa per le proprietà elementari dei numeri reali.

4 Funzioni primitive ricorsive

In una delle sue tante formulazioni equivalenti, la tesi di Church afferma che la classe delle funzioni calcolabili coincide con una classe di funzioni introdotta da Kleene, e nota come classe delle “funzioni μ-ricorsive”, o “funzioni ricorsive generali” (che si può dimostrare coincidere con la classe delle funzioni calcolabili su una macchina di Turing). Prima di definire tale classe introdurremo la classe più piccola, ma già molto comprensiva, delle “funzioni ricorsive primitive”. Tali funzioni costituiscono un sottoinsieme dell’insieme delle funzioni numeriche calcolabili. Cominciamo con un esempio. La funzione fattoriale è definita da:

0! = 1,

(n + 1)! = (n + 1) · n!.

Questa definizione è “ricorsiva” in quanto il simbolo della funzione fattoriale compare sia a sinistra che a destra di una delle uguaglianze che lo definiscono. La prima equazione definisce il fattoriale di zero. La seconda mostra come calcolare il fattoriale di n + 1 supponendo di aver già precedentemente calcolato il fattoriale di n.

Questo genere di definizioni, in cui una funzione f viene definita dando il valore di f(0) e definendo f(n + 1) in termini di n ed f(n) (tramite funzioni ausiliarie note), vengono dette “definizioni primitive ricorsive”. Generalizzando al caso di funzioni di più variabili diciamo che una funzione f: N^{n+1} → N si dice ottenuta per ricorsione primitiva da g: N^{n} → N e da h: N^{n+2} → N se per ogni x_{1}, …, x_{n}, y ∈ N,

f(x_{1}, …, x_{n}, 0) = g(x_{1}, …, x_{n}),

f(x_{1}, …, x_{n}, y + 1) = h(x_{1}, …, x_{n}, y, f(x_{1}, …, x_{n}, y)).

Il valore di f(x_{1}, …, x_{n}, 0) è dato dalla prima equazione per qualunque valore dei parametri x_{1}, …, x_{n}, e supponendo di conoscere il valore di f(x_{1}, …, x_{n}, y) possiamo ottenere per mezzo della seconda equazione il valore di f(x_{1}, …, x_{n}, y + 1).

Nel caso senza parametri (n = 0) la funzione g di riduce a una costante k e lo schema di ricursione diventa f(0) = k e f(y + 1) = h(y, f(y)). Nel caso in cui h dipenda solo dal secondo argomento nel senso che h(y, z) = g(z) per una certa g, otteniamo f(y+1) = g(f(y)) dove f(y+1) dipende solo da f(y) e non anche da y. In questo caso f(y) non è niente altro che l’iterazione y volte della funzione g, cioè f(y) = g(g(… g(k)) dove g viene ripetuta y volte e k è il valore iniziale f(0). In presenza di parametri x⃗ = (x_{1}, …, x_{n}) l’iterazione diventa f(x⃗, 0) = g(x⃗) e f(x⃗, y + 1) = g(x⃗, f(x⃗, y)).

Una funzione f: N^{k} → N si dice ottenuta per composizione a partire dalle funzioni g, h_{1}, …, h_{n} se per ogni x_{1}, …, x_{k} ∈ N,

f(x_{1}, …, x_{k}) = g(h_{1}(x_{1}, …, x_{k}), …, h_{n}(x_{1}, …, x_{k})).

Le funzioni primitive ricorsive sono, per definizione, la più piccola classe di funzioni numeriche chiusa per composizione e ricursione primitiva che contiene le seguenti funzioni iniziali:

1) La funzione zero: Z(x) = 0,

2) la funzione successore: S(x) = x + 1,

3) le funzioni proiezione: U_{i}^{n}(x_{1}, …, x_{n}) = x_{i} (assumiamo 1 ≤ i ≤ n). È facile verificare che la somma è primitiva ricorsiva. Infatti x + y può

essere definita iterando y volte il successore a partire da x: x + 0 = x, x + s(y) = s(x + y).

Analogamente il prodotto può essere definito iterando la somma, e l’esponenziale iterando il prodotto.

La funzione predecessore (con la convenzione che il predecessore di zero è zero) è primitiva ricorsiva in quanto può essere definita da p(0) = 0, p(S(x)) = x. Per far rientrare la seconda uguaglianza nello schema definitorio p(S(x)) = h(x, p(x)) basta scegliere come h la funzione U_{1}^{2}.

La funzione “sottrazione con il punto”, che coincide con la sottrazione dove questa fornisce un risultato non negativo ed è zero negli altri casi, è primitiva ricorsiva in quanto può essere definita iterando il predecessore: x −^{·} 0 = x, x −^{·} S(y) = p(x −^{·} y). Analogamente si può definire la “divisione sui naturali” iterando la sottrazione con il punto.

Predicati primitivi ricorsivi

Un insieme P ⊆ N^{k} si dice primitivo ricorsivo se la sua funzione caratteristica χ_{P} (definita da χ_{P} (a⃗) = 0 se a⃗ ∉ P e χ_{P} (a⃗) = 1 se a⃗ ∈ P), è primitiva ricorsiva. L’insieme P ⊆ N^{k} può anche essere pensato come una relazione (o “predicato”) a k-argomenti su N e scriviamo in tal caso P (a_{1}, …, a_{n}) anziché (a_{1}, …, a_{n}) ∈ P.

Non è del tutto banale mostrare che il predicato di uguaglianza x = y è primitivo ricorsivo, e cioè che lo è la funzione χ_{=}: N^{2} → N che vale uno o zero a seconda che il primo argomento sia uguale al secondo. Abbiamo bisogno di alcuni risultati preliminari. Innanzitutto il predicato di uguaglianza a zero “x = 0” è primitivo ricorsivo in quanto la sua funzione caratteristica χ_{=0} può essere definita da: χ_{=0}(0) = 1, χ_{=0}(S(x)) = 0. La disuguaglianza x ≤ y si può esprimere dicendo che x −^{·} y è uguale a zero. Ne segue che la relazione ≤ è primitiva ricorsiva in quanto la sua funzione caratteristica si ottiene componendo la funzione differenza con la funzione caratteristica del predicato di uguaglianza a zero. Definiamo x ≥ y come y ≤ x. Anche ≥ è una relazione primitiva ricorsiva poiché la sua funzione caratteristica può essere definita dalla funzione caratteristica di ≤ e dalle proiezioni U_{1}^{2} e U_{2}^{2} che opportunamente composte ci permettono di permutare le variabili: χ_{≥}(x, y) = χ_{≤}(U_{2}^{2}(x, y), U_{1}^{2}(x, y)). Per mostrare che il predicato di uguaglianza è primitivo ricorsivo esprimiamo x = y come la congiunzione di x ≤ y e x ≥ y. Passando alle funzioni caratteristiche la congiunzione diventa il prodotto e otteniamo: χ_{=}(x, y) = χ_{≤}(x, y)·χ_{≥}(y, x), da cui la nostra tesi.

Se P ⊂ N^{n} è un predicato primitivo ricorsivo e f: N^{k} → N è una funzione primitiva ricorsiva, per composizione l’insieme {(x_{1}, …, x_{k}, y_{1}, …, y_{n−1}) | P (g(x_{1}, …, x_{k}), y_{1}, …, y_{n−1})} è primitivo ricorsivo. In particolare prendendo come P il predicato di uguaglianza, vediamo che se f: N^{k} → N è una funzione primitiva ricorsiva il suo grafico Grafo(f) = {(x_{1}, …, x_{k}, y) | f(x_{1}, …, x_{k}) = y} è un insieme primitivo ricorsivo.

Il viceversa non è però vero: se una funzione f: N^{k} → N ha come grafico un insieme primitivo ricorsivo P ⊂ N^{k+1}, non è detto che f sia primitiva ricorsiva. Vedremo però che se f oltre ad avere un grafo primitivo ricorsivo è maggiorata da una funzione primitiva ricorsiva, allora è essa stessa primitiva ricorsiva.

Connettivi booleani e quantificatori limitati

Proposizione 4.1 I predicati primitivi ricorsivi sono chiusi per connettivi booleani.

Dim. La funzione caratteristica della congiunzione di due predicati è il prodotto delle rispettive funzioni caratteristiche. La funzione caratteristica della negazione di un predicato si ottiene componendo la funzione 1 −^{·} x con la funzione caratteristica del predicato stesso. Gli altri connettivi si ottengono dalla congiunzione e dalla negazione. QED

Per la proposizione appena dimostrata i sottoinsiemi primitivi ricorsivi di N^{k} costituiscono un’algebra di Boole, ovvero sono chiusi per intersezioni finite, unioni finite e complementi.

In generale i predicati primitivi ricorsivi non sono chiusi rispetto ai quantificatori ∀x ed ∃x. Se {(x, y⃗) | P (x, y⃗)} è primitivo ricorsivo, non è detto che {y⃗ | ∀xP (x, y⃗)} e {y⃗ | ∃xP (x, y⃗)} siano primitivi ricorsivi. Questo non dovrebbe stupire in quanto mentre si ha sempre un metodo finito per stabilire se un predicato primitivo ricorsivo è verificato per un dato valore degli argomenti, non esiste in generale un criterio finito per stabilire se un dato y⃗ verifica ∀xP (x, y⃗) o ∃xP (x, y⃗). Il seguente teorema mostra che la situazione cambia se limitiamo i quantificatori in modo che la variabile quantificata vari su un insieme finito.

Teorema 4.2 Se P è un predicato primitivo ricorsivo di n + 1 variabili, allora lo è anche il predicato R definito da R(x_{1}, …, x_{n}, z) ↔ ∀y ≤ zP (x_{1}, …, x_{n}, y). Analogamente con ∃y ≤ z al posto di ∀y ≤ z. In breve, i predicati primitivi ricorsivi sono chiusi per quantificazione limitata.

Dim. Passando alle funzioni caratteristiche il quantificatore universale limitato ∀x ≤ z diventa una produttoria:

χ_{R}(x_{1}, …, x_{n}, z) = Π_{y=0}^{z}χ_{P} (x_{1}, …, x_{n}, y).

Mostriamo dunque che le funzioni primitive ricorsive sono chiuse per produttorie Π_{y=0}^{z}. Sia dunque g una funzione primitiva e consideriamo la funzione f(x⃗, z) = Π_{y=0}^{z}g(x⃗, y). Possiamo dare una definizione primitiva ricorsiva di f nel modo sequente:

f(x⃗, 0) = g(x⃗, 0),

f(x⃗, z + 1) = f(x⃗, z) · g(x⃗, z + 1).

Il caso del quantificatore esistenziale limitato si riconduce al caso del quantificatore universale limitato tramite la negazione: ∃x ≤ tφ ↔ ¬∀x ≤ t¬φ. QED

Corollario 4.3 Il predicato “x è primo” è primitivo ricorsivo.

Dim. x è primo se e solo se ∀u, v ≤ x(x = u · v → u = 1 ∨ v = 1). Basta ora usare il fatto che il predicato di uguaglianza è primitivo ricorsivo, la moltiplicazione è primitiva ricorsiva, e i predicati primitivi ricorsivi sono chiusi per connettivi booleani e quantificazioni limitate. QED

Mostriamo ora che i predicati primitivi ricorsivi sono chiusi ripetto alle definizioni per casi.

Lemma 4.4 Sia P (x⃗) un predicato primitivo ricorsivo e definiamo f(x⃗) = g(x⃗) se P (x⃗), f(x⃗) = h(x⃗) se ¬P (x⃗). Allora se g, h sono funzioni primitive ricorsive, anche f lo è.

Dim. f(x⃗) = χ_{P} (x⃗) · g(x⃗) + χ_{¬P} (x⃗) · h(x⃗). QED

Il lemma precedente si generalizza a più di due casi: basta applicare il lemma ripetutamente. Indicheremo la funzione f del precedente lemma con la notazione:

f(x⃗) = se P (x), allora f(x⃗), altrimenti g(x⃗).

Minimalizzazione limitata

Introduciamo la notazione min x ≤ z.P (x) per indicare il minimo x ≤ z che soddisfa il predicato P (x) se un tale x esiste, e conveniamo che min x ≤ z.P (x) sia uguale a z se tale x non esiste. (Oltre ad x il predicato P può contenere altre variabili che servono come parametri.)

Lemma 4.5 Sia f definita da f(x_{1}, …, x_{k}, z) = min y ≤ z.P (x_{1}, …, x_{n}, y). Se P è un predicato primitivo ricorsivo, allora f è primitiva ricorsiva.

Dim. Possiamo dare una definizione primitiva ricorsiva di f tramite le equazioni:

f(x_{1}, …, x_{n}, 0) = 0,

f(x_{1}, …, x_{n}, z + 1) = se ∃y ≤ zP (x_{1}, …, x_{n}, y), allora f(x_{1}, …, x_{n}, z), altrimenti z + 1. QED

Oltre a minimalizzazioni limitate della forma min y ≤ z.P possiamo ammettere minimalizzazioni della forma min y ≤ g(x⃗, z).P dove g è primitiva ricorsiva: basta comporre con g.

La successione dei primi è primitiva ricorsiva

Sia p(i) l’i + 1-esimo numero primo, cioè p(0) = 2, p(1) = 3, p(2) = 5, p(3) = 7, p(4) = 11, . . ..

Proposizione 4.6 La funzione i ↦ p(i) è primitiva ricorsiva.

Dim. Dato x, per il teorema di Euclide esiste un numero primo q con x < q ≤ x! + 1. (Infatti sia q un divisore primo di x! + 1. Se q fosse minore o uguale a x, allora dividerebbe x!. Ma questa è una contraddizione perchè un numero diverso da 1 non può dividere al tempo stesso x! e x! + 1.) Sia q(x) il minimo numero primo maggiore di x. Poiché possiamo limitare q(x) con x! + 1, la funzione x ↦ q(x) è primitiva ricorsiva in quanto è definibile per minimalizzazione limitata a partire dal predicato primitivo ricorsivo “x è primo” e dalla funzione primitiva ricorsiva x! + 1. Possiamo ora definire in modo primitivo ricorsivo p(0) = 2, p(i + 1) = q(p(i)). QED

Codifica di successioni tramite la scomposizione in primi

Sia p(i) l’i + 1-esimo numero primo. Fissato n ∈ N, la funzione (x_{0}, …, x_{n}) ↦ Π_{i=0}^{n}p(i)^{x_{i}+1} da N^{n+1} a N è iniettiva (per l’unicità della scomposizione in primi) e primitiva ricorsiva. In particolare abbiamo le funzioni iniettive e primitive ricorsive (x, y) ↦ 2^{x+1}3^{y+1} da N^{2} ad N e (x, y, z) ↦ 2^{x+1}3^{y+1}5^{z+1} da N^{3} ad N. Possiamo usare queste funzioni per codificare una coppia, una tripla, e più in generale una successione finita di numeri naturali, con un singolo numero naturale: (a_{0}, a_{1}, …, a_{n}) è codificata da Π_{i=0}^{n}p(i)^{a_{i}+1} che indichiamo per brevità con ⟨a_{0}, a_{1} …, a_{n+1}⟩. Ad esempio ⟨3, 1, 0⟩ = 2^{4} · 3^{2} · 5^{1} = 360. Conveniamo che il numero 1 codifichi la successione vuota di lunghezza zero.

Una codifica leggermente più semplice si ottiene decrementando tutti gli esponenti di uno, associando ad esempio (3, 1, 0) con 2^{3} · 3^{1} · 5^{0}, ma lo svantaggio è che la tripla (3, 1, 0) avrebbe la stessa codifica della coppia (3, 1).

Si osservi che alcuni numeri, come ad esempio 2^{3} · 5^{7} non codificano alcuna successione. Un numero codifica una successione se e solo se i numeri primi che lo dividono costituiscono un segmento iniziale dei numeri primi (nel senso che se c’è un primo ci devono essere quelli minori di lui).

Proposizione 4.7 1. L’insieme dei numeri che codificano una successione è primitivo ricorsivo.

2. Esiste una funzione Lunghezza: N → N primitiva ricorsiva tale che se s codifica una successione di lunghezza n, allora Lunghezza(s) = n (non ha importanza quale valore abbia la funzione su argomenti che non codificano una successione).

3. Esiste una funzione Estrai: N^{2} → N primitiva ricorsiva, tale che se s codifica una successione di lunghezza n e i < n allora Estrai(i, s) è l’(i + 1)-esimo elemento della successione.

4. Esiste una funzione Cat: N^{2} → N che dati come argomenti due numeri che codificano due successioni fornisce come valore il numero che codifica la concatenazione delle due successioni: Cat(⟨a_{1}, …, a_{n}⟩, ⟨b_{1}, …, b_{m}⟩) = ⟨a_{1}, …, a_{n}, b_{1}, …, b_{m}⟩. Conveniamo che una successione non venga alterata concatenandola con la successione vuota.

Dim. 1. Il predicato x|y (x divide y) può essere espresso con quantificatori limitati dalla formula ∃z ≤ x(x ⊙ z = y). Ora s codifica una successione se e solo se ∀i ≤ s(p(i + 1) | s → p(i) | s). Ne consegue “s codifica una successione” è esprimibile con quantificatori limitati a partire da predicati e funzioni primitive ricorsive, ed è pertanto un predicato primitivo ricorsivo.

2. Se una successione è codificata da s, la sua lunghezza è il minimo i tale che p(i) non divide s. Possiamo maggiorare tale i con s, e quindi definire la funzione lunghezza per minimalizzazione limitata.

3. Possiamo definire per minimalizzazione limitata Estrai(i, s) come il minimo a ≤ s tale che p(i)^{a+2} non divide s.

4. Date due successioni codificate da s e r, la loro concatenazione è codificata dal minimo t tale che ∀i < Lunghezza(s) Estrai(i, t) = Estrai(i, s) e ∀j < Lunghezza(r) Estrai(Lunghezza(s) + j, t) = Estrai(j, r). Per concludere basta dare una limitazione primitiva ricorsiva a t. A tal fine osserviamo che una successione di lunghezza m è codificata da un numero ≤ p(m)^{m·N} dove N è il massimo degli elementi della successione. Ne segue che possiamo limitare t con p(T)^{T ·T} dove T = s + r. QED

Ricursione sul decorso dei valori

Teorema 4.8 Data una funzione h: N^{2} → N sia f: N → N l’unica funzione tale che per ogni x, f(x) = h(x, ⟨f(0), …, f(x − 1)⟩). In particolare f(0) = h(0, ⟨⟩) dove ⟨⟩ = 1 codifica la succesione vuota. Se h è primitiva ricorsiva, anche f lo è. Un risultato analogo vale per funzioni di più argomenti alcuni dei quali giocano il ruolo di parametri. In questo caso l’equazione che definisce f diventa: f(y⃗, x) = h(y⃗, x, ⟨f(y⃗, 0), …, f(y⃗, x − 1)⟩)

Dim. Per semplicità di notazione consideriamo il caso senza parametri, e introduciamo la funzione ausiliaria definita da:

f^{#}(x) = ⟨f(0), …, f(x)⟩ = π_{i≤x}p(i)^{f(i)+1}

La funzione f si ottiene in modo primitivo ricorsivo da f^{#} estraendo l’ultima componente, basta quindi mostrare che f^{#} è primitiva ricorsiva. Sia a = ⟨f(0)⟩). Valgono le identità f^{#}(0) = a e f^{#}(x + 1) = Cat(f^{#}(x), f(x + 1)) = Cat(f^{#}(x), h(x + 1, f^{#}(x)). Ne consegue che f^{#} è primitiva ricorsiva. QED

Usando la ricursione sul decorso dei valori si possono ottenere funzioni che dipendono da un qualsiasi numero di valori precedenti scelti in modo primitivo ricorsivo.

5 Funzioni ricorsive generali

Dato un predicato P ⊂ N^{k}, possiamo definire una funzione parziale f: N^{k} → N stipulando che per ogni x ∈ N^{k}, f(x) = min yP (x, y) se tale y esiste, e f(x) è indefinita altrimenti. Se P è un predicato algoritmicamente calcolabile, f è una funzione calcolabile parziale: infatti per calcolare f(x) basta calcolare in sequenza i valori di verità di P (x, 0), P (x, 1), P (x, 2), … (usando un algoritmo per calcolare P), fermandosi se si trova un y tale che vale P (x, y), e ponendo in tal caso f(x) = y. Se un tale y non esiste il calcolo dei successivi valori del predicato va avanti all’infinito.

L’operatore di minimalizzazione appena definito porta da predicati (che possiamo identificare con le funzioni totali a valori 0, 1) a funzioni parziali. È possibile estendere tale operatore ad un operatore μ da funzioni parziali a funzioni parziali nel modo seguente. Data una funzione parziale g: N^{k+1} ⇝ N definiamo una funzione parziale f: N^{k} ⇝ N, f(x⃗) = μyg(x⃗, y) = 1 nel modo seguente (il valore 1 è stato scelto perchè, nel caso delle funzioni caratteristiche dei predicati, 1 corrisponde al valore “vero”):

f(x⃗) = y se g(x⃗, y) = 1 ∧ ∀i < y[g(x⃗, i) ≠ 1 ∧ g(x⃗, i) ≠⊥].

f(x⃗) =⊥ se non esiste alcun y tale che g(x⃗, y) = 1 ∧ ∀i < y g(x⃗, i) ≠ 1 e g(x⃗, i) ≠⊥.

La funzione f così definita si dice ottenuta per minimalizzazione da g. Dimostriamo ora che se g è una funzione calcolabile parziale, allora f(x⃗) = μy.g(x⃗, y) = 1 è una funzione calcolabile parziale. Per trovare il valore di f(x⃗) possiamo calcolare in sequenza g(x⃗, 0), g(x⃗, 1), g(x⃗, 2), … (usando l’algoritmo per g) fermandoci se e quando troviamo un y tale che g(x⃗, y) = 1. Tale y se esiste è il valore di f(x⃗). Si noti che questo algoritmo prima di iniziare a calcolare g(x⃗, y) aspetta che il calcolo di g(x⃗, 0), g(x⃗, 1), …, g(x⃗, y− 1) sia stato portato a termine. Quindi l’algoritmo non termina esattamente in quei casi in cui abbiamo posto f(x⃗) =⊥.

Abbiamo così dimostrato:

Proposizione 5.1 L’operatore di minimalizzazione μ porta da funzioni parziali calcolabili a funzioni parziali calcolabili.

Un simile risultato è vero anche per gli operatori di composizione e ricursione primitiva se facciamo alcune ovvie convenzioni sui domini di definitione delle composizioni di funzioni parziali e delle funzioni ottenute per ricursione primitiva da funzioni parziali. Per quanto riguarda la composizione f(x⃗) = g(h_{1}(x⃗), …, h_{k}(x⃗)) conveniamo che f(x⃗) è definita (per un dato x⃗) se lo sono tutte le h_{i}(x⃗) e se inoltre g è definita sui valori delle h_{i}(x⃗). Questa non è l’unica convenzione possibile ma è la più semplice. Con questa convenzione una funzione composta della forma f(x) = U_{1}^{2}(h_{1}(x), h_{2}(x)) risulta indefinita ogniqualvolta h_{2}(x) è indefinita, anche se U_{1}^{2}: N^{2} → N dipende solo dal primo argomento. Per la ricursione primitiva si fa una convenzione analoga. L’idea generale è che

una funzione parziale f: N^{k} → N ∪ {⊥} si estende in modo naturale ad una funzione f: (N∪{⊥})^{k} → N∪{⊥} usando la convenzione che il risultato è ⊥ se uno degli argomenti è uguale a ⊥.

Alla luce di questa convenzione consideriamo di nuovo la ricursione primitiva

f(x⃗, 0) = g(x⃗),

f(x⃗, y + 1) = h(x⃗, y, f(x⃗, y))

dove però ora tutte le uguaglianze vanno considerate come uguaglianze tra funzioni da (N ∪ {⊥})^{k} a N ∪ {⊥}. Ne segue che se f(x⃗, y) =⊥, allora f(x⃗, y + 1) = h(x⃗, y, ⊥) =⊥. Quindi in generale se f(x⃗, i) =⊥, allora ∀kf(x⃗, i + k) =⊥. È facile verificare che:

Proposizione 5.2 Se g ed h sono funzioni parziali calcolabili, e se f è definita per ricursione primitiva da g ed h, anche f è parziale calcolabile.

Dim. Per calcolare b = f(x⃗, y) si calcolino in successione b_{0} = g(x⃗), b_{1} = h(x⃗, 1, b_{0}), b_{2} = h(x⃗, 2, b_{1}), b_{3} = h(x⃗, 3, b_{2}), etc. (usando gli algoritmi per calcolare g ed h), fino a che si arriva a b = b_{y} = f(x⃗, b_{y−1}). Se uno dei b_{i} con i < y non è definito il calcolo non termina mai in accordo con il fatto che in questi casi f(x⃗, y) =⊥. QED

Definizione 5.3 Le funzioni μ-ricorsive sono la più piccola classe di funzioni numeriche parziali contenente le funzioni primitive ricorsive iniziali e chiusa per composizione, ricursione primitiva e minimalizzazione (come operatori da funzioni parziali a funzioni parziali).

Il teorema di forma normale di Kleene stabilisce che ogni funzione μricorsiva f: N^{k} ⇝ N si può scrivere nella forma f(x⃗) = U(min yP (x⃗, y)), dove U è una funzione primitiva ricorsiva e P è un predicato primitivo ricorsivo. In particolare questo risultato dice che f si può definire usando una sola volta l’operatore di minimalizzazione.

Si può dimostrare che le funzioni μ-ricorsive coincidono con le funzioni Turing calcolabili parziali. Useremo il termine funzioni ricorsive parziali per indicare questa comune classe di funzioni. La tesi di Church afferma che una funzione parziale f: N^{k} ⇝ N è calcolabile se e solo se è parziale ricorsiva.

Una funzione ricorsiva generale che risulta definita per ogni valore dei suoi argomenti viene detta ricorsiva totale.

6 Insiemi ricorsivi e ricorsivamente enumerabili

Un insieme A ⊆ N^{k} è ricorsivo se la sua funzione caratteristica è parziale ricorsiva (ovviamente essendo una funzione caratteristica è sicuramente totale).

Un insieme A ⊆ N^{k} è semi-ricorsivo se è il dominio di una funzione parziale ricorsiva f: N^{k} ⇝ N.

Un insieme A ⊆ N è ricorsivamente enumerabile se è l’immagine di una funzione parziale ricorsiva f: N ⇝ N. Nel caso di sottoinsiemi di N^{k} possiamo adoperare una codifica ricorsiva totale biunivoca c: N^{k} → N per ricondurci al caso di sottoinsiemi di N. Diremo cioè che A ⊆ N^{k} è ricorsivamente enumerabile se {c(x_{1}, …, x_{n}) | (x_{1}, …, x_{n}) ∈ A} è ricorsivamente enumerabile.

Si può dimostrare che ogni insieme ricorsivo è semi-ricorsivo e che un sottoinsieme di N^{k} è ricorsivamente enumerabile se e solo se è semi-ricorsivo.

Se assumiamo la tesi di Church, decidibile = ricorsivo, e semidecidibile = semi-ricorsivo (= algoritmicamente enumerabile = ricorsivamente enumerabile).

7 Aritmetizzazione della sintassi e predicato di dimostrabilità

Faremo uso dei risultati sulla codifica delle successioni sviluppate nella sezione sulle funzioni primitive ricorsive.

Sia L un linguaggio del primo ordine con un numero finito di simboli di funzione, relazione e costante e associamo ad ogni tale simbolo s un numero naturale #(s). Associamo poi ai simboli logici ¬, ∨, ∧, →, ∀, ∃, = altri numeri naturali #(¬), #(∨), #(∧), #(→), #(∀), #(∃), #(=) diversi tra loro. Consideriamo infine un nuovo numero naturale che indichiamo con #(v).

Definizione 7.1 Associamo ad ogni L-termine t un numero naturale ⌈t⌉ nel modo seguente.

1. Associamo alla variabile v_{i} il numero ⌈v_{i}⌉ = ⟨#(v), i⟩.

2. Se c è un simbolo di costante di L, ⌈c⌉ = ⟨#(c)⟩.

3. Se f è un simbolo di funzione n-aria di L, e t è un L-termine della forma f(t_{1}, …, t_{n}), ⌈t⌉ = ⟨⌈f⌉, ⌈t_{1}⌉, …, ⌈t_{n}⌉⟩.

Definizione 7.2 Associamo ad ogni L-formula φ un numero naturale ⌈φ⌉ nel modo seguente.

1. Se t_{1}, t_{2} sono L-termini, ⌈t_{1} = t_{2}⌉ = ⟨#(=), ⌈t_{1}⌉, ⌈t_{2}⌉⟩.

2. Se R è un simbolo di relazione n-aria di L, e t_{1}, …, t_{n} sono L-termini, allora ⌈R(t_{1}, …, t_{n})⌉ = ⟨⌈R⌉, ⌈t_{1}⌉, …, ⌈t_{n}⌉⟩.

3. Se α, β sono L-formule, allora ⌈¬α⌉ = ⟨⌈¬⌉, ⌈α⌉⟩, ⌈(α ∨ β)⌉ = ⟨⌈∨⌉, ⌈α⌉, ⌈β⌉⟩, ⌈(α ∧ β)⌉ = ⟨⌈∧⌉, ⌈α⌉, ⌈β⌉⟩, ⌈(α → β)⌉ = ⟨⌈→ ⌉, ⌈α⌉, ⌈β⌉⟩, ⌈∀v_{i}α⌉ = ⟨⌈∀⌉, ⌈v_{i}⌉, ⌈α⌉⟩, ⌈∃v_{i}α⌉ = ⟨⌈∃⌉, ⌈v_{i}⌉, ⌈α⌉⟩.

Lemma 7.3 L’insieme {⌈t⌉ | t è un L-termine } è primitivo ricorsivo.

Dim. Supponiamo per semplicità che il linguaggio L consista di un simbolo di funzione binaria f, un simbolo di constante c, e un simbolo di relazione binaria R.

Abbiamo: t è un L-termine se e solo se t è la costante c oppure t è una variabile v_{i} è una variabile, oppure t = f(t_{1}, t_{2}) dove t_{1} e t_{2} sono L-termini.

Quindi:

n codifica un L-termine se e solo se n = ⌈c⌉, oppure esiste i < n tale che n = ⟨⌈v⌉, i⟩, oppure esistono u, v < n tali che n = ⟨⌈f⌉, u, v⟩ e u, v codificano L-termini.

In questo modo abbiamo definito il valore di verità di “n codifica un L-termine” in termini dei valori di verità degli enunciati “u codifica un Ltermine”, dove u < n, usando funzioni ausiliarie primitive ricorsive. Da ciò segue facilmente che l’insieme delle codifiche degli L-termini è primitivo ricorsivo. Per i dettagli si può procedere nel modo seguente. Dobbiamo mostrare che la funzione caratteristica degli L-termini, ovvero la funzione T: N → N che vale 1 sulle codifiche di L-termini e 0 altrimenti, è primitiva ricorsiva. A tal fine mostreremo che T può essere definita per ricursione sul decorso dei valori, ovvero T (n) = h(n, ⟨T (0), …, T (n − 1)⟩) per una opportuna funzione primitiva ricorsiva h: N^{2} → N. Basterà definire h nel modo seguente:

i) h(n, s) = 1 se n = ⌈c⌉ oppure ∃i < n: n = ⟨⌈v⌉, i⟩ oppure “s codifica una successione di lunghezza n” e ∃u, v < n: n = ⟨⌈f⌉, u, v⟩ e Estrai(u, s) = 1 e Estrai(v, s) = 1;

ii) h(n, s) = 0 altrimenti.

La funzione h così definita è primitiva ricorsiva in quanto definita per casi a partire da predicati primitivi ricorsivi. QED

Lemma 7.4 L’insieme {⌈ϕ⌉ | ϕ è una L-formula } è primitivo ricorsivo.

Dim. La dimostrazione è del tutto simile a quella del precedente lemma, e si basa sul fatto che possiamo definire il valore di verità dell’enunciato “n codifica una L-formula” in termini del valore di verità degli enunciati “a codifica una L-formula”, dove a < n, usando funzioni ausiliarie primitive ricorsive (tra cui la funzione caratteristica degli L-termini).

Supponiamo per semplicità che L contenga un simbolo di relazione binaria R e nessun altro simbolo di relazione. Abbiamo:

“n codifica una L-formula” se e solo se ∃u, v < n tali che “u, v codificano L-termini” e (n = ⟨#(=), u, v⟩ o n = ⟨#(R), u, v⟩), oppure ∃a, b < n tali che “a, b codificano L-formule” e (n = ⟨#(¬), a⟩ o n = ⟨#(∨), a, b⟩ o n = ⟨#(∧), a, b⟩ o n = ⟨#(→ ), a, b⟩ o ∃i < n: n = ⟨#(∀), ⟨#(v), i⟩, a⟩ o ∃i < n: n = ⟨#(∃), ⟨#(v), i⟩, a⟩).

Possiamo ora procedere come nel lemma precedente ottenendo una definizione della funzione caratteristica delle L-formule per ricursione sul decorso dei valori. QED

Lemma 7.5 Esiste una funzione primitiva ricorsiva sub: N^{3} → N tale che sub(⌈ϕ⌉, i, ⌈t⌉) = ⌈ϕ[t/v_{i}]⌉ per ogni L-formula ϕ e ogni L-termine t. (Ricordiamo che ϕ[t/v_{i}] è il risultato della sostituzione in ϕ di tutte le occorrenze libere di v_{i} con il termine t.)

Dim. Basterà fare in modo che sub soddisfi le clausole che seguono, dove f è un simbolo di funzione n-aria di L, R è un simbolo di relazione n-aria di L, t_{1}, …, t_{n} sono L-termine, α, β sono L-formule. (Dalle clausole segue che sub effettua la sostituzione di v_{i} con t non solo all’interno di una formula ma anche anche all’interno di un termine.)

sub(⌈v_{i}⌉, , i, y) = y
sub(⌈v_{i}⌉, j, y) = ⌈v_{i}⌉ se i ≠ j
sub(⌈f(t_{1}, …, t_{n})⌉, i, y) = ⟨⌈f⌉, sub(⌈t_{1}⌉, i, y), …, sub(⌈t_{n}⌉, i, y)⟩
sub(⌈R(t_{1}, …, t_{n})⌉, i, y) = ⟨⌈R⌉, sub(⌈t_{1}⌉, i, y), …, sub(⌈t_{n}⌉, i, y)⟩
sub(⌈¬α⌉, i, y) = ⟨⌈¬⌉, sub(⌈α⌉, i, y)⟩
sub(⌈(α ∨ β)⌉, i, y) = ⟨⌈∨⌉, sub(⌈α⌉, i, y), sub(⌈β⌉, i, y)⟩
sub(⌈(α ∧ β)⌉, i, y) = ⟨⌈∧⌉, sub(⌈α⌉, i, y), sub(⌈β⌉, i, y)⟩
sub(⌈(α → β)⌉, i, y) = ⟨⌈→⌉, sub(⌈α⌉, i, y), sub(⌈β⌉, i, y)⟩
sub(⌈∀v_{i}α⌉, i, y) = ⟨⌈∀⌉, ⌈v_{i}⌉, sub(⌈α⌉, i, y)⟩ se i ≠ j
sub(⌈∀v_{i}α⌉, i, y) = ⌈∀v_{i}α⌉
sub(⌈∃v_{i}α⌉, i, y) = ⟨⌈∃⌉, ⌈v_{i}⌉, sub(⌈α⌉, i, y)⟩ se i ≠ j
sub(⌈∃v_{i}α⌉, i, y) = ⌈∃v_{i}α⌉

È possibile dare una definizione di sub per ricursione sul decorso dei valori della forma sub(n, i, y) = h(n, i, ⟨sub(0, i, y), …, sub(n−1, i, y)⟩) per una opportuna funzione primitiva ricorsiva h(n, s). La funzione h è definita per casi (tanti casi quante le clausole sopra date). A titolo di esempio diamo il caso relativo a n = ⌈(α ∧ β)⌉:

se ∃a, b < n tali che n = ⟨⌈∧⌉, a, b⟩, allora h(n, i, s) =
⟨⌈∧⌉, Estrai(a, s), Estrai(b, s)⟩.

QED

Osservazione 7.6 È possibile dare una definizione più semplice di sub se anzichè richiedere sub(⌈ϕ⌉, i, ⌈t⌉) = ⌈ϕ[t/v_{i}]⌉ richiediamo solamente che sub(⌈ϕ⌉, i, ⌈t⌉) sia la codifica non della formula ϕ[t/v_{i}] ma della formula a lei equivalente ∀v_{i}(t = v_{i} → ϕ). Questo è in effetti l’approccio che abbiamo seguito a lezione.

Corollario 7.7 I seguenti insiemi sono primitivi ricorsivi.

1. L’insieme delle coppie (⌈ϕ⌉, i) tali che ϕ è una L-formula e v_{i} occorre libera in ϕ.

2. L’insieme dei numeri di Gödel delle L-formule chiuse.

3. L’insieme delle coppie (⌈t⌉, i) tali che t è un L-termine e la variabile v_{i} occorre in t.

4. L’insieme delle terne (⌈ϕ⌉, i, ⌈t⌉) tali che ϕ è una L-formula, t è un L-termine, e t è sostituibile per v_{i} in ϕ.

Dim. Sia ϕ una L-formula. Chiaramente una variabile v_{j} con un indice j maggiore del numero di Gödel di ϕ non occorre in ϕ (nè libera nè legata), e quindi se la sostituiamo al posto di una variabile che occorre libera in ϕ otteniamo una formula contenente v_{j} e pertanto diversa da ϕ. Ne segue che, ponendo j = ⌈ϕ⌉ + 1, v_{i} occorre libera in ϕ, se e solo se ϕ ≠ ϕ[v_{j}/v_{i}]. Quindi l’insieme del punto 1 è definibile in modo primitivo ricorsivo come l’insieme delle coppie (a, i) tali che a codifica una L-formula e sub(a, i, ⟨⌈v⌉, a + 1⟩) ≠ a. Per il punto 2. basta osservare che a codifica una formula chiusa se per ogni i ≤ a si ha sub(a, i, ⟨⌈v⌉, a + 1⟩) = a. Il punto 3. è analogo al punto 1. Per l’ultimo punto osserviamo che t è sostituibile al posto di v_{i} in ϕ se e solo se ogni variabile v_{j} occorrente in t è sostituibile al posto di v_{i} in ϕ, e questo avviene se e solo se ϕ[v_{j}/v_{i}][v_{i}/v_{j}] = ϕ[v_{i}/v_{j}], ovvero sostituendo le occorrenze libere di v_{i} con v_{j}, e poi quelle di v_{j} con v_{i} nella formula risultante, si ottiene lo stesso risultato che sostituendo direttamente quelle di v_{j} con v_{i}. Questa condizione è esprimibile in modo primitivo ricorsivo tramite la funzione sub. QED Teorema 7.8 Sia T una L-teoria tale che l’insieme {⌈ϕ⌉ | ϕ è un assioma di T } è primitivo ricorsivo. Allora esiste una relazione binaria primitiva ricorsiva Prov_{T} tale che ϕ è un teorema di T se e solo se ∃x ∈ N: Prov_{T} (x, ⌈ϕ⌉)}.

Dim. Il fatto che una data formula sia un teorema di T non dipende dal sistema dimostrativo scelto (a condizione di considerare solo sistemi dimostrativi per i quali vale il teorema di completezza di Gödel). Tuttavia per procedere nella nostra dimostrazione dobbiamo fissare uno specifico sistema dimostrativo, in quanto il predicato Prov_{T} dipenderà da questa scelta avendosi:

Prov_{T} (x, ⌈ϕ⌉) se e solo se x codifica una dimostrazione di ϕ

Per fissare le idee consideriamo il sistema dimostrativo nello stile Hilbert-Frege descritto nell’articolo di Barwise nell’Handbook of Mathematical Logic. Una dimostrazione consisterà allora di una successione finita di formule di cui ognuna è un assioma logico, un assioma di T, oppure segue da formule precedenti tramite opportune regole di inferenza. Le regole sono le seguenti: da A e A → B posso dedurre B. Da A → B(x) posso dedurre A → ∀xB(x) a condizione che x non sia libera in A. Da B(x) → A posso dedurre ∃xB(x) → A a condizione che x non sia libera in A. Possiamo dedurre senza bisogno di alcuna premessa tutte le tautologie e gli assiomi dell’uguaglianza (riflessività, simmetria, transitività, e sostitutività espressa dallo schema: x = y∧ϕ(x) → ϕ(y)). Se t è un termine sostituibile al posto di x in A, posso dedurre senza premesse le formule della forma ∀xA(x) → A(t) (cioè ∀xA → A[t/x]) e quelle della forma A(t) → ∃xA(x).

Definiamo Prov_{T} (x, n) in modo primitivo ricorsivo come congiunzione delle seguenti condizioni:

1. Esiste k ≤ x tale che x codifica una successione di lunghezza k e Estrai(k, x) = n.

2. Per ogni i < Lunghezza(x) Estrai(i, x) codifica una formula.

3. Per ogni i < Lunghezza(x) vale uno dei casi seguenti casi:

(a) ∃a, i, s < n tale che “a codifica una L-formula”, “s codifica un L-termine sostituibile al posto di v_{i} nella formula codificata da a”, e n = ⟨#(∀)⟨#(v), i⟩, ⟨#(→), a, sub(a, i, s)⟩⟩.

(b) ∃j, l < i ed esistono a, b ≤ x tali che a, b codificano formule, e Estrai(j, x) = ⟨#(→), a, b⟩ e Estrai(l, x) = a e Estrai(i, x) = b.

(c) Estrai(i, x) codifica un assioma di T.

(d) Gli altri casi sono simili e lasciati al lettore.

QED

8 Ogni funzione calcolabile è rappresentabile nella teoria Q di Robinson

Ci proponiamo di dimostrare che se f: N^{k} ⇝ N è una funzione ricorsiva generale, allora il grafico di f è definibile nella struttura (N, 0, 1, S, +, ·) da una formula del primo ordine ϕ(x⃗, y) in k + 1 variabili libere. Dimostreremo in realtà il risultato più forte che il grafico di f è binumerabile nella teoria Q di Robinson (vedi Teorema ??).

La teoria Q di Robinson assiomatizza alcune delle proprietà dei numeri naturali, ma a differenza della aritmetica di Peano non ha alcun assioma di induzione. Come conseguenza Q è una teoria molto debole. Gli assiomi di Q sono i seguenti (formulati in un linguaggio che contiene i simboli 0, S, +, · per zero, successore, somma e prodotto):

Q1. S(x) = S(y) → x = y,

Q2. 0 ≠ S(x),

Q3. x ≠ 0 → ∃y(x = S(y)),

Q4. x + 0 = x,

Q5. x + S(y) = S(x + y),

Q6. x · 0 = 0,

Q7. x · S(y) = x · y + x.

Chiaramente le proprietà espresse dagli assiomi di Q sono verificate nei numeri naturali con le solite operazioni aritmetiche di zero, successore, somma e prodotto. Quindi N è un modello di Q (e scriviamo N ⊧ Q), ma non è certo l’unico modello. Gli assiomi di Q sono infatti troppo deboli per caratterizzare N.

Un’altro modello si può ottenere nel modo seguente. Sia Z[x] l’anello dei polinomi in una variabile a coefficienti in Z. Definiamo un ordine totale su Z[x] stabilendo che un polinomio p(x) ∈ Z[x] è positivo se lim_{x→∞} p(x) > 0 13. Sia Z[x]^{+} l’insieme dei polinomi non-negativi dell’anello Z[x]: p(x) ∈ Z[x]^{+} se e solo se p(x) ≥ 0 (cioè p(x) > 0 o p(x) = 0). Consideriamo le solite operazioni di somma e prodotto tra polinomi. È facile verificare che i polinomi non-negativi sono chiusi per somme e prodotti ed quindi anche per l’operazione successore (sommare il polinomio costante 1), inoltre Z[x]^{+} con queste operazioni verifica tutti gli assiomi di Q. Ad esempio il secondo assioma è soddisfatto in quanto il polinomio costante zero non è il successore di alcun polinomio non-negativo.

L’interesse per la teoria Q è motivato dal fatto che Q è in grado di verificare la correttezza o la falsità di ogni “calcolo numerico”. Ad esempio Q dimostra tutti i casi particolari della legge di commutatività della moltiplicazione: 2 · 3 = 3 · 2, 3 · 7 = 7 · 3, etc. Tuttavia, a causa della mancanza di assiomi di induzione, Q non è in grado di “generalizzare” e dimostrare la validità universale della legge commutativa: ∀x, y(x · y = y · x). Vedremo però che Q dimostra ∀x, y ≤ 10(x · y = y · x). Più in generale Q è in grado di stabilire la verità o la falsità di qualsiasi formula aritmetica che contenga solo quantificatori “limitati”. Il motivo è che la verità di tali formule si riconduce al controllo di un numero finito di casi particolari.

Alcune formule dimostrabili in Q

Ogni termine chiuso t di Q interpretato in N denota un numero naturale. Ad esempio [S(0) + S(0)]^{N} = 2. Se n ∈ N il termine S(S(S(… S(0)))) (n volte S) viene detto il numerale di n e indicato con \overline{n}.

Lemma 8.1 ∀a, b, c ∈ N, se a + b = c, allora Q ⊢ \overline{a} + \overline{b} = \overline{c}.

Dim. Per induzione su b (l’induzione avviene nella metateoria non all’interno di Q, che peraltro non ha assiomi di induzione).

Se b = 0 basta usare il fatto che Q ⊢ ∀x(x + 0 = x).

Se b > 0 e a + b = c, allora a + (b − 1) = c − 1 e per ipotesi induttiva Q ⊢ \overline{a} + \overline{b − 1} = \overline{c − 1}. Inoltre Q ⊢ x + S(y) = S(x + y). Prendendo x = \overline{a}, y = \overline{b − 1}, otteniamo Q ⊢ \overline{a} + \overline{b} = \overline{c}. QED

Lemma 8.2 ∀a, b, c ∈ N, se a · b = c, allora Q ⊢ \overline{a} · \overline{b} = \overline{c}.

13Equivalentemente un polinomio a_{0} + a_{1}x + … + a_{n}x^{n}, con a_{n} ≠ 0, è positivo se e solo se a_{n} > 0

Dim. Per induzione su b (nella metateoria) usando il lemma precedente. Per la base dell’induzione usiamo il fatto che Q ⊢ ∀x(x · 0 = 0). Per il passo induttivo usiamo Q ⊢ x · S(y) = x · y + x. QED

Corollario 8.3 Per ogni termine chiuso t di L(Q) esiste n ∈ N tale che Q ⊢ t = \overline{n}.

Dim. Per induzione sulla lunghezza di t.

Se t è la costante 0, allora prendiamo n = 0.

Se t = t_{1} + t_{2}, allora per ipotesi induttiva esistono a, b ∈ N tali che Q ⊢ t_{1} = \overline{a} e Q ⊢ t_{2} = \overline{b}. Sia c = a+b. Per i lemmi precedenti Q ⊢ \overline{a}+\overline{b} = \overline{c}. Ne segue che Q ⊢ t_{1} + t_{2} = \overline{c}, cioè Q ⊢ t = \overline{c}.

Se t = t_{1} · t_{2} procediamo analogamente. QED

Abbiamo così dimostrato che Q effettua correttamente il calcolo della addizione e moltiplicazione di numeri naturali ed è in grado di dimostrare che ogni termine chiuso corrisponde ad un numero naturale.

Lemma 8.4 ∀a, b ∈ N, se a ≠ b, allora Q ⊢ \overline{a} ≠ \overline{b}.

Dim. Possiamo assumere a < b. La dimostrazione è per induzione su a. Se 0 = a < b, il risultato segue dal fatto che Q ⊢ ∀x.0 ≠ S(x). Se 0 < a < b, allora a−1 ≠ b−1 e per ipotesi induttiva Q ⊢ \overline{a − 1} ≠ \overline{b − 1}.

Inoltre Q ⊢ ∀x, y.S(x) = S(y) → x = y, e quindi Q ⊢ ∀x, y.x ≠ y → S(x) ≠ S(y). Prendendo x = \overline{a − 1}, y = \overline{b − 1} otteniamo Q ⊢ \overline{a} ≠ \overline{b}. QED

Lemma 8.5 ∀a, b ∈ N, se a = b, allora Q ⊢ \overline{a} = \overline{b}.

Dim. Segue da Q ⊢ ∀x.x = x. QED

Lemma 8.6 Se t_{1} e t_{2} sono termini chiusi di L(Q) allora Q ⊢ t_{1} = t_{2} oppure Q ⊢ t_{1} ≠ t_{2}.

Dim. Siano a, b ∈ N tali che Q ⊢ t_{1} = \overline{a} e Q ⊢ t_{2} = \overline{b}. Se a ≠ b, allora Q ⊢ \overline{a} ≠ \overline{b} e quindi Q ⊢ t_{1} ≠ t_{2}. Analogamente se a = b, Q ⊢ t_{1} = t_{2}. QED

Numeri non-standard

Dato un modello M di Q consideriamo il sottoinsieme M′ ⊆ M di quegli elementi di M che sono l’interpretazione di qualche numerale \overline{n}, ovvero M′ = \{x ∈ M | ∃n ∈ N.x = \overline{n}^{M}\}.

Gli elementi di M′ sono chiamati numeri standard di M, mentre gli elementi di M − M′ sono chiamati numeri non-standard di M.

I numeri standard costituiscono quindi il più piccolo sottoinsieme di M contenente lo 0 e chiuso per la funzione successore S (valutata in M). Dai risultati fin qui mostrati segue che l’addizione e la moltimplicazione di numeri standard si comporta come la usuale addizione e moltiplicazione di numeri naturali e quindi M′ è una sottostruttura di M isomorfa ad N con le usuali operazioni di addizione e moltiplicazione. Inoltre esiste un unico isomorfismo da N ad M′ dato dalla mappa che manda n ∈ N in \overline{n}^{M}. L’unicità segue dal fatto che un qualsiasi omomorfismo di N in M deve mandare lo 0 nello 0 e preservare il successore S. Ne segue che N è contenuto (o meglio immergibile) in ogni modello M di Q e che M è isomorfo ad N se e solo se M non ha numeri non-standard.

Esempio: N è contenuto nel modello Z[x]^{+} e i numeri non-standard sono esattamente i polinomi non-costanti.

La relazione ≤ in modelli di Q

Il linguaggio di Q non comprende il simbolo ≤. Tuttavia possiamo definire x ≤ y come ∃z.z + x = y. Con questa definizione abbiamo:

Corollario 8.7 ∀n ∈ N, Q ⊢ ∀x ( x ≤ \overline{n} ↔ x = \overline{0} ∨ x = \overline{1} ∨ … ∨ x = \overline{n}).

Dim. Induzione su n. Il verso da destra a sinistra è facile. Mostriamo l’altro verso.

Caso base: Sia n = 0. Se x ≤ 0, allora z + x = 0 per qualche z. Mostreremo che x = 0. Se per assurdo x ≠ 0, allora x = S(u) per qualche u, e z + x = z + S(u) = S(z + u) = 0 contraddicendo il fatto che 0 non è il successore di alcun elemento.

Passo induttivo: Sia n > 0. Ragioniamo in Q. Supponiamo x ≤ \overline{n}. Sia z tale che z + x = \overline{n}. Se x è diverso da 0, per Q3 possiamo scrivere x = S(y). Per Q5 z + y = \overline{n − 1}. Quindi y ≤ \overline{n − 1}. Per ipotesi induttiva y = 0 ∨ … ∨ y = \overline{n − 1}. Quindi x = \overline{1} ∨ … ∨ x = \overline{n}. QED

Il risultato appena ottenuto implica che in un qualsiasi modello M di Q un elemento a ∈ M che è minore di un numero standard \overline{n}^{M} (cioè M ⊧ a ≤ \overline{n}) è necessariamente un numero standard, e inoltre è un numero standard della forma \overline{m}^{M} per qualche m ≤ n. In altre parole l’isomorfismo tra N e i numeri standard di M preserva non solo 0, S, + e ·, ma anche la relazione ≤.

Per abuso di linguaggio identificheremo talvolta N con i numeri standard di M e scriveremo quindi n anzichè \overline{n}^{M}.

Corollario 8.8 Sia n ∈ N. Sono equivalenti:

1) ∀a ≤ nQ ⊢ φ(\overline{a}),

2) Q ⊢ ∀x ≤ \overline{n}ϕ(x).

Lemma 8.9 ∀a, b ∈ N, Q ⊢ \overline{a} ≤ \overline{b} oppure Q ⊢ ¬(\overline{a} ≤ \overline{b}).

Dim. Se a ≤ b, allora Q ⊢ \overline{a} = \overline{0} ∨ \overline{a} = \overline{1} ∨ … ∨ \overline{a} = \overline{b} (in quanto la disgiunzione contiene \overline{a} = \overline{a}) e quindi Q ⊢ \overline{a} ≤ \overline{b}.

Se a > b, allora Q ⊢ ∀x . x = 0 ∨ … ∨ x = \overline{b} → x ≠ \overline{a} (poichè n ≠ m implica Q ⊢ \overline{n} ≠ \overline{m}), da cui Q ⊢ ∀x.x ≤ \overline{b} → x ≠ \overline{a} e quindi Q ⊢ ¬(\overline{a} ≤ \overline{b}). QED

Lemma 8.10 ∀b ∈ NQ ⊢ ∀x(x ≤ \overline{b} ∨ \overline{b} < x) ^{14}.

Dim. Per induzione su b. Ragionando in Q fissiamo x e mostriamo x ≤ \overline{b} o x ≥ \overline{b}. Per l’assioma Q4 0 ≤ x. Supponiamo dunque b > 0. Per ipotesi induttiva x ≤ \overline{b − 1} o x ≥ \overline{b − 1}. Nel primo caso per il Lemma ?? x ≤ \overline{b}. Nel secondo caso sia z tale che z + \overline{b − 1} = x. Se z = 0, x = \overline{b − 1} ≤ \overline{b}. Se z = S(y), allora y + \overline{b} = x e quindi \overline{b} ≤ x. In ogni caso x ≤ \overline{b} o x ≥ \overline{b}. QED

In un modello non-standard M di Q la relazione ≤ non è mai un buon ordine (in quanto se x ∈ M è non-standard, allora M contiene la catena discendente infinita x, x − 1, x − 2, x − 3, …). In alcuni modelli di Q la relazione ≤ non è neppure un ordine totale. Tuttavia abbiamo:

Lemma 8.11 Sia M ⊧ Q e sia A ⊆ M un sottoinsieme di M contenente un numero standard n. Allora A ha un minimo elemento m, ovvero esiste m ∈ A tale che ∀a ∈ A M ⊧ m ≤ a.

14Dove x < y sta per x ≤ y ∧ x ≠ y.

Dim. L’insieme A′ = {x ∈ A | M ⊧ x ≤ n} è un insieme che contiene solo numeri standard minori di n e quindi in particolare è un insieme finito e totalmente ordinato (in quanto tra numeri standard la relazione ≤ è un ordine totale). Ne segue che A′ ha un minimo elemento a ∈ A′. Tale a è anche un minimo di A perchè se x ∈ A − A′ , allora ¬(x ≤ n) (dove ≤ è calcolato in M) e dato che n è standard per la proposizione precedente n < x, da cui a < x. QED

Le formule con quantificatori limitati sono decidibili in Q

Un enunciato φ si dice decidibile in Q (o Q-decidibile) se Q ⊢ φ oppure Q ⊢ ¬φ. Una formula φ(x_{1}, …, x_{n}) si dice Q-determinata se ogni sua istanza numerica è decidibile, cioè ∀a_{1}, …, a_{n} ∈ N, Q ⊢ φ(\overline{a_{1}}, …, \overline{a_{n}}) oppure Q ⊢ ¬φ(\overline{a_{1}}, …, \overline{a_{n}}). Ovviamente se ϕ è un enunciato (n = 0) allora ϕ è Qdeterminato se e solo se è Q-decidibile.

Da un punto di vista semantico (cioè dei modelli) dire che φ(x_{1}, …, x_{n}) è Q-determinata significa che ∀a_{1}, …, a_{n} ∈ N l’enunciato φ(\overline{a_{1}}, …, \overline{a_{n}}) ha lo stesso valore di verità in tutti i modelli di Q, cioè e vero in tutti i modelli di Q (e in particolare in N) oppure è falso in tutti i modelli di Q.

Da questa caratterizzazione è immediato vedere che una combinazione booleana di formule Q-determinate è Q-determinata. Ad esempio supponiamo che φ(x_{1}, …, x_{n}) e ϕ(x_{1}, …, x_{n}) siano Q-determinate e mostriamo che la disgiunzione φ(x_{1}, …, x_{n}) ∨ ϕ(x_{1}, …, x_{n}) è Q-determinata. Siano a_{1}, …, a_{n} ∈ N. Si hanno quattro possibili casi.

1) Q ⊢ φ(\overline{a_{1}}, …, \overline{a_{n}}) e Q ⊢ ϕ(\overline{a_{1}}, …, \overline{a_{n}}).

2) Q ⊢ φ(\overline{a_{1}}, …, \overline{a_{n}}) e Q ⊢ ¬ϕ(\overline{a_{1}}, …, \overline{a_{n}}).

3) Q ⊢ ¬φ(\overline{a_{1}}, …, \overline{a_{n}}) e Q ⊢ ϕ(\overline{a_{1}}, …, \overline{a_{n}}).

4) Q ⊢ ¬φ(\overline{a_{1}}, …, \overline{a_{n}}) e Q ⊢ ¬ϕ(\overline{a_{1}}, …, \overline{a_{n}}).

I casi in cui Q non dimostra nessuna delle formule in questione nè la loro negazione è esculso perchè φ e ϕ sono Q-determinate. Nel caso 4 abbiamo per inferenza tautologica Q ⊢ ¬(φ(\overline{a_{1}}, …, \overline{a_{n}}) ∨ ϕ(\overline{a_{1}}, …, \overline{a_{n}})). Negli altri tre casi Q ⊢ φ(\overline{a_{1}}, …, \overline{a_{n}}) ∨ ϕ(\overline{a_{1}}, …, \overline{a_{n}}). Quindi φ ∨ ϕ è Q-determinata.

Sebbene il linguaggio di Q non abbia il simbolo ≤, possiamo definire ≤ come sopra e introdurre come al solito i quantificatori limitati ∀x ≤ t e ∃x ≤ t (dove t è un termine non centenente la x) vengono tramite le abbreviazioni:

∀x ≤ tφ sta per ∀x(x ≤ t → φ)

∃x ≤ tφ sta per ∃x(x ≤ t ∧ φ)

Lemma 8.12 Se φ è Q-determinata e t è un termine non contenente la x, allora le formule ∀x ≤ tφ e ∃x ≤ tφ sono Q-determinate.

Dim. Siano y_{1}, …, y_{n} le variabili libere di ∀x ≤ tφ. Allora ∀x ≤ tφ può essere scritta nella forma ∀x ≤ t(y_{1}, …, y_{n})φ(x, y_{1}, …, y_{n}). Siano a_{1}, …, a_{n} ∈ N. Dobbiamo mostrare che l’enunciato ∀x ≤ t(\overline{a_{1}}, …, \overline{a_{n}})φ(x, \overline{a_{1}}, …, \overline{a_{n}}) è decidibile in Q. Sia b ∈ N tale che Q ⊢ \overline{b} = t(\overline{a_{1}}, …, \overline{a_{n}}). Basta allora mostrare che l’enunciato ∀x ≤ \overline{b}φ(x, \overline{a_{1}}, …, \overline{a_{n}}) è decidibile in Q (in pratica con questo passaggio ci siamo ricondotti al caso in cui t è una variabile). Poichè Q ⊢ ∀x.x ≤ \overline{b} ↔ x = \overline{0} ∨ x = \overline{1} ∨ … ∨ x = \overline{b}, l’enunciato ∀x ≤ \overline{b}φ(x, \overline{a_{1}}, …, \overline{a_{n}}) è equivalente, in Q, all’enunciato φ(\overline{0}, \overline{a_{1}}, …, \overline{a_{n}}) ∧ φ(\overline{1}, \overline{a_{1}}, …, \overline{a_{n}}) ∧ … ∧ φ(\overline{b}, \overline{a_{1}}, …, \overline{a_{n}}) e quest’ultimo è decidibile in Q in quanto combinazione booleana di enunciati decidibili in Q.

Il caso del quantificatore ∃x ≤ t si tratta analogamente considerando la disgiunzione φ(\overline{0}, \overline{a_{1}}, …, \overline{a_{n}}) ∨ φ(\overline{1}, \overline{a_{1}}, …, \overline{a_{n}}) ∨ … ∨ φ(\overline{b}, \overline{a_{1}}, …, \overline{a_{n}}). QED

Una formula Δ_{0}, è una formula senza quantificatori o una formula i cui quantificatori siano tutti limitati.

Corollario 8.13 Ogni formula Δ_{0} è Q-determinata.

Per ogni enunciato ϕ ∈ Δ_{0} abbiamo quindi:

1) se N ⊧ ϕ, allora Q ⊢ ϕ,

2) se N ⊧ ¬ϕ, allora Q ⊢ ¬ϕ.

Ne segue, ad esempio, che Q ⊢ ∀x∀y ≤ \overline{15}(x + y = y + x). D’altra parte si può mostrare che Q ⊬ ∀x, y(x + y = y + x) in quanto ci sono modelli M di Q in cui la addizione non è commutativa. Naturalmente il fallimento della commutatività si può verificare solo per elementi non-standard di M in quanto gli elementi standard di qualsiasi modello di Q commutano (in quanto formano una struttura isomorfa ad N).

Una spiegazione intuitiva del fatto che gli enunciati Δ_{0} sono decidibili in Q sta nel fatto che un enunciato ϕ ∈ Δ_{0} è vero in un modello M di Q se e solo se è vero nella sottostruttura M′ di M costituita dai numeri standard (dimostrarlo come esercizio per induzione sulla lunghezza della formula usando la semantica di Tarski). Poichè M′ è isomorfo ad N ne segue che ϕ è vera in M se e solo se è vera in N e per l’arbitrarietà di M possiamo concludere che ϕ ha lo stesso valore di verità in tutti i modelli di Q e quindi è decidibile in Q.

Definizione 8.14 Le formule Σ_{1} sono la più piccola classe di formule contenenti le Δ_{0} e chiusa per congiunzioni, disgiunzioni, quantificatori universali, e quantificatori esistenziali anche illimitati. Non richiediamo la chiusura per negazioni.

Lemma 8.15 Se ϕ è un enunciato Σ_{1} e N ⊧ ϕ, allora Q ⊢ ϕ.

Dim. Per induzione sulla complessità di ϕ. Il caso interessante è quando ϕ inizia con un quantificatore esistenziale illimitato ed è quindi della forma ∃xψ(x). Supponiamo che tale enunciato sia vero in N e sia a ∈ N tale che N ⊧ ψ(\overline{a}). Per induzione Q ⊢ ϕ(\overline{a}), da cui segue che Q dimostra ∃xψ(x). QED

Riassumendo abbiamo:

1) Gli enunciati Δ_{0} veri in N sono dimostrabili in Q.

2) Gli enunciati Δ_{0} falsi in N sono refutabili in Q (cioè è dimostrabile la negazione).

3) Gli enunciati Σ_{1} veri in N sono dimostrabili in Q.

4) Gli enunciati Σ_{1} falsi in N non sono dimostrabili in Q (poichè N ⊧ Q). Non è però detto che un enunciato Σ_{1} falso in N sia refutabile in Q, ad

esempio ∃x, y.x + y ≠ y + x è una formula Σ_{1} falsa in N ma non refutabile in Q. Quindi esistono formule Σ_{1} non Q-determinate.

Rappresentabilità in Q delle funzioni primitive ricorsive

Un insieme A ⊆ N^{k} è binumerabile in Q se esiste una formula φ_{A}(x_{1}, …, x_{k}) ^{15} tale che ∀a_{1}, …, a_{k} ∈ N,

1) se (a_{1}, …, a_{k}) ∈ A, allora Q ⊢ φ_{A}(\overline{a_{1}}, …, \overline{a_{k}}),

2) se (a_{1}, …, a_{k}) ∉ A, allora Q ⊢ ¬φ_{A}(\overline{a_{1}}, …, \overline{a_{k}}).

Proposizione 8.16 Ogni insieme Δ_{0}-definibile è binumerabile in Q.

Dim. Segue dal fatto che ogni formula Δ_{0} è Q-determinata. QED

Una funzione totale f: N^{k} → N è binumerabile in Q, se il suo grafo è binumerabile in Q, cioè esiste una formula φ_{f}(x_{1}, …, x_{k}, y) tale che ∀a_{1}, …, a_{k} ∈ N:

1) se f(a_{1}, …, a_{k}) = b, allora Q ⊢ φ_{f}(\overline{a_{1}}, …, \overline{a_{k}}, \overline{b}), 2) se f(a_{1}, …, a_{k}) ≠ b, allora Q ⊢ ¬φ_{f}(\overline{a_{1}}, …, \overline{a_{k}}, \overline{b}). Se valgono queste due condizioni diciamo che φ_{f} binumera f. Se oltre ad (1) e (2) vale la condizione

15Un insieme può essere binumerato da tante formule non Q-equivalenti, quindi la notazione φ_{A} è ambigua.

3) Q ⊢ ∃!yφ_{f}(\overline{a_{1}}, …, \overline{a_{k}}, y)

allora diciamo che f è binumerata funzionalente da φ_{f}. Ciò equivale a richiedere che Q ⊢ ∀y(φ_{f}(\overline{a_{1}}, …, \overline{a_{k}}, y) ⟺ y = \overline{b}) dove b = f(a_{1}, …, a_{k}).

Mostreremo che il grafico della funzione esponenziale, ovvero l’insieme {(x, y, z) | x^{y} = z}, è binumerabile funzionalmente in Q, e inoltre è possibile binumerarlo con una formula Σ_{1}^{0}. Lo stesso vale più in generale per una funzione primitiva ricorsiva o anche ricorsiva generale.

A tal fine abbiamo bisogno di un modo alternativo di codificare le successioni, non basato sulla scomposizione in fattori primi (che richiede l’esponenziazione) ma basato invece sul teorema cinese dei resti.

Teorema 8.17 (Teorema cinese dei resti) Siano a_{0}, a_{1}, …, a_{n} numeri a due a due relativamente primi. Siano b_{0}, b_{1}, …, b_{n} numeri arbitrari. Allora esiste un numero x che per ogni i ≤ n:

x ≡ b_{i} (mod a_{i})

(Il numero x è univocamente determinato modulo il prodotto degli a_{i}.)

Dim. Assumiamo dapprima che uno dei b_{i} sia 1 e tutti gli altri siano 0. Dato i ≤ n cerchiamo dunque un x_{i}tale che

x_{i} ≡ 1 (mod a_{i})

x_{i} ≡ 0 (mod a_{j}) ∀j ≠ i.

Poichè a_{i} e Π_{j≠i}a_{j} sono relativamente primi, esistono α, β tali che α · a_{i} + β · Π_{j≠i}a_{j} = 1. Basta ora porre x_{i} = β · Π_{j≠i}a_{j}. Per risolvere il sistema originale basta scegliere x = b_{0}x_{0} + b_{1}x_{1} + … + b_{n}x_{n}. QED

Per poter applicare per i nostri scopi il teorema cinese dei resti ci occorre un modo per poter generare con facilità una successione di numeri primi tra loro a_{0}, …, a_{n}. Il seguente lemma mostra che esistono progressioni aritmetiche arbitrariamente lunghe composte di numeri arbitrariamente grandi e a due a due relativamente primi.

Lemma 8.18 Per ogni n, x esiste d > x tale che la progressione aritmetica d + 1, 2d + 1, 3d + 1, …, nd + 1 è composta da numeri relativamente primi.

Dim. È sufficiente prendere d = y! dove y > max(n, x). Se infatti un numero primi p dividesse due elementi della successione d+1, 2d+1, …, nd+ 1, diciamo p|(i + 1)d + 1 e p|(j + 1)d + 1 con i > j, allora p dividerebbe la loro differenza (i − j)d e quindi p|(i − j) oppure p|d. Ma p|d conduce subito ad un assurdo in quanto avendosi anche p|(i + 1)d + 1 ne conseguirebbe p|1. D’altra parte se p|(i − j) allora, visto che i − j ≤ n < y, ne conseguirebbe p|y! cioè di nuovo p|d che è assurdo. QED

Sia re(x, y) il resto della divisione di x per y, cioè re(x, y) = r se e solo se ∃q ≤ x(x = qy + r ∧ 0 ≤ r < y). La funzione β di Gödel, β: N^{3} → N, è definita da: β(c, d, i) = re(c, (i + 1)d + 1). Osserviamo che il grafo della funzione β è Δ_{0}^{N}: β(c, d, i) = r ↔ ∃q ≤ c(c = q[(i + 1)d + 1] + r ∧ 0 ≤ r < (i+1)d+1). La proprietà fondamentale della funzione β di Gödel è espressa dal seguente:

Lemma 8.19 Per ogni n ed ogni seguenza di numeri b_{0}, b_{1}, …, b_{n} esistono c, d tali che β(c, d, 0) = b_{0}, β(c, d, 1) = b_{1}, …, β(c, d, n) = b_{n}.

Dim. Dati b_{0}, …, b_{n} scegliamo d in modo tale che i numeri d + 1, 2d + 1, …, nd + 1 siano relativamente primi e d sia più grande di tutti i b_{i}. Ora scegliamo c in modo che soddisfi le congruenze c ≡ b_{i} (mod (i + 1)d + 1) per i < n. Ne segue che per ogni i < n, b_{i} è il resto della divisione di c per (i + 1)d + 1, ovvero b_{i} = β(c, d, i). QED

In virtù del precedente lemma possiamo pensare alla coppia c, d come ad una codifica della successione b_{0}, …, b_{n}. La funzione β può essere interpretata nel modo seguente: β(c, d, i) = l’i-esimo elemento della successione codificata da (c, d). Il lemma ci garantisce che ogni successione ha (almeno) una codifica. Volendo potremmo usare una opportuna “funzione coppia” per codificare (c, d) con un singolo numero. In tal modo giungeremmo ad un metodo per codificare le sequenze con un singolo numero anzichè due, ma questo non è necessario per i nostri scopi.

La funzione β può essere usata in alternativa alla Estrai vista precedentemente. Essendo Δ_{0}-definibile, il grafico della funzione β è Q-determinato.

Lemma 8.20 La funzione β di Gödel è binumerabile funzionalmente in Q.

Dim. Facile esercizio. QED

Teorema 8.21 Ogni funzione primitiva ricorsiva è binumerabile funzionalmente in Q (da una formula Σ_{1}^{0}).

Dim. Basta mostrare che le funzioni binumerabili funzionalmente in Q (da una formula Σ_{1}^{N}) contengono le funzioni primitive ricorsive iniziali, e sono chiuse per composizione e ricursione primitiva.

Lasciamo al lettore la verifica per le funzioni iniziali.

La chiusura per composizione è semplice: supponiamo ad esempio che f(x) = h(g_{1}(x), g_{2}(x)). Allora f(x) = y se e solo se ∃a, b, c(a = g_{1}(x) ∧ b = g_{2}(x) ∧ y = h(a, b)), da cui sostituendo le uguaglianze che coinvolgono g_{1}, g_{2}, h con le formule che binumerano funzionalmente tali funzioni, otteniamo la formula che binumera funzionalmente f.

Chiusura per ricursione primitiva.

Sia f definita per ricursione primitiva da g e da h:

f(x⃗, 0) = g(x⃗),

f(x⃗, y + 1) = h(x⃗, y, f(x⃗, y)).

Fissati x⃗, y si ha che f(x⃗, y) = z se e solo se esiste una successione di numeri a_{0}, a_{1}, …, a_{y} tale che:

1) a_{0} = g(x⃗),

2) a_{y} = z,

3) ∀i < y a_{i+1} = h(x⃗, y, a_{i}).

Per i risultati sulla funzione β di Gödel esistono due numeri c, d che codificano l’intera successione a_{0}, a_{1}, …, a_{y} nel senso che β(c, d, 0) = a_{0}, β(c, d, 1) = a_{1}, …, β(c, d, y) = a_{y}. Abbiamo ora l’equivalenza: f(x⃗, y) = z se e solo se ∃c, d :

1) β(c, d, 0) = g(x⃗),

2) β(c, d, y) = z,

3) ∀i < yβ(c, d, i + 1) = h(x⃗, y, β(c, d, i)).

Usando il fatto che la funzione β e le funzioni g ed h sono binumerabili funzionalmente in Q, si può verificare che l’espressione così ottenuta per f (rimpiazzando opportunamente β, g, h con le rispettive formule) binumera funzionalmente f in Q. Si osservi che c, d non sono univocamente determinati da x⃗, y, ma i numeri β(c, d, i) (i = 0, …, y) sono univocamente determinati. QED

Possiamo rafforzare il teorema come segue:

Teorema 8.22 Ogni funzione ricorsiva totale è binumerabile funzionalmente in Q (da una formula Σ_{1}^{0}).

Dim. Basta integrare la dimostrazione precedente nel modo seguente: Chiusura per minimalizzazione

Sia f(x⃗) il minimo y tale che g(x⃗, y) = 0 (supponeniamo che esista). Osserviamo che f(x⃗) = y se e solo se g(x⃗, y) = 0∧∀i < y∃v ≠ 0 g(x⃗, i) = v. Assumiamo che g sia funzionalmente binumerabile in Q dalla formula G(x⃗, y). Allora f è funzionalmente binumerabile in Q dalla formula G(x⃗, y, 0) ∧ ∀i < y∃v ≠ 0 G(x⃗, i, v). (Verificare come esercizio.) QED

Poiché N è un modello di Q otteniamo:

Corollario 8.23 Ogni funzione ricorsiva totale è binumerabile funzionalmente in Q (da una formula Σ_{1}^{0}).

9 Teoremi di incompletezza

Supponiamo che L contenga un simbolo di funzione unario s e un simbolo di costante 0.

Lemma 9.1 Esiste una funzione primitiva ricorsiva num: N → N tale che per ogni n ∈ N, num(n) = ⌈s^{n}(0)⌉, dove il termine s^{n}(0) è definito da s^{0}(0) = 0 e s^{n+1}(0) = s(s^{n}(0)).

Dim. num(0) = ⌈0⌉, num(n + 1) = ⟨⌈s⌉, num(n)⟩. QED

Se ⌈α⌉ = n ∈ N, indichiamo con \overline{⌈α⌉} il termine s^{n}(0) (la cui interpretazione nella struttura N è proprio il numero n). Data una formula α e un termine t, scriviamo α(t) per α[t/v_{0}].

Lemma 9.2 Esiste una funzione primitiva ricorsiva D: N → N tale che per ogni formula α, D(⌈α⌉) = ⌈α(\overline{⌈α⌉})⌉.

Dim. D(x) = sub(x, 0, num(x)). QED

Lemma 9.3 Sia α(x) una formula nella variabile libera x. Allora esiste una formula β tale che Q dimostra l’equivalenza β ↔ α(\overline{⌈β⌉}).

Dim. Sia δ(x, y) la formula che binumera funzionalmente D in Q. Poniamo β = γ(\overline{⌈γ⌉}) dove γ = γ(v_{0}) è la formula ∀y(δ(v_{0}, y) → α(y)). Allora in Q si ha: γ(\overline{⌈γ⌉}) se e solo se ∀y(δ(\overline{⌈γ⌉}, y) → α(y)), e visto che l’unico y che verifica δ(\overline{⌈γ⌉}, y) è \overline{⌈γ(\overline{⌈γ⌉})⌉}, questo vale se e solo se α(\overline{⌈γ(\overline{⌈γ⌉})⌉}). QED Teorema 9.4 La teoria P A (aritmetica di Peano del primo ordine) è incompleta.

Dim. Poiché le codifiche degli assiomi di P A sono un insieme primitivo ricorsivo, per il Teorema ?? esiste un insieme primitivo ricorsivo Prov tale che P A ⊢ φ se e solo se ∃n : (n, ⌈φ⌉) ∈ Prov. Sia P (x, y) una formula che binumera Prov in Q. Sia Teo(x) la formula ∃dP (d, x). Sia G un enunciato tale che Q dimostra G ↔ ¬Teo(\overline{⌈G⌉}). Interpretatando questa equivalenza nel modello N, si ha in particolare che G è vera (in N) se e solo se G non è dimostrabile in P A. Mostriamo che nè G nè la sua negazione è dimostrabile in P A.

Se per assurdo P A ⊢ G, allora esiste n tale che (n, ⌈G⌉) ∈ Prov. Fissato un tale n si ha Q ⊢ P (n, \overline{⌈G⌉}). Quindi Q ⊢ ∃dP (d, \overline{⌈G⌉}), ovvero Q ⊢ Teo(\overline{⌈G⌉}). Ma allora per la scelta di G, Q ⊢ ¬G, e poiché P A contiene Q, P A ⊢ ¬G. Questo è impossibile, in quanto P A è coerente.

Abbiamo quindi dimostrato che G non è dimostrabile in P A, e per la scelta di G ne segue che G è vera (in N). Ma allora nemmeno la negazione di G è dimostrabile in P A in quanto P A dimostra solo cose vere in N (essendo N un suo modello). QED

Con essenzialmente la stessa dimostrazione si ha:

Teorema 9.5 Sia T una teoria coerente, contenente Q, avente N tra i suoi modelli, e tale che l’insieme dei numeri di Gödel dei suoi assiomi è ricorsivo totale. Allora T è incompleta.

Definizione 9.6 Sia T una teoria nel linguaggio dell’aritmetica. T è ωcoerente se non è possibile che T dimostri un enunciato della forma ∃xφ(x) e al tempo stesso, per ogni n, T ⊢ ¬φ(\overline{n}).

Osservazione 9.7 Se T ha come modello N, T è ω-coerente. Se T è ωcoerente, allora T è coerente (affinché una teoria sia coerente basta che vi sia un enunciato non dimostrabile).

Lemma 9.8 Sia T una teoria ω-coerente contenente Q e sia σ un enunciato Σ_{1}^{0}. Allora T ⊢ σ se e solo se σ è vero nel modello N.

Dim. Ci limitiamo a considerare il caso in cui σ è della forma ∃xθ(x) con θ ∈ Δ_{0}. Se σ è vero in N, allora per qualche n ∈ N, θ(\overline{n}) è vero in N, e quindi dimostrabile in Q (essendo θ ∈ Δ_{0}). Ne segue che θ(\overline{n}) è dimostrabile in T, e quindi anche ∃xθ(x) lo è.

Viceversa se T ⊢ σ e se per assurdo σ fosse falso in N, allora per ogni n varrebbe in N l’enunciato ¬θ(\overline{n}) e pertanto questo enunciato sarebbe dimostrabile in Q (essendo Δ_{0}) e quindi in T, contraddicendo la ω-coerenza. QED

Teorema 9.9 Sia T una teoria ω-coerente, contenente Q, e tale che l’insieme dei numeri di Gödel dei suoi assiomi è ricorsivo totale. Allora T è incompleta.

Dim. Poiché le codifiche degli assiomi di T sono un insieme ricorsivo, esiste un insieme ricorsivo Prov tale che T ⊢ φ se e solo se ∃n : (n, ⌈φ⌉) ∈ Prov. Sia P (x, y) una formula che binumera Prov in Q. Sia Teo(x) la formula ∃dP (d, x). Sia G un enunciato tale che Q dimostra G ↔ ¬Teo(\overline{⌈G⌉}).

Se per assurdo T ⊢ G, allora esiste n tale che (n, ⌈G⌉) ∈ Prov. Fissato un tale n si ha Q ⊢ P (n, \overline{⌈G⌉}). Quindi Q ⊢ ∃dP (d, \overline{⌈G⌉}), ovvero Q ⊢ Teo(\overline{⌈G⌉}). Ma allora per la scelta di G, Q ⊢ ¬G, e poiché T contiene Q, T ⊢ ¬G. Questo è impossibile, in quanto T è coerente.

Abbiamo quindi dimostrato che G non è dimostrabile in T, e pertanto per ogni n si ha (n, ⌈G⌉) ∉ Prov, da cui discende ¬P (\overline{n}, \overline{⌈G⌉}) è dimostrabile in Q e quindi in T. Ma allora per la ω-coerenza T ⊬ ∃xP (x, \overline{⌈G⌉}), e per definizione di G, T ⊬ ¬G. QED

Teorema 9.10 Sia T una teoria ω-coerente, contenente Q, e tale che l’insieme dei numeri di Gödel dei suoi assiomi è ricorsivo totale. Allora T è indecidibile (nel senso che l’insieme dei suoi teoremi non è ricorsivo). In particolare P A è indecidibile.

Dim. Sia K_{0} ⊂ N un insieme ricorsivamente enumerabile e non ricorsivo. Essendo ricorsivamente enumerabile K_{0} è definibile in N da una formula σ(x) ∈ Σ_{1}^{0} in una variabile libera. Per ogni n ∈ N, n ∈ K_{0} se e solo se σ(\overline{n}) è vera in N, e per la ω-coerenza di T, questo avviene se e solo se T ⊢ σ(\overline{n}). Ne segue che se avessimo un algoritmo per stabilire se un enunciato è un teorema di T, ne avremmo uno per stabilire se un numero appartiene a K_{0}. QED Osservazione 9.11 La incompletezza di P A segue anche direttamente dalla sua indecidibilità, in quanto una teoria completa con un insieme di assiomi ricorsivo è decidibile.

Rosser ha dimostrato che nei teoremi sopra enunciati, l’ipotesi di ω coerenza di può indebolire nell’ipotesi di semplice coerenza.

Si può dimostrare che la formula G nella dimostrazione del Teorema ?? equivale in P A alla formula Con(P A), definita da ∃x¬T eo(x), che esprime la coerenza di P A. Quindi P A non dimostra la sua propria coerenza.

Teorema 9.12 P A ⊬ Con(P A).

Dim.(Cenni) Per dimostrare, nella teoria P A, l’equivalenza G ↔ Con(P A), notiamo che l’implicazione da sinistra a destra è ovvia in quanto G implica ¬T eo(⌈G⌉), che ovviamente implica ¬∃xT eo(x). L’implicazione inversa Con(P A) → G si ottiene formalizzando in P A la prima parte della dimostrazione del Teorema ??, quella cioè in cui si mostra P A ⊬ G. In tale dimostrazione si usa solo la coerenza di P A (e non che N sia un modello). Formalizzando il ragionamento si ottiene una dimostrazione, in P A, dell’implicazione Con(P A) → ¬T eo(⌈G⌉). Poiché ¬T eo(⌈G⌉) equivale dimostrabilmente a G, si ha P A ⊢ Con(P A) → G. QED