Appunti del corso di Elementi di Logica, Calcolabilità e Complessità

A. Berarducci

Versione preliminare, 20 Maggio 2002

Sommario Questi appunti sono ad uso esclusivo degli studenti del corso e sono

ancora INCOMPLETI e da perfezionare. Gli argomenti di calcolabilità si possono trovare in forma più esauriente nel libro di N.J.Cutland, Computability, An introduction to recursive function theory, Cambridge University Press 1980.

Indice

1 Macchine a registri 3 1.1 Registri e configurazione di memoria . . . . . . . . . . . . . . . . 3 1.2 Contatore di programma . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Stato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Istruzioni e programmi . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Semantica delle istruzioni . . . . . . . . . . . . . . . . . . . . . . 4 1.6 Semantica dei programmi . . . . . . . . . . . . . . . . . . . . . . 5

1.6.1 Funzioni parziali . . . . . . . . . . . . . . . . . . . . . . . 5 1.6.2 Trasformazione di memoria determinata da un programma 5 1.6.3 Nomi dei registri . . . . . . . . . . . . . . . . . . . . . . . 6

1.7 Funzioni calcolabili . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.8 Concatenazione di programmi . . . . . . . . . . . . . . . . . . . . 7 1.9 Programmi con istruzioni etichettate . . . . . . . . . . . . . . . . 8 1.10 Diagrammi di flusso . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.11 Uso di funzioni predefinite . . . . . . . . . . . . . . . . . . . . . . 9

2 Funzioni ricorsive parziali 10 2.1 Funzione ricorsiva parziale associata ad un programma . . . . . . 10 2.2 Composizione di funzioni ricorsive parziali . . . . . . . . . . . . . 11 2.3 Ricursione primitiva . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3.1 Funzioni primitive ricorsive . . . . . . . . . . . . . . . . . 12 2.4 Minimalizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4.1 Funzioni μ-ricorsive di Kleene . . . . . . . . . . . . . . . . 14 2.5 Altri operatori ricorsivi . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.1 Sommatorie e produttorie limitate . . . . . . . . . . . . . 14 2.5.2 Minimalizzazione limitata . . . . . . . . . . . . . . . . . . 15 2.5.3 Ricursione sul decorso dei valori . . . . . . . . . . . . . . 15

3 Tesi di Church 15

4 Predicati decidibili 16 4.1 Definizioni per casi . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 Algebra di Boole degli insiemi decidibili . . . . . . . . . . . . . . 17 4.3 Quantificatori limitati . . . . . . . . . . . . . . . . . . . . . . . . 17

5 Codifiche 17 5.1 Codifica delle stringhe . . . . . . . . . . . . . . . . . . . . . . . . 18 5.2 Codifica delle coppie . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.3 Codifica delle successioni a supporto finito . . . . . . . . . . . . . 18 5.4 Codifica degli insiemi finiti . . . . . . . . . . . . . . . . . . . . . 19 5.5 Codifica delle successioni finite . . . . . . . . . . . . . . . . . . . 19

6 Predicati semidecidibili 20 6.1 Operazioni logiche tra predicati semidecidibili . . . . . . . . . . . 20 6.2 Teorema di Post . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.3 Quantificatori limitati su predicati semidecidibili . . . . . . . . . 21 6.4 Enumerazioni ricorsive degli insiemi semidecidibili . . . . . . . . 21 6.5 Enumerazioni ricorsive crescenti degli insiemi decidibili . . . . . . 22

7 Codifica dei programmi 22 7.1 Una funzione non calcolabile . . . . . . . . . . . . . . . . . . . . 23

8 Programmi universali 23 8.1 Forma normale di Kleene . . . . . . . . . . . . . . . . . . . . . . 23 8.2 Dimostrazione del teorema di Kleene . . . . . . . . . . . . . . . . 25

9 Il problema della fermata 27

10 Riducibilità molti-uno 28

11 Il teorema s-m-n e la completezza del problema della fermata 29

12 Equivalenza tra programmi 30 12.1 Teorema di Rice . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

13 Il secondo teorema di punto fisso 31

14.4 Gli insiemi ricorsivamente enumerabili sono definibili in (ℕ; +, ·) 34

14 Gerarchia aritmetica 31 14.1 Insiemi aritmetici . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.2 Insiemi definibili nella struttura (ℕ; +, ·) . . . . . . . . . . . . . . 32 14.3 Funzione β di Gödel . . . . . . . . . . . . . . . . . . . . . . . . . 32 15 Teorie formali per l’aritmetica 35

15.1 L’aritmetica di Peano del secondo ordine . . . . . . . . . . . . . . 35 15.2 La teoria Q di Robinson . . . . . . . . . . . . . . . . . . . . . . . 37 15.3 L’aritmetica di Peano del primo ordine . . . . . . . . . . . . . . . 38 15.4 Conseguenza logica . . . . . . . . . . . . . . . . . . . . . . . . . . 39 15.5 Dimostrazioni formali . . . . . . . . . . . . . . . . . . . . . . . . 40 15.6 Alcune formule dimostrabili in Q . . . . . . . . . . . . . . . . . . 41 15.7 Numeri non-standard . . . . . . . . . . . . . . . . . . . . . . . . . 43 15.8 La relazione ≤ in modelli di Q . . . . . . . . . . . . . . . . . . . 43 15.9 Le formule con quantificatori limitati sono decidibili in Q …. 45 15.10Rappresentabilità in Q delle funzioni ricorsive . . . . . . . . . . . 46

16 Teoremi di incompletezza di Gödel 48 16.1 Aritmetizzazione della sintassi e predicato di dimostrabilità … 48 16.2 Enunciati indimostrabili . . . . . . . . . . . . . . . . . . . . . . . 51

1 Macchine a registri

Una macchina a registri è un modello idealizzato di calcolatore proposto da Shepherdson e Sturgis nel 1963. Ci baseremo su tale modello per dare una definizione di funzione calcolabile (le prime definizioni di funzione calcolabile risalgono agli anni 1930-40). A differenza di un calcolatore reale una macchina a registri ha una capacità di memoria potenzialmente illimitata (la memoria di un calcolatore è un dispositivo che ha la funzione di immagazzinare dell’informazione opportunamente codificata). Ogni programma per macchina a registri può essere realizzato anche su un calcolatore reale (e viceversa), ma su quest’ultimo non sarà possibile elaborare dati che superino delle fissate capacità di memoria.

1.1 Registri e configurazione di memoria

Una macchina a registri ha infiniti registri di memoria R_{0}, R_{1}, R_{2}, . . .. In ogni momento del calcolo ogni registro R_{i} contiene un numero naturale a_{i}, ma solo un numero finito di essi contengono un numero diverso da zero. La successione dei numeri naturali (a_{0}, a_{1}, a_{2}, …) contenuti nei vari registri in un dato momento viene detta configurazione di memoria.

1.2 Contatore di programma

Una macchina a registri ha anche uno speciale registro chiamato contatore di programma. Il contatore di programma contiene un numero che indica quale sia la prossima istruzione da eseguire. All’inizio del calcolo il contatore contiene il numero 1.

1.3 Stato

Lo stato di una macchina a registri in un dato momento è dato dal contenuto dei registri di memoria e dal contenuto del contatore di programma.

1.4 Istruzioni e programmi

Un programma P per macchina a registri è una lista finita (I_{1}, …, I_{s}) di istruzioni. Le istruzioni possono essere dei seguenti tipi.

• R_{n} := 0,

• R_{n} := R_{n} + 1,

• R_{n} := R_{m},

• if R_{n} = R_{m} go to q.

Le istruzioni dei primi tre tipi sono dette istruzioni di assegnazione, le istruzioni del quarto tipo sono dette istruzioni di salto condizionato. Se in un dato momento il contatore di programma contiene il numero i, con 1 ≤ i ≤ s, viene eseguita l’istruzione I_{i}, altrimenti la macchina si arresta. Una istruzione della forma “if R_{n} = R_{m} go to s + 1”, dove s è la lunghezza del programma, equivale quindi ad un comando di arresto.

1.5 Semantica delle istruzioni

L’esecuzione di una istruzione all’interno di un programma comporta un cambiamento dello stato, ovvero della configurazione di memoria e del contatore di programma. Consideriamo innanzitutto il cambiamento della configurazione di memoria:

• L’esecuzione di R_{n} := 0 memorizza il numero 0 nel registro R_{n} (cancellando i dati precedentemente contenuti in tale registro e lasciando invariato il contenuto degli altri registri).

• L’esecuzione di R_{n} := R_{n} + 1 incrementa di uno il contenuto del registro R_{n}.

• L’esecuzione di R_{n} := R_{m} memorizza nel registro R_{n} il contenuto del registro R_{m}.

• L’esecuzione di una istruzione di salto condizionato non modifica la configuazione di memoria.

Consideriamo ora il cambiamento del contatore di programma:

• L’esecuzione di una istruzioni di assegnazione comporta un incremento di 1 del contenuto del contatore di programma.

• L’esecuzione di una istruzione della forma “if R_{n} = R_{m} go to q” modifica il contenuto del contatore di programma come segue. Il contenuto del contatore di programma viene posto uguale a q se i contenuti dei registri R_{n} ed R_{m} sono uguali, altrimenti il contatore viene incrementato di 1.

1.6 Semantica dei programmi

1.6.1 Funzioni parziali

1.1 Definizione. Data una relazione f ⊆ A×B definiamo il suo dominio come l’insieme dom(f) = {a ∈ A | ∃b ∈ B (a, b) ∈ f}, e la sua immagine come l’insieme Im(f) = {b ∈ B | ∃a ∈ A (a, b) ∈ f}. Se per ogni a ∈ dom(f) esiste un unico b ∈ B tale che (a, b) ∈ f, allora diciamo che f è una funzione parziale da A a B, e scriviamo f: A → B per indicare questo fatto. Se inoltre dom(f) = A diciamo che f è una funzione totale da A a B. Data una funzione parziale f: A → B scriviamo f(a) = b se (a, b) ∈ f. Inoltre, dato un elemento a ∈ A, scriviamo f(a) ↓ se a ∈ dom(f), e f(a) ↑ altrimenti. Due funzioni parziali f: A → B e g: A → B sono uguali se hanno lo stesso dominio A′ ⊆ A e se per ogni a ∈ A′ si ha f(a) = g(a).

1.2 Definizione. Date due funzioni parziali f: A → B e g: B → C, la loro composizione g∘f è la funzione parziale h: A → C definita come segue: h(a) = c se e solo se esiste b ∈ B con f(a) = b e g(b) = c. Scriviamo h(x) = g(f(x)) per dire che h è la composizione g ∘ f. Fissato un valore di x, abbiamo h(x) ↓ se e solo se x ∈ dom(f) e f(x) ∈ dom(g).

1.3 Esempio. Se f(x) ↑, allora (0 · f(x)) ↑.

1.6.2 Trasformazione di memoria determinata da un programma

1.4 Definizione. Un calcolo del programma P è una successione finita o infinita (s_{0}, s_{1}, s_{2}, …) di stati. A partire da un dato stato viene eseguita l’istruzione indicata dal contatore di programma. L’esecuzione dell’istruzione determina il successivo stato del calcolo secondo le regole sopra date. Il calcolo ha termine se e quando si raggiunge uno stato di arresto, ovvero uno stato in cui il contatore di programma contiene un numero che non corrisponde ad alcuna istruzione del programma.

1.5 Definizione. Indichiamo con ℕ^{∞} l’insieme di tutte le possibili configurazioni di memoria, ovvero di tutte le successioni infinite di numeri naturali che sono zero da un certo punto in poi. Un programma P definisce una funzione parziale

P: ℕ^{∞} → ℕ^{∞}

come segue: P(c) = c′ se il calcolo del programma P a partire dallo stato s = (c, 1) avente configurazione di memoria c ∈ ℕ^{∞} e contatore di programma 1, termina dopo un numero finito di passi in uno stato di arresto avente c′ come configurazione di memoria. Se non viene mai raggiunto uno stato di arresto P(c) ↑.

1.6 Esempio. Il seguente programma scambia il contenuto dei registri R_{1} ed R_{2}.

1. R_{3} := R_{1};

2. R_{1} := R_{2};

3. R_{2} := R_{3}.

1.6.3 Nomi dei registri

Nello scrivere un programma risulta comodo riferirsi ai registri di memoria attraverso dei nomi simbolici, scrivendo ad esempio x, y, z, …, anziché R_{1}, R_{2}, R_{3}, . . .. Il programma dell’esempio precedente assume allora la forma:

1. z := x;

2. x := y;

3. y := z.

dove x, y, z sono nomi di registri (da non confondersi con il contenuto dei registri stessi).

1.7 Funzioni calcolabili

1.7 Definizione. Supponiamo di voler scrivere un programma P per macchina a registri per calcolare una funzione da ℕ^{m} a ℕ^{n}. Distinguiamo a tal fine i registri di memoria usati dal programma in tre gruppi.

1. Registri di input: contengono, all’inizio del calcolo, i dati di ingresso (a_{1}, …, a_{m}) ∈ ℕ^{m} (non ci occupiamo del problema di come vengano forniti alla macchina tali dati: possiamo ad esempio immaginare che vengano digitati da una apposita tastiera).

2. Registri di output: conterrano alla fine del calcolo, se questo ha termine, i risultati finali (b_{1}, …, b_{n}) ∈ ℕ^{n} a cui siamo interessati (non ci occupiamo del problema di come vengano letti o stampati tali risultati).

3. Registri di lavoro: consistono di tutti gli altri registri che vengono usati dal programma e contengono informazioni utili al suo funzionamento. In genere supporremo che all’inizio del calcolo tutti i registri di lavoro contengano il numero zero.

La funzione parziale da ℕ^{m} a ℕ^{n} calcolata dal programma P, rispetto ad una fissata scelta di m registri di input x_{1}, …, x_{m} ed n registri di output y_{1}, …, y_{n}, viene indicata con la notazione

(y_{1}, …, y_{n}) := P (x_{1}, …, x_{m})  (1)

ed è definita dalla composizione

ℕ^{m} ⟶^{Inputx_{1},...,x_{m}} ℕ^{∞} ⟶^{P} ℕ^{∞} ⟶^{Outputy_{1},...,y_{n}} ℕ^{n},  (2)

dove Inputx_{1}, …, x_{m}: ℕ^{m} → ℕ^{∞} è la funzione che immagazzina i dati di ingresso negli m registri di input, P: ℕ^{∞} → ℕ^{∞} è la funzione parziale descritta nella Definizione 1.5, e Outputy_{1}, …, y_{n}: ℕ^{∞} → ℕ^{n} è la funzione che legge dalla configurazione di memoria i dati contenuti negli n registri di output.

1.8 Esempio. Supponendo che x_{0}, x_{1}, x_{2} siano i primi tre registri di memoria R_{0}, R_{1}, R_{2}, Inputx_{0}, x_{1}, x_{2}(3, 5, 4) = (3, 5, 4, 0, 0, 0, …).

Supponendo che y_{1}, y_{2} siano i registri R_{0} ed R_{3} rispettivamente, abbiamo Outputy_{1}, y_{2}(3, 2, 7, 9, 8, 0, 0, …) = (3, 9).

1.9 Definizione. Una funzione parziale f: ℕ^{m} → ℕ^{n} è calcolabile se e solo se coincide con la funzione calcolata da un programma P, rispetto ad una data scelta di m registri di input ed n registri di output.

Nel seguito quando scriveremo un programma per calcolare una funzione da ℕ^{m} ad ℕ^{n} lo accompagneremo da un commento che dichiara quali siano i registri di input e output (in un vero linguaggio di programmazione tale dichiarazione farebbe parte integrante del programma).

1.10 Esercizio. Si scrivano dei programmi per calcolare la somma e il prodotto di due numeri.

1.11 Esercizio. La funzione pred(x) = x −^{·} 1 (predecessore sugli interi non negativi) è definita da: pred(0) = 0 e pred(n + 1) = n. Si scriva un programma per calcolare pred.

Suggerimento: dati due registri a, b si definisca la macroistruzione (a, b) := (a + 1, a) come la successione di istruzioni b := a; a := a + 1. Inizialmente si assegnino ad a, b i valori 0, 0. Dato un numero x di cui si vuole calcolare il predecessore, si iteri la macroistruzione fino a quando a contiene il numero x. A quel punto b contiene il predecessore di x.

1.8 Concatenazione di programmi

1.12 Proposizione. Dati due programmi P = (I_{1}, …, I_{s}) e Q = (J_{1}, …, J_{k}), è possibile costruire un programma P; Q, detto la concatenazione di P e Q, il cui effetto è il seguente. Se P e Q definiscono le funzioni parziali sulle configurazioni di memoria P: ℕ^{∞} → ℕ^{∞}, e Q: ℕ^{∞} → ℕ^{∞}, allora P; Q definisce la funzione parziale Q ∘ P: ℕ^{∞} → ℕ^{∞}. In altre parole esequire P; Q equivale ad esequire prima P e poi Q.

Dimostrazione. Basta concatenare le istruzioni di P e Q ricalcolando gli indirizzi di ritorno delle istruzioni di salto condizionato per tener conto che la numerazione delle istruzioni è cambiata. Più precisamente si definisce P; Q come segue. Se nè P nè Q contengono istruzioni di salto condizionato, allora P; Q si ottiene semplicemente giustapponendo le istruzioni di Q a quelle di P, ovvero P; Q = (I_{1}, …, I_{s}, J_{1}, …, J_{k}). In presenza di istruzioni di tipo “if R_{m} = R_{n} go to q”, si pone P; Q = (I_{1}^{∗}, …, I_{s}^{∗}, J_{1}^{∗}, …, J_{k}^{∗}) dove I_{i}^{∗} e J_{i}^{∗} sono definite come segue. Se I_{i} e J_{i} non sono istruzioni di salto condizionato allora I_{i}^{∗} = I_{i} e J_{i}^{∗} = J_{i}. Se J_{i} è della forma “if R_{m} = R_{n} go to q”, allora J_{i}^{∗} è l’istruzione “if R_{m} = R_{n} go to q + s” (s è il numero di istruzioni di P). Se I_{i} è della forma “if R_{m} = R_{n} go to q”, allora I_{i}^{∗} = I_{i} eccetto che nel caso in cui q > s, nel qual caso I_{i}^{∗} è l’istruzione “if R_{m} = R_{n} go to s + 1” (per fare in modo che al termine della esecuzione di P, il calcolo riparta dalla prima istruzione di Q).

1.9 Programmi con istruzioni etichettate

Per evitare di dover ricalcolare gli indirizzi di rimando delle istruzioni di salto condizionato quando si concatenano due programmi, conviene etichettare le istruzioni e usare istruzioni di salto condizionato del tipo “se R_{i} = R_{j} vai a q”, dove q è l’etichetta dell’istruzione a cui si rimanda, anziché l’indice numerico che identifica la sua posizione nel programma. Nel seguito useremo liberamente la convenzione delle etichette (che possono essere anche essere dei numeri).

1.10 Diagrammi di flusso

Un altro modo, sostanzialmente equivalente alle etichette, è di usare delle freccie per indicare la prossima istruzione da eseguire. Questa idea dà luogo alla seguente definizione.

1.13 Definizione. Un diagramma di flusso è un modo di rappresentare in forma grafica un programma. Anziché rappresentare un programma come una successione P = (I_{1}, …, I_{s}) di istruzioni, si disegna un grafo in cui ogni nodo, eccetto due nodi speciali di INIZIO e FINE, è etichettato da una istruzione di assegnazione (della forma “R_{m} := 0” oppure “R_{n} := R_{n} + 1” oppure “R_{m} := R_{m}”) o con una istruzione di controllo (della forma “R_{m} = R_{n}?”). I nodi sono collegati da frecce nel modo seguente. Se un nodo contiene una istruzione di assegnazione, allora da quel nodo parte una freccia che punta al nodo contenente la prossima istruzione da eseguire. Da un nodo contenente una istruzione di controllo della forma “R_{m} = R_{n}?” partono due freccie etichettate SI e NO, dove la freccia SI punta al nodo contenente la prossima istruzione da eseguire nel caso la condizione di controllo sia verificata (ovvero se in quel momento i registri R_{m} ed R_{n} contengono lo stesso numero), e la freccia NO punta al nodo contenente la prossima istruzione da eseguire nel caso la condizione di controllo non sia verificata. (Le condizioni di controllo giocano lo stesso ruolo delle istruzioni di salto condizionato “if R_{m} = R_{n} go to q” precedentemente viste.) Dal nodo INIZIO parte una freccia che indica la prima istruzione da eseguire. Se seguendo le freccie si arriva al nodo FINE il calcolo termina. La semantica dei diagrammi di flusso si definisce in modo analogo alla semantica dei programmi. Ogni programma P = (I_{1}, …, I_{s}) può essere rappresentato in forma di diagramma di flusso. Viceversa si può dimostrare che per ogni diagramma di flusso si può scrivere un programma a lui equivalente (nel senso che definisce la stessa trasformazione di memoria).

1.14 Esercizio. 1. Si scriva un programma per calcolare la sottrazione tra due numeri naturali (definita uguale a zero se il numero da sottrarre è maggiore del numero da cui si sottrae).

2. Si scriva un programma per calcolare il massimo tra due numeri.

3. Consideriamo delle istruzioni di salto condizionato che controllino delle disuguaglianze anzichè delle uguaglianze (del tipo “se R_{i} ≥ R_{j} vai a q”). Si mostri che tali istruzioni possono essere simulate usando le usuali istruzioni di salto condizionato sulle uguaglianze (suggerimento: a ≥ b equivale a max(a, b) = a).

4. Si scriva un programma per calcolare il resto e il quozionte di una divisione e se ne dimostri la correttezza.

5. Si scriva un programma per calcolare il massimo comun divisore tra due numeri e se ne dimostri la correttezza.

6. Si scriva un programma per calcolare la funzione fattoriale.

1.11 Uso di funzioni predefinite

1.15 Definizione. All’interno di un programma o di un diagramma di flusso, oltre alle istruzioni base, possiamo usare delle macroistruzioni (o procedure) che corrispondono a programmi precedentemente definiti. In altre parole, se abbiamo già definito un programma P per calcolare una certa funzione parziale f: ℕ^{m} → ℕ^{n} usando i registri di input x_{1}, …, x_{n} e i registri di output y_{1}, …, y_{m}, possiamo utilizzare all’interno di un diagramma di flusso la macroistruzione (y_{1}, …, y_{m}) := f(x_{1}, …, x_{n}) la cui esecuzione ha il seguente effetto: supponendo che a_{1}, …, a_{m} siano i contenuti dei registri x_{1}, …, x_{n} prima della esecuzione della macroistruzione, allora dopo l’esecuzione della macroistruzione i contenuti dei registri y_{1}, …, y_{m} sono dati dal vettore di valori (b_{1}, …, b_{n}) = f(a_{1}, …, a_{m}), a condizione che f(a_{1}, …, a_{m}) ↓, mentre in caso contrario l’esecuzione dell’istruzione porta ad un calcolo non terminante.

La legittimità dell’uso delle macroistruzioni è espressa dalla seguente proposizione.

1.16 Proposizione. Un programma che fa uso di macroistruzioni (y_{1}, …, y_{m}) := f(x_{1}, …, x_{n}), dove f: ℕ^{m} → ℕ^{n} è una funzione parziale calcolata da un programma precedentemente definito, può essere trasformato in un programma che non fa uso di macroistruzioni.

Dimostrazione. Basta sostanzialmente sostituire la macroistruzione con la successione delle istruzioni che la definiscono, prendendosi cura di ridefinire in modo appropriato gli indirizzi a cui rimandano le istruzioni di salto condizionato (come nella dimostrazione della Propositione 1.12). È però necessario prendere alcune cautele nella scelta dei registri di lavoro. Se infatti la successione di istruzioni che definisce una data macroistruzione usasse come registri di lavoro gli stessi registri che vengono usati nel resto del programma per altri scopi, si potrebbero ovviamente avere degli effetti collaterali indesiderati. A ciò si può porre rimedio cambiando se necessario i registri di lavoro della macroistruzione.

1.17 Esempio. Sia f: ℕ^{n} → ℕ una funzione definita da un polinomio a coefficienti interi non negativi. Allora f è calcolabile e possiamo quindi usare la macroistruzione y := f(x_{1}, …, x_{n}).

2 Funzioni ricorsive parziali

Il nostro prossimo obbiettivo è di dare una caratterizzazione delle funzioni numeriche calcolabili senza far riferimento alle macchine a registri (o ad altr modelli idealizzati di calcolatore). Per funzione numerica intendiamo una funzione parziale da ℕ^{n} ad ℕ, per un certo n. Dimostreremo che le funzioni numeriche calcolabili coincidono cone le funzioni che possono essere generate, a partire da certe funzioni iniziali, applicando degli opportuni “operatori”. Un operatore è una funzione che porta funzioni parziali in funzioni parziali. Per generare tutte le funzioni numeriche calcolabili ci bastano tre tipi di operatori: la composizione, la ricursione primitiva, e la minimalizzazione. Chi abbia qualche familiarità con la programmazione in linguaggi tipo FORTRAM o PASCAL noterà la somiglianza tra la ricursione primitiva e i costrutti della forma “for i = 1 to n, do Q”, e tra la minimalizzazione e i costrutti della forma “while P do Q”.

2.1 Funzione ricorsiva parziale associata ad un programma

2.1 Definizione. Sia n ∈ ℕ e sia P un programma. La funzione parziale φ_{P}^{n} : ℕ^{n} → ℕ definita da P e da n è la funzione parziale calcolata dal programma P usando come registri di input R_{1}, …, R_{n} e come registro di output R_{0} (vedi Definizione 1.9). Più esplicitamente:

1. φ_{P}^{n} (a_{1}, …, a_{n}) = b se eseguendo il programma P a partire dallo stato iniziale in cui i primi n registri R_{1}, …, R_{n} contengono a_{1}, …, a_{n}, gli altri registri contengono 0, e il contatore di programma contiene 1, si determina un calcolo che si arresta dopo un numero finito di passi con b nel registro R_{0}.

2. φ_{P}^{n} (a_{1}, …, a_{n}) ↑ (indefinita) se partendo dallo stato iniziale sopra definito si determina un calcolo che non si arresta mai.

2.2 Definizione. Sia f: ℕ^{n} → ℕ una funzione parziale. Diciamo che f è ricorsiva parziale (o calcolabile parziale) se e solo se esiste un programma P tale che f = φ_{P}^{n}. Se inoltre dom(f) = ℕ^{n} diciamo che f è ricorsiva totale (o calcolabile totale).

Abbiamo quindi: Funzioni ricorsive totali = Funzioni ricorsive parziali ∩ Funzioni totali.

2.2 Composizione di funzioni ricorsive parziali

2.3 Proposizione. La composizione di funzioni ricorsive parziali è ricorsiva parziale. Più precisamente sia f(x⃗) = h(g_{1}(x⃗), …, g_{k}(x⃗)), dove si intende che f(x⃗) è definita se lo sono tutte le g_{i}(x⃗) e se (g_{1}(x⃗), …, g_{k}(x⃗)) ∈ dom(h). Se h, g_{1}, …, g_{k} sono funzioni ricorsive parziali, anche f è una funzione ricorsiva parziale.

Dimostrazione. Il seguente programma calcola f, facendo uso di macroistruzioni per calcolare h, g_{1}, …, g_{k}.

• Input x_{1}, …, x_{n} (questo è un commento per dire che usiamo x_{1}, …, x_{n} come registri di input).

• z_{1} := g_{1}(x_{1}, …, x_{n}); …; z_{k} := g_{k}(x_{1}, …, x_{n});

• y := h(z_{1}, …, z_{k});

• Output y.

2.4 Esempio. 1. f(x, y, z) = x + y + z è calcolabile in quanto si ottiene componendo con se stessa la funzione calcolabile x + y.

2. Se (x, y) ↦ f(x, y) è calcolabile, allora per ogni fissato b, x ↦ f(x, b) è calcolabile.

2.3 Ricursione primitiva

2.5 Definizione. Date due funzioni parziali h: ℕ^{n+2} → ℕ, g: ℕ^{n} → ℕ definiamo una funzione parziale f: ℕ^{n+1} → ℕ nel modo seguente.

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

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

dove

• (x⃗, 0) ∈ dom(f) sse x⃗ ∈ dom(g),

• (x⃗, y + 1) ∈ dom(f) sse (x⃗, y) ∈ dom(f) e (x⃗, y, f(x⃗, y)) ∈ dom(h).

Diciamo che f è ottenuta per ricursione primitiva da h e g. Si noti che se h, g sono funzioni totali anche f lo è. Ammettiamo il caso n = 0 in cui le variabili x⃗ sono mancanti. In tal caso g non è una funzione ma un numero g ∈ ℕ.

2.6 Teorema. Se h, g sono calcolabili, anche f è calcolabile. Dimostrazione. Il seguente programma calcola f usando dei sottoprogrammi per calcolare h e g.

1. Input x_{1}, …, x_{n}, y;

2. z := g(x⃗);

3. k := 0;

4. se k = y vai al punto 8 (altrimenti vai al prossimo punto);

5. z := h(x⃗, y, z);

6. k := k + 1;

7. vai al punto 4;

8. Output z.

2.3.1 Funzioni primitive ricorsive 2.7 Definizione. Una funzione è primitiva ricorsiva se si ottiene, a partire dalle seguenti funzioni iniziali, per composizione e ricursione primitiva applicate a funzioni precedentemente ottenute. Funzioni iniziali:

1. La funzione costante zero c_{0} : ℕ → ℕ.

2. La funzione successore s: ℕ → ℕ.

3. La funzione U_{i}^{n}: ℕ^{n} → ℕ che manda (x_{1}, …, x_{n}) in x_{i}. 2.8 Esercizio. Le seguenti funzioni sono primitive ricorsive. Somma, prodotto, sottrazione (definita uguale a zero se il numero da sottrare è più grande del numero da cui si sottrae), esponenziazione, quoziente e resto di una divisione, |x = y|, fattoriale, minimo, massimo, massimo comun divisore, minimo comune multiplo. 2.9 Fatto. Le funzioni primitive ricorsive sono un sottoinsieme proprio dell’insieme delle funzioni ricorsive totali.

2.4 Minimalizzazione

La minimalizzazione è un operatore μ che porta funzioni (ricorsive) parziali in funzioni (ricorsive) parziali. Abbiamo già visto un esempio di un simile operatore: la ricursione primitiva. A differenza della ricursione primitiva, la minimalizzazione può generare funzioni non totali anche quando viene applicata a funzioni totali. Definiamo dapprima la minimalizzazione applicata a funzioni totali, per poi vedere il caso generale.

2.10 Proposizione. Sia h: ℕ^{n+1} → ℕ una funzione totale e sia f(x⃗) = μz(h(x⃗, z) = 0) la funzione parziale definita come segue:

f(x⃗) = \{ \begin{matrix}min\{z | h(x⃗, z) = 0\} & se ∃z(h(x⃗, z) = 0) \\ ↑ & altrimenti \end{matrix}

Se h è ricorsiva (totale), allora f è parziale ricorsiva.

Dimostrazione. Il seguente programma calcola f, usando un sottoprogramma per calcolare h.

1. Input x⃗;

2. z := 0;

3. u := h(x⃗, z);

4. se u = 0 vai al punto 7;

5. z := z + 1;

6. vai al punto 3;

7. Output z.

La totalità di h garantisce che il punto 3 abbia sempre termine e che quindi fino a che non si trovi il valore di z desiderato si continui ad incrementare z di 1.

2.11 Corollario. Sia h: ℕ → ℕ una funzione ricorsiva totale invertibile. Allora l’inversa h^{−1}ℕ → ℕ è ricorsiva totale.

Dimostrazione. Basta osservare che h^{−1}(y) = μz(h(z) = y). Questo rientra nello schema della minimalizzazione scrivendo “h(z) = y” nella forma “|h(z) − y| = 0” (è facile vedere che |u − v| è una funzione ricorsiva, anzi addirittura primitiva ricorsiva).

Consideriamo ora la definizione dell’operatore di minimalizzazione μ quando venga applicato a funzioni parziali.

2.12 Proposizione. Sia h: ℕ^{n+1} → ℕ una funzione parziale e sia f(x⃗, y) = μz(h(x⃗, z) = 0) la funzione parziale definita come segue:

f(x⃗, y) = \{ \begin{matrix}min\{z | h(x⃗, z) = y ∧ ∀u < zh(x⃗, u) ↓\} & se tale z esiste \\ ↑ & altrimenti \end{matrix}

Se h è parziale ricorsiva, allora f è parziale ricorsiva.

Dimostrazione. Il programma per calcolare f è esattamente come nella Proposizione 2.10. Nelle presenti ipotesi h potrebbe non essere totale e quindi il programma potrebbe entrare in una condizione di non terminazione senza che z continui ad essere incrementato. Affinché il programma termini deve quindi accadere non soltanto che esista z tale che h(x⃗, z) = y, ma anche che il programma non entri in una condizione di non terminazione prima di trovare il minimo tale z. Ciò equivale a dire che deve essere verificata la condizione ∀u < zh(x⃗, u) ↓.

2.4.1 Funzioni μ-ricorsive di Kleene

2.13 Definizione. Una funzione parziale f: ℕ^{n} → ℕ è μ-ricorsiva se si ottiene, a partire dalle funzioni iniziali della Definizione 2.7, per composizione, ricursione primitiva e minimalizzazione, applicate a funzioni precedentemente ottenute.

2.14 Teorema. La classe delle funzioni μ-ricorsive è inclusa nella classe delle funzioni calcolabili da un programma per macchine a registri.

Dimostrazione. La classe delle funzioni calcolabili con una macchina a registri contiene le funzioni iniziali della Definizione 2.7 e abbiamo visto che gli operatori di composizione, ricursione primitiva e minimalizzazione non fanno uscire da tale classe.

Vedremo nel seguito che vale anche il viceversa: una funzione parziale f: ℕ^{n} → ℕ è μ-ricorsiva se e solo se è calcolabile da un programma per macchine a registri.

2.5 Altri operatori ricorsivi

Oltre alla composizione, alla ricursione primitiva, e alla minimalizzazione, ci sono molti altri operatori che applicati a funzioni ricorsive parziali generano funzioni ricorsive parziali. In questa sezione ne consideriamo alcuni particolarmente utili.

2.5.1 Sommatorie e produttorie limitate

2.15 Esercizio. Definiamo

1. f_{1}(x⃗, y) = Σ_{z<y}h(x⃗, y).

2. f_{2}(x⃗, y) = Π_{z<y}h(x⃗, y).

Se h è totale ricorsiva, anche f_{1}, f_{2} lo sono. Se h è primitiva ricorsiva, anche f_{1}, f_{2} lo sono.

2.5.2 Minimalizzazione limitata

2.16 Proposizione. Sia f(x⃗, y) = μz < y(h(x⃗, z) = 0) la funzione definita come segue:

f(x⃗, y) = \{ \begin{matrix}min\{z | z < y ∧ h(x⃗, z) = 0\} & se tale z esiste \\ y & altrimenti \end{matrix}

Se h è totale ricorsiva, anche f è totale ricorsiva. Se h è primitiva ricorsiva, anche h è primitiva ricorsiva.

Dimostrazione. Basta osservare che f(x⃗, y) = Σ_{v<y}Π_{u<v}sg(h(x⃗, u)) dove sg è la funzione ricorsiva primitiva definita da sg(0) = 0, sg(x + 1) = 1.

2.5.3 Ricursione sul decorso dei valori

2.17 Teorema. Data una funzione h: ℕ^{2} → ℕ sia f: ℕ → ℕ l’unica funzione tale che per ogni x, f(x) = h(x, ⟨f(0), …, f(x−1)⟩), dove ⟨f(0), …, f(x−1)⟩ ∈ ℕ indica la codifica della successione. 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)⟩)

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

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.

3 Tesi di Church

Ci sono due nozioni di funzione calcolabile. Una nozione informale secondo la quale una funzione è calcolabile se esiste un’algoritmo per calcolarla (lasciando indefinito il concetto intuitivo di algoritmo), e una nozione formale secondo la quale una funzione è calcolabile se esiste un programma per macchine a registri per calcolarla. La tesi di Church afferma che la nozione informale coincide con la nozione formale: tutte le funzioni intuitivamente calcolabili sono calcolabili con una macchina a registri (Church faceva riferimento alle macchine di Turing, ma si può dimostrare la loro equivalenza con le macchine a registri). La tesi di Church non è dimostrabile formalmente in quanto appunto collega una nozione formale con una nozione informale. La fiducia nella verità della tesi si basa sull’esperienza e sul fatto che diverse formalizzazioni della nozione di funzione calcolabile si sono dimostrate equivalenti.

Facendo appello alla tesi di Church possiamo ad esempio dimostrare:

3.1 Proposizione. Sia f(n) l’n-esima cifra dello sviluppo decimale di π. La funzione f è calcolabile con una macchina a registri.

Dimostrazione. Usiamo la serie di Hutton per π. Sia

h_{n} = \frac{(n!2^{n})^{2}}{(2n + 1)!} (\frac{12}{5} (\frac{1}{10})^{n} + \frac{14}{25} (\frac{1}{50})^{n}) .

Sia s_{k} = Σ_{n≤k}h_{n}. Si ha: s_{k} < π < s_{k} + (\frac{1}{10})^{k}. Questo ci fornisce un algoritmo per trovare le prime k cifre decimali di π e quindi per calcolare f (C’è qualche piccola difficoltà dovuta alla non unicità dello sviluppo decimale nel caso di sviluppi che finiscono con tutti nove da un certo punto in poi, ad esempio 0, 9999 … = 1. Tuttavia siccome π non è razionale, in particolare il suo sviluppo decimale non termina con tutti nove, e possiamo quindi trovare n > k tale che lo sviluppo di s_{n} non termina con tutti nove. Le prime k cifre dello sviluppo di π saranno allora uguali a quelle di s_{n}). Dalla tesi di Church segue che esiste un programma per macchine a registri per calcolare f.

Per dimostrare la proposizione senza fare appello alla tesi di Church dobbiamo scrivere esplicitamente il programma per macchine a registri che calcola f.

4 Predicati decidibili

La nozione di “predicato” o “relazione” può essere ricondotta alla nozione di insieme nel modo seguente. Dato un sottoinsieme M ⊆ ℕ^{m} scriviamo M(x_{1}, …, x_{m}) se e solo se (x_{1}, …, x_{m}) ∈ M. Se vale M(x_{1}, …, x_{m}) diciamo che (x_{1}, …, x_{m}) verifica il predicato (o relazione) M.

4.1 Definizione. Un insieme A ⊆ ℕ^{k} è decidibile se la sua funzione caratteristica χ_{A}: ℕ^{k} → {0, 1} è calcolabile (χ_{A} vale 1 su A e zero su ℕ^{k} − A). Un predicato è decidibile se l’insieme degli elementi che lo verificano è decidibile. Useremo “ricorsivo” come sinonimo di “decidibile”.

4.2 Proposizione. Se f: ℕ^{k} → ℕ è una funzione ricorsiva totale, allora il suo grafico {(x_{1}, …, x_{k}, y) | f(x_{1}, …, x_{k}) = y} è decidibile.

Dimostrazione. La funzione caratteristica del grafico di f è data dalla funzione

calcolabile 1 −^{·} |y − f(x_{1}, …, x_{k})|.

4.1 Definizioni per casi

4.3 Teorema. Definiamo

g(x⃗) = \{ \begin{matrix}f_{1}(x⃗) & se M_{1}(x⃗) \\ f_{2}(x⃗) & se M_{2}(x⃗) \end{matrix}

Se M_{1}, M_{2} sono predicati ricorsivi, e f_{1}, f_{2} sono funzioni calcolabili totali, allora g è una funzione calcolabile totale.

Dimostrazione. g(x⃗) = χ_{M_{1}}(x⃗)f_{1}(x⃗) + χ_{M_{2}}(x⃗)f_{2}(x⃗).

4.2 Algebra di Boole degli insiemi decidibili

4.4 Proposizione. L’unione o l’intersezione di due sottoinsiemi decidibili A, B di ℕ^{k} è decidibile. Il complemento ∼ A = ℕ^{k} − A di un sottoinsieme decidibile A di ℕ^{k} è decidibile.

Dimostrazione. χ_{A∩B}(x⃗) = min(χ_{A}(x⃗), χ_{B}(x⃗)), χ_{A∪B}(x⃗) = max(χ_{A}(x), χ_{B}(x⃗)), χ_{∼A}(x⃗) = 1 − χ_{A}(x⃗).

Una forma equivalente della proposizione è la seguente.

4.5 Proposizione. Dati due predicati decidibili A(x⃗) e B(x⃗) (su ℕ^{n}), la loro congiunzione A(x⃗)∧B(x⃗) è un predicato decidibile. Similamente la disgiunzione A(x⃗) ∨ B(x⃗) è decidibile, e la negazione ¬A(x⃗) è decidibile.

4.3 Quantificatori limitati

4.6 Proposizione. Definiamo

• M_{1}(x⃗, y) ≡ ∀z < yR(x⃗, z)

• M_{2}(x⃗, y) ≡ ∃z < yR(x⃗, z)

Se R è un predicato decidibile, anche M_{1} ed M_{2} sono predicati decidibili.

Dimostrazione. Per il primo punto osserviamo che χ_{M_{1}}(x⃗, y) = Π_{z<y}χ_{R}(x⃗, z). Per il secondo punto definiamo not(x) = 1 − x. Usando l’equivalenza ∃z < yR(x⃗, z) ⟺ ¬∀z < y¬R(x⃗, y) otteniamo χ_{M_{2}}(x⃗, y) = notΠ_{z<y}notχ_{R}(x⃗, z).

5 Codifiche

Definiamo il concetto di funzione calcolabile su domini diversi da ℕ.

5.1 Definizione. Una codifica di un insieme numerabile D è una funzione biunivoca α: D → ℕ, o più in generale una funzione iniettiva α: D → ℕ la cui immagine sia un sottoinsieme ricorsivo di ℕ. Sia f: D → D una funzione parziale. f è calcolabile rispetto alla codifica biunivoca α: D → ℕ se α ∘ f ∘ α^{−1} : ℕ → ℕ è una funzione ricorsiva parziale.

5.2 Esempio. Codifichiamo ℤ associando ad ogni n ≥ 0 il numero α(n) = 2n e ad ogni n < 0 il numero α(n) = −2n − 1. Rispetto a questa codifica, le funzioni di somma e prodotto su ℤ sono calcolabili, e il predicato x ≥ 0 è calcolabile.

5.1 Codifica delle stringhe

Un alfabeto è un insieme di simboli. Sia Σ = {a_{1}, …, a_{k}} un alfabeto finito. Sia Σ^{∗} = ⋃_{n∈ℕ} Σ^{n} l’insieme delle stringhe (successioni finite) su Σ. Indichiamo con λ ∈ Σ^{∗} la stringa vuota. Diamo una codifica α: Σ^{∗} → ℕ come segue.

• α(λ) = 0.

• α(a_{r_{0}} … a_{r_{m}}) = r_{0} + r_{1}k + … + r_{m}k^{m}.

Possiamo parlare di funzioni calcolabili su stringhe riferendoci a questa codifica.

5.2 Codifica delle coppie

5.3 Definizione. La funzione Coppia: ℕ^{2} → ℕ definita da Coppia(x, y) = 2^{x}(1 + 2y) − 1 è una corrispondenza biunivoca tra ℕ^{2} ed ℕ. Inoltre Coppia e le due funzioni inverse sono primitive ricorsive.

5.4 Definizione. La funzione Tripla: ℕ^{3} → ℕ definita da Tripla(x, y, z) = Coppia(x, Coppia(y, z)) è una corrispondenza biunivoca tra ℕ^{3} ed ℕ. Inoltre Tripla e le sue tre funzioni inverse sono primitive ricorsive.

5.3 Codifica delle successioni a supporto finito

Sia p(x) = lo x + 1-esimo numero primo. (Quindi p(0) = 2, p(1) = 3, p(2) = 5, . . ..)

5.5 Proposizione. Il predicato “x è primo” è primitivo ricorsivo. La funzione x ↦ p(x) è ricorsiva primitiva.

Dimostrazione. Il predicato “x è primo” è primitivo ricorsivo in quanto può essere espresso a partire da predicati primitivi ricorsivi usando i connettivi booleani e i quantificatori limitati nel modo seguente: ∀u, v ≤ x(uv = x → u = 1∨v = 1). Definiamo per ricursione primitiva p(0) = 2, p(n+1) = H(p(n)) dove H(x) = μy(y è primo ∧ y > x).

5.6 Definizione. Sia (a_{i} | i ∈ ℕ) una successione di numeri naturali. Diciamo che la successione ha supporto finito l’insieme degli i tali che a_{i} ≠ 0 è un insieme finito.

5.7 Definizione. Diamo una corrispondenza biunivoca tra numeri naturali e successioni a supporto finito come segue. Alla successione (a_{i} | i ∈ ℕ) corrisponde il numero c = Π_{i∈ℕ}p(i)^{a_{i}}, detto la codifica della successione. La produttoria è ben definita in quanto tutti i fattori eccetto un numero finito sono uguali ad 1.

Non ha senso chiedersi se la codifica sopra data sia μ-ricorsiva in quanto si tratta di una funzione da ℕ^{∞} ad ℕ. Possiamo però chiederci se la funzione che estrae l’i-esimo elemento da una successione è μ-ricorsiva, rispetto alla codifica data. Più precisamente abbiamo:

5.8 Proposizione. Sia (x)_{i} l’esponente di p_{i} nella scomposizione in fattori primi di x. In altre parole, se x = Π_{i}p(i)^{a_{i}} codifica la successione a supporto finito (a_{i} | i ∈ ℕ), allora (x)_{i} = a_{i} estrae l’i+1-esimo elemento della successione. La funzione (x, i) ↦ (x)_{i}, da ℕ^{2} ad ℕ, è primitiva ricorsiva.

Dimostrazione. Possiamo definire per minimalizzazione limitata (x)_{i} = μu < x¬(p(i)^{u+1} | x).

5.4 Codifica degli insiemi finiti

5.9 Definizione. Diamo una corrispondenza biunivoca tra numeri naturali e insiemi finiti di numeri naturali. All’insieme vuoto associamo 0. Ad un insieme di n elementi {a_{1}, …, a_{n}} associamo 2^{a_{1}} + … + 2^{a_{n}}.

5.5 Codifica delle successioni finite

5.10 Definizione. Diamo una corrispondenza biunivoca tra numeri naturali e successioni finite di numeri naturali. Ad una successione finita (a_{1}, …, a_{n}) di numeri naturali, associamo un numero naturale ⟨a_{1}, …, a_{n}⟩ ∈ ℕ, detto la codifica della successione, definito come segue.

• ⟨⟩ = 0;

• ⟨a_{1}⟩ = 2^{a_{1}};

• ⟨a_{1}, a_{2}, …, a_{n}⟩ = 2^{a_{1}}(1 + 2(⟨a_{2}, …, a_{n}⟩)

In altre parole: ⟨a_{1}, a_{2}, a_{3}, …, a_{n}⟩ = 2^{a_{1}} + 2^{a_{1}+a_{2}+1} + 2^{a_{1}+a_{2}+a_{3}+2} + … + 2^{a_{1}+a_{2}+...+a_{n}+n−1}.

La biunivocità della codifica si dimostra osservando che ⟨a_{1}, a_{2}, a_{3}, …, a_{n}⟩ è il numero che, nella rappresentazione in base due, inizia con a_{0} cifre uguali a zero, seguite dalla cifra 1, seguite da a_{1} cifre uguali a zero, seguita da 1, e così via.

5.11 Proposizione. Esistono funzioni ricorsive primitive lh: ℕ → ℕ, Cat: ℕ^{2} → ℕ, π: ℕ^{2} → ℕ tali che:

• lh(⟨a_{1}, …, a_{n}⟩) = n;

• Cat(⟨a_{1}, …, a_{n}⟩, ⟨b_{1}, …, b_{k}⟩) = ⟨a_{1}, …, a_{n}, b_{1}, …, b_{k}⟩;

• π(i, ⟨a_{1}, …, a_{n}⟩) = a_{i} se 1 ≤ i ≤ n.

Dimostrazione. Definiamo:

• lh(2^{x}(1 + 2y)) = 1 + lh(y), lh(2^{x}) = 1, lh(0) = 0;

• Cat(a, b) = a + 2^{lh(a)}b;

• π(0, n) = 0, π(1, 0) = 0, π(1, 2^{x}(1 + 2y)) = x, π(n + 2, 2^{x}(1 + 2y)) = π(n + 1, y).

Lasciamo al lettore la verifica che tali funzioni sono primitive ricorsive.

Talvolta, dato un insieme numerabile D, risulta più facile trovare una funzione iniettiva da D ad ℕ, che una biunivoca. La seguente proposizione può risultare utile per trovare codifiche biunivoche.

5.12 Esercizio. Sia A ⊂ ℕ un insieme infinito ricorsivo. Allora esiste una funzione ricorsiva biunivoca f: A → ℕ.

6 Predicati semidecidibili

6.1 Definizione. Diciamo che M ⊆ ℕ^{m} è semidecidibile, o ricorsivamente enumerabile, se e solo se esiste un predicato decidibile R ⊆ ℕ^{m+1} tale che M(x⃗) ≡ ∃yR(x⃗, y).

6.2 Proposizione. Se M è decidibile, è anche semidecidibile.

6.3 Proposizione. Se M ⊆ ℕ^{m} è un insieme semidecidibile, allora M è il dominio di una funzione ricorsiva parziale f: ℕ^{m} → ℕ.

Dimostrazione. Sia M(x⃗) ≡ ∃yR(x⃗, y) con R decidibile e definiamo f(x⃗) = μyR(x⃗, y).

Dimostreremo nel seguito che vale anche il viceversa: un insieme è semidecidibile se e solo se è il dominio di una funzione ricorsiva parziale.

6.1 Operazioni logiche tra predicati semidecidibili

6.4 Teorema. Se M(x⃗, y_{1}, …, y_{k}) è un predicato semidecidibile, allora lo è anche ∃y_{1}, …, y_{k}M(x⃗, y_{1}, …, y_{k}).

Dimostrazione. Essendo semidecidibile M(x⃗, y⃗) può essere scritto nella forma ∃zR(x⃗, y_{1}, …, y_{k}, z), dove R è decidibile. Dobbiamo mostrare la semidecidibilità del predicato ∃y_{1}, …, y_{k}∃zR(x⃗, y_{1}, …, y_{k}, z). A tal fine basta scriverlo nella forma equivalente ∃t(∃y_{1} < t … ∃y_{k} < t∃z < tR(x⃗, y, z)) osservando che la parte in parentesi è decidibile.

6.5 Teorema. L’unione e l’intersezione di due insiemi semidecidibili R, S ⊆ ℕ^{m}, è semidecidibile. Di conseguenza la congiunzione e la disgiunzione di due predicati semidecidibili è semidecidibile.

6.2 Teorema di Post

In contrasto con quanto avviene per i predicati decidibili, il complemento di un predicato semidecidibile non è in generale semidecidibile.

6.6 Teorema. Sia A ⊆ ℕ^{m}. Supponiamo che sia A che il suo complemento ℕ^{m} − A siano semidecidibili. Allora A è decidibile.

Dimostrazione. Possiamo scrivere A(x⃗) ≡ ∃yR(x⃗, y) ed ¬A(x⃗) ≡ ∃yS(x⃗, y) con R, S decidibili. Sia f la funzione totale ricorsiva f(x⃗) = μy(R(x⃗, y) ∨ S(x⃗, y)). Abbiamo A(x⃗) ≡ R(x⃗, f(x⃗)), e quindi A è decidibile.

6.7 Osservazione. Vale anche il viceversa: se A è decidibile allora sia A che il suo complemento sono semidecidibili (in quanto sono addirittura decidibili).

6.3 Quantificatori limitati su predicati semidecidibili

6.8 Proposizione. Se R(x⃗, z) è un predicato semidecidibile, anche i predicati ∀z < yR(x⃗, z) e ∃z < yR(x⃗, z) sono semidecidibili.

Dimostrazione. Sia R(x⃗, z) ≡ ∃tP (x⃗, z, t), con P ricorsivo.

Dobbiamo mostrare che il predicato ∀z < y∃tP (x⃗, z, t) è semidecidibile. Basta a tal fine scriverlo nella forma equivalente ∃s(∀z < y∃t < sP (x⃗, z, t)), e osservare che la parte in parentesi è decidibile.

Dobbiamo ora mostrare che il predicato ∃z < y∃tR(x⃗, z, t) è semidecidibile. Basta a tal fine scriverlo nella forma equivalente ∃z∃t(z < y ∧ R(x⃗, z, t)) e usare il Teorema 6.4

Riassumendo: sia i predicati decidibili che quelli semidecidibili sono stabili per congiunzioni, disgiunzioni e quantificatori limitati. I predicati decidibili sono stabili per negazioni. I predicati semidecidibili sono stabili per quantificazione esistenziale.

6.4 Enumerazioni ricorsive degli insiemi semidecidibili

IL seguente teorema giustifica il nome “ricorsivamente enumerabile” come sinonimo di “semidecidibile”.

6.9 Teorema. A ⊆ ℕ è semidecidibile se e solo se è vuoto oppure è della forma A = {f(n) | n ∈ ℕ} per qualche funzione ricorsiva totale f: ℕ → ℕ.

Dimostrazione. Se A è vuoto è sia semidecidibile che ricorsivamente enumerabile, quindi assumiamo A non vuoto e fissiamo un elemento a ∈ A.

Sia A semidecidibile. Allora A = {x | ∃yR(x, y)} per qualche predicato ricorsivo R. La funzione binaria

g(x, y) = \{ \begin{matrix}x & se R(x, y) \\ a & altrimenti \end{matrix}

è calcolabile totale e ha come immagine A. Per finire definiamo una funzione calcolabile totale unaria f che ha la stessa immagine. Basta porre f(x) = g((x)_{0}, (x)_{1})), dove (x)_{0} e (x)_{1} sono gli esponenti di 2 e 3 nella scomposizione in primi di x (vedi Definizione 5.7).

Per il verso opposto sia A = Im(f) con f: ℕ → ℕ calcolabile totale. Allora y ∈ A se e solo se ∃x(f(x) = y). Il predicato in parentesi è decidibile, quindi A è semidecidibile.

6.5 Enumerazioni ricorsive crescenti degli insiemi decidibili

6.10 Teorema. Sia A ⊆ ℕ un insieme infinito. A è ricorsivo se e solo se esiste una funzione ricorsiva totale crescente f: ℕ → ℕ tale che A = Im(f).

Dimostrazione. Supponiamo che A sia ricorsivo e definiamo f(0) = min A, f(n+ 1) = min x(x ∈ A ∧ x > f(n)). Allora f è ricorsiva ed ha A come immagine.

Viceversa supponiamo A = Im(f) con f crescente. Allora y ∈ A se e solo se ∃n ≤ y(f(n) = y). Ne segue che A è ricorsivo.

6.11 Teorema. Ogni insieme ricorsivamente enumerabile infinito A ⊆ ℕ ha un sottoinsieme infinito ricorsivo.

Dimostrazione. Sia A = Im(f). Definiamo g(0) = f(0), g(n + 1) = f(k(n)), dove k(n) = μy(f(y) > g(n)). Poiché g è crescente, l’insieme Im(g) ⊆ A è ricorsivo.

7 Codifica dei programmi

Fissiamo una codifica Coppia: ℕ^{2} → ℕ delle coppie, e una codifica Tripla: ℕ^{3} → ℕ delle triple.

7.1 Definizione. Ogni istruzione per macchina a registri può essere codificata con un numero naturale come segue.

Istruzione  Codifica
R_{n} := 0  4n
R_{n} := R_{n+1}  4n + 1
R_{m} := R_{n}  4Coppia(m, n) + 2
if R_{m} = R_{n} go to q 4Tripla(m, n, q) + 3

Un programma P = (I_{1}, I_{2}, I_{3}, …, I_{n}) è codificato da ⟨a_{1}, a_{2}, a_{3}, …, a_{n}⟩ = 2^{a_{1}} + 2^{a_{1}+a_{2}+1} + 2^{a_{1}+a_{2}+a_{3}+2} + … + 2^{a_{1}+a_{2}+...+a_{n}+n−1} (vedi Definizione 5.10), dove a_{i} ∈ ℕ è la codifica dell’istruzione I_{i}.

La codifica dei programmi sopra descritta è una corrispondenza biunivoca tra programmi e numeri naturali.

7.2 Definizione. Indichiamo con P_{e} il programma codificato da e. Dato n ∈ ℕ, sia ϕ_{e}^{n}: ℕ^{n} → ℕ la funzione parziale di n argomenti calcolata dal programma P_{e} usando come registri di input R_{1}, …, R_{n} e come registro di output R_{0}. Sia ϕ_{e} = ϕ_{e}^{1}

7.1 Una funzione non calcolabile

7.3 Teorema. Sia

f(n) = \{ \begin{matrix}ϕ_{n}(n) + 1 & se ϕ_{n}(n) ↓ \\ 0 & altrimenti \end{matrix}

La funzione f non è calcolabile.

Dimostrazione. Se f è calcolabile esiste e ∈ ℕ tale che f = ϕ_{e}. Per come è definita chiaramente f è una funzione totale. Quindi ϕ_{e}(e) è definita. Di nuovo per la definizione di f abbiamo allora f(e) = ϕ_{e}(e) + 1. Questo contraddice f = ϕ_{e}.

Vedremo, come conseguenza del “teorema della funzione universale”, che la funzione n ↦ ϕ_{n}(n) è una funzione calcolabile parziale. Quindi il motivo per cui la funzione sopra definita non è calcolabile deve risiedere nel fatto che il predicato ϕ_{n}(n) ↓ che discrimina i due casi non è decidibile.

8 Programmi universali

8.1 Forma normale di Kleene

8.1 Definizione. Scriviamo ϕ_{e}(x_{1}, …, x_{n}) ↓_{≤t} se e solo se il calcolo di P_{e} su input x_{1}, …, x_{n} termina in al più t passi. Scriviamo “ϕ_{e}(x_{1}, …, x_{n}) ↓_{≤t}= y” se termina dopo al più t passi con output y (assumiamo che i registri di input siano R_{1}, …, R_{n} e il registro di output sia R_{0}). Usiamo ϕ_{e}(x_{1}, …, x_{n}) ↓ y come notazione equivalente a ϕ_{e}(x_{1}, …, x_{n}) = y.

8.2 Teorema. (Kleene) I seguenti insiemi sono primitivi ricorsivi.

1. {(e, x_{1}, …, x_{n}, y, t) | ϕ_{e}(x_{1}, … x_{n}) ↓_{≤t}= y};

2. {(e, x_{1}, …, x_{n}, t) | ϕ_{e}(x_{1}, … x_{n}) ↓_{≤t}}.

Per dimostrare la ricorsività degli insiemi sopra dati facciamo uso della tesi di Church. Un algoritmo per risolvere il problema è il seguente: si esegua il programma P_{e} per t passi e si determini se dopo t passi il calcolo è terminato. In caso affermativo si determini il valore di uscita. Daremo nel seguito una dimostrazione che non fa uso della tesi di Church e che fornirà l’ulteriore informazione che gli insiemi dati sono primitivi ricorsivi.

8.3 Teorema. (Forma normale di Kleene) Sia n ∈ ℕ. Esiste una funzione primitiva ricorsiva U e un predicato primitivo ricorsivo T^{n} tale che 1. ϕ_{e}^{n}(x_{1}, …, x_{n}) ↓ sse ∃zT^{n}(e, x_{1}, …, x_{n}, z).

2. ϕ_{e}^{n}(x_{1}, …, x_{n}) = U(μzT^{n}(e, x_{1}, …, x_{n}, z).

Dimostrazione. Definiamo T^{n}(e, x_{1}, …, x_{n}, z) come ϕ_{e}(x_{1}, …, x_{n}) ↓_{(z)_{1}}= (z)_{0}, e U(z) = (z)_{0}.

Il predicato T^{n}(e, x_{1}, …, x_{n}, z) è detto predicato di Turing, ed esprime il fatto che z codifica l’output e il tempo di calcolo del programma P_{e} su input x_{1}, …, x_{n} (quindi se z esiste la macchina si arresta). La funzione U estrae l’output da tale codifica.

8.4 Corollario. Un insieme A ⊆ ℕ^{n} è semidecidibile se e solo se è il dominio di una funzione ricorsiva parziale.

Dimostrazione. Dal primo punto del Teorema 8.3 segue, fissando e, che il dominio di una funzione parziale ricorsiva è semidecidibile.

Viceversa abbiamo già visto che ogni predicato semidecidibile ∃zR(x⃗, z) (con R decidibile) è il dominio di una funzione parziale ricorsiva f(x⃗) = μzR(x⃗, z).

8.5 Corollario. Sia W_{x} = dom(ϕ_{x}^{1}). Allora la successione W_{0}, W_{1}, W_{2}, … enumera tutti e soli i sottoinsiemi semidecidibili di ℕ.

8.6 Corollario. Una funzione parziale f: ℕ^{k} → ℕ è calcolabile con una macchina a registri se e solo se è μ-ricorsiva.

Dimostrazione. Sia f calcolabile da una macchina a registri. Sia e ∈ ℕ il codice della macchina. Allora f(x⃗) = ϕ_{e}(x⃗) = U(μzT^{n}(e, x⃗, z)). Essendo U, T^{n} primitivi ricorsivi, ne segue che f è μ-ricorsiva. Il verso opposto è il Teorema 2.14

8.7 Osservazione. La dimostrazione del corollario mostra che ogni funzione μricorsiva può essere definita usando una sola volta l’operatore di minializzazione.

Fissato e ∈ ℕ, la funzione x ↦ ϕ_{e}(x) è ovviamente calcolabile, essendo la funzione calcolata dal programma con codice e. Il seguente risultato mostra che (e, x) ↦ ϕ_{e}(x) è anch’essa calcolabile. Usando la tesi di Church possiamo ragionare nel modo seguente. Per calcolare tale funzione su input (e, x) si decodifichi e per trovare il programma P_{e} corrispondente, e poi si calcoli P_{e} su input x.

8.8 Corollario. (Funzione universale) La funzione parziale ψ_{U}^{n}: ℕ^{n+1} → ℕ, definita da ψ_{U}^{n}(e, x_{1}, …, x_{n}) = ϕ_{e}^{n}(x_{1}, …, x_{n}), è ricorsiva parziale.

Dimostrazione. ψ_{U}^{n}(e, x_{1}, …, x_{n}) = U(μzT^{n}(e, x_{1}, …, x_{n}, z).

8.9 Esercizio. (non esistenza di un polinomio universale) Fissiamo una codifica α: ℤ[x] → ℕ dei polinomi. Sia h: ℕ^{2} → ℕ definita da h(e, x) = p(x), dove p è il polinomio con codice e. Si mostri che h non può essere una funzione polinomiale.

8.10 Esercizio. (non esistenza di una funzione primitiva ricorsiva universale) Fissiamo una numerazione α: ℕ → F delle funzioni primitive ricorsive di un argomento. Sia h: ℕ^{2} → ℕ definita da h(e, x) = q(x), dove q è la funzione primitiva ricorsiva con codice e. Si mostri che q non può essere una funzione primitiva ricorsiva.

Per dimostrare il Teorema 8.2 abbiamo bisogno di codificare la successione degli stati che costituisce il calcolo di una macchina a registri. Ciò viene fatto nelle sezioni seguenti.

8.2 Dimostrazione del teorema di Kleene

8.11 Definizione. La configurazione di memoria di una macchina a regitri in un dato istante è codificata dal numero c = Π_{i=0}^{∞}p(i)^{r_{i}}, dove r_{i} ∈ ℕ è il contenuto del registro R_{i}. Affinché la produttoria abbia senso si assume che al più un numero finito di registri contenga un numero diverso da zero.

8.12 Lemma. Sia I una istruzione per macchina a registri. Definiamo [I]: ℕ → ℕ nel modo seguente. Se c ∈ ℕ codifica una configurazione di memoria, [I](c) ∈ ℕ codifica la nuova configurazione di memoria dopo l’esecuzione di I. Sia ⌈I⌉ ∈ ℕ la codifica dell’istruzione I. La funzione Mem: ℕ^{2} → ℕ definita da Mem(⌈I⌉, x) = [I](x) è primitiva ricorsiva.

Dimostrazione. Definiamo Mem(i, x) per casi, ricordando la Definizione 7.1. Se i = 4n (i codifica R_{n} := 0), allora Mem(i, x) = _{\frac{x}{p_{0}^{(x)_{0}}}} · p_{0}^{(x)_{n}}. Osserviamo

che n è una funzione primitiva ricorsiva di i (n = i/4).

Se i = 4n + 1 (i codifica R_{n} := R_{n+1}), Mem(i, x) = x · p_{n}. Osserviamo che n è una funzione primitiva ricorsiva di i.

Se i = 4Coppia(m, n) + 2 (i codifica R_{m} := R_{n}), Mem(i, x) = \frac{x}{p_{m}^{(x)m}} · p_{m}^{(x)_{n}}. Osserviamo che m, n sono funzioni primitive ricorsive di i.

Se i = 4Tripla(m, n, q)+3 (i codifica if R_{m} = R_{n} go to q), allora Mem(i, x) = x.

I quattro casi possono essere distinti da predicati primitivi ricorsivi P_{0}, …, P_{3} (dove P_{k}(i) ⟺ i è congruo ad k modulo 4), e le funzioni coinvolte nei vari casi sono primitive ricorsive. Possiamo concludere che Mem è primitiva ricorsiva.

8.13 Definizione. Ricordiamo che lo stato di una macchina a registri in un dato istante è dato dalla configurazione di memoria e dal contenuto del contatore di programma. Codifichiamo lo stato con il numero Coppia(c, j) ∈ ℕ, dove c codifica la configurazione di memoria e j è il contenuto del contatore di programma.

8.14 Lemma. Il predicato “s codifica uno stato di arresto del programma P_{e}” è un predicato primitivo ricorsivo nelle variabili e, s.

Dimostrazione. Dato s = Coppia(c, j), possiamo ottenere c, j come funzioni primitive di s (ad esempio j = μx(∃c′, j′ ≤ s(s = Coppia(c′, j′) ∧ x = j′))). Ora basta notare che s codifica uno stato di arresto se e solo se j = 0 o j ≥ lh(e), dove lh(e) è la lunghezza del programma P_{e}.

8.15 Lemma. Sia I una istruzione per macchina a registri. Definiamo Next: ℕ^{2} → ℕ nel modo seguente. Se s = Coppia(c, j) ∈ ℕ codifica uno stato non di arresto, s′ = Next(e, s) ∈ ℕ è la codifica del nuovo stato dopo l’esecuzione della j-esima istruzione del programma P_{e}. Se s codifica uno stato di arresto Next(e, s) = s. La funzione Next è primitiva ricorsiva.

Dimostrazione. Possiamo dare una definizione primitiva ricorsiva di Next(e, s) nel modo seguente. Osserviamo che, ponendo s = Coppia(c, j), possiamo ricavare c, j come funzioni ricorsive di s. Quindi nella definizione di Next(e, s) possiamo liberamente usare c, j. Distinguamo i seguenti casi.

Se j = 0 o j > lh(e) (cioè s codifica uno stato di arresto) allora Next(e, s) = s. Se invece 1 ≤ j ≤ lh(e), distinguiamo i seguenti sottocasi, ricordando che

π(j, e) estrae il codice della j-esima istruzione dal programma P_{e}.

• Se π(j, e) = 4n (cioè se la j-esima istruzione è R_{n} := 0), allora Next(e, s) = Coppia([R_{n} := 0](c), j+1) (per il Lemma 8.12 = Coppia(Mem(π(j, e), c), j+ 1), una funzione primitiva ricorsiva di e, s);

• Se π(j, e) = 4n+1 (la j-esima istruzione è R_{n} := R_{n}+1), allora Next(e, s) = Coppia([R_{n} := R_{m}](c), j + 1);

• Se π(j, e) = 4Coppia(m, n) + 2 (la j-esima istruzione è R_{n} := R_{m}), allora Next(e, s) = Coppia([R_{n} := R_{m}](c), j + 1);

• Se π(j, e) = 4Tripla(m, n, q) + 3 (la j-esima istruzione è if R_{n} = R_{m} go to q), allora

Next(e, s) = \{ \begin{matrix}Coppia(c, q) & se (c)_{m} = (c)_{m} \\ Coppia(c, j + 1) & altrimenti \end{matrix}

I predicati che distinguono i casi sono predicati primitivi ricorsivi in e, s. Le funzioni coinvolte nei vari casi sono anch’esse primitive ricorsive in e, s. Ne concludiamo che Next è primitiva ricorsiva.

8.16 Lemma. Sia Input^{n}: ℕ^{n} → ℕ la funzione così definita. Input^{n}(a_{1}, …, a_{n}) = s se e solo se s codifica lo stato iniziale di una macchina registri su input a_{1}, …, a_{n}, ovvero lo stato in cui il contatore di programma contiene 1, i registri di memoria R_{1}, …, R_{n} contengono rispettivamente i numeri a_{1}, …, a_{n}, e gli altri registri contengono 0. La funzione Input è primitiva ricorsiva.

Dimostrazione. Per n fissato, la funzione h(a_{1}, …, a_{n}) = ⟨a_{1}, …, a_{n}⟩ è primitiva ricorsiva. Definiamo Input^{n}(a_{1}, …, a_{n}) = Coppia(h(a_{1}, …, a_{n}), 1).

8.17 Lemma. Sia n ∈ ℕ e sia Stato^{n}: ℕ^{n+2} → ℕ la funzione definita nel modo seguente. Stato(e, x_{1}, …, x_{n}, t) = s′ se s′ codifica lo stato in cui si trova, dopo t passi di calcolo, una macchina con programma P_{e} che viene fatta partire con input x_{1}, …, x_{n}. La funzione Stato è primitiva ricorsiva.

Dimostrazione. . Definiamo per ricursione primitiva Stato(e, x_{1}, …, x_{n}, 0) = Input(x_{1}, …, x_{n}), Stato(e, x_{1}, …, x_{n}, t + 1) = Next(e, Stato(e, x_{1}, …, x_{n}, t)).

8.18 Lemma. Sia Output: ℕ → ℕ la funzione così definita. Output(s) = n se e solo se s codifica uno stato contenente n nel registro di output R_{0}. La funzione Output è primitiva ricorsiva.

Dimostrazione. Output(s) = n se e solo se s = Coppia(c, i) e n = (c)_{0}.

8.19 Teorema. Il predicato ϕ_{e}(x_{1}, …, x_{n}) ↓_{≤t} è un predicato primitivo ricorsivo nelle variabili e, x_{1}, …, x_{n}, t.

Dimostrazione. Tale predicato equivale a: “Stato(e, x_{1}, …, x_{n}, t) codifica uno stato di arresto”.

8.20 Teorema. Il predicato ϕ_{e}(x_{1}, …, x_{n}) ↓_{≤t}= y è un predicato primitivo ricorsivo nelle variabili e, x_{1}, …, x_{n}, t, y.

Dimostrazione. Tale predicato equivale alla congiunzione ϕ_{e}(x_{1}, …, x_{n}) ↓_{≤t} e y = Output(Stato(e, x_{1}, …, x_{n}, t)).

9 Il problema della fermata

9.1 Definizione. Sia K_{0} = {x | ϕ_{x}(x) ↓} e K = {(x, y) | ϕ_{x}(y) ↓}.

9.2 Proposizione. K e K_{0} sono semidecidibili.

Dimostrazione. (x, y) ∈ K se e solo se ∃t(ϕ_{x}(x) ↓_{≤t}), e poiché il predicato in parentesi è decidibile otteniamo la semidecidibilità di K. Inoltre x ∈ K_{0} se e solo se (x, x) ∈ K, quindi anche K_{0} è semidecidibile.

9.3 Teorema. (Indecidibilità del problema della fermata) K e K_{0} non sono decidibili.

Dimostrazione. Sia W_{x} = dom(ϕ_{x}^{1}) ⊆ ℕ. Si osservi che x ∈ K_{0} ⟺ x ∈ W_{x}. Se K_{0} fosse decidibile lo sarebbe anche il suo complemento, e quindi il predicato x ∉ W_{x} sarebbe decidibile. Ma allora a maggior ragione {x | x ∉ W_{x}} sarebbe semidecidibile e coinciderebbe dunque con W_{e} per qualche e. Avremmo allora x ∉ W_{x} ⟺ x ∈ W_{e}. Ponendo x = e si raggiunge un assurdo. Quindi K_{0} non è decidibile.

D’altra parte se K fosse decidibile lo sarebbe anche K_{0} in quanto x ∈ K_{0} se e solo se (x, x) ∈ K.

Un problema strettamente connesso al problema della fermata è il problema della totalità.

9.4 Teorema. L’insieme T OT = {x | ϕ_{x}è totale } non è decidibile.

Dimostrazione. Definiamo per casi

f(n) = \{ \begin{matrix}ϕ_{n}(n) + 1 & se ϕ_{n} è totale \\ 0 & altrimenti \end{matrix}

Si osservi che f è totale. Inoltre f non è calcolabile, perchè se f = ϕ_{e} otterremmo f(e) = f(e) + 1. D’altra parte, per il teorema della funzione universale, n ↦ ϕ_{n}(n) è calcolabile. Ne segue che il predicato che distingue i due casi non è decidibile.

Possiamo rafforzare il teorema:

9.5 Teorema. L’insieme T OT = {x | ϕ_{x}è totale } non è semidecidibile.

Dimostrazione. Se T OT fosse semidecidibile sarebbe l’immagine di una funzione totale ricorsiva h: ℕ → ℕ. Sia f(x) = ϕ_{h(x)}(x) + 1. Visto che h(x) ∈ T OT, f è totale. Inoltre per il teorema della funzione universale f è ricorsiva. Ne segue che f = ϕ_{e} con e ∈ T OT = Im(h). Sia e = h(n). Per definizione di f abbiamo f(n) = ϕ_{h(n)}(n) + 1, ma d’altra parte per definizione di n abbiamo f(n) = ϕ_{h(n)}, da cui l’assurdo f(n) = f(n) + 1. (Si noti che questa uguaglianza non produrrebbe una contraddizione se f non fosse definita in n.)

Osserviamo che mentre i predicati semidecidibili si possono scrivere nella forma ∃yR(x⃗, y) con R decidibile, per il predicato x ∈ T OT serve un quantificatore in più: x ∈ T OT se e solo se ∀u∃t(ϕ_{x}(u) ↓_{≤t}), dove il predicato in parentesi è decidibile.

10 Riducibilità molti-uno

10.1 Definizione. Siano A ⊆ ℕ^{m}, B ⊆ ℕ^{n}. Diciamo A ≤_{m} B (A si riduce a B tramite una riduzione molti-uno) se esiste f: ℕ^{m} → ℕ^{n} calcolabile totale (f è calcolabile se lo sono tutte le sue n funzioni componenti f_{i}: ℕ^{m} → ℕ), tale che ∀x ∈ ℕ^{m} si ha x ∈ A sse f(x) ∈ B.

10.2 Teorema. Se A ≤_{m} B e B è decidibile, allora A è decidibile.

Dimostrazione. χ_{A}(x) = χ_{B}(fx).

Intuitivamente, se A ≤_{m} B, allora B è almeno altrettanto complicato di A.

10.3 Corollario. Se A ≤_{m} B e A è indecidibile, allora B è decidibile. In particolare se K_{0} ≤_{m} B, allora B è indecidibile.

10.4 Esempio. K_{0} ≤_{m} K.

Dimostrazione. Sia g: ℕ → ℕ^{2}, x ↦ (x, x). Abbiamo x ∈ K_{0} sse g(x) ∈ K.

Quindi la indecidibilità di K segue da quella di K_{0}.

10.5 Osservazione. Un difetto della riducibilità molti-uno, è che in generale un insieme non si riduce molti-uno al suo complemento, nonostante a livello intuitivo se abbiamo un metodo per decidere l’appartenenza ad un insieme abbiamo anche un metodo per decidere l’appartenenza al suo complemento. Esistono altri tipi di riduzione tra problemi che non hanno questo difetto (riduzione di Turing).

10.6 Definizione. Un insieme B è r.e.-completo, se è ricorsivamente enumerabile (= semidecidibile) e se per ogni insieme ricorsivamente enumerabile A si ha A ≤_{m} B.

Vedremo che esistono insiemi r.e.-completi: K e K_{0} sono due esempi. Per dimostrarlo avremo bisogno del ”teorema s.m.n.”.

11 Il teorema s-m-n e la completezza del problema della fermata

Il teorema s-m-n è un utile strumento per dimostrare la riducibilità molti-uno tra vari problemi.

11.1 Teorema. Esiste una funzione totale ricorsiva s: ℕ^{2} → ℕ tale che, per ogni x, y,

ϕ_{e}^{2}(x, y) = ϕ_{s(e,x)}^{1}(y)

Più in generale, dati m, n, esiste una funzione totale ricorsiva s: ℕ^{m+1} → ℕ tale che

ϕ_{e}^{m+n}(x⃗, y⃗) = ϕ_{s(e,x⃗)}^{n}(y⃗)

dove x⃗ = (x_{1}, …, x_{m}) ∈ ℕ^{m} e y⃗ = (y_{1}, …, y_{n}) ∈ ℕ^{n}.

(In effetti s si può scegliere addirittura primitiva ricorsiva.)

Dimostrazione. Dimostriamo il teorema nel caso m = n = 1, il caso generale è analogo. É chiaro che, fissato x, la funzione di un argomento y ↦ ϕ_{e}^{2}(x, y) è calcolabile, e quindi esisterà un programma P_{a}, dipendente da x e da e, che calcola tale funzione. Il teorema asserisce che a si può trovare come funzione totale ricorsiva di x ed e.

Veniamo ai dettagli. Ricordiamo che ϕ_{e}^{2} è la funzione definita dal programma P_{e} usando come registri di input R_{1} ed R_{2} e ϕ_{a}^{1}(x) è la funzione definita dal programma P_{a} usando come registro di input R_{1} (in entrambi i casi il registro di output è R_{0}). Definiamo s(e, x) come la codifica del programma seguente:

• Input R_{1} (questo è un commento, non fa parte del programma);

• R_{2} := R_{1};

• R_{1} := x;

• P_{e} dove P_{e} è il programma con codice e e R_{1} := x è una macroistruzione il cui effetto è di memorizzare il numero x nel registro R_{1}.

La codifica di questo programma è data da una funzione primitiva ricorsiva applicata alle codifiche delle macroistruzioni che lo compongono. Per finire basta osservare che la codifica della macroistruzione R_{1} := x è una funzione ricorsiva primitiva di x. (Per x > 0 possiamo definire induttivamente R_{1} := x come R_{1} := x − 1; R_{1} := R_{1} + 1.)

11.2 Corollario. Data una funzione parziale ricorsiva f(x⃗, y⃗) esiste una funzione totale ricorsiva h(x⃗) tale che f(x⃗, y⃗) = ϕ_{h(x⃗)}(y⃗).

Dimostrazione. Sia f(x⃗, y⃗) = ϕ_{e}^{m+n}(x⃗, y⃗) e sia h(x⃗) = s(e, x⃗).

11.3 Teorema. (Completezza del problema della fermata) Sia A un insieme semidecidibile. Allora A ≤_{m} K_{0}.

Dimostrazione. Abbiamo x ∈ A ⟺ ∃yR(x, y), per un certo predicato ricorsivo R. Definiamo la funzione parziale ricorsiva f(x, y) = μyR(x, y). Allora f(x, y) ↓ (per ogni y) se e solo se x ∈ A. Per il teorema s-m-n esiste una funzione ricorsiva totale h tale che f(x, y) = ϕ_{h(x)}(y). Ne segue che x ∈ A se e solo se ϕ_{h(x)}(h(x)) ↓, e cioè se e solo se h(x) ∈ K_{0}.

12 Equivalenza tra programmi

12.1 Teorema. L’insieme {x | ϕ_{x} = 0} è indecidibile.

Dimostrazione. Definiamo

f(x, y) = \{ \begin{matrix}0 & se ϕ_{x}(x) ↓ \\ ↑ & altrimenti \end{matrix}

Per il teorema della funzione universale x ↦ ϕ_{x}(x) è calcolabile. Per il teorema s-m-n esiste una funzione ricorsiva totale k: ℕ → ℕ tale che f(x, y) = ϕ_{k(x)}(y). Abbiamo ϕ_{x}(x) ↓ sse ϕ_{k(x)} = 0. Quindi la funzione k è una riduzione di K_{0} a {x | ϕ_{x} = 0}, mostrando che quest’ultimo è indecidibile.

12.2 Corollario. L’insieme {(x, y) | ϕ_{x} = ϕ_{y}} è indecidibile.

Dimostrazione. Sia e tale che ϕ_{e} è la funzione costante zero. Allora x ∈ 𝕂_{0} ⟺ (x, e) ∈ {(x, y) | ϕ_{x} = ϕ_{y}}. Pertanto la funzione h(x) = (x, e) riduce K_{0} all’insieme dato.

12.3 Definizione. Sia A ⊆ ℕ. Diciamo che A è estensionale se ϕ_{x} = ϕ_{y} e x ∈ A implica y ∈ A.

Ogni insieme estensionale determina una classe di funzioni calcolabili e viceversa.

12.1 Teorema di Rice

12.4 Teorema. (Rice) Sia A ⊆ ℕ un insieme estensionale diverso da ∅ e da ℕ. Allora A è indecidibile.

Dimostrazione. Sia P_{e} un programma per la funzione sempre indefinita. Distinguiamo due casi seconda che e ∈ A o e ∉ A.

Primo caso. Supponiamo e ∉ A. Scegliamo a ∈ A e dia g(x) = ϕ_{a}(x). Definiamo

f(x, y) = \{ \begin{matrix}g(y) & se ϕ_{x}(x) ↓ \\ ↑ & altrimenti \end{matrix}

Per il teorema s-m-n (e il teorema della funzione universale) esiste una funzione calcolabile totale k: ℕ → ℕ tale che f(x, y) = ϕ_{k(x)}(y). Abbiamo ϕ_{x}(x) ↓ sse ϕ_{k(x)} = g. Ne segue che ϕ_{x}(x) ↓ sse k(x) ∈ A. Abbiamo così ridotto K_{0} ad A, e quindi A è indecidibile.

Secondo caso. Supponiamo e ∈ A. Sia B il complemento di A. Ragionando come nel primo caso mostriamo che B è indecidibile. Ma allora anche A è indecidibile.

13 Il secondo teorema di punto fisso

Vedi Cutland.

14 Gerarchia aritmetica

14.1 Insiemi aritmetici

14.1 Definizione. Un predicato P (x⃗) è aritmetico se e solo se equivale ad un predicato della forma Q_{1}y_{1} … Q_{n}y_{n}R(x⃗, y_{1}, …, y_{n}), dove ogni Q_{i} è un quantiticatore universale od esistenziale ed R è un predicato ricorsivo.

Possiamo classificare la complessità dei predicati aritmetici contando il numero dei quantificatori davanti ad un predicato ricorsivo. Più precisamente conviene contare il numero di alternanze tra quantificatori universali ed esistenziali, in quanto è facile vedere che un blocco di quantificatori successivi dello stesso tipo (tutti universali o tutti esistenziali) può essere sostituito da un solo quantificatore di quel tipo usando una codifica delle successioni finite. Ad esempio ∀y_{1}∀y_{2}R(x⃗, y_{1}, y_{2}) equivale a ∀yR(x⃗, (y)_{1}, (y)_{2}), dove (y)_{i} è l’esponente di p_{i} nella scomposizione in primi di y (possiamo pensare ad (y)_{i} come all’iesimo elemento della successione codificata da y). Diamo quindi la definizione seguente:

14.2 Definizione. Un predicato P (x⃗) è Σ_{n}^{0} se e solo se si può ottenere da un predicato ricorsivo premettendo ad esso n quantificatori (o blocchi di quantificatori dello stesso tipo) di cui il primo, quello più esterno, esistenziale. I predicati Π_{n}^{0} sono definiti in modo analogo, ma con il primo quantificatore universale.

Analoghe definizioni si applicano agli insiemi, identificando un predicato con l’insieme degli elementi che lo verificano.

14.3 Osservazione. Gli insiemi ricorsivamente enumerabili sono esattamente quelli Σ_{1}^{0}. Gli insiemi Π_{0}^{n} sono i complementi degli insemi Σ_{n}^{0}. L’intersezione Π_{1}^{0} ∩ Σ_{1}^{0} è costituita dagli insiemi ricorsivi. Valgono le inclusioni Σ_{n}^{0} ∪ Π_{n}^{0} ⊆ Σ_{n+1}^{0} ∩ Π_{n+1}^{0}. L’unione ⋃_{n} Σ_{n}^{0} = ⋃_{n} Π_{n}^{0} coincide con la classe di tutti gli insiemi aritmetici.

14.2 Insiemi definibili nella struttura (ℕ; +, ·)

Indichiamo con (ℕ; +, ·) la struttura dei numeri naturali con le funzioni di addizione e moltiplicazione.

14.4 Definizione. Un predicato definibile (al primo ordine) nella struttura (ℕ; +, ·) è un predicato P (x_{1}, …, x_{n}) che può essere espresso da una formula in cui possono comparire esclusivamente i simboli +, ·, gli elementi di ℕ, le parentesi, le variabili, i connettivi booleani, e il quantificatore universale (∃x) ed esistenziale (∀x), dove tutte le variabili denotano numeri naturali. Analoghe definizioni valgono per altre strutture al posto di (ℕ; +, ·).

14.5 Esempio. La relazione ≤ è definibile in (ℕ; +, ·). Infatti x ≤ y se e solo se ∃z(x + z = y). Quindi i predicati definibili in (ℕ; +, ·) coincidono con quelli definibili in (ℕ, +, ·, ≤).

14.6 Esempio. Il predicato “x è primo” è definibile tramite la formula “∀u, v(x = u · v → u = 1 ∨ v = 1)”.

14.7 Definizione. Un insieme è definibile se è della forma {(a_{1}, …, a_{n}) | P (a_{1}, …, a_{n})}, dove P è un predicato definibile. Una funzione è definibile se il suo grafico è definibile.

L’esempio mostra che l’insieme dei primi è definibile in (ℕ; +, ·). Mostreremo che ogni predicato ricorsivo è definibile in (ℕ; +, ·). Ne seguirà che gli insiemi definibili in tale struttura coincidono con i predicati aritmetici.

14.3 Funzione β di Gödel

Per mostrare che ogni predicato ricorsivo è definibile in (ℕ; +, ·), avremo bisogno di un modo di codificare le successioni che sia definibile in questa struttura. La codifica basata sulla scomposizione in primi è per il momento inutilizzabile in quanto richiede l’esponenziazione che ancora non abbiamo mostrato essere definibile. Una codifica alternativa è basata sul seguente:

14.8 Teorema. (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}.)

Dimostrazione. 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}.

Per l’applicazione a cui siamo interessati i moduli a_{i} saranno forniti dal seguente lemma.

14.9 Lemma. 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.

Dimostrazione. È sufficiente prendere d = y! dove y > max(n, x). Se infatti un numero primo 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.

14.10 Definizione. 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, β: ℕ^{3} → ℕ, è definita da: β(c, d, i) = re(c, (i + 1)d + 1).

14.11 Osservazione. Il grafico della funzione β è definabile in (ℕ; +, ·). Infatti β(c, d, i) = r ↔ ∃q(c = q[(i + 1)d + 1] + r ∧ 0 ≤ r < (i + 1)d + 1). Si noti che il quantificatore esistenziale ∃q può in effetti essere equivalentemente sostituito dal quantificatore limitato ∃q ≤ c. Pertanto il grafico della funzione β è definibile da una formula con quantificatori limitati. Questa osservazione risulterà utile nel seguito.

La proprietà fondamentale della funzione β di Gödel è espressa dal seguente:

14.12 Lemma. Per ogni n ed ogni successione finita 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}.

Dimostrazione. 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. Poiché b_{i} < (i + 1)d + 1, ne segue che b_{i} è il resto della divisione di c per (i + 1)d + 1, ovvero b_{i} = β(c, d, i).

La funzione β può essere interpretata nel modo seguente: β(c, d, i) = l’iesimo elemento della successione codificata da (c, d).

14.4 Gli insiemi ricorsivamente enumerabili sono definibili in (ℕ; +, ·)

14.13 Teorema. Ogni funzione ricorsiva parziale è definibile in (ℕ; +, ·).

Dimostrazione. Ricordiamo che le funzioni ricorsive parziali sono la più piccola classe di funzioni parziali contenente alcune funzioni iniziali (la funzione costante zero, il successore, e le funzioni proiezione), e chiusa rispetto alla composizione, alle definizioni per ricursione primitiva, e alla minimalizzazione.

Lasciamo al lettore la verifica che le funzioni iniziali sono definibili (nella struttura (ℕ; +, ·)).

Mostriamo che le funzioni definibili sono chiuse per composizione: 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 definiscono tali funzioni, otteniamo una formula per 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 definibili, si ottiene per sostituzione una formula che definisce f.

Chiusura per minimalizzazione

Sia f(x⃗) = μyg(x⃗, y) = 0. Osserviamo che f(x⃗) = y se e solo se g(x⃗, y) = 0 ∧ ∀i < y∃v ≠ 0 g(x⃗, i) = v. Assumendo che g sia definibile, da quest’ultima espressione ricaviamo una formula che definisce il grafico di f.

14.14 Definizione. Una formula aritmetica si dice Δ_{0} o limitata, se tutti i quantificatori che vi compaiono sono limitati. Una formula aritmetica si dice ∃Δ^{0}, se è ottenuta premettendo un certo numero di quantificatori esistenziali davanti ad una formula Δ_{0}.

Analizzando la dimostrazione del teorema precedente si ottiene:

14.15 Osservazione. Ogni funzione ricorsiva parziale è definibile in (ℕ; +, ·) da una formula ∃Δ_{0}.

14.16 Corollario. Ogni insieme ricorsivamente enumerabile è definibile in (ℕ; +, ·). Inoltre la formula che lo definisce può essere presa di complessità ∃Δ_{0}.

Dimostrazione. Sia A ⊆ ℕ^{k} ricorsivamente enumerabile. Allora A = dom(g) per una certa g ricorsiva parziale. Abbiamo x⃗ ∈ A se e solo se ∃y ∈ ℕ(g(x⃗) = y). Per i risultati precedenti il predicato g(x⃗) = y è definibile in (ℕ; +, ·) da una formula ∃Δ_{0}. Aggiungendo il quantificatore ∃y la formula rimane Δ⃗_{0}, quindi anche A è definibile da una formula Δ⃗_{0}.

14.17 Corollario. Gli insiemi ricorsivamente enumerabili sono esattamente quegli insiemi definibili in (ℕ; +, ·) che possono essere definiti da una formula ∃Δ_{0}.

Dimostrazione. Avendo già dimostrato la parte difficile, rimane solo da verificare che ogni insieme definibile da una formula ∃Δ_{0} è ricorsivamente enumerabile. Osserviamo che gli insiemi definibili da una formula Δ_{0} sono ricorsivi (addirittura primitivi ricorsivi) essendo ottenuti da predicati ricorsivi (i grafici di + e ·) per mezzo di connettivi booleani e quantificatori limitati. Per concludere basta osservare che i predicati ricorsivamente enumerabili sono stabili per quantificazione esistenziale.

14.18 Osservazione. Indicando con Δ_{0}^{ℕ} la classe dei predicati definibili in (ℕ; +, ·) da una formula Δ_{0}, si hanno le inclusioni Δ_{0}^{ℕ} ⊂ Primitivi ricorsivi ⊂ Ricorsivi. Tali inclusioni sono strette. Valgono però le uguaglianze ∃Δ_{0}^{ℕ} = ∃Primitivi ricorsivi = ∃Ricorsivi, in quanto ognuna di queste classi coincide con la classe dei predicati ricorsivamente enumerabili.

15 Teorie formali per l’aritmetica

15.1 L’aritmetica di Peano del secondo ordine

L’aritmetica di Peano P A^{2} (l’indice 2 sta ad indicare che si tratta di una teoria del “secondo ordine”) è una teoria formale assiomatizzata dai seguenti assiomi.

P1. ∀xy(S(x) = S(y) → x = y)

P2. ∀x(0 ≠ S(x))

P3 (Induzione). ∀P (P (0) ∧ ∀x(P (x) → P (Sx)) → ∀yP (y)).

15.1 Definizione. Un modello di P A^{2} è una struttura (M; S^{M}, 0^{M}) dove M è un insieme non vuoto, 0^{M} è un elemento di M, S^{M} è una funzione (totale) da M ad M, e gli assiomi sono soddisfatti interpretando i simboli 0 e S come l’elemento 0^{M} e la funzione S^{M}, e convenendo che le variabili x, y variano nell’insieme M, mentre P varia nell’insieme delle parti di M (scriviamo P (x) se x ∈ P).

15.2 Osservazione. I numeri naturali con lo zero e il successore sono un modello di P A^{2}. Vedremo che P A^{2} definisce la struttura dei numeri naturali a meno di isomorfismo, nel senso che tutti i modelli di P A^{2} sono isomorfi tra loro.

15.3 Osservazione. Intuitivamente l’assioma di induzione garantisce che tutti gli elementi di un modello di P A^{2} si ottengono a partire da 0 applicando la funzione successore un numero finito di volte. Infatti l’insieme P degli elementi che così si ottengono contiene 0 ed è ovviamente chiuso per successore, e pertanto in base all’assioma di induzione contiene ogni elemento del modello. Questa spiegazione ha valore euristico ma è informale, in quanto assume a livello intuitivo la nozione “numero finito di volte”, ovvero sostanzialmente la nozione di numero naturale, che è proprio ciò che gli assiomi si prefiggono di definire.

15.4 Osservazione. P1, P2 sono formule “del primo ordine” in quanto le variabili quantificate variano sul dominio del modello, mentre P3 è una formula “del secondo ordine” in quanto la variabile quantificata P assume valori nell’insieme delle parti del modello. In generale una formula del secondo ordine può contenere variabili che assumono come valori relazioni n-arie sul dominio del modello. Chiaramente la distizione tra primo e secondo ordine dipende dalle nostre convenzioni sulla interpretazione delle formule.

15.5 Osservazione. Non c’è bisogno di aggiungere alla teoria P A^{2} assiomi riguardandi la somma, il prodotto, o la relazione d’ordine ≤, in quanto queste operazioni possono essere definite da opportune formule (del secondo ordine) a partire da zero e successore. Ad esempio x ≤ y può essere definito come ∀P (P (x) ∧ ∀u(P (u) → P (S(u))) → P (y)). La relazione x + y = z può essere definita da ∀R(R(x, 0, x)∧∀uv(R(x, u, v) → R(x, Su, Sv)) → R(x, y, z)), dove R varia tra le relazioni ternarie. Lasciamo come esercizio la definizione di x·y = z.

Mostriamo che, dato un qualsiasi modello (M; S^{M}, 0^{M}) di P A^{2}, è possibile giustificare l’uso di definizioni ricorsive su M.

15.6 Teorema. (Definizioni ricorsive) Sia (M; S^{M}, 0^{M}) un modello dell’aritmetica di Peano. Sia N un insieme non vuoto, sia h una funzione h: N → N e sia a un elemento di N. Esiste una e una sola funzione F: M → N tale che F (0^{M}) = a ed F (S^{M}x) = h(F (x)).

Dimostrazione. La dimostrazione avviene all’interno di una opportuna metateoria insiemistica, che in questa trattazione viene assunta a livello intuitivo ma che potrebbe essere formalizzata. La funzione F viene definita (identificando una funzione con il suo grafico) come l’intersezione della classe di tutte le relazioni binarie R ⊆ M × N che godono delle seguenti proprietà: 1) 0^{M}Ra; 2) se xRy, allora S^{M}(x)R h(y). Osserviamo che esiste almeno una relazione con queste proprietà: basta considerare la relazione che vale tra ogni elemento di M e ogni elemento di N. Ha senso dunque considerare l’intersezione F ⊆ M ×N di tutte queste relazioni. Si verifica che F è essa stessa una relazione che gode delle stesse proprietà, ed è ovviamente la più piccola tale relazione. Mostriamo che F è una funzione, ovvero che per ogni x ∈ M esiste uno ed un solo y ∈ N tale che xF y (fatto ciò potremo scrivere F x = y). Consideriamo a tal fine l’insieme P ⊆ M di tutti gli x ∈ M per i quali esiste un y ∈ N tale che xF y. Tale insieme contiene 0^{M} in quanto 0^{M}F a. Inoltre P è chiuso per successore in quanto se xF y allora S^{M}(x)F h(y). Siccome M verifica l’assioma di induzione, possiamo concluderne che P = M. Abbiamo così mostrato che per ogni x ∈ M esiste almeno un y ∈ N per cui xF y.

Analogamente si mostra l’unicità di y, cioè il fatto che F è una funzione. Basta considerare questa volta l’insieme Q ⊆ M di tutti gli x ∈ M tali che ∀y, z ∈ N(xF y ∧ xF z → y = z) e mostrare che Q = M. Basta dunque verificare che Q contiene 0^{M} ed è chiuso per successore. Sappiamo che 0^{M}F a. Se avessimo 0^{M}F y anche per qualche y ≠ a, togliendo la coppia (0^{N}, y) da F si otterrebbe una relazione R ⊆ F che continua a verificare le proprietà 1) e 2), contraddicendo la minimalità di F. Quindi 0^{M} ∈ Q. Supponiamo ora che x ∈ Q e consideriamo l’unico y ∈ N tale che xF y. Abbiamo allora S^{M}(x)F h(y). Se ci fosse un elemento b ≠ h(y) tale che S^{M}(x)F b, togliendo la coppia (S^{M}x, b) da F otterremmo di nuovo una relazione che verifica 1) e 2) contraddicendo la minimalità di F. Abbiamo così mostrato che F è effettivamente una funzione da M ad N.

Per mostrare l’unicità di F consideriamo un’altra funzione G: M → N tale che G(0^{M}) = a e G(S^{M}x) = h(Gx). Sia P ⊆ M l’insieme di tutti gli x ∈ M tali che F x = Gx. Chiaramente 0^{M} ∈ P, e inoltre se x ∈ P si ha G(S^{M}x) = h(Gx) = h(F x) = F (S^{M}x), e quindi S^{M}x ∈ P. Di nuovo per l’assiome di induzione possiamo concludere P = M, e pertanto G = F.

15.7 Teorema. (Dedekind) Tutti i modelli dell’aritmetica di Peano (assiomatizzata da P 1, P 2, P 3) sono isomorfi tra loro.

Dimostrazione. Siano (M; S^{M}, 0^{M}) ed (N; S^{N}, 0^{N}) due modelli. Poichè M è un modello, per il Teorema 15.6 esiste una funzione f: M → N che manda lo zero di M nello zero di N e preserva il successore, nel senso che f(S^{M}x) = S^{N}(fx). Analogamente esiste g: N → M nel verso opposto con analoghe proprietà. La composizione g ∘ f: M → M manda anche essa lo zero in zero e preserva il successore, e pertanto per la proprietà di unicità espressa dal Teorema 15.6, coincide con l’identità su M (in quanto anche l’identità manda zero in zero e preserva il successore). Analogamente f ∘ g è l’identità su N, e quindi f, g sono l’una l’inversa dell’altra, da cui segue che sono entrambe isomorfismi.

15.8 Osservazione. Il teorema precedente mostra che se esiste un modello esso è unico esso è unico a meno di isomorfismo, ma non mostra l’esistenza di un modello. L’esistenza può essere dimostrata all’interno di una opportuna teoria assiomatica degli insiemi, quale la teoria di Zermelo Fraenkel, facendo uso del cosiddetto “assioma dell’infinito”.

15.2 La teoria Q di Robinson

La teoria Q di Robinson assiomatizza alcune delle proprietà dei numeri naturali, ma non ha assiomi di induzione. 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 → ∃z(x = S(z)), Q4. x + 0 = x, Q5. x + S(y) = S(x + y), Q6. x · 0 = 0, Q7. x · S(y) = x · y + x. In questi assiomi i quantificatori sono stati sottointesi: le variabili x, y si

intendono quantificate universalmente. Le proprietà espresse dagli assiomi di Q sono verificate nei numeri naturali con le solite operazioni aritmetiche di zero, successore, somma e prodotto. Esistono però altri modelli di Q non isomorfi al modello ℕ dei numeri naturali.

15.9 Esempio. Un’altro modello di Q si può ottenere nel modo seguente. Sia ℤ[x] l’anello dei polinomi in una variabile a coefficienti in ℤ. Definiamo un ordine totale su ℤ[x] stabilendo che un polinomio p(x) ∈ ℤ[x] è positivo se lim_{x→∞} p(x) > 0. Equivalentemente un polinomio a_{0} + a_{1}x + … + a_{n}x^{n}, con a_{n} ≠ 0, è positivo se e solo se a_{n} > 0. Sia ℤ[x]^{+} l’insieme dei polinomi non negativi (positivi o zero) dell’anello ℤ[x]. 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 ℤ[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.

La definizione formale di modello è analoga alla Definizione 15.1:

15.10 Definizione. Un modello di Q è una struttura (M; +^{M}, ·^{M}, S^{M}, 0^{M}) dove M è un insieme non vuoto, +^{M} e ·^{M} sono funzioni binarie (totali) su M, S^{M} è una funzione unaria, e 0^{M} è un elemento di M, dove si richiede che gli assiomi di Q siano verificati interpretando i simboli +, ·, S, 0 con le corrispondenti funzioni di M (il simbolo = è interpretato come la relazione di uguaglianza), e stipulando che le variabili assumano valori tra gli elementi di M.

15.3 L’aritmetica di Peano del primo ordine

15.11 Definizione. L’aritmetica di Peano del primo ordine, che indicheremo con P A, o con P A^{1} per ricordarci che si tratta di una teoria del primo ordine, è una teoria formulata nello stesso linguaggio L = {+, ·, S, 0} della teoria di Robinson Q, e che possiede, oltre agli assiomi di Q, il cosiddetto schema di induzione. Tale schema è una lista infinità di assiomi, uno per ogni coppia (ϕ, x) dove ϕ è una formula del primo ordine di L, e x è una variabile libera di ϕ (la variabile su cui facciamo l’induzione). Alla coppia (ϕ, x) associamo l’assioma Ind_{ϕ,x} definito come ϕ(0)∧∀x(ϕ(x) → ϕ(Sx)) → ∀yϕ(y), dove la notazione ϕ(t), indica la formula ottenuta sostituendo t al posto delle occorrenze libere di x in ϕ. La formula ϕ potrebbe contenere altre variabili libere oltre alla x, nel qual caso si intende che le rimanenti variabili siano quantificate universalmente nel corrispondente assioma Ind_{ϕ,x}. Ad esempio se ϕ = ϕ(x, z) ha come variabili libere x e z, l’assioma Ind_{ϕ,x} è ∀z[ϕ(0, z)∧∀x(ϕ(x, z) → ϕ(Sx, z)) → ∀yϕ(y, z)], dove l’induzione si fa su x e l’altra variabile libera z si comporta come un parametro.

15.12 Osservazione. La differenza tra l’assioma di induzione del secondo ordine ∀P (P (0) ∧ ∀x(P (x) → P (Sx)) → ∀yP (y)), e lo schema di assiomi di induzione, è che nel primo caso la proprietà di induzione viene chiesta per ogni possibile proprietà P, mentre nel secondo caso viene chiesta solo per quelle proprietà P (x) che sono definibili da una formula (possibilmente con parametri). Pur non possedendo l’induzione nella sua piena forza, P A^{1} è tuttavia una teoria molto potente: quando facciamo una dimostrazione per induzione, quasi sempre la proprietà su cui facciamo l’induzione è di fatto definibile da una formula.

Il concetto di modello per P A^{1} si definisce in modo analogo a quanto visto in precendenza per le altre terie. Ogni modello di P A^{1} è anche un modello di Q ma non viceversa. Ci sono modelli di Q che non verificano lo schema di induzione.

15.13 Esercizio. Il modello ℤ[x]^{+} di Q non è modello di P A^{1}. Suggerimento: si consideri l’insieme degli elementi che sono divisibili per due o il cui successore è divisibile per due.

15.14 Osservazione. Il motivo per considerare P A^{1} anziché la più naturale P A^{2}, è che per la logica del primo ordine vale il teorema di completezza: un enunciato ϕ del primo ordine è vero in tutti i modelli di una teoria T del primo ordine se e solo se esiste una dimostrazione formale di ϕ da T.

15.4 Conseguenza logica

Ricordiamo la definizione di conseguenza logica.

15.15 Definizione. (Conseguenza logica) Un enunciato ϕ è conseguenza logica di una teoria T se è vero in tutti i modelli di T. Il concetto di conseguenza logica dipende ovviamente dalla definizione del concetto di modello.

Dimostrare ϕ da T significa dimostrare che ϕ è conseguenza logica di T.

15.16 Esempio. L’enunciato ∀x∃y(2y = x ∨ 2y = x + 1) (dove abbiamo usato le abbreviazioni 1 = S(0) e 2 = S(1)), non è conseguenza logica di Q in quanto nel modello ℤ[x]^{+} dell’Esempio 15.9 non è vero che ogni elemento è divisibile per due o il suo successore lo è (la variabile x di ℤ[x]^{+} non è il doppio di alcun polinomio, e neppure x + 1 lo è).

15.17 Osservazione. È possibile trovare modelli di Q in cui non vale la legge commutativa della somma e del prodotto. Quindi ∀xy(x + y = y + x) non è conseguenza logica di Q.

15.18 Esercizio. Si dimostri in P A^{1} la commutatività dell’addizione e della moltiplicazione.

15.5 Dimostrazioni formali

15.19 Fatto. (Dimostrazioni formali) Il teorema di completezza per il calcolo dei predicati, afferma che, nel caso di teorie ed enunciati del primo ordine, è possibile dare esplicitamente un insieme finito di regole di inferenza logiche che è sufficiente per dimostrare tutte le conseguenze logiche di una qualsiasi teoria. Una possibile scelta delle regole logiche è data dalla Definizione 15.21. Una dimostrazione condotta utilizzando esclusivamente le regole fissate viene detta dimostrazione formale. L’adeguatezza delle regole della Definizione 15.21 viene dimostrata all’interno di una opportuna metateoria insiemistica.

15.20 Osservazione. Il teorema di completezza non si applica alla teoria P A^{2}, essendo questa una teoria del secondo ordine. Per tale teoria abbiamo definito il concetto di modello e quindi la nozione di conseguenza logica, ma non è possibile dare una corrispondente nozione di dimostrazione formale tale che tutte le conseguenze logiche di P A^{2} abbiano una dimostrazione formale.

15.21 Definizione. (Regole di inferenza logiche) Scriviamo Γ ⊢ ϕ per esprimere il fatto che la tesi ϕ è deducibile dall’insieme di ipotesi Γ. Scriviamo Γ, ϕ per l’insieme Γ ∪ {ϕ}, dove Γ è un insieme di formule e ϕ è una formula. Scriviamo ϕ(t/x) per il risultato della sostituzione del termine t al posto di tutte le occorrenze libere della variabile x nella formula ϕ.

• (Ax)ϕ ⊢ ϕ

• (Wk)\frac{Γ ⊢ ϕ}{Γ, α ⊢ ϕ}

• (⊢ ∧)\frac{Γ ⊢ α  Γ ⊢ β}{Γ ⊢ α ∧ β}

• (∧ ⊢)\frac{Γ, α ⊢ γ}{Γ, α ∧ β ⊢ γ}  (∧ ⊢)\frac{Γ, β ⊢ γ}{Γ, α ∧ β ⊢ γ}

• (∨ ⊢)\frac{Γ ⊢ α}{Γ ⊢ α ∨ β}  (∨ ⊢)\frac{Γ ⊢ β}{Γ ⊢ α ∨ β}

• (⊢ ∨)\frac{Γ, α ⊢ γ  Γ, β ⊢ γ}{Γ, α ∨ β ⊢ γ}

• (⊢→)\frac{Γ, α ⊢ β}{Γ ⊢ α → β}  (→ /e)\frac{Γ ⊢ α  Γ ⊢ α → β}{Γ ⊢ β}

• (⊢⊥)\frac{Γ ⊢ α  Γ ⊢ ¬α}{Γ ⊢⊥}  (⊥) \frac{Γ ⊢⊥}{Γ ⊢ α}
• (¬ ⊢)\frac{Γ ⊢ α}{Γ, ¬α ⊢⊥}  (⊢ ¬)\frac{Γ, α ⊢⊥}{Γ ⊢ ¬α}

• (RAA)\frac{Γ, ¬α ⊢⊥}{Γ ⊢ α}

• (⊢ ∀)\frac{Γ ⊢ ϕ(y/x)}{Γ ⊢ ∀xϕ} dove y è una variabile che non occorre libera in Γ.

• (∀/e)\frac{Γ ⊢ ∀xϕ}{Γ ⊢ ϕ(t/x)} dove t è un qualsiasi termine sostituibile per x in ϕ.

• (⊢ ∃)\frac{Γ ⊢ ϕ(t/x)}{Γ ⊢ ∃xϕ} dove t è un qualsiasi termine sostituibile per x in ϕ.

• (∃ ⊢)\frac{Γ, ϕ(y/x) ⊢ γ}{Γ, ∃xϕ ⊢ γ} dove y è una variabile che non occorre libera in Γ o

in γ.

• (⊢=)Γ ⊢ x = x

• (= /e)\frac{Γ ⊢ ϕ(t/x)  Γ ⊢ t = t′}{Γ ⊢ ϕ(t′/x)}

dove t, t′ sono termini sostituibili per x in ϕ.

Se T è una teoria, dare una dimostrazione formale di un enunciato ϕ da T, significa trovare un sottoinsieme Γ degli assiomi di T e dedurre Γ ⊢ ϕ usando le regole sopra date.

15.22 Osservazione. Non bisogna confondere il concetto di dimostrazione rigorosa con il concetto di dimostrazione formale. Una dimostrazione può essere rigorosa pur non essendo formale. Nella prossima sezione mostreremo che certi enunciati sono veri in tutti i modelli della teoria Q dandono delle dimostrazioni rigorose seppure non formali.

15.6 Alcune formule dimostrabili in Q

Dato n ∈ ℕ, il termine S(S(S(… S(0)))) (n volte S) viene detto il numerale di n e indicato con \overline{n} o con S^{n}0.

15.23 Lemma. ∀a, b, c ∈ ℕ, se a + b = c, allora Q ⊢ \overline{a} + \overline{b} = \overline{c} (nel senso che l’enunciato \overline{a} + \overline{b} = \overline{c} è vero in tutti i modelli di Q).

Quindi as esempio Q dimostra S(S(0)) + S(S(S(0))) = S(S(S(S(S(0))))).

Dimostrazione. 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) (dove sottointendiamo ∀xy). Prendendo x = \overline{a}, y = \overline{b − 1}, otteniamo Q ⊢ \overline{a} + \overline{b} = \overline{c}.

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

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

15.25 Definizione. I termini del linguaggio L = L(Q) = {+, ·, S, 0} sono le espressioni che è possibile costruire usando le variabili e i simboli di L, correttamente parentesizzate. Ad esempio (S(x) + S(0)) · 0 è un termine di L, o L-termine.

15.26 Corollario. Per ogni termine chiuso t di L esiste n ∈ ℕ tale che Q ⊢ t = \overline{n}.

Ad esempio Q dimostra che (S(0) + S(0)) · (S(0) + S(0)) = S(S(S(S(0)))).

Dimostrazione. 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 ∈ ℕ 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.

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.

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

Dimostrazione. Segue dal fatto che Q, così come ogni altra teoria, dimostra ∀x(x = x).

Abbiamo fino ad ora dimostrato solamente uguaglianze. Veniamo ora alle disuguaglianze.

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

Ad esempio Q dimostra S(0) ≠ S(S(0)).

Dimostrazione. 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}.

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

Dimostrazione. Siano a, b ∈ ℕ 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}.

15.7 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 ∈ ℕ x = \overline{n}^{M}\}, dove \overline{n}^{M} = S^{M}(S^{M}(… S^{M}(0^{M}))) (con n occorrenze di S^{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 il più piccolo sottoinsieme di M contenente lo 0 di M e chiuso per la funzione successore S di M. Ne segue che se M è modello di P A^{2} tutti i suoi elementi sono standard: basta applicare l’assioma di induzione all’insieme degli elementi standard. Siccome l’insieme dei numeri standard non è necessariamente definibile da una formula del primo ordine, lo stesso ragionamento non è fattibile in P A^{1}.

Dai risultati fin qui mostrati per Q segue che l’addizione e la moltiplicazione di numeri standard si comporta come la usuale addizione e moltiplicazione di numeri naturali, nel senso che il sottoinsieme M′ ⊆ M dei numeri standard costituisce una sottostruttura di M isomorfa ad ℕ con le usuali operazioni di addizione e moltiplicazione. Inoltre esiste un unico isomorfismo da ℕ ad M′ dato dalla mappa che manda n ∈ ℕ in \overline{n}^{M}. L’unicità segue dal fatto che un qualsiasi omomorfismo di ℕ in M deve mandare 0 in 0^{M} e preservare il successore S. Ne segue che ℕ è immergibile in ogni modello M di Q, e che M è isomorfo ad ℕ se e solo se M non ha numeri non-standard.

15.30 Esempio. Nel modello ℤ[x]^{+} di Q i numeri non-standard sono esattamente i polinomi non-costanti.

15.8 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:

15.31 Lemma. ∀n ∈ ℕ, Q ⊢ ∀x ( x ≤ \overline{n} ↔ x = \overline{0} ∨ x = \overline{1} ∨ … ∨ x = \overline{n}).

Dimostrazione. Induzione su n. Fissiamo un modello M di Q ed un elemento x di M e mostriamo che in M vale la doppia implicazione x ≤ \overline{n} ↔ x = \overline{0} ∨ x = \overline{1} ∨ … ∨ x = \overline{n}).

L’implicazione da destra a sinistra segue dalla definizione di ≤ e dal Lemma 15.23. Mostriamo l’altra implicazione.

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 e Q1 z+y = \overline{n − 1}. Quindi y ≤ \overline{n − 1}. Per ipotesi induttiva y = \overline{0}∨…∨y = \overline{n − 1}. Quindi x = \overline{1} ∨ … ∨ x = \overline{n}.

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} è necessariamente un numero standard, e inoltre è un numero standard della forma \overline{m}^{M} per qualche m ≤ n. In altre parole l’isomorfismo tra ℕ e i numeri standard di M preserva non solo 0, S, + e ·, ma anche la relazione ≤.

15.32 Corollario. ∀n ∈ ℕ Q ⊢ ∀x.x ≤ \overline{n + 1} ⟷ x ≤ \overline{n} ∨ x = \overline{n + 1}.

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

15.33 Corollario. Sia n ∈ ℕ. Sono equivalenti:

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

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

15.34 Lemma. ∀a, b ∈ ℕ, Q ⊢ \overline{a} ≤ \overline{b} oppure Q ⊢ ¬(\overline{a} ≤ \overline{b}). Il primo caso capita se a ≤ b. Il secondo se a > b.

Dimostrazione. Se a ≤ b, allora Q ⊢ \overline{a} = 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} per il Lemma 15.31.

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}).

Conveniamo che x < y stia per x ≤ y ∧ x ≠ y.

15.35 Lemma. ∀b ∈ ℕ Q ⊢ ∀x(x ≤ \overline{b} ∨ \overline{b} < x).

Dimostrazione. Per induzione su b. Ragionando in Q fissiamo x e mostriamo x ≤ \overline{b} o x ≥ \overline{b}. Per l’assioma Q4 x + 0 = x e quindi 0 ≤ x. Supponiamo dunque b > 0. Per ipotesi induttiva x ≤ \overline{b − 1} o x ≥ \overline{b − 1}. Nel primo caso per il Lemma 15.31 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}.

In un modello non-standard M di Q la relazione ≤ non è un buon ordine, nel senso che contiene delle successioni discendent infinite x, x − 1, x − 2, x − 3, …, dove x − 1 indica un elemento y tale che S(y) = x, x − 2 un elemento z tale che S(S(z)) = x e così via. In alcuni modelli di Q la relazione ≤ non è neppure un ordine totale. Tuttavia abbiamo:

15.36 Lemma. 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.

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

15.9 Le formule con quantificatori limitati sono decidibili in Q

Un enunciato si dice indipendente da Q se Q ⊬ ϕ e Q ⊬ ¬ϕ. Ad esempio l’enunciato ∀x∃y(2y = x ∨ 2y = x + 1) è indipendente da Q. Un enunciato φ si dice decidibile in Q (o Q-decidibile) se Q ⊢ φ oppure Q ⊢ ¬φ. Quindi un enunciato è decidibile se non è indipendente. Questa nozione non va confusa con la decidibilità nel senso della teoria della calcolabilità, la quale si riferisce ad insiemi o predicati, mentre la decidibilità in Q si riferisce a singoli enunciati.

Da un punto di vista semantico (cioè dei modelli) dire che φ è indipendente da Q significa che ϕ è vero in certi modelli di Q e falso in altri. Dirre che ϕ è decidibile in Q significa che φ 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 ℕ) oppure è falso in tutti i modelli di Q.

Da questa caratterizzazione è immediato vedere:

15.37 Lemma. Una combinazione booleana di enunciati decidibili in Q è decidibile in Q.

Dimostrazione. Ad esempio supponiamo che φ e ϕ siano decidibili in Q e mostriamo che la disgiunzione φ ∨ ϕ è decidibile in Q. Si hanno quattro possibili casi.

1) Q ⊢ φ e Q ⊢ ϕ.

2) Q ⊢ φ e Q ⊢ ¬ϕ.

3) Q ⊢ ¬φ e Q ⊢ ϕ.

4) Q ⊢ ¬φ e Q ⊢ ¬ϕ.

I casi in cui Q non dimostra nessuna delle formule in questione nè la loro negazione è escluso perchè φ e ϕ sono decidibili in Q. Nel caso 4 abbiamo Q ⊢ ¬(φ ∨ ϕ). Negli altri tre casi Q ⊢ φ ∨ ϕ. Quindi φ ∨ ϕ è decidibile in Q.

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

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

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

15.39 Lemma. Se φ(\overline{n}) è decidibile in Q per ogni n ∈ ℕ, e se t è un termine chiuso, allora gli enunciati ∀x ≤ tφ(x) e ∃x ≤ tφ(x) sono decidibili in Q.

Dimostrazione. Sia b ∈ ℕ tale che Q ⊢ \overline{b} = t. Basta allora mostrare che l’enunciato ∀x ≤ \overline{b}φ(x, \overline{a_{1}}, …, \overline{a_{n}}) è decidibile in Q. Poichè Q ⊢ ∀x.x ≤ \overline{b} ↔ x = \overline{0} ∨ x = \overline{1} ∨ … ∨ x = \overline{b}, l’enunciato ∀x ≤ \overline{b}φ(x) è equivalente, in Q, all’enunciato φ(\overline{0}) ∧ φ(\overline{1}) ∧ … ∧ φ(\overline{b}) 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{1}) ∨ … ∨ φ(\overline{b}).

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

15.40 Corollario. Ogni enunciato Δ_{0} è decidibile in Q.

Dimostrazione. Segue dai risultati precedenti per induzione sul numero dei connettivi logici della formula.

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

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

2) se ℕ ⊧ ¬ϕ, 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 ℕ).

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). Poichè M′ è isomorfo ad ℕ ne segue che ϕ è vera in M se e solo se è vera in ℕ 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.

Ricordiamo che una formula si dice ∃Δ^{0}, se è ottenuta premettendo un certo numero di quantificatori esistenziali davanti ad una formula Δ_{0}.

15.41 Lemma. Se ϕ è un enunciato ∃Δ^{0} e ℕ ⊧ ϕ, allora Q ⊢ ϕ.

Dimostrazione. Supponiamo che ϕ sia della forma ∃x_{1} … x_{n}ψ(x_{1}, …, x_{n}) con ψ ∈ Δ_{0}. Assumiamo che ϕ sia vero in ℕ e siano a_{1}, …, a_{n} ∈ ℕ tali che ℕ ⊧ ψ(\overline{a_{1}}, …, \overline{a_{n}}). Per la decidibilità delle formule Δ_{0}, Q ⊢ ψ(\overline{a_{1}}, …, \overline{a_{n}}), da cui segue Q ⊢ ∃x_{1} … x_{n}ψ(x_{1}, …, x_{n}).

Riassumendo abbiamo:

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

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

3) Gli enunciati ∃Δ_{0} veri in ℕ sono dimostrabili in Q.

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

esempio ∃x, y.x + y ≠ y + x è una formula ∃Δ_{0} falsa in ℕ ma non refutabile in Q. Quindi esistono formule ∃Δ_{0} non decidibili in Q.

15.10 Rappresentabilità in Q delle funzioni ricorsive

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

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}}).

La notazione φ_{A} è leggermente ambigua in quanto un insieme A può essere binumerato da tante formule non equivalenti in Q.

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

Dimostrazione. Segue dal fatto che ogni formula Δ_{0} è decidibile in Q.

15.44 Definizione. Una funzione totale f: ℕ^{k} → ℕ è 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} ∈ ℕ:

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

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}).

Il seguente teorema mostra che ogni relazione semidecidibile contiene il grafico di una funzione.

15.45 Teorema. (Selezione) Sia R ⊆ ℕ^{2} un predicato semidecidibile. Esiste una funzione ricorsiva parziale f tale che per ogni x ∈ ℕ se esiste un y tale che R(x, y), allora si ha R(x, f(x)).

Dimostrazione. Definiamo u = ⟨y, z⟩ se e solo se 2u = (y + z)(y + z + 1) + x. La corrispondenza (y, z) ↦ ⟨y, z⟩ è una funzione biunivoca da ℕ^{2} ad ℕ. Fissiamo un predicato decidibile D(x, y, z) tale che R(x, y) se e solo se ∃zD(x, y, z). Basta definire f(x) = π_{1}(μ⟨y, z⟩D(x, y, z)) dove π_{1} estrae la componente y della coppia ⟨y, z⟩ e μ⟨y, z⟩D(x, y, z) è una abbreviazione per μu∃y, z ≤ u(u = ⟨y, z⟩ ∧ D(x, y, z)).

15.46 Teorema. Ogni funzione ricorsiva totale f: ℕ^{k} → ℕ è binumerata funzionalmente in Q. Inoltre la formula binumerante può essere scelta di complessità ∃Δ_{0}.

Diamo due dimostrazioni. Della prima forniamo solo un cenno.

Dimostrazione. (Cenno) Analizzando i dettagli della dimostrazione del Teorema 14.13, si vede che la stessa dimostrazione funziona sostituendo “definibile in ℕ” con “binumerabile in Q”.

La seconda dimostrazione usa le idee del teorema di selezione.

Dimostrazione. Per semplicità supponiamo che k = 1, cioè che f sia una funzione di un argomento. Il grafico di f: ℕ → ℕ è ricorsivamente enumerabile, quindi è definibile (nel modello standard ℕ) da una formula ρ(x, y) della forma ∃zϕ(x, y, z) con ϕ ∈ Δ_{0}, nel senso che fa = b se e solo se ℕ ⊧ ∃zϕ(\overline{a}, \overline{b}, z).

Fissiamo una tale formula. Poichè le formule di complessità ∃Δ_{0} che sono vere nel modello standard ℕ sono dimostrabili in Q, questa condizione implica Q ⊢ ∃zϕ(\overline{a}, \overline{b}, z) (vale anche l’implicazione inversa essendo Q un modello di ℕ, ma questo non ci garantisce la binumerabilità, nè tantomeno la binumerabilità funzionale). Non è detto che una qualsiasi formula che definisce (in ℕ) il grafico di f binumeri funzionalemente f in Q. L’idea allora è di applicare il Teorema di Selezione 15.45 alla relazione definita dalla formula ρ(x, y). In generale il teorema di selezione permette di trovare, all’interno di una relazione, il grafico di una funzione. Se viene applicato alla relazione ρ(x, y), che già definisce (in ℕ) il grafico di una funzione, esso fornirà una nuova formula θ(x, y) che definisce lo stesso grafico, con il vantaggio che per la nuova formula si potrà dimostrare la binumerabilità funzionale in Q.

Veniamo ai dettagli. Poniamo u = ⟨y, z⟩ se e solo se 2u = (y + z)(y + z + 1) + x. La corrispondenza (y, z) ↦ ⟨y, z⟩ è una funzione biunivoca da ℕ^{2} ad ℕ. Definiamo θ(x, y) come la formula ∃u∃z[u = ⟨y, z⟩ ∧ ϕ(x, y, z) ∧ ∀u′, y′, z′ < u(u′ = ⟨y′, z′⟩ → ¬ϕ(x, y′, z′))]. Mostriamo che la formula θ(x, y) binumera funzionalmente f in Q. Supponiamo a tale fine che fa = b. Qualsiasi coppia (u, v) ∈ ℕ^{2} tale che ℕ ⊧ ϕ(a, u, v) deve avere u = b (perché ∃zϕ(x, y, z) definisce il grafico di f). Tra tutte queste coppie sia (b, c) quella che ha la minima codifica. Poiché ℕ ⊧ ϕ(a, b, c) si ha Q ⊢ ϕ(\overline{a}, \overline{b}, \overline{c}) (essendo ϕ ∈ Δ_{0}). Per la minimalità di ⟨b, c⟩, e per il fatto che Q dimostra tutti gli enunciati limitati veri, Q ⊢ ∀u, b′, c′ < \overline{⟨b, c⟩}(u = ⟨b′, c′⟩ → ¬ϕ(\overline{a}, b′, c′)). Ne segue che Q ⊢ θ(\overline{a}, \overline{b}). Resta da dimostrare che Q ⊢ ∀y(θ(\overline{a}, y) → y = \overline{b}). Ragionando in Q, supponiamo che valga θ(\overline{a}, y) per un certo y (in un modello di Q tale y potrebbe essere non standard). Esiste allora z tale che ϕ(\overline{a}, y, z) e per ogni y′, z′ tali che ⟨y′, z′⟩ < ⟨y, z⟩ si ha ¬ϕ(\overline{a}, y′, z′). In particolare, visto che vale ϕ(\overline{a}, \overline{b}, \overline{c}), non può essere che \overline{⟨b, c⟩} < ⟨y, z⟩, e pertanto deve essere ⟨y, z⟩ ≤ \overline{⟨b, c⟩}. Non può valere la disuguaglianza stretta in quanto abbiamo ∀u, b′, c′ < \overline{⟨b, c⟩}(u = ⟨b′, c′⟩ → ¬ϕ(\overline{a}, b′, c′)) (avendo dimostrato questa formula in Q). Pertanto vale l’uguaglianza, e ne segue y = \overline{b}.

16 Teoremi di incompletezza di Gödel

16.1 Aritmetizzazione della sintassi e predicato di dimostrabilità

Sia L un linguaggio del primo ordine con un numero finito di simboli di funzione, relazione e costante (ad esempio L = {+, ·, S, 0}) e associamo ad ogni simbolo s di L 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).

16.1 Definizione. Fissiamo una codifica delle successioni di numeri naturali e scriviamo ⟨a_{1}, …, a_{n}⟩ per indicare la codifica della successione a_{1}, …, a_{n}. 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}⌉⟩.

16.2 Definizione. 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}⌉, ⌈α⌉⟩.

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

Dimostrazione. 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 Ltermine” in termini dei valori di verità degli enunciati “u codifica un L-termine”, 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: ℕ → ℕ 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: ℕ^{2} → ℕ. 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.

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

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

16.5 Lemma. Esiste una funzione primitiva ricorsiva sub: ℕ^{3} → ℕ 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.)

Dimostrazione. Basterà fare in modo che sub soddisfi le clausole che seguono, dove abbiamo indicato con f un generico simbolo di funzione n-aria di L, con R un generico simbolo di relazione n-aria di L, con t_{1}, …, t_{n} degli L-termini, e con α, β delle L-formule.

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}α⌉, j, y) = ⟨⌈∀⌉, ⌈v_{i}⌉, sub(⌈α⌉, j, y)⟩ se i ≠ j
sub(⌈∀v_{i}α⌉, i, y) = ⌈∀v_{i}α⌉
sub(⌈∃v_{i}α⌉, j, y) = ⟨⌈∃⌉, ⌈v_{i}⌉, sub(⌈α⌉, j, 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).

16.6 Osservazione. È 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} → ϕ).

16.7 Teorema. Sia T una L-teoria (consideriamo solo teorie del primo ordine) tale che l’insieme {⌈ϕ⌉ | ϕ è un assioma di T } è ricorsivo. Allora l’insieme delle conseguenze logiche di T (o più precisamente delle loro codifiche) è ricorsivamente enumerabile.

Dimostrazione. Basta mostrare che esiste un insieme ricorsivo Prov_{T} ⊆ ℕ^{2} tale che ϕ è un teorema di T se e solo se ∃n ∈ ℕ: (x, ⌈ϕ⌉) ∈ Prov_{T}.È possibile codificare con dei numeri le dimostrazioni formali. Definiamo Prov_{T} come l’insieme di tutte le coppie (n, ⌈ϕ⌉) tali che n codifica una dimostrazione formale di ϕ da T. L’insieme così ottenuto è ricorsivo a condizione che gli assiomi di T costituiscano un insieme ricorsivo.

16.8 Osservazione. Il teorema vale anche indebolendo le ipotesi: basta che l’insieme delle codifiche degli assiomi si ricorsivamente enumerabile.

Ricordiamo che una teoria è completa se per ogni enunciato ϕ si ha T ⊢ ϕ oppure T ⊢ ¬ϕ.

16.9 Corollario. Sia T una teoria completa con un insieme ricorsivo di assiomi. Allora T è decidibile, ovvero l’insieme {⌈ϕ⌉ | T ⊢ ϕ} è ricorsivo.

Dimostrazione. L’insieme in questione è ricorsivamente enumerabile. In virtù della completezza il suo complemento (all’interno dell’insieme ricorsivo di tutte le formule) consiste delle formule ϕ tali che ¬ϕ è un teorema di T. Questo secondo insieme è anch’esso ricorsivamente enumerabile, e per il teorema di Post concludiamo che sono entrambi ricorsivi.

16.2 Enunciati indimostrabili

Consideriamo il linguaggio L = {+, ·, S, 0}.

16.10 Lemma. Esiste una funzione primitiva ricorsiva num: ℕ → ℕ tale che per ogni 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)).

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

Se ⌈α⌉ = n ∈ ℕ, indichiamo con \overline{⌈α⌉} il termine S^{n}(0). Data una formula α e un termine t, scriviamo α(t) per α[t/v_{0}].

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

Dimostrazione. D(x) = sub(x, 0, num(x)).

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

Dimostrazione. Sia δ(x, y) una 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{⌈γ⌉})⌉}).

16.13 Teorema. La teoria P A (aritmetica di Peano del primo ordine) è incompleta, ovvero esistono enunciati ϕ tali che P A ⊬ ϕ e P A ⊬ ¬ϕ.

Dimostrazione. Poiché le codifiche degli assiomi di P A sono un insieme primitivo ricorsivo 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 ℕ, si ha in particolare che G è vera (in ℕ) 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 pertanto l’enunciato ¬Teo(\overline{⌈G⌉}) è vero (in ℕ) in quanto esprime proprio la non dimostrabilità di G. Ma G equivale in tutti i modelli di Q a tale enunciato, e quindi G è vero in ℕ. Ma allora nemmeno la negazione di G è dimostrabile in P A in quanto P A dimostra solo cose vere in ℕ (essendo ℕ un suo modello).

Con essenzialmente la stessa dimostrazione si ha:

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

16.15 Definizione. 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}).

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

16.17 Lemma. Sia T una teoria ω-coerente contenente Q e sia σ un enunciato ∃Δ_{0}. Allora T ⊢ σ se e solo se σ è vero nel modello ℕ.

Dimostrazione. Consideriamo il caso in cui σ è della forma ∃xθ(x) con θ ∈ Δ_{0}. Se σ è vero in ℕ, allora per qualche n ∈ ℕ, θ(\overline{n}) è vero in ℕ, 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 ℕ, allora per ogni n varrebbe in ℕ l’enunciato ¬θ(\overline{n}) e pertanto questo enunciato sarebbe dimostrabile in Q (essendo Δ_{0}) e quindi in T, contraddicendo la ω-coerenza.

16.18 Teorema. 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.

Dimostrazione. 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 che ¬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.

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

Dimostrazione. Sia K_{0} ⊂ ℕ un insieme ricorsivamente enumerabile e non ricorsivo. Essendo ricorsivamente enumerabile K_{0} è definibile in ℕ da una formula σ(x) ∈ ∃Δ_{0} in una variabile libera. Per ogni n ∈ ℕ, n ∈ K_{0} se e solo se σ(\overline{n}) è vera in ℕ, 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}.

16.20 Osservazione. 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 16.13 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.

16.21 Teorema. P A ⊬ Con(P A).

Dimostrazione. (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 ∃x¬T eo(x). L’implicazione inversa Con(P A) → G si ottiene formalizzando in P A la prima parte della dimostrazione del Teorema 16.13, quella cioè in cui si mostra P A ⊬ G. In tale dimostrazione si usa solo la coerenza di P A (e non che ℕ 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.

16.22 Teorema. (Church) Il calcolo dei predicati è indecidibile.

Dimostrazione. Si ha Q ⊢ ϕ se e solo se ⊢ ⋀ Q → ϕ, dove ⋀ Q indica la congiunzione di tutti gli assiomi di Q (che sono in numero finito). Ne segue che se avessimo un algoritmo per stabilire se una formula è logicamente valida, applicandolo alla formula ⋀ Q → ϕ otterremmo un algoritmo per stabilire se una formula ϕ è teorema di Q, che abbiamo visto essere impossibile.