Appunti ed esercizi del corso di Istituzioni di Logica Matematica

Prof. A. Berarducci

Versione del 4 Gen. 2002, Rivista 8 Marzo 2002

Le seguenti note sono provvisorie ed imperfette. Sono state scritte ad uso degli studenti che hanno seguito il corso.

Contents

1 Calcolo proposizionale 2

1.1 Tavole di verità . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Associatività e parentesi. . . . . . . . . . . . . . . . . . . 4 1.2 Tautologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 Complessità delle tautologie . . . . . . . . . . . . . . . . . 5 1.3 Equivalenza logica e implicazione logica. . . . . . . . . . . . . . . 6

2 Sintassi del calcolo dei predicati 7 2.1 Segnatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Termini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Formule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Variabili libere e legate . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Sostituzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Semantica del calcolo dei predicati 10

3.1 L-strutture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1.1 Omomorfismi di L-strutture . . . . . . . . . . . . . . . . . 11 3.2 Semantica di Tarksi . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Cenni sulla logica del secondo ordine 15

5 Teorie assiomatiche 16 5.1 Teorie, modelli, e conseguenza logica . . . . . . . . . . . . . . . . 16 5.2 Teorie complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.3 Teorie deduttivamente chiuse . . . . . . . . . . . . . . . . . . . . 18

6 Insiemi di Hintikka 20 7 Completezza 22

7.1 Il sistema dimostrativo di Hilbert-Frege . . . . . . . . . . . . . . 22 7.1.1 Assiomi logici . . . . . . . . . . . . . . . . . . . . . . . . . 23 7.1.2 Regole di inferenza . . . . . . . . . . . . . . . . . . . . . . 23 7.1.3 Teoremi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.1.4 Dimostrazioni formali . . . . . . . . . . . . . . . . . . . . 24 7.1.5 Alcuni utili metateoremi . . . . . . . . . . . . . . . . . . . 24

7.2 Teorema di correttezza per il calcolo dei predicati . . . . . . . . . 25 7.3 Teorema di deduzione . . . . . . . . . . . . . . . . . . . . . . . . 28 7.4 Completezza del sistema di Hilbert-Frege . . . . . . . . . . . . . 28

8 Compattezza 31 8.1 Teorema di compattezza . . . . . . . . . . . . . . . . . . . . . . . 31 8.2 Teorema di Löweinheim - Skolem verso l’alto . . . . . . . . . . . 32

9 Elementare equivalenza e sottostrutture elementari 32 9.1 Elementare equivalenza . . . . . . . . . . . . . . . . . . . . . . . 32 9.2 Sottostrutture elementari . . . . . . . . . . . . . . . . . . . . . . 33 9.3 Teorema di Lowenheim - Skolem verso il basso . . . . . . . . . . 35

10 Cenni di teoria della calcolabilità 37 10.1 Algoritmi e funzioni calcolabili . . . . . . . . . . . . . . . . . . . 37 10.2 Funzioni calcolabili parziali . . . . . . . . . . . . . . . . . . . . . 38 10.3 Macchine di Turing . . . . . . . . . . . . . . . . . . . . . . . . . . 39

10.3.1 Funzione parziale calcolata da una macchina di Turing. . 40 10.4 Tesi di Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 10.5 Insiemi decidibili e semidecidibili . . . . . . . . . . . . . . . . . . 41 10.6 Ricorsiva enumerabilità dei teoremi . . . . . . . . . . . . . . . . . 44

11 Eliminazione dei quantificatori 45

12 Decidibilità della teoria dei campi algebricamente chiusi e della teoria dei numeri complessi 48

13 Decidibilità della teoria dei campi reali chiusi e della teoria dei numeri reali 50

14 Esercizi 52

1 Calcolo proposizionale

1.1 Tavole di verità

Una proposizione è un enunciato di cui ha senso chiedersi se sia vero o falso. Ad esempio “3 > 2” è una proposizione vera, mentre “2 > 3” è una proposizione falsa. Assumiamo la concezione classica secondo cui una proposizione è o vera o falsa (principio del terzo escluso), ma non può essere sia vera che falsa (principio di non contraddizione).

I connettivi booleani sono usati per costruire proposizioni complesse a partire da proposizioni semplici. Nella formalizzazione del linguaggio matematico i connettivi di cui faremo maggiore uso sono indicati con i simboli ¬, ∧, ∨, →, ↔. La loro traduzione approssimativa in italiano è la seguente:

“¬A” significa “non A” (negazione), “A ∧ B” significa “A e B” (congiunzione), “A ∨ B” significa “A o B” (disgiunzione), “A → B” significa “se A, allora B” (implicazione), “A ↔ B” significa “A se e solo se B” (doppia implicazione).

Le lettere A, B sopra usate indicano generiche proposizioni. La traduzione che abbiamo dato è solo approssimativa: non c’è una perfetta corrispondenza tra l’uso dei connettivi in una lingua naturale come l’italiano e il loro uso nel linguaggio matematico.

Ad una proposizione ϕ associamo il valore di verità 1 o 0 a seconda che essa sia vera o falsa.

I connettivi booleani sono vero-funzionali nel senso che il valore di verità di una proposizione composta dipende solo dal valore di verità delle proposizioni semplici che la costituiscono. Questo avviene secondo le seguenti tavole di verità che precisano il significato dei connettivi.

\begin{matrix}A & ¬A \\ 0 & 1 \\ 1 & 0 \end{matrix}

La tavola dice che la proposizione ¬A è vera se A è falsa, ed è invece falsa se A è vera. La negazione inverte il valore di verità. Diamo ora le tavole degli altri connettivi.

\begin{matrix}A & B & A ∧ B & A ∨ B & A → B & A ↔ B \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}

Le prime due colonne indicano i quattro possibili valori di verità di A e B. Le altre colonne indicano i corrispondenti valori degli enunciati composti A∧B, A ∨ B, A → B, A ↔ B. Discutiamo ora in dettaglio le tavole del ∨ e →.

La tavola di verità del connettivo ∨ dice che A ∨ B è vera se almeno uno di A e B è vero, senza escludere la possibilità che entrambi siano veri. Questa modalità di disgiunzione corrisponde al “vel” della lingua latina e viene chiamata disgiunzione inclusiva. Esiste anche una disgiunzione escusiva, corrispondente all’ “aut” latino, che indichiamo con il simbolo ⊕ ed è definita dalla seguente tavola di verità:

\begin{matrix}A & B & A ⊕ B \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}

Dalle tavole di verità risulta che l’implicazione A → B è falsa solo nel caso in cui la premessa A è vera e il conseguente B è falso. In particolare se la premessa A è falsa, l’enunciato A → B è sempre vero a prescindere da quale sia l’enunciato B: da una premessa falsa segue ogni proposizione. L’implicazione così definita viene detta implicazione materiale. Secondo le nostre definizioni un enunciato quale il seguente risulta vero per qualsiasi valore di x:

x è un numero primo maggiore di due → x è dispari

se ad esempio x = 3 l’implicazione è vera in quanto sia la premessa che la conclusione sono vere, mentre se x = 4 l’implicazione è ugualmente vera perché la premessa è falsa.

Un enunciato composto della forma A → B equivale a ¬A ∨ B, nel senso che ha lo stesso valore di verità comunque si scelgano le proposizioni A, B. Ciò si può verificare utilizzando le tavole di verità (si assegnino nei quattro modi possibili i valori 0, 1 ad A, B e si verifichi che A → B risulta avere sempre lo stesso valore di ¬A ∨ B).

1.1.1 Associatività e parentesi.

Le parentesi hanno lo scopo di indicare l’ordine in cui si effettuano le operazioni. Non potremmo scrivere A ∧ B ∨ C in quanto non si capirebbe se intendiamo (A ∧ B) ∨ C (prendere prima la congiunzione di A e B e poi fare la disgiunzione con C) o se invece intendiamo A ∧ (B ∨ C). Possiamo però scrivere senza ambiguità A∧B ∧C in quanto il connettivo ∧ è associativo, ovvero (A∧B)∧C equivale a A ∧ (B ∧ C) e l’ordine non conta. Analogamente si può verificare che (A∨B)∨C equivale a A∨(B ∨C) (associatività di ∨) e quindi possiamo scrivere senza ambiguità A ∨ B ∨ C. Osserviamo che A ∨ B ∨ C è vero se almeno uno degli enunciati A, B, C è vero mentre A∧B ∧C è vero se tutti e tre gli enunciati A, B, C sono veri.

Per un ulteriore risparmio di parentesi stabiliamo la convenzione che in assenza di parentesi ∧ e ∨ legano maggiormente di → e ¬ lega maggiormente di ∧ e ∨, quindi ad esempio ¬A ∧ B → C significa ((¬A) ∧ B) → C.

1.2 Tautologie

Se pensiamo alle lettere A, B, C come a variabili, le espressioni A → B, ¬A ∨ B, (A ∧ B) ∨ C sono esempi di formule proposizionali. Da una formula proposizionale si ottiene una proposizione andando a sostituire le variabili A, B, C, … che che vi compaiono con delle proposizioni. Ad esempio dalla formula A → B possiamo ottenere la proposizione vera “Nevica → fa freddo” sostituendo la variabile A con la proposizione “Nevica” e la variabile B con la proposizione “fa freddo”. Dalla stessa formula possiamo anche ottenere la proposizione falsa “3 = 3 → 1 > 4” sostituendo “A” con “3 = 3” e “B” con “1 > 4”. In generale possiamo definire una formula proposizionale come una espressione ottenuta combinando tra loro alcuni simboli A, B, C, … detti variabili proposizionali tramite i connettivi e le parentesi, in modo che sostituendo delle proposizioni al posto delle variabili si ottenga una proposizione. Più precisamente:

Definizione 1.1 L’insieme delle formule proposizionali è un insieme di espressioni definito induttivamente come segue. Ogni variabile proposizionale è una formula proposizionale. Se ϕ e ψ sono formule proposizionali, lo sono anche (¬ϕ), (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ → ψ), (ϕ ↔ ψ). (Potremmo fare a meno di ϕ ↔ ψ considerandola come abbreviazione di (ϕ → ψ) ∧ (ψ → ϕ).) Si noti che gni formula è racchiusa da un paio di parentesi. Nello scrivere esempi di formule possiamo omettere le parentesi superflue seguendo le convenzioni date precedentemente.

Da una stessa formula proposizionale si possono ottenere infinite proposizioni diverse a seconda delle sostituzioni. Con certe sostituzioni potremmo ottenere una proposizione vera, con certe altre una proposizione falsa.

Definizione 1.2 Una formula proposizionale ϕ si dice una tautologia se è vera per ogni valore delle sue variabili, cioè otteniamo una proposizione vera comunque sostituiamo delle proposizioni al posto delle sue variabili.

Ad esempio A ∨ ¬A è una tautologia, in quanto risulta vera sia nel caso in cui A è una proposizione vera, sia nel caso in cui A è una proposizione falsa. Analogamente (A → B)∧¬B → ¬A è una tautologia, in quanto usando le tavole si vede che essa risulta vera nei quattro possibili casi per i valori di A e B (A vera e B vera, A vera e B falsa, A falsa e B vera, A falsa e B falsa). Una proposizione ottenuta per sostituzione da una tautologia sarà anch’essa detta tautologia. Ad esempio la proposizione “piove ∨ ¬piove” è una tautologia essendo ottenuta per sostituzione dalla formula tautologica A ∨ ¬A. Come si vede da questo esempio una tautologia ha contenuto informativo nullo. Affermare “piove o non piove” non ci dà alcuna informazione sul fatto se piova o meno. In generale un enunciato che esprime una tautologia è vero a prescindere dalla verità o falsità degli enunciati elementari che lo costituiscono, e quindi non comunica nulla riguardo alla verità o falsità di questi ultimi. Possiamo dire che tautologia è vera in virtù esclusivamente della sua forma sintattica, e non del suo contenuto.

1.2.1 Complessità delle tautologie

Un metodo per riconoscere se una formula con n variabili è una tautologia è quello di considerare i 2^{n} possibili casi per i valori di verità delle sue variabili e verificare usando le tavole che in ognuno dei casi la proposizione composta che ne risulta è vera. Si tratta di una procedura semplice e meccanica ma che nel caso ci siano molte variabili richiede molto tempo, anche da parte di un calcolatore. Esistono altri metodi per controllare se una formula è una tautologia, ma tutti i metodi noti richiedono una quantità di passaggi esponenziale al crescere del numero delle variabili. Il problema di stabilire se esistano metodi più efficienti (che permettano di riconoscere le tautologie in tempo polinomiale anziché esponenziale) è tuttora irrisolto.

1.3 Equivalenza logica e implicazione logica.

Due formule proposizionali ϕ e ψ si dicono logicamente equivalenti, e scriviamo in tal caso ϕ ≡ ψ, se la formula ϕ ↔ ψ è una tautologia. Questo avviene se e solo se ϕ e ψ hanno la stessa tavola di verità, cioè se forniscono lo stesso valore di verità per qualsiasi valore 1, 0 che sia assegnato alle loro variabili. Ad esempio A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C), come si può verificare assegnando ad A, B, C i valori 1, 0 negli otto modi possibili e verificando che in ciascun caso il valore di A ∧ (B ∨ C) è uguale a quello di (A ∧ B) ∨ (A ∧ C).

Una formula proposizionale ϕ implica logicamente un’altra formula proposizionale ψ se la formula ϕ → ψ è una tautologia. Questo equivale a dire che per tutti i valori delle variabili per cui ϕ assume il valore 1, anche ψ assume il valore 1 (ma ψ potrebbe assumere il valore 1 in un numero maggiore di casi). Ad esempio A ∧ B implica logicamente A ∨ B, in quanto se A ∧ B risulta vera per certi valori di A, B, anche A ∨ B deve risultare vera per gli stessi valori.

Osserviamo che due formule sono equivalenti se l’una implica logicamente l’altra e viceversa.

Osservazione 1.3 Si noti la differenza tra l’implicazione materiale che abbiamo visto precedentemente e l’implicazione logica. L’implicazione materiale è una implicazione tra proposizioni, mentre l’implicazione logica è una implicazione tra formule proposizionali. Una proposizione ha un valore fisso di verità 1 od 0, mentre una formula proposizionale è una espressione contenente varibili proposizionali e di per sè non è nè vera nè falsa: solo se si fissa una specifica assegnazione di valori alle sue variabili diventa vera o falsa, e in generale potrebbe risultare vera per certi valori delle sue variabili e falsa per altri.

Esempio 1.4 (Paradossi dell’implicazione materiale) Anche se può sembrare poco intuitivo, date due proposizioni ce ne è sempre una delle due che implica materialmente l’altra: infatti se la prima delle due è una proposizione falsa, essa implica qualsiasi proposizione, e quindi in particolare la seconda, mentre se invece è una proposizione vera, essa è implicata da qualsiasi proposizione. Non è invece detto che date due formule proposizionali ce ne sia sempre una delle due che implica logicamente l’altra: basta prendere una formula che consiste solamente di una variabile proposizionale A, e un’altra formula che consiste di un’altra variabile proposizionale B, e notare che nè A → B nè B → A sono tautologie (in quanto la prima risulta falsa se diamo ad A il valore 1 e a B il valore 0, mentre la seconda risulta falsa se diamo a B il valore 1 e ad A il valore 0).

2 Sintassi del calcolo dei predicati

2.1 Segnatura

La segnatura di un linguaggio del primo ordine è dato da un insiemi di simboli (possibilmente anche vuoto) divisi in tre categorie, simboli di costante, simboli di funzione, e simboli di relazione, e da una funzione chiamata “arità” che associa ad ogni simbolo un numero naturale, dove l’arit di ogni simbolo di costante è zero, mentre le arità dei simboli di funzione e di relazione sono interi positivi.

Esempio 2.1 La segnatura del linguaggio degli anelli ordinati con unità è data da L = {0, 1, +, ·, ≤}, dove 0, 1 sono simboli di costante, +, · sono simboli di funzioni binarie (cioè di arità 2), e ≤ è un simbolo di relazione binario.

2.2 Termini

Un linguaggio del primo ordine è costituito, oltre che dai simboli di una data segnatura L, anche da altri simboli, tra cui un insieme V di simboli chiamati variabili. Definiamo induttivamente l’insieme T er_{L}(V) degli L-termini (con variabili da V) come il più piccolo insieme di espressioni che soddisfa le seguenti clausole induttive:

1. Ogni variabile x ∈ V è un L-termine;

2. ogni simbolo di costante di L è un L-termine;

3. se t_{1}, …, t_{n} sono L-termini, e f è un simbolo di funzione di arità n della segnatura L, allora f(t_{1}, …, t_{n}) è un L-termine;

Un termine in cui non occorrano variabili viene detto termine chiuso. Si noti che se la segnatura L non contiene simboli di costante , allora non ci sono L-termini chiusi, e se la segnatura non contiene nè simboli di costante nè simboli di funzione allora gli unici L-termini sono le variabili (questo avviene ad esempio per la segnatura L = {≤} della teoria degli ordini lineari, o per la segnatura L = {∈} della teoria degli insiemi).

Esempio 2.2 Consideriamo la segnatura L = {0, 1, +, ·, ≤}, dove 0, 1 sono simboli di costante, +, · sono simboli per funzioni binarie, ≤ è un simbolo di relazione binario. Esempi di L-termini sono 0, 0 + 1, z · ((x + y) + 1), dove x, y, z sono variabili e per semplicità abbiamo usato la notazione infissa xfy anziché f(x, y) quando f è un simbolo di funzione binaria (cioè per i simboli · e +). Nella segnatura di questo esempio i termini corrispondono ad espressioni algebriche polinomiali. Osserviamo che i simboli di relazione della segnatura non contribuiscono alla formazione dei termini.

2.3 Formule

Oltre ai simboli di una data segnatura L e ad un insieme infinito V di variabili, l’alfabeto di un linguaggio del primo ordine contiene anche i simboli ¬, ∧, ∨, → per i connettivi booleani, i simboli ∀, ∃ per i quantificatori, il simbolo = (opzionale), e le parentesi. La differenza tra due linguaggi del primo ordine è data solo dalla scelta delle segnatura, essendo tutti gli altri simboli sempre presenti (a parte il simbolo di = che può esserci o no).

L’insieme delle L-formule è definito induttivamente come il più piccolo insieme di espressioni che verifica le seguenti clausole induttive:

1. Se R è un simbolo di relazione di L di arità n e t_{1}, …, t_{n} sono degli L-termini, allora R(t_{1}, …, t_{n}) è una L-formula.

2. Se α e β sono L-formule, allora (¬α), (α ∧ β), (α → β), (α ∨ β) sono L-formule.

3. Se α è una L-formula e x è una variabile, allora (∀xα) e (∃xα) sono Lformule.

Si usa distinguere tra linguaggi con simbolo di uguaglianza e linguaggi senza simbolo di uguaglianza. Nel caso di linguaggi con simbolo di uguaglianza dobbiamo aggiungere:

4. Per ogni coppia di termini s, t, l’espressione s = t è una L-formula.

Una L-formula atomica è una L-formula in cui non compaiono connettivi logici (ovvero i simboli ¬, ∧, ∨, →, ∀, ∃). Le formule atomiche sono dunque solo quelle della forma R(t_{1}, …, t_{n}) oppure della forma t_{1} = t_{2}, dove i t_{i} sono termini, e R è un simbolo di relazione di L. Se la segnatura non contiene simboli di relazione le uniche formule atomiche sono quelle del secondo tipo.

Il simbolo di uguaglianza “=” non appartiene alla segnatura L del linguaggio, ma all’insieme dei cosiddetti simboli logici, al pari dei simboli dei connettivi logici ∀, ∃, ¬, etc. Alla segnatura appartengono solo i simboli la cui interpretazione può variare, mentre all’insieme dei simboli logici appartengono quei simboli il cui significato è fissato (si veda la sezione sulla semantica).

Negli esempi di L-formule ometteremo per comodità le parentesi ridondanti quando non sussista ambiguità di lettura, ovvero qualora esista un unico modo di aggiungere le parentesi mancanti in modo da ottenere una L-formula. Ad esempio la formula ((x = x ∧ x = y) ∨ y = z) può essere scritta in forma abbreviata come (x = x ∧ x = y) ∨ y = z. La stessa formula non può invece essere abbreviata come x = x ∧ x = y ∨ y = z in quanto aggiungendo delle parentesi potremmo ottenere, oltre a quella data prima, anche la formula (x = x ∧ (x = y ∨ y = z)). Resta inteso che queste sono solo abbreviazioni informali, e la definizione ufficiale di L-formula rimane quella data precedentemente.

2.4 Variabili libere e legate

Una occorrenza di una variabile x in una formula α si dice legata se occorre in una sottoformula β di α immediatamente preceduta da un quantificatore ∀x o ∃x. Una occorrenza non legata si dice libera.

Esempio 2.3 La formula x = x ∧ ∀z(z = z) ha due occorrenze legate di z e due occorrenze libere di x.

È possibile che una variabile occorra sia libera che legata in una stessa formula, come ad esempio in x = x ∧ ∀x(x = x), in cui le prime due occorrenze sono libere e le altre sono legate. Quando parleremo della intepretazione delle formule, sarà chiaro che la formula x = x∧∀x(x = x) va intepretata nello stesso modo della formula x = x ∧ ∀z(z = z). Le occorrenze di variabili legate possono sempre essere “ridenominate” in modo che una stessa variabile non occorra sia libera che legata nella stessa formula.

Le variabili libere di una una formula sono le variabili che hanno almeno una occorrenza libera nella formula. Ad esempio le variabili libere di x = y ∧ ∀u∃x(x = u) sono la x e la y (sebbene la x abbia anche una occorrenza legata).

Indichiamo con F v(α) l’insieme delle variabili libere di α. Chiaramente tutte le variabili che occorrono in una formula atomica sono libere. I quantificatori fanno calare l’insieme delle variabili libere: F v(∀xα) = F v(α) \ {x} e similmente F v(∃xα) = F v(α) \ {x}. Per i connettivi booleani abbiamo F v(¬α) = F v(α), F v(α → β) = F v(α) ∪ F v(β), e similmente per ∨ e ∧ si prende l’unione.

Una formula senza variabili libere viene detta formula chiusa o enunciato.

2.5 Sostituzioni

Se α è un termine o una formula, e t_{1}, …, t_{n} sono termini, indichiamo con α(t_{1}/x_{1}, …, t_{n}/x_{n}) il termine o formula risultante da α dalla simultanea sostituzione di ogni occorrenza libera della variabile x_{i} in α con t_{i} per i = 1, …, n. Se le variabili x_{1}, …, x_{n} di cui si sta parlando sono sottointese scriviamo più semplicemente α(t_{1}, …, t_{n}) invece di α(t_{1}/x_{1}, …, t_{n}/x_{n}). Ad esempio ∀xα(x) → α(t) è la stessa cosa di ∀xα → α(t/x) (in quanto se sottointendiamo la x, allora α(t) coincide con α(t/x) e α(x) coincide con α(x/x), che è proprio α).

Si noti che in generale la formula α(t_{1}/x_{1}, t_{2}/x_{2}), ottenuta per sostituzione simultanea, non coincide con la formula α(t_{1}/x_{1})(t_{2}/x_{2}), in cui la sostituzione (t_{2}/x_{2}) viene effettuata dopo la sostituzione (t_{1}/x_{1}), che a sua volta può non coincidere con la formula α(t_{2}/x_{2})(t_{1}/x_{1}), in cui le sostituzioni vengono fatte nell’ordine inverso.

Esercizio 2.4 Se x_{1} ed x_{2} sono variabili distinte, α(t_{1}/x_{1})(t_{2}/x_{2}) coincide con α(t_{2}/x_{2})(t′_{1}/x_{1}), dove t′_{1} è il termine risultante dalla sostituzione di t_{2} al posto delle occorrenze di x_{2} in t_{1}. In particolare se non vi sono occorrenze di x_{2} in t_{1}, allora t′_{1} coincide con t_{1} e l’ordine delle sostituzioni non conta.

Nel caso di termini chiusi tutti i modi di effettuare le sostituzioni (simultanee o in sequenza) danno lo stesso risultato.

Osservazione 2.5 L’implicazione espressa dalla formula ∀xα(x) → α(t) non è sempre “logicamente valida”. Definiremo più tardi questo concetto, ma intanto diamo un esempio intuitivo. Sia ϕ(x) la formula ∃y(x = y) e sia t il termine y + 1. Allora ∀xϕ(x) è l’enunciato ∀x∃y(x = y), che è sempre vero, mentre ϕ(t) è l’enunciato ∃y(y + 1 = y) che non è vero se interpretiamo i simboli +, 1 come la addizione tra numeri naturali e come il numero naturale “uno”.

Affinchè l’implicazione ∀xα(x) → α(t) risulti logicamente valida dobbiamo porre delle restrizioni sul termine t da sostituire.

Definizione 2.6 Un termine t è sostituibile al posto di una variabile x in una formula α se per ogni variabile y in t, nessuna occorrenza libera di x in α appare all’interno di una sottoformula della forma ∃yβ o ∀yβ. In altre parole questo significa che le variabili di t non diventano legate dopo che si è effettuata la sostituzione α(t/x).

Si noti che un termine chiuso è sempre sostituibile al posto di qualsiasi variabile in qualsiasi formula.

3 Semantica del calcolo dei predicati

3.1 L-strutture

Definizione 3.1 (L-struttura) Sia L una segnatura. Una L-struttura M consiste di:

1. Un insieme non vuoto dom(M) detto dominio (oppure universo) della struttura.

2. Una corrispondenza c ↦ c_{M} che associa ad ogni simbolo di costante c di L un elemento c_{M} ∈ dom(M), detto interpretazione del simbolo c in M.

3. Una corrispondenza f ↦ f_{M} che associa ad ogni simbolo di funzione f di L di arità n, una funzione f_{M}: dom(M)^{n} → dom(M), detta interpretazione del simbolo f in M.

4. Una corrispondenza R ↦ R_{M} che associa ad ogni simbolo di relazione R di L di arità n, una relazione R_{M} ⊆ dom(M)^{n}, detta interpretazione del simbolo R in M.

Notazione. È importante non confondere i simboli con le loro interpretazioni in una data struttura M. Tuttavi quando l’interpretazione dei simboli della segnatura sia chiara dal contesto, o sia suggerita dalla scelta dei simboli usati, useremo la stessa notazione per i simboli e le loro interpretazioni.

Esempio 3.2 Le strutture algebriche usuali possono essere viste come L-strutture.

Gli anelli sono esempi L-strutture dove L = {0, 1, +, ·} e i simboli 0, 1, +, · sono intepretati in modo da soddisfare gli assiomi degli anelli. Similmente i gruppi sono L-strutture con L = {1, ·}.

Gli spazi vettoriali sono L-strutture generalizzate in cui esistono non uno ma due tipi di oggetti nel dominio (vettori e scalari). È tuttavia anche possibile pensare agli spazi vettoriali come ad una L-struttura M dove il dominio dom(M) comprende sia vettori che scalari ma ci sia un simbolo di predicato unario V nella segnatura L che serve a distinguere gli uni dagli altri (cioè V è interpretato come il sottoinsieme di dom(M) consistente dei vettori).

Un ordine parziale è una L-struttura dove L = {≤} e ≤ è un simbolo di predicato binario la cui interpretazione deve soddisfare le proprietà degli ordini parziali).

Non è invece possibile pensare in modo semplice ad uno spazio topologico come ad una L-struttura.

3.1.1 Omomorfismi di L-strutture

Definizione 3.3 Un isomorfismo ϕ: A → B tra due L-strutture A e B è dato da una mappa \underline{iniettiva} e \underline{suriettiva} ϕ: dom(A) → dom(B) che preserva tutte le funzioni e relazioni che interpretano i simboli di L. Più precisamente:

1. se c è un simbolo di costante, allora ϕ(c_{A}) = c_{B};

2. se f è un simbolo di funzione di arità n e a_{1}, …, a_{n} ∈ dom(A), allora ϕ(f_{A}(a_{1}, …, a_{n})) = f_{B}(ϕ(a_{1}), …, ϕ(a_{n}));

3. se R è un simbolo di relazione di arità n e a_{1}, …, a_{n} ∈ dom(A), allora (a_{1}, …, a_{n}) ∈ R_{A} se e solo se (ϕ(a_{1}), …, ϕ(a_{n})) ∈ R_{B}.

Esempio 3.4 Sia L una segnatura con un simbolo di relazione binario f. Sia (R; +) la L-struttura avente come dominio i numeri reali e in cui f è interpretato come la funzione somma, e sia (R^{>0}; ×) la L-struttura avente come dominio i numeri reali positivi e in cui f è interpretato come la funzione prodotto. Allora la funzione esponenziale x ↦ e^{x} è un isomorfismo da (R; +) a (R^{>0}; ×).

Definizione 3.5 Il concetto di immersione si ottiene da quello di isomorfismo rinunciando alla richiesta che ϕ sia suriettiva. Una immersione è dunque un isomorfismo verso la sua immagine.

Esempio 3.6 Sia L = {0, 1, +, −, ·, ≤} e consideriamo le L-strutture Z e R (con l’ovvia interpretazione dei simboli). Allora la funzione ϕ che manda un numero intero n (inteso come elemento di Z) nel numero n inteso come elemento di R, è una immersione di Z in R.

Definizione 3.7 Date due L-strutture A e B diciamo che A è una sottostruttura di B se dom(A) ⊆ dom(B) e la funzione identità i: dom(A) → dom(B) è una immersione. Ciò significa che i simboli di costante sono intepretati nello stesso modo in A e in B, e i simboli di funzione e relazione sono interpretati in A come la restrizione agli elementi di A delle funzioni e relazioni che intepretano gli stessi simboli in B. Per indicare che A è una sottostruttura di B scriviamo A ⊆ B. Osserviamo che un sottoinsieme del dominio di una struttura è il dominio di una sottostruttura se e solo se contiene le intepretazioni dei simboli di costante ed è chiuso rispetto alle interpretazioni dei simboli di funzione.

Esempio 3.8 Se pensiamo agli interi come inclusi nei reali, abbiamo che Z è una sottostruttura di R (notazione: Z ⊆ R).

Il concetto di omomorfismo si ottiene indebolendo il concetto di isomorfismo come segue.

Definizione 3.9 Un omomorfismo ϕ: A → B tra due L-strutture A e B è dato da una mappa ϕ: dom(A) → dom(B) tale che:

1. se c è un simbolo di costante, allora ϕ(c_{A}) = c_{B};

2. se f è un simbolo di funzione di arità n e a_{1}, …, a_{n} ∈ dom(A), allora ϕ(f_{A}(a_{1}, …, a_{n})) = f_{B}(ϕ(a_{1}), …, ϕ(a_{n}));

3. se R è un simbolo di relazione di arità n, a_{1}, …, a_{n} ∈ dom(A), e (a_{1}, …, a_{n}) ∈ R_{A}, allora (ϕ(a_{1}), …, ϕ(a_{n})) ∈ R_{B}.

Ad esempio sia Z/(n) l’anello degli interi modulo n considerato come una L-struttura con L = {0, 1, +, −, ·}. Allora la funzione che manda un intero x nella sua classe resto modulo n costituisce un omomorfismo da Z a Z/(n) che non è nè un isomorfismo né una immersione.

Esempio 3.10 Se consideriamo Z e R come L-strutture con L = {0, 1, +, −, ·} (con la usuale interpretazione dei simboli) allora un omomorfismo f: Z → R è un omomorfismo di anelli (e ce ne è uno solo, che è in effetti una immersione), mentre se consideriamo Z e R come L-strutture con L = {≤} (e la solita intepretazione del ≤) allora un omomorfismo f: Z → R è una qualsiasi funzione f: dom(Z) → dom(R) debolmente crescente, ovvero una funzione tale che x ≤ y implica f(x) ≤ f(y). Ad esempio la funzione x ↦ x^{3} è un omomorfismo d’ordine ma non di anelli.

Scegliere la segnatura in un modo anziché un altro dipende da quali funzioni vogliamo considerare come omomorfismi, ovvero da quali caratteristiche strutturali vogliamo che siano preservate.

3.2 Semantica di Tarksi

Definizione 3.11 Data una L-struttura M, una formula con parametri da M è una espressione che si ottiene da una L-formula φ sostituendo alcune sue variabili libere x_{1}, …, x_{n} con elementi a_{1}, …, a_{n} del dominio di M. Similmente per termini. In particolare ogni elemento a ∈ dom(M) è un termine con parametri da M (prendiamo come L-termine una variabile x, e sostituiamo x con a). I termini e le formule chiusi, con o senza parametri, sono quelli in cui non vi sono variabili libere.

Le notazioni sulle sostituzioni si estendono al caso dei parametri come segue. Se a_{1}, …, a_{n} ∈ dom(M), indichiamo con ϕ(a_{1}/x_{1}, …, a_{n}/x_{n}) la formula con parametri da M che si ottiene sostituendo le occorrenze libere della variabile x_{i} con a_{i} (i = 1, …, n). Se è implicito di quali variabili x_{1}, …, x_{n} si sta parlando, scriviamo ϕ(a_{1}, …, a_{n}) invece di ϕ(a_{1}/x_{1}, …, a_{n}/x_{n}). Similmente per i termini.

Esempio 3.12 Sia L = {0, 1, +, ·} e sia R la L-struttura dei numeri reali. Allora (x+y)+1 è un L-termine (senza parametri), (\sqrt{2}+y)+1 è un L-termine contenente il parametro \sqrt{2} da R, e (\sqrt{2} + \sqrt{2}) + 1 è un termine chiuso con parametri da R.

In questo esempio “1” non è un parametro, ma un simbolo di costante della segnatura L. Se volessimo un L-termine che contiene come parametro il numero 1 inteso come elemento di R, allora a rigore dovremmo usare due notazioni diverse per il simbolo 1 ∈ L e il numero 1 ∈ R.

Esempi di L-formule con parametri sono (\sqrt{2} + y) + 1 = y (aperta) e ∀x∃y((\sqrt{2} + y) + 1 = y) (chiusa).

Osservazione 3.13 Volendo formalizzare in una metateoria insiemistica (ad esempio nella teoria di Zermelo-Fraenkel) la definizione appena data di formula con parametri da una struttura M possono sorgere alcune difficoltà. Essendo infatti il dominio di M un insieme del tutto arbitrario, nulla esclude che M contenga tra i suoi elementi alcuni oggetti di tipo sintattico, come i simboli, o le stringhe di simboli, che vengono usati nel costruire le L-formule. Ad esempio potrebbe capitare che il simbolo ”∀” appartenga al dominio di M. È ovvio che in tal caso si avrebbero dei problemi di leggibilità delle formule con parametri da M. Vi sono vari modi per ovviare a tale inconveniente. Una possibilità è quella di ridefinire una formula con parametri come una coppia costituita da una L-formula φ, e da una “sostituzione” (a_{1}/x_{1}, …, a_{n}/x_{n}). L’idea è che, usando le coppie, la sostituzione non viene realmente effettuata ma viene lasciata semplicemente indicata. Con questa impostazione potremmo continuare ad usare la notazione φ(a_{1}/x_{1}, …, a_{n}/x_{n}) assumendo che essa denoti la coppia, anziché il risultato della sostituzione. Nel seguito tuttavia ignoreremo queste difficoltà e continueremo a lavorare con la Definizione 3.11 precedentemente data, supponendo implicitamente di volta in volta, senza perdita di generalità, che il dominio della struttura considerata non contenga elementi che possano causare problemi di leggibilità delle formule con parametri.

Definizione 3.14 (Interpretazione dei termini chiusi) Se t è un termine chiuso con parametri dalla L-struttura M, associamo a t un elemento M(t) ∈ dom(M) semplicemente rimpiazzando i simboli di funzione e di costante presenti in t con la loro interpretazione in M e calcolando il valore di t corrispondente. Più precisamente:

1. Se t è l’elemento a ∈ dom(M) (abbiamo visto che gli elementi di dom(M) sono casi particolari di termini con parametri), allora M(t) = a; 2. Se t è un simbolo di costante c di L, allora M(t) = c_{M} (l’interpretazione

del simbolo c in M).

3. Se t = f(t_{1}, …, t_{n}), allora induttivamente M(t) = f_{M}(M(t_{1}), …, M(t_{n})), dove f_{M}: dom(M)^{n} → dom(M) è la funzione che interpretata il simbolo f in M.

Definizione 3.15 (Interpretazione delle formule chiuse con parametri) Sia M una L-struttura, e sia ϕ è una L-formula \underline{chiusa} con parametri da M. Scriviamo M ⊧ ϕ per esprimere il fatto che ϕ rappresenta un enunciato vero qualora si interpretino i simboli nel modo seguente: le variabili variano su elementi del dominio di M e quindi i quantificatori “∀x” ed “existsx” vanno quindi letti come “per ogni x ∈ dom(M)” ed ”esiste x ∈ dom(M) ”; i simboli della segnatura di L hanno il significato loro attribuito dalla Definizione 3.1 e rappresentano quindi particolari elementi, funzioni e relazioni su M; il connettivo ¬ significa “non”; ∧ significa “e”; ∨ significa “o”; → significa “implica”; Il simbolo = significa “è uguale a”.

Più formalmente, diciamo che tra M e ϕ sussiste la relazione M ⊧ φ se ciò segue dalle seguenti clausole induttive. L’induzione viene fatta sul numero dei connettivi di ϕ.

1. M ⊧ ∀xϕ(x) se e solo se per ogni a ∈ dom(M), M ⊧ ϕ(a);

2. M ⊧ ∃xϕ(x) se esiste a ∈ dom(M) tale che M ⊧ ϕ(a);

3. M ⊧ ¬ϕ se e solo se M |̸= ϕ (cioè non vale M ⊧ ϕ);

4. M ⊧ ϕ ∧ ψ se e solo se M ⊧ ϕ e M ⊧ ψ;

5. M ⊧ ϕ ∨ ψ se e solo se M ⊧ ϕ o M ⊧ ψ (nel senso che almeno una delle due è vera, senza escludere il caso che lo siano entrambe);

6. M ⊧ ϕ → ψ se e solo se M ⊧ ψ o M |̸= ϕ (senza escludere che si presentino entrambi i casi).

Per la base dell’induzione dobbiamo considerare il caso delle formule atomiche (cioè senza connettivi). Aggiungiamo a tal fine le seguenti clausole, dove R è un simbolo di predicato di L di arità n, e L e i vari t_{i} sono L-termini chiusi con parametri da M.

7. M ⊧ R(t_{1}, …, t_{n}) se e solo se (M(t_{1}), …, M(t_{n})) ∈ R_{M};

8. M ⊧ t_{1} = t_{2} se e solo se M(t_{1}) e M(t_{2}) sono lo stesso elemento.

Se vale M ⊧ ϕ diciamo che ϕ è vera in M, o che M soddisfa ϕ. Anche se fossimo stati solamente interessati alla definizione di verità per formule chiuse \underline{senza parametri} per poter dare una definizione induttiva della relazione di soddisfacibilità non ci saremmo potuti esimere dal definirla anche per formule chiuse con parametri, come si vede dalla clausola “M ⊧ ∀xϕ(x) se e solo se per ogni a ∈ dom(M), M ⊧ ϕ(a)”.

Esercizio 3.16 Sia α(x) è una formula la cui unica variabile libera è x. Se t e t′ sono termini chiusi con M(t) = M(t′), allora M ⊧ α(t) se e solo se M ⊧ α(t′).

Esercizio 3.17 Se M è isomorfa a N ed M ⊧ ϕ, allora N ⊧ ϕ.

4 Cenni sulla logica del secondo ordine

Nella logica del secondo ordine il concetto di segnatura e di L-struttura non cambia. Quello che cambia è il concetto di L-formula e di intepretazione di una L-formula in una L-struttura. In una L-formula del secondo ordine possono comparire due tipi di variabili: variabili su individui e su relazioni. Ogni variabile su relazioni ha un intero positivo ad essa associato detto la sua arità. I quantificatori ∀ ed ∃ possono essere applicati ad entrambi i tipi di variabili. Data una L-struttura M, le variabili su individui variano sugli elementi del dominio di M, mentre le variabili su relazioni di arità n variano sull’insieme di tutte le relazioni n-arie sul dominio di M.

Esempio 4.1 Sia L = {0, 1, +, ·}. L’assioma di induzione per i numeri naturali può essere formulato nel modo seguente usando una variabile “R” su relazioni unarie, e altre variabili x, y su individui:

∀R((R(0) ∧ ∀x(R(x) → R(x + 1))) → ∀yR(y))

Esempio 4.2 Sia L = {0, 1, +, ·, ≤}. L’assioma di completezza dei numeri reali, intesi come L-struttura, può essere formulato nel modo seguente usando una variabile “R” su relazioni unarie, e altre variabili x, y, x′ su individui:

∀R(“R ha un maggiorante” → “R ha un estremo superiore”)

dove “R ha un maggiorante” è la formula

∃x∀y(R(y) → y ≤ x)

mentre “R ha un estremo superiore” è la formula

∃x[∀y(R(y) → y ≤ x) ∧ ∀x′(∀y(R(y) → y ≤ x′) → x ≤ x′)].

La logica del secondo ordine ha capacità espressive molto superiori a quella del primo ordine, ma ha lo svantaggio che non si è possibile definire per essa un concetto adeguato di “dimostrazione formale” per il quale valga un teorema di completezza, cosa che invece è possibile per la logica del primo ordine (si veda la sezione sul sistema dimostrativo di Hilbert-Frege).

5 Teorie assiomatiche

5.1 Teorie, modelli, e conseguenza logica

Definizione 5.1 Sia M una L-struttura e sia ϕ una L-formula(con o senza parametri da M) con variabili libere incluse in {x_{1}, …, x_{n}}. La formula chiusa ∀x_{1} … x_{n}ϕ viene detta una chiusura universale di ϕ. Diciamo che ϕ è universalmente vera in M, oppure valida in M, se una sua chiusura universale è vera in M (cioè se M ⊧ ∀x_{1} … x_{n}ϕ). Detto in altri termini, ϕ è universalmente vera in M se è vera in M per qualsiasi valore delle sue variabili libere. Per formule chiuse la verità e la universale verità coincidono.

Notazione 5.2 La notazione M ⊧ ϕ è fino ad ora stata adoperata sono nel caso in cui ϕ è una formula chiusa. Ne estendiamo ora l’uso a formule qualsiasi sottointendendo i quantificatori universali con la convenzione che M ⊧ ϕ significa la stessa cosa di M ⊧ ∀x_{1} … x_{n}ϕ.

Ad esempio se M è un gruppo scriveremo M ⊧ x · y = y · x se e solo se M è commutativo.

Osservazione 5.3 Se M è una L-struttura ϕ è una L-formula, potrebbe capitare che nè ϕ nè la sua negazione ¬ϕ sia valida (= universalmente vera) in M. Per tali formule non vale quindi nè M ⊧ ϕ nè M ⊧ ¬ϕ. Ad esempio la formula x > 1 non è universalmente vera nel campo ordinato R dei numeri reali, ma neppure la sua negazione ¬(x > 1) è universalmente vera. Per una formula chiusa α invece si ha sempre che M ⊧ α oppure M ⊧ ¬α (se α non è vera, per definizione lo è la sua negazione). In generale le tavole di verità valgono solo per formule chiuse (che sono le uniche per cui ha senso chiedersi se sono vere in una data struttura). Ad esempio se M ⊧ ϕ ∨ ψ non è detto che M ⊧ ϕ o M ⊧ ψ, a meno che non assumiamo che ϕ e ψ siano formule chiuse.

Definizione 5.4 Una teoria T è una coppia consistente di una segnatura L e di un insieme di L-formule chiamate assiomi di T.

Definizione 5.5 Un modello di una L-teoria T è una L-struttura in cui risultano validi (universalmente veri) tutti gli assiomi di T. Se M è un modello di T scriviamo M ⊧ T. Quindi M ⊧ T se per ogni assioma ϕ di T, si ha M ⊧ ϕ. Indichiamo con Mod(T) la classe di tutti i modelli di T. Una L-teoria T si dice semanticamente coerente, o anche soddisfacibile, se ha almeno un modello.

Definizione 5.6 (Conseguenza logica) Sia ϕ una L-formula chiusa e T una Lteoria. Diciamo che ϕ segue logicamente da T, e scriviamo T ⊧ ϕ, se non esiste nessuna L-struttura che rende validi tutti gli assiomi di T e non rende valida ϕ. In altre parole:

T ⊧ ϕ se e solo se Mod(T) ⊆ Mod(ϕ)

ovvero tutte le L-strutture in cui tutti gli assiomi di T sono universalmente veri, rendono universalmente vera ϕ. In particolare se T è insoddisfacibile, cioè se Mod(T) = ∅, allora vale sempre T ⊧ ϕ.

Notiamo che il simbolo “⊧” viene usato in due modi diversi a seconda che a sinistra del simbolo vi sia una L-teoria (nel qual caso ⊧ rappresenta la relazione di conseguenza logica) o una L-struttura (nel qual caso ⊧ rappresenta la relazione di soddisfacibilità).

Definizione 5.7 (Teorie equivalenti) Due L-teorie T_{1} e T_{2} si dicono equivalenti se hanno le stesse conseguenze: {ϕ | T_{1} ⊧ ϕ} = {ϕ | T_{2} ⊧ ϕ}.

Esercizio 5.8 Due teorie sono equivalenti se e solo se hanno gli stessi modelli.

Ogni teoria è equivalente ad una teoria i cui assiomi sono formule chiuse: basta prendere la chiusura universale dei suoi assiomi. Senza perdita di generalità avremmo quindi potuto restringerci a teorie i cui assiomi sono formule chiuse, e usare la notazione T ⊧ ϕ solo nel caso di formule chiuse. Tuttavia ammettere formule aperte risulterà conveniente quando andremo a definire il concetto di dimostrazione formale nel sistema dimostrativo di Hilbert-Frege.

Definizione 5.9 (Formule logicamente valide) Sia L una data segnatura e sia ϕ una L-formula. Diciamo che ϕ è logicamente valida, e scriviamo ⊧ ϕ, se ϕ è valida in ogni L-struttura.

Osserviamo che se T è la L-teoria con un insieme vuoto di assiomi, allora ogni L-struttura è modello di T, e pertanto si ha ⊧ ϕ se e solo se T ⊧ ϕ.

Proposizione 5.10 Sia T una L-teoria e siano α e β due L-formule chiuse. Allora T ⊧ α → β se e solo se T, α ⊧ β, dove con la notazione “T, α” abbiamo indicato la L-teoria che ha come assiomi la formula α e tutti gli assiomi di T. Questa equivalenza traduce il fatto intuitivo che dimostrare α → β equivale a dimostrare β prendendo come ulteriore ipotesi α.

Osservazione 5.11 La precedente proposizione non si estende al caso in cui α e β non siano chiuse perchè ci sono dei quantificatori universali sottointesi di cui tenere conto. Ad esempio x = 0 ⊧ y = 0 significa ∀x(x = 0) ⊧ ∀y(y = 0), che esprime una affermazione vera. Invece ⊧ x = 0 → y = 0 significa ⊧ ∀xy(x = 0 → y = 0), che è falso.

Corollario 5.12 Se T è una teoria che ha come assiomi un numero finito di formule chiuse ϕ_{1}, …, ϕ_{k}, allora T ⊧ ψ se e solo se ⊧ ϕ_{1} ∧ … ∧ ϕ_{k} → ψ.

Dim. È facile dare una dimostrazione applicando direttamente le definizioni. Alternativamente possiamo applicare k volte la Proposizione 5.10 ottenendo che T ⊧ ψ se e solo se ⊧ ϕ_{1} → (ϕ_{2} → (… (→ ϕ_{k} → ψ))). Per concludere basta notare che A → (B → C) equivale a (A ∧ B) → C). QED

Il problema di stabilire se una data formula ψ segue dagli assiomi di una teoria T con un numero finito di assiomi (chiusi), si riconduce quindi al problema di stabilire se una certa altra formula a lei associata è logicamente valida. Il problema di determinare quali siano le formule logicamente valide acquista quindi una grande importanza. Purtroppo non esiste un algoritmo generale per stabilire se una formula è logicamente valida (Teorema di Church).

5.2 Teorie complete

Definizione 5.13 Una L-teoria T è completa (semanticamente) se innanzitutto ha un modello e inoltre per ogni L-formula chiusa ϕ, si ha T ⊧ ϕ oppure T ⊧ ¬ϕ (e non entrambe, altrimenti T non sarebbe semanticamente coerente).

Detto informalmente, una teoria è completa se è in grado di stabilire la verità o la falsità di qualsiasi enunciato, non lasciandone alcuno indeciso.

Osservazione 5.14 Una teoria T è completa se, preso un qualsiasi enunciato ϕ, o ϕ è vero in tutti i modelli di T, oppure ¬ϕ è vero in tutti i modelli di T. Non può capitare che ϕ sia vero in qualche modello e falso in un altro.

Esempio 5.15 Sia T la teoria dei gruppi, ovvero la teoria che ha come assiomi x · (y · z) = (x · y) · z, x · 1 = x, 1 · x = 1, x · x^{−1} = 1, x^{−1} · x = 1, formulati in un linguaggio con un simbolo di costante 1 per l’elemento neutro, un simbolo di funzione binaria · per l’operazione di gruppo, e un simbolo di funzione unario per l’inverso. Un gruppo è, per definizione, un modello di T. La teoria T non è completa. Sia infatti ϕ l’enunciato ∀x, y(x · y = y · x), che esprime la legge commutativa. Poiché esistono sia gruppi commutativi che non commutativi, non si ha nè T ⊧ ϕ nè T ⊧ ¬ϕ.

Un esempio di gruppo non commutativo è il gruppo delle matrici 2 × 2, dove 1 è intepretato come la funzione identità, e · come la moltiplicazione riga per colonne di matrici. Un esempio di gruppo commutativo è il gruppo additivo dei numeri interi, dove il simbolo · viene intepretato come la somma, e il simbolo 1 come lo zero (siamo liberi di farlo!).

Definizione 5.16 Un esempio di teoria completa è il seguente. Sia M una L-struttura (ad esempio un dato gruppo), e sia T h(M) la teoria che ha come assiomi tutti gli L-enunciati veri in M. Allora T h(M) è una L-teoria completa chiamata teoria completa della struttura M. L’esempio è un po’ artificioso in quanto si tratta di una teoria completa di cui gli assiomi non sono dati esplicitamente.

Esercizio 5.17 Una L-teoria T è completa se e solo se per ogni coppia di Lenunciati α e β si ha: T ⊧ α ∨ β se e solo se T ⊧ α o T ⊧ β.

Esercizio 5.18 Una teoria T è completa (nel senso semantico) se è soddisfacibile e se comunque si prenda un suo modello M si ha che T h(M) equivale a T.

5.3 Teorie deduttivamente chiuse

Definizione 5.19 Una L-teoria T si dice deduttivamente chiusa (da un punto di vista semantico) se l’insieme {ϕ | T ⊧ ϕ} delle sue conseguenze, coincide con l’insieme dei suoi assiomi.

Esercizio 5.20 Una teoria con un numero finito di assiomi, come ad esempio la teoria i cui assiomi sono gli assiomi dei gruppi, non è mai deduttivamente chiusa. Tuttavia ogni teoria T è equivalente ad una teoria T′ deduttivamente chiusa: basta prendere come insieme di assiomi per T′ l’insieme {ϕ | T ⊧ ϕ} (il lettore può fare per esercizio le dovute verifiche).

Abbiamo visto come da una teoria T possiamo ottenere una classe di Lstrutture semplicemente prendendo la classe Mod(T) dei suoi modelli. È possibile anche fare il percorso inverso, partendo da una classe di L-strutture, per ottenere una L-teoria.

Definizione 5.21 Data una classe K di L-strutture indichiamo con T h(K) la L-teoria che ha come assiomi gli enunciati che sono veri in ogni struttura A ∈ K.

Esercizio 5.22 La teoria T h(K) sopra definita è deduttivamente chiusa. Inoltre ogni teoria deduttivamente chiusa T è della forma T h(K) per una opportuna classe K di L-strutture: basta prendere K = Mod(T) e osservare che T h(Mod(T)) = {ϕ | T ⊧ ϕ}.

La seguente definizione e il conseguente esercizio mettono in luce una simmetria tra teorie e classi di strutture.

Definizione 5.23 Sia K una classe di L-strutture. Diciamo che K è una classe elementare se per qualche L-teoria T si ha K = Mod(T). Ad esempio la classe dei gruppi è elementare.

Esercizio 5.24 L’operazione T ↦ Mod(T) porta da teorie a classi elementari di strutture, mentre K ↦ T h(K) porta da classi di strutture a teorie deduttivamente chiuse. Se restringiamo la prima operazione a teorie deduttivamente chiuse, e la seconda operazione a classi elementari di strutture, allora le due operazioni diventano l’una l’inversa dell’altra. In altre parole per una teoria deduttivamente chiusa T abbiamo T = T h(Mod(T)) (mentre per T arbitraria in generale vale solo l’inclusione “⊆”) e per una classe elementare di strutture K abbiamo K = Mod(T h(K)) (mentre per K arbitraria in generale vale solo l’inclusione “⊆”).

Dall’Esercizio 5.18 segue:

Osservazione 5.25 Sia L-teoria T semanticamente coerente e deduttivamente chiusa. Allora T è completa se e solo se preso un qualsiasi suo modello M si ha T = T h(M) (ricordiamo che T h(M) è la teoria che ha come assiomi tutte gli enunciati veri in M).

Esercizio 5.26 Sia T una L-teoria semanticamente coerente e deduttivamente chiusa. Allora T è completa se e solo se è massimale tra le teorie semanticamente coerenti, cioè non è possibile ampliare l’insieme dei suoi assiomi in modo da ottenere una teoria che continua ad essere semanticamente coerente.

6 Insiemi di Hintikka

Gli insiemi di Hintikka sono usati nella dimostrazione di completezza di vari sistemi dimostrativi (vedi sezione sul sistema dimostrativo di Hilbert-Frege).

Definizione 6.1 (Insiemi di Hintikka) Sia T un insieme di L-formule chiuse. Diciamo che T è un insieme di Hintikka (per L) se per ogni scelta di L-formule chiuse ϕ, ψ si ha:

1. se ϕ ∈ T, allora ¬ϕ ∉ T,

2. se ¬¬ϕ ∈ T, allora ϕ ∈ T,

3. se ϕ ∧ ψ ∈ T, allora ϕ ∈ T e ψ ∈ T,

4. se ¬(ϕ ∧ ψ) ∈ T, allora ¬ϕ ∈ T o ¬ψ ∈ T,

5. se ϕ ∨ ψ ∈ T, allora ϕ ∈ T o ψ ∈ T,

6. se ¬(ϕ ∨ ψ) ∈ T, allora ¬ϕ ∈ T e ¬ψ ∈ T,

7. se ϕ → ψ ∈ T, allora ¬ϕ ∈ T o ψ ∈ T,

8. se ¬(ϕ → ψ) ∈ T, allora ϕ ∈ T e ¬ψ ∈ T,

9. se ∀xϕ(x) ∈ T, allora per ogni L-termine chiuso t, ϕ(t) ∈ T,

10. se ¬∀xϕ(x) ∈ T, allora esiste un L-termine chiuso t tale che ¬ϕ(t) ∈ T,

11. se ∃xϕ(x) ∈ T, allora esiste un L-termine chiuso t, tale che ϕ(t) ∈ T,

12. se ¬∃xϕ(x) ∈ T, allora per ogni L-termine chiuso t, ¬ϕ(t) ∈ T.

Per linguaggi senza simbolo di uguaglianza = possiamo fermarci qui. Altrimenti dobbiamo aggiungere le seguenti proprietà dell’uguaglianza:

1. (riflessività) per ogni L-termine chiuso t, t = t ∈ T,

2. (sostituibilità) per ogni L-formula ϕ(x) e termini chiusi t e t′, se t = t′ ∈ T, allora ϕ(t) ∈ T se e solo se ϕ(t′) ∈ T.

Nella ultima clausola possiamo anche limitarsi a formule atomiche ϕ(x).

Definizione 6.2 Un insieme di Hintikka completo è un insieme di Hintikka tale che per ogni L-formula chiusa ϕ, o ϕ o la sua negazione ¬ϕ appartengano a T (e non tutte e due, altrimenti non sarebbe di Hintikka).

Esercizio 6.3 Si consideri un linguaggio senza simbolo di uguaglianza nella segnatura L = {R, c}, dove R è un simbolo di relazione binario e c è un simbolo di costante. Si trovi un insieme di Hintikka finito contenente la formula ∀x∃y(R(x, y) ∨ R(y, x)). Si dimostri che se ampliamo L con l’aggiunta di un simbolo di funzione f, qualsiasi insieme di Hintikka contenente la formula sopra data è infinito.

Teorema 6.4 Ogni insieme di Hintikka T ha un modello M. Inoltre possiamo prendere M in modo tale che ogni elemento del dominio di M è l’interpretazione di un termine chiuso della segnatura L di T.

Dim. Per semplicità consideriamo prima il caso di linguaggi senza il simbolo di uguaglianza né simboli di funzione. In questo caso gli unici termini chiusi di L sono le costanti. Prendiamo come dom(M) l’insieme delle costanti di L. Dato un simbolo di relazione R di arità n, definiamo la sua interpretazione R^{M} ⊆ dom(M)^{n} come l’insieme di tutte le n-uple (c_{1}, …, c_{k}) tali che R(c_{1}, …, c_{n}) ∈ T. In questo modo abbiamo definito una L-struttura che rende veri tutti gli enunciati atomici in T, e falsi gli enunciati atomici non in T. Sia ora ϕ un arbitrario L-enunciato. Usando le proprietà di Hintikka segue per induzione sul numero dei connettivi di ϕ che se ϕ ∈ T, allora M ⊧ ϕ (se T è un insieme di Hintikka completo sarà anche vero che se ϕ ∉ T, allora M ⊧ ¬ϕ).

Consideriamo ad esempio il caso ¬ϕ ∈ T. Dalle proprietà di Hintikka segue che ϕ ∉ T. Se ϕ è atomica, concludiamo che M ⊧ ¬ϕ per definizione di M. Se invece ϕ non è atomica, allora deve cominciare con un connettivo. Supponiamo ad esempio che tale connettivo sia ∨, cioè ¬ϕ = ¬(α ∨ β). Usando le proprietà di Hintikka abbiamo ¬α ∈ T e ¬β ∈ T. Per induzione possiamo concludere M ⊧ ¬α e M ⊧ ¬β, da cui poi segue M ⊧ ¬(α ∨ β).

Lasciamo al lettore la verifica degli altri casi. Questo conclude la dimostrazione nel caso il linguaggio non ha simboli di funzione e il simbolo di uguaglianza.

Consideriamo ora il caso in cui L può contenere il simbolo di uguaglianza e simboli di funzione. Ricordiamo che il simbolo di uguaglianza deve essere interpretato come la relazione di uguaglianza, quindi se t = t′ ∈ T dobbiamo fare in modo che t e t′ siano interpretati con lo stesso elemento del modello M che vogliamo costruire.

A tal fine prendiamo come dom(M) l’insieme degli L-termini chiusi quozientato rispetto alla relazione di equivalenza ∼ definita da t ∼ t′ sse t = t′ ∈ T. Segue dalle proprietà di Hintikka dell’uguaglianza che ∼ è in effetti una relazione di equivalenza. Indichiamo con t/ ∼ la classe di equivalenza di t rispetto a ∼.

Dato un simbolo di funzione f di L di arità n definiamo la sua interpretazione f^{M}: dom(M)^{n} → dom(M) ponendo: f^{M}(t_{1}/ ∼, …, t_{n}/ ∼) = f(t_{1}, …, t_{n})/ ∼. Questa definizione è be posta perchè dalla proprietà di Hintikka di sostituibilità (applicata ripetute volte) segue che se t_{1} ∼ t′_{1}, …, t_{n} ∼ t′_{n} allora f(t_{1}, …, t_{n}) ∼ f(t′_{1}, …, t′_{n}).

Resta solo da definire l’interpretazione R^{M} dei simboli di relazione di L (se ve ne sono). Se R ha arità n e t_{1}, …, t_{n} sono termini chiusi, poniamo (t_{1}/ ∼, …, t_{n}/ ∼) ∈ R^{M} sse R(t_{1}, …, t_{n}) ∈ T. Questo è ben posto per la sostitutività. Abbiamo così definito una L-struttura M.

Per induzione sulla lunghezza dei termini chiusi t, segue che t^{M} = t/ ∼. Quindi se t = t′ ∈ T, allora t^{M} = t/ ∼ = t′/ ∼ = t^{′M}, e quindi M ⊧ t = t′ (si noti che per abuso di linguaggio abbiamo usato “=” sia come simbolo che come la vera relazione di uguaglianza). Viceversa se t = t′ ∉ T, allora t/ ∼ ≠ t′/ ∼ e M ⊧ t ≠ t′. Quindi M rende veri per lo meno gli enunciati di T della forma t = t′, e falsi gli enunciati della forma t = t′ che non sono in T. Similmente si verifica che R(t_{1}, …, t_{n}) ∈ T sse M ⊧ R(t_{1}, …, t_{n}). Quindi tra gli enunciati atomici (senza connettivi) M rende veri tutti e soli quelli che sono in T. Ragionando per induzione sulla complessità della formula, usando le proprietà di Hintitkka per i passi induttivi, vediamo che ogni ϕ ∈ T (non necessariamente atomica) è vera M. Consideriamo nel dettaglio il caso in cui ϕ è della forma ∃xθ(x). Se ϕ ∈ T, allora essendo T di Hintikka deve esistere un termine chiuso t tale che θ(t) ∈ T. Per induzione θ(t) è vero nel modello M. Ma allora deve essere vero anche ∃xθ(x). QED

Corollario 6.5 Se un insieme di L-enunciati T è incluso in un insieme T′ di Hintikka (possibilmente in un linguaggio L′ più esteso), allora T ha un modello. Se inoltre T è incluso in un insieme di Hintikka finito, allora T ha un modello finito.

Dim. Poichè T′ è di Hintikka T′ ha un modello M′. Ne segue che T ha come modello la restrizione di M′ al linguaggio di T. La parte sulla finitezza è lasciata al lettore. QED

Il precedente corollario è in effetti una condizione necessaria e sufficiente affinchè T abbia un modello. In effetti se T ha un modello M, il diagramma elementare di M, definito piú sotto, è un insieme di Hintikka contenente T.

Definizione 6.6 Data una L-struttura M definiamo la teoria ED(M), detta diagramma elementare di M, come la teoria nel linguaggio L[M] ottenuto da L aggiungendo un simbolo di costante c_{m} per ogni m ∈ dom(M), e avente come assiomi tutti gli L[M]-enunciati che risultano veri in M quando si interpreta c_{m} con m.

7 Completezza

Data una L-teoria T e una formula ϕ, vogliamo definire il concetto di “dimostrazione formale di ϕ da T ”. Mostreremo che esiste una tale dimostrazione formale se e solo se T ⊧ ϕ (ricordiamo che ciò significa: ogni modello di T è modello di ϕ). Quindi o esiste una dimostrazione formale di ϕ da T, oppure esiste un contromodello, ovvero una L-struttura in cui tutti gli assiomi di T sono validi, ma in cui ϕ non vale.

7.1 Il sistema dimostrativo di Hilbert-Frege

Nel sistema di Hilbert-Frege una dimostrazione formale di ϕ da T consiste di una successione finita di formule di cui l’ultima è ϕ, mentre le altre sono o assiomi di T, o “assiomi logici”, oppure seguono da precedenti formula tramite una “regola di inferenza”. Cominciamo con gli assiomi logici.

7.1.1 Assiomi logici

Sia L una segnatura, siano α, β, γ etc. arbitrarie L-formule (possibilmente aperte). Abbiamo i seguenti schemi di assiomi logici. Assiomi proposizionali. Ogni tautologia è un assioma logico, dove per tautologia intendiamo una L-formula che si ottiene da una tautologia del calcolo proposizionale sostituendo le variabili proposizionali con arbitrarie L-formule (non necessariamente chiuse). Ad esempio le seguenti sono tautologie per ogni scelta di α, β, γ.

A0) α → α

A1) α → (β → α)

A2) (α → (β → γ)) → ((α → γ) → (α → γ))

A3) ((¬β → ¬α) → ((¬β → α) → β))

Assiomi dell’uguaglianza.

Per ogni simbolo di funzione f in L (di arità n) e ogni simbolo di relazione R in L (di arità n) abbiamo i seguenti assiomi.

Riflessività) x = x.

Simmetria) x = y → y = x.

Transitività) x = y → (y = z → x = z).

Congruenza) x_{1} = y_{1} → (… → (x_{n} = y_{n} → (f(x_{1}, …, x_{n}) = f(y_{1}, …, y_{n})))).

Sostituibilità) x_{1} = y_{1} → (… → (x_{n} = y_{n} → (R(x_{1}, …, x_{n}) → R(y_{1}, …, y_{n})))).

Alternativamente avremmo potuto prendere come assiomi tutte le L-formule della forma t = t (dove t è un L-termine), più tutte le formule della forma t_{1} = t_{2} ∧ ϕ(t_{1}) → ϕ(t_{2}) e quelle della forma t_{1} = t_{2} ∧ ϕ(t_{2}) → ϕ(t_{1}). Assiomi sui quantificatori.

Sia α una formula e sia t un termine sostituibile al posto di una variabile x in α. Abbiamo gli assiomi.

• α(t) → ∃xα(x).

• ∀xα(x) → α(t).

7.1.2 Regole di inferenza

• (modus ponens) Dalle due premesse α e α → β posso trarre la conclusione β.

Notazione: \frac{α,α→β}{β}.

• (∀-introduzione) Sia x una variabile che non occorre libera nella formula α. Dalla premessa α → β posso trarre la conclusione α → ∀xβ.

Notazione: \frac{α→β}{α→∀xβ}.

• (∃-introduzione) Sia x una variabile che non occorre libera nella formula α. Dalla premessa α → β posso trarre la conclusione ∃xα → β.

Notazione: \frac{α→β}{∃xα→β}.

Alcuni degli assiomi e regole sono ridondanti. Ad esempio si sarebbe potuto definire ∃xα come ¬∀x¬α ed eliminare tutti gli assiomi e regole che riguardano ∃. Viceversa si sarebbe potuto definire ∀xα come ¬∃x¬α ed eliminare gli assiomi e regole del ∀. Cosí facendo non si perde nulla nel senso che gli assiomi e regole che sono stati omessi diventano derivabili dagli altri.

7.1.3 Teoremi

Sia T una L-teoria. I teoremi di T si definiscono induttivamente nel modo seguente (nel sistema di Hilbert-Frege): tutti gli assiomi di T e tutti gli assiomi logici (nella segnatura L) sono teoremi di T. Se le premesse di una regola di inferenza sono teoremi di T, anche la sua conclusione è un teorema di T. Niente altro è un teorema di T.

Se ϕ è un teorema di T, scriviamo T ⊢ ϕ. Se T è la L-teoria con un insieme vuoto di assiomi scriviamo ⊢ ϕ per T ⊢ ϕ. Ciò significa che ϕ è deducibile usando solamente gli assiomi logici.

7.1.4 Dimostrazioni formali

Una dimostrazione formale di ϕ da una L-teoria T (nel sistema Hilbert-Frege) è una sequenza finita di L-formule (α_{0}, α_{1}, …, α_{n}) tale che α_{n} = ϕ e ogni formula o è un assioma di T, o è un assioma logico, o segue da formule precedenti nella sequenza tramite una regola di inferenza. È facile verificare che ϕ è un teorema di T se e solo se esiste una dimostrazione di ϕ da T.

7.1.5 Alcuni utili metateoremi

Lemma 7.1 (compattezza, versione sintattica) Se T ⊢ ϕ, esiste una sottoteoria finita (cioè con un numero finito di assiomi) T′ di T tale che T′ ⊢ ϕ. In particolare , prendendo ϕ =⊥, se T non è HF -coerente anche una sua sottoteoria finita non lo è.

Dim. Basta osservare che una dimostrazione formale può usare solo un insieme finito di assiomi. QED

Esercizio 7.2

T ⊢ α(x) se e solo se T ⊢ ∀xα(x).

Dim. Una delle implicazioni segue dall’assioma ∀xα(x) → α(t) prendendo t = x. L’altra direzione segue dalla regola di inferenza \frac{ϕ→α}{ϕ→∀xα} prendendo come ϕ una formula dimostrabile in T e che non contiene la x libera e poi applicando il modus ponens e opportune tautologie (completare per esercizio). QED

Più difficile è il seguente:

Esercizio 7.3 Ogni tautologia si può dedurre dai quattro schemi di tautologia A0 - A3 sopra elencati, usando solamente la regola di Modus Ponens.

Definizione 7.4 Diciamo che una L-formula α è una conseguenza tautologica di L-formule β_{1}, …, β_{n} se (β_{1}∧… β_{n}) → α è una tautologia, o equivalentemente β_{1} → (β_{2} → … → (β_{n} → α)) è una tautologia.

Usando ripetute volte il modus ponens si dimostra:

Esercizio 7.5 Se T ⊢ β_{1}, …, T ⊢ β_{n} e α è conseguenza tautologica di β_{1}, …, β_{n}, allora T ⊢ α.

7.2 Teorema di correttezza per il calcolo dei predicati

Mostreremo che gli assiomi e le regole di inferenza che abbiamo dato corrispondono a metodi di ragionamento corretti.

Teorema 7.6 (Correttezza degli assiomi logici) Gli assiomi logici (su una segnatura L) sono logicamente validi (cioè universalmente veri in ogni L-struttura).

Dim. La dimostrazione userà a livello di “metateoria” gli stessi principi logici (se non ancora più complicati) di quelli di cui si vuole giustificare la correttezza a livello di “teoria oggetto” (la teoria oggetto è il sistema di Hilbert-Frege, la metateoria sono i ragionamenti che facciamo, al di fuori di tale sistema, per dimostrare proprietà del sistema). Se non altro per illustrare la differenza tra i vari livelli linguistici diamo comunque una dimostrazione.

Tralasciamo la verifica per gli assiomi proposizionali.

Il fatto che gli assiomi della uguaglianza siano logicamente validi segue semplicemente dal fatto che nella semantica di Tarski abbiamo imposto che il simbolo = venga interpretato come la relazione di uguaglianza, la quale gode ovviamente di tutte le proprietà espresse dagli assiomi della uguaglianza.

Restano da verificare gli assiomi che riguardano i quantificatori. Verifichiamo solamente la validità dell’assioma ∀xα(x) → α(t) dove t è un termine sostituibile per x in α. È qui che interviene in modo cruciale la definizione di “sostituibile”. Osserviamo che la formula ∀xα(x) → α(t) non è necessariamente un enunciato in quanto in primo luogo il termine t potrebbe contenere delle variabili, e in secondo luogo la formula α(x) stessa può contenere delle variabili libere diverse da x. Supponiamo che le variabili libere di ∀xα(x) → α(t) siano incluse in {y_{1}, …, y_{n}} (non escludiamo il caso in cui qualche y_{i} coincida con x che può verificarsi se t contiene la x). Dobbiamo mostrare che per ogni L-struttura M, abbiamo

M ⊧ ∀y_{1}, …, y_{n}(∀xα(x) → α(t))  (1)

Poichè t è sostituibile per x in α, le variabili di t sono incluse in {y_{1}, …, y_{n}}. Infatti se t contenesse qualche altra variabile z, allora z non non potendo essere libera in ∀xα(x) → α(t) (se no sarebbe una delle y_{i}), non può essere libera nemmeno in α(t) e pertanto deve essere stata legata dopo la sostituzione di t in α(x), contraddicendo il fatto che t era sostituibile.

Per la semantica di Tarski (1) equivale a:

Per ogni a_{1}, …, a_{n} ∈ dom(M),

M ⊧ (∀xα(x) → α(t))^{s}  (2)

dove s è la sostituzione (a_{1}/y_{1}, …, a_{n}/y_{n}).

La (2) equivale a

M ⊧ ((∀xα(x))^{s} → α^{s}(t^{s}))  (3).

Ora poichè le variabili di t sono incluse in {y_{1}, …, y_{n}}, t^{s} è un termine senza variabili, e quindi esiste b ∈ dom(M) con b = M(t^{s}). Ne segue che M ⊧ α^{s}(t^{s}) ↔ α^{s}(b), e quindi (3) equivale a:

M ⊧ (∀xα^{s}(x) → α^{s}(b))  (4)

La verità di questa ultima asserzione segue dalla semantica di Tarski del ∀ applicata alla formula con parametri α^{s}. QED

Cosa vuol dire che una regola di inferenza corrisponde a un metodo di ragionamento corretto? La seguente definizione fornisce una possibile risposta.

Definizione 7.7 Diciamo che una regola di inferenza è corretta, se ogniqualvolta le premesse della regola sono universalmente vere in una L-struttura M, allora la conclusione è universalmente vera in M.

Osservazione 7.8 La correttezza di una regola equivale alla validità logica di un enunciato corrispondente, cioè l’enunciato che esprime che la congiunzione delle quantificazioni universali delle premesse della regola implica la quantificazione universale della conclusione della regola.

Teorema 7.9 (Correttezza delle regole) Le regole di inferenza del sistema di Hilbert-Frege sono corrette.

Dim. Consideriamo solo la regola \frac{α→β}{α→∀xβ} dove x non appare libera in α. Supponiamo che le variabili libere di α e β siano incluse in {y_{1}, …, y_{n}}. Supponiamo che

M ⊧ ∀y_{1}, …, y_{n}(α → β)  (1).

Dobbiamo verificare che M ⊧ ∀y_{1}, …, y_{n}(α → ∀xβ). Ciò significa che per ogni valutazione delle variabili s: {y_{1}, …, y_{n}} → dom(M)

M ⊧ α^{s} → (∀xβ)^{s}  (2)

Poichè x non occorre libera nè in α (per ipotesi) nè in ∀xβ (perchè è quantificata da ∀x), la (2) equivale a

M ⊧ α^{s′} → (∀xβ)^{s′}

dove dom(s′) = dom(s) \ {x} e s′ coincide con s nel dominio comune. Notiamo che (∀xβ)^{s′} coincide con (∀xβ^{s′}) (usando x ∉ dom(s′)). Supponiamo per assurdo che M ⊧ α^{s′} e che M |̸= ∀xβ^{s′}. Allora esiste a ∈ dom(M) tale che M |̸= β^{s′}(a/x). Sia f l’unione delle sostituzioni s′ e (a/x). Allora M |̸= β^{f}. D’altra parte M ⊧ α^{f} (perché M ⊧ α^{s′} e le due formule con parametri α^{f} e α^{s′} coincidono in quanto x non è libera in α). Ora M ⊧ α^{f} e M |̸= β^{f} contraddicono la (1). QED

Teorema 7.10 (Teorema di correttezza) Se T ⊢ ϕ, allora T ⊧ ϕ.

Dim. Supponiamo T ⊢ ϕ e sia M un modello di T. Ne segue che tutti gli assiomi di T sono universalmente veri in M. D’altra parte anche gli assiomi logici sono universalmente veri in M (in quanto sono universalmente veri in ogni L-struttura) e le regole di inferenza preservano la universale verità in M. Quindi tutti i teoremi di T sono universalmente veri in M e in particolare M ⊧ ϕ. QED

In particolare prendento come T la L-struttura senza assiomi non-logici, abbiamo che se ⊢ ϕ allora ⊧ ϕ, cioè ϕ è logicamente valida.

Definizione 7.11 Sia ⊥ una formula chiusa tale che ⊢ ¬ ⊥, ad esempio una formula chiusa della forma ⊥= A ∧ ¬A.

Definizione 7.12 1. T è HF-coerente se e solo se T ⊬⊥.

2. T è HF-completa se è HF-coerente e per ogni L-formula chiusa ϕ si ha T ⊢ ϕ oppure T ⊢ ¬ϕ.

Dal teorema di correttezza segue:

Corollario 7.13 Se T ha un modello, allora T è HF-coerente.

7.3 Teorema di deduzione

Teorema 7.14 Sia L una segnatura, β una L-formula, e α una L-formula chiusa. Se T ∪ {α} ⊢ β, allora T ⊢ α → β (il viceversa è semplice).

Dim. Sia (β_{1}, …, β_{n}) una dimostrazione formale di β da T ∪ {α}. Mostreremo per induzione su i ≤ n che T ⊢ α → β_{i}. Assumiamo per ipotesi induttiva che per ogni j < i, T ⊢ α → β_{j}. Per mostrare che T ⊢ α → β_{i} distinguiamo vari casi.

Caso 1. β_{i} è un assioma logico oppure un assioma di T. Ne segue che T ⊢ β_{i} e quindi per conseguenza tautologica T ⊢ α → β_{i}.

Caso 2. β_{i} è α. Poichè α → α è uno degli assiomi logici del sistema HF, T ⊢ α → β_{i}.

Caso 3. β_{i} segue da due formule precedenti per modus ponens, diciamo da β_{j} e β_{k} (con j, k < i) dove β_{k} = β_{j} → β_{i}. Per ipotesi induttiva abbiamo T ⊢ α → β_{j} e T ⊢ α → (β_{j} → β_{i}). Per conseguenza tautologica T ⊢ α → β_{i}.

Caso 4. β_{i} segue da β_{j} per ∃-introduzione (j < i). Allora β_{j} è della forma γ → δ e β_{i} è ∃xγ → δ, dove x ∉ F v(δ). Per ipotesi induttiva T ⊢ α → (γ → δ). Per conseguenza tautologica T ⊢ γ → (α → δ). Poichè α è un enunciato, α non contiene la x libera, e quindi x ∉ F v(α → δ). Possiamo quindi applicare la regola di ∃-introduzione per concludere T ⊢ ∃xγ → (α → δ) e quindi per conseguenza tautologica T ⊢ α → (∃xγ → δ), ovvero T ⊢ α → β_{i}.

Caso 5. β_{i} segue da β_{j} per ∀-introduzione. Simile al caso 3. QED

Osservazione 7.15 Il teorema di deduzione non vale se α non è un enunciato. Ad esempio {x = 0} ⊢ {y = 0}, ma ⊬ {x = 0} → {y = 0}.

7.4 Completezza del sistema di Hilbert-Frege

Per HF-dimostrazione intendiamo una dimostrazione nel sistema di Hilbert-Frege.

Definizione 7.16 T è una teoria di Henkin se e solo se per ogni L(T)-enunciato della forma ∃xβ(x), esiste una costante c ∈ L(T), tale che T ⊢ ∃xβ(x) → β(c).

Esercizio 7.17 Gli assiomi logici e le regole di inferenza del sistema Hilbert-Frege sono tali che rimpiazzando un simbolo di costante c con una veriabile y in un assioma o una regola di inferenza in cui non occorre la y, si ottiene di nuovo un assioma o una regola del sistema. L’ipotesi che y non occorra nell’assioma o regola è essenziale: ∀zϕ(z) → ϕ(c) è un assioma logico del sistema di Hilbert-Frege, mentre ∀zϕ(z) → ϕ(y) non lo è a meno che y non sia sostituibile per z in ϕ.

Lemma 7.18 (Lemma sulle costanti) Se c è un simbolo di costante di L(T) che non viene menzionato in alcun assioma di T, e se T ⊢ α(c/x), allora T ⊢ ∀xα(x). Inoltre è possibile dare una HF-dimostrazione di ∀xα(x) da T che non menziona in alcuna sua formula la costante c.

Dim. Sia p una dimostrazione di α(c) da T. Rimpiazzando ovunque nella dimostrazione c con una nuova variabile y che non appare nè libera nè legata nelle formule di p, otteniamo una dimostrazione di α(y) da T. Per verificare ciò usiamo, oltre al fatto che c non è menzionata negli assiomi logici di T, anche l’esercizio precedente. Per concludere notiamo che da una dimostrazione di α(y) se ne ottiene una di ∀yα(y) per un risultato precedente, e da qui una di α(x) per particolarizzazione, e infine una di ∀xα(x). QED

Definizione 7.19 Un un enunciato di Henkin è un enunciato del tipo ∃xα(x) → α(c) dove c è un simbolo di costante.

Lemma 7.20 Se T è una teoria HF-coerente e T′ è ottenuta da T aggiungendo ai suoi assiomi un enunciato di Henkin ∃xα(x) → α(c), dove c è un nuovo simbolo di costante che non appartenere alla segnatura L di T, allora T′ è HFcoerente. (La segnatura di T′ è data da L′ = L ∪ {c}).

Dim. Se T′ è incoerente, allora T ∪ {∃xα → α(c)} ⊢_{L′} ⊥ dove ⊢_{L′} indica che la dimostrazione consiste di formule nella segnatura L′. Per il teorema di deduzione T ⊢_{L′} (∃xα(x) → α(c)) → ⊥. Per conseguenza tautologica T ⊢_{L′} ∃xα(x) e T ⊢_{L′} ¬α(c). Poichè c non compare nè in α nè tra gli assiomi di T, da T ⊢_{L′} ∃xα(x) possiamo dedurre T ⊢_{L} ∃xα(x) (rimpiazzando nella dimostrazione ogni occorrenza della variabile c con una variabile y che non compare nella dimostrazione), e da T ⊢_{L′} ¬α(c) otteniamo per il lemma sulle costanti T ⊢_{L} ∀x¬α(x). D’altra parte T ⊢_{L} ∃xα e ne segue facilmente che T è incoerente (basta mostrare nel sistema HF che ⊢ ∃xα → ¬∀x¬α e poi ragionare per conseguenza tautologica). QED

Lemma 7.21 L’unione di una catena {T_{i} | i ∈ I} di L-teorie HF-coerenti è HF-coerente.

Dim. Sia T = ⋃_{i∈ω} T_{i} e supponiamo che T ⊢⊥. Poichè una dimostrazione formale nel sistema HF può coinvolgere solo un numero finito di assiomi deve esistere un T_{i} che contiene tutti gli assiomi usati nella dimostrazione di ⊥ da T, e quindi T_{i} ⊢⊥. QED

Lemma 7.22 Se T è HF-coerente, esiste una teoria HF-coerente e di Henkin T_{H}, ottenuta aggiungendo a T un insieme di enunciati di Henkin, tale che L(T) ⊆ L(T_{H}) e Ax(T) ⊆ Ax(T_{H}).

Dim. Definiamo una operazione tra teorie T ↦ T^{∗} nel modo seguente. Sia L^{∗} il linguaggio che si ottiene da L = L(T) con l’aggiunta, per ogni enunciato di L della forma ∃xα, di una corrispondente nuova costante che indicheremo c(∃xα) (distinti enunciati corrispondendo a distinte costanti). Sia T^{∗} la teoria formulata nel linguaggio L^{∗} e i cui assiomi comprendono quelli di T e tutti gli enunciati di Henkin della forma ∃xα(x) → α(c(∃xα)/x) dove ∃xα(x) è un enunciato di L.

Usando ripetutamente il Lemma precedente si dimostra che qualsiasi sottoteoria finita di T^{∗} è HF-coerente, quindi anche T^{∗} è HF-coerente (in quanto una eventuale HF-dimostrazione di ⊥ può usare solo un numero finito di assiomi).

Si noti che T^{∗} non è necessariamente una teoria di Henkin perchè, pur essendo vero che tutti gli ∃-enunciati di L(T) hanno una corrispondente costante di Henkin, cio’ non è necessariamente vero per tutti gli ∃-enunciati di L(T^{∗}). Per porre rimedio a ciò dobbiamo iterare il procedimento T ↦ T^{∗} infinite volte come segue.

Sia T_{0} = T, T_{n+1} = T_{n}^{∗}. Sia T_{ω} l’unione delle teorie T_{n} per n ∈ ω. Poichè tutte le T_{n} sono coerenti lo è anche T_{ω} per il lemma precedente.

Per finire verifichiamo che T_{ω} è una teoria di Henkin. Sia infatti ∃xα un ∃-enunciato di L(T_{ω}). Poichè ∃xα puo’ contenere solo un numero finito delle nuove costanti, esiste n ∈ ω tale che ∃xα è un enunciato di L(T_{n}). Ma allora ∃xα(x) → α(c(∃xα)/x) è un assioma di T_{n+1} e quindi di T_{ω}. QED

Lemma 7.23 Sia T una teoria HF-coerente e sia ϕ un L-enunciato. Allora almeno una delle due teorie T ∪ {ϕ} e T ∪ {¬ϕ} (possibilmente anche tutte e due) è HF-coerente.

Dim. Supponiamo per assurdo che T, ϕ ⊢⊥ e T, ¬ϕ ⊢⊥. Allora per il teorema di deduzione T ⊢ ϕ →⊥ e T ⊢ ¬ϕ →⊥, e quindi per conseguenza tautologica T ⊢⊥. QED

Lemma 7.24 (Lemma di Lindembaum) Sia T una L-teoria HF-coerente. Allora esiste una teoria HF-coerente T′ nello stesso linguaggio L, tale che per ogni L-enunciato ϕ abbiamo ϕ ∈ T′ oppure ¬ϕ ∈ T′. In particolare T′ è HFcompleta.

Dim. Nel caso che L sia numerabile anche l’insieme degli L-enunciati lo sarà e possiamo procedere nel modo seguente. Sia {ϕ_{n} | n ∈ ω} una enumerazione di tutti gli L-enunciati. Definiamo T_{0} = T. Supponiamo induttivamente di aver già definito una teoria HF-coerente T_{n}. Per il lemma precedente sappiamo che almeno una delle due teorie T_{n} ∪{ϕ_{n}} e T_{n} ∪{¬ϕ_{n}} è HF-coerente. Scegliamone una delle due che lo sia e chiamiamola T_{n+1}. Ora consideriamo la teoria T_{ω} = ⋃_{n∈ω} T_{n}. Poiché l’unione di una catena di teorie HF-coerenti è HF-coerente T_{ω} è HF-coerente, e possiamo porre T′ = T_{ω}.

Nel caso in cui L non sia numerabile dobbiamo iterare la costruzione precedente nel transfinito, oppure fare appello al lemma di Zorn (se un insieme parzialmente ordinato gode della proprietà che ogni catena ha un maggiorante, allora esiste un elemento massimale). Applichiamo il lemma di Zorn alla classe di tutte le L-teorie HF-coerenti e contenenti T, ordinate per inclusione. Sappiamo che in questo ordine ogni catena ha un maggiorante (l’unione), e quindi esiste una teoria HF-coerente massimale T′ contenente T. Tale T′ ha le proprietà richieste perché se no esisterebbe un L-enunciato ϕ tale che T′ non contiene né ϕ né la sua negazione. Ma una delle teorie T′ ∪ {ϕ} e T′ ∪ {¬ϕ} è HF-coerente, e questo contraddice la massimalità di T′. QED

Teorema 7.25 (Teorema di completezza del sistema di Hilbert - Frege) Se una L-teoria T è HF-coerente, allora T è soddisfacibile.

Dim. Applicando prima il Lemma 7.22 e poi il Lemma di Lindembaum 7.24 abbiamo che T è inclusa in una teoria T′ di Henkin e HF-completa, in un linguaggio ampliato L′. In effetti i Lemmi ci forniscono una teoria T′ con l’ulteriore proprietà che per ogni L-formula chiusa ϕ, o ϕ o la sua negazione appartengono agli assiomi di T′. Ne segue che T′ è deduttivamente chiusa (in senso sintattico), cioè per ogni enunciato ϕ tale che T′ ⊢ ϕ, si ha che ϕ appartiene agli assiomi di T′ (altrimenti la sua negazione ci apparterrebbe e T′ non sarebbe HF-coerente).

Per il teorema 6.4 basta mostrare che T′ è un insieme di Hintikka (identifichiamo la teoria T′ con l’insieme dei suoi assiomi). Per verificare la clausola relativa al quantificatore esistenziale supponiamo che ∃xϕ(x) ∈ T′. Essendo di Henkin, T′ contiene l’assioma ∃xϕ(x) → ϕ(c) per un certo simbolo di costante c. Dobbiamo mostrare che T′ contiene ϕ(c). In caso contrario T′ conterrebbe ¬ϕ(c), e questo è assurdo perchè allora per conseguenza tautologica T′ conterrebbe ¬∃xϕ(x), contraddicendo il fatto che una teoria HF-coerente non può contenere al tempo stesso una formula e la sua negazione. Le verifica delle altre clausole nella definizione di insieme di Hintikka sono lasciate al lettore. QED

Corollario 7.26 T ⊢ ϕ se e solo se T ⊧ ϕ.

Dim. Possiamo assumere che T ∪ {ϕ} consista unicamente di formule chiuse (se no mettiamo dei quantificatori universali, e nulla cambia). La direzione → segue dal teorema di correttezza. Per l’altra direzione osserviamo che se T ⊬ ϕ, allora T, ¬ϕ ⊬⊥ (se no per il teorema di deduzione T ⊢ ¬ϕ →⊥ e per conseguenza tautologica T ⊢ ϕ). Dal teorema precedente segue ora che esiste un modello di T, ¬ϕ, e quindi T |̸= ϕ. QED

8 Compattezza

8.1 Teorema di compattezza

Teorema 8.1 (Teorema di compattezza) Sia T una L-teoria e ϕ una L-formula.

1. Se T ⊧ ϕ, allora esiste una sottoteoria finita T′ di T tale che T′ ⊧ ϕ.

2. Se ogni sottoteoria finita di T ha un modello anche T ha un modello.

Dim. 1. Per il teorema di completezza T ⊧ ϕ equivale a T ⊢ ϕ, ovvero all’esistenza di una dimostrazione formale di ϕ da T. Poichè dimostrazione formale è una successione finita di formule, basta prendere come sottoteoria finita T′ quella formata dagli assiomi che occorrono in una fissata dimostrazione formale di ϕ.

2. Il fatto che T non abbia modello equivale all’affermazione che T ⊧⊥ (si ricordi che ⊥ denota una formula che equivale alla negazione di una tautologia). Ora basta applicare il punto 1. prendendo ϕ =⊥. QED

8.2 Teorema di Löweinheim - Skolem verso l’alto

Teorema 8.2 (Löweinheim - Skolem verso l’alto)

1. Sia T una L-teoria. Se per ogni intero positivo n esiste un modello M_{n} di T di cardinalità maggiore di n, allora T ha un modello infinito.

2. Se T ha un modello infinito, allora T ha modelli di cardinalità arbitrariamente grande.

Dim. Supponiamo che per ogni n T abbia un modello di cardinalità maggiore di n. Sia κ un numero cardinale infinito e sia L′ il linguaggio ottenuto da L con l’aggiunta di un insieme C di cardinalità κ di nuovi simboli di costante. Sia T′ la L′-teoria i cui assiomi sono quelli di T più tutti gli assiomi della forma c ≠ c′, dove c, c′ sono costanti distinte di C. Dimostriamo innanzitutto che ogni sottoteoria finita S di T′ ha un modello. A tal fine osserviamo che S può contenere solo un numero finito dei nuovi assiomi, ed esiste dunque un numero naturale n tale che i nuovi assiomi sono della forma c_{i} ≠ c_{j}, per 1 ≤ i < j ≤ n. Scegliamo un modello A di T di cardinalità ≥ n, e consideriamo n elementi distinti a_{1}, …, a_{n} di A. Sia A′ la L′-struttura che espande A interpretando c_{i} con a_{i}. Tale A′ è un modello di S. Per il teorema di compattezza possiamo concludere che T′ ha un modello B, che deve essere di cardinalità ≥ κ in quanto deve verificare tutti i nuovi assiomi c ≠ c′. La restrizione di B al linguaggio originale L è una L-struttura di cardinalità ≥ κ modello di T. QED

9 Elementare equivalenza e sottostrutture elementari

9.1 Elementare equivalenza

Definizione 9.1 Due L-strutture A e B si dicono elementarmente equivalenti, A ≡ B se e solo se hanno la stessa teoria completa: T h(A) = T h(B).

In altre parole due strutture A e B sono elementarmente equivalenti se e solo se non cè nessuna proprietà del primo ordine che le distingue, cioè per ogni L-enunciato ϕ, A ⊧ ϕ se e solo se B ⊧ ϕ.

Un caso particolare di due strutture elementarmente equivalenti è dato da due strutture isomorfe, le quali non sono distinguibili da nessuna proprietà strutturale (che non faccia riferimento cioè alla natura degli elementi del dominio), e quindi a maggior ragione da nessuna proprietà del primo ordine.

9.2 Sottostrutture elementari

Definizione 9.2 (Immersione elementare) Un morfismo f: A → B tra due Lstrutture si dice una immersione elementare se per ogni n e per ogni L-formula ϕ(x_{1}, …, x_{n}) con variabili libere incluse in {x_{1}, …, x_{n}} e per ogni a_{1}, …, a_{n} ∈ A, si ha:

se A ⊧ ϕ(a_{1}, …, a_{n}), allora B ⊧ ϕ(f(a_{1}), …, f(a_{n}))

Siccome questa implicazione deve valere per tutte le ϕ, allora rimpiazzando ϕ con la sua negazione vediamo che deve in effetti valere un doppia implicazione: A ⊧ ϕ(a_{1}, …, a_{n}), se e solo se B ⊧ ϕ(f(a_{1}), …, f(a_{n})).

In generale la maggior parte dei morfismi che un algebrista considera non sono elementari. Essere elementare è una condizione molto forte che non si verifica molto spesso.

Poichè tra le formule ϕ c’è anche il predicato di non-uguaglianza ¬(x = y), una immersione elementare è necessariamente iniettiva (ed è quindi un isomorfismo sulla sua immagine).

Un esempio di immersione elementare è l’inclusione del campo dei numeri reali algebrici nel campo dei numeri reali. Un esempio più semplice è l’immersione dei numeri razionali nei numeri reali se consideriamo solo la struttura di ordine. Invece l’immersione dei razionali nei reali come anelli non è elementare: basta considerare la formula (senza variabili libere) ¬∃x(x^{2} = 2). Essa è vera in Q e non in R.

Una ovvia condizione necessaria, ma non sufficiente, affinché esista una immersione elementare di A in B è che A ≡ B, cioè che A sia elementarmente equivalente a B: (basta considerare nella definizione di immersione elementare formule senza variabili libere).

Definizione 9.3 (Sottostruttura elementare) Una sottostruttura B di A si dice sottostruttura elementare, e scriviamo A ≺ B, se e solo se la inclusione di A in B è una immersione elementare.

Il seguente esempio illustra la differenza tra elementare equivalenza e sottostruttura elementare. Il punto cruciale da osservare è che il concetto di elementare equivalenza fa riferimento a formule senza parametri, mentre quello di sottostruttura elementare fa riferimento a formule con parametri.

Esempio 9.4 Sia L = (<) e consideriamo la L-struttura costituita dall’insieme ordinato dei numeri interi Z, e la sua sottostruttura 2Z costituita dai numeri pari. Allora 2Z è elementarmente equivalente a Z (in quanto è addirittura isomorfo), ma non è una sua sottostruttura elementare perchè la formula ∃x(2 < x < 4), con parametri da 2Z, è vera in Z ma non in 2Z.

La seguente proposizione mostra come rimpiazzare un’immersione con una sottostruttura (che sarà elementare se l’immersione era elementare).

Proposizione 9.5 Se f: A → B è una immersione (elementare), allora esiste una L-struttura B′ isomorfa a B tale che A è una sottostruttura (elementare) di B′.

Dim. Sia f(A) ⊆ B l’immagine di f, e sia X un insieme della stessa cardinalità di B \ f(A) e disgiunto da A. Definiamo B′ = A ∪ X. Ne segue che c’è una corrispondenza biunivoca h: B′ → B che coincide con f su A. Definiamo le funzioni e le relazioni su B′ in modo da ottenere una struttura B′ con dominio B′ tale che h sia non solo una corrispondenza biunivoca, ma un isomorfismo da B′ a B. QED

Definizione 9.6 Data una sottostruttura (non necessariamente elementare) A di B, diciamo che una formula ϕ(x_{1}, …, x_{n}) è preservata verso l’alto se per ogni a_{1}, …, a_{n} ∈ A, si ha:

se A ⊧ ϕ(a_{1}, …, a_{n}), allora B ⊧ ϕ(a_{1}, …, a_{n})

Se invece vale l’implicazione da B ad A diciamo che ϕ è preservata verso il basso.

Usando questa terminologia vediamo che A è una sottostruttura elementare di B se e solo se tutte le formule sono preservate sia verso l’alto che verso il basso (prendendo le negazioni si vede che se tutte sono preservate verso l’alto lo sono anche verso il basso).

Esempio 9.7 Consideriamo due anelli A ⊆ B, intesi come L-strutture con L = {0, 1, −1, +, ·}, e un polinomio f a coefficienti in A. Il fatto che f abbia uno zero in A può essere espresso con la formula ∃x⃗f(x⃗) = 0. Questa formula contiene i coefficienti a_{1}, …, a_{n} del polinomio come parametri, e per esplicitare la loro presenza possiamo riscrivere la formula come ∃x⃗g(x⃗, a_{1}, …, a_{n}) = 0 dove g(x⃗, y_{1}, …, y_{n}) è un polinomio a coefficienti in Z (rappresentabile con una L-formula senza parametri). La L-formula ∃x⃗g(x⃗, x_{1}, …, x_{n}) = 0 è ovviamente preservata verso l’alto, perchè se un polinomio a coefficienti in A ha una soluzione in A, ha anche una soluzione in B.

In generale tutte le formule esistenziali, cioè del tipo ∃x⃗ϕ(x⃗, y⃗), dove ϕ non ha quantificatori, sono preservate verso l’alto. Vicerversa tutte le formule universali, cioè del tipo ∀x⃗ϕ(x⃗, y⃗), dove ϕ non ha quantificatori, sono preservate verso il basso. Ad esempio una sottostruttura di un gruppo è sempre un gruppo, perché gli assiomi dei gruppi sono di tipo universale.

Per gli altri tipi di formule può non esserci nè la preservabilità verso l’alto nè verso il basso. Ad esempio la formula ∃x∀y(x ≤ y) che esprime l’esistenza di un minimo in un ordine lineare non è preservata nè verso l’alto nè verso il basso (Z non ha un minimo, N ⊆ Z lo ha).

Tutte le formule atomiche sono preservate sia verso l’alto che verso il basso come segue facilmente dalla definizione di sottostruttura. Sono solo i quantificatori che distruggono la preservabilitá. Se una classe di formule è preservata sia verso l’alto che verso il basso, lo è anche la classe di tutte le formule che si ottengono da queste con i connettivi booleani ¬, ∧, ∨. I due connettivi ∧ e ∨, mantengono la preservabilità verso l’alto, il connettivo ¬ inverte la preservabilitá verso l’alto con quella verso il basso.

Osservazione 9.8 Si può dimostrare che una L-formula è preservate verso l’alto per tutte le possibili scelte di L-strutture A ⊆ B se e solo se è logicamente equivalenti a una formula esistenziale.

9.3 Teorema di Lowenheim - Skolem verso il basso

Lemma 9.9 (Criterio di Tarski - Vaught) Consideriamo due L-strutture A ⊆ B. Supponiamo che per ogni L-formula della forma ∃yϕ(y, x_{1}, …, x_{n}) e parametri a_{1}, …, a_{n} ∈ A, si abbia che se B ⊧ ∃yϕ(y, a_{1}, …, a_{n}), allora esiste a ∈ A tale che B ⊧ ϕ(a, a_{1}, …, a_{n}). Ne segue che A ≺ B. (∃yϕ(y, x_{1}, …, x_{n}) non è necessariamente una formula esistenziale perchè potrebbe contenere altri quantificatori all’interno.)

Dim. Per induzione sul numero dei connettivi della formula θ(x_{1}, …, x_{k}) mostriamo che per ogni a_{1}, …, a_{k} ∈ A, B ⊧ θ(a_{1}, …, a_{k}) se e solo se A ⊧ θ(a_{1}, …, a_{k}), cioè θ è preservata in entrambe le direzioni.

Se θ è atomica, allora l’equivalenza da dimostrare segue dal fatto che A è una sottostruttura di B.

Se una classe di formule è preservata in entrambe le direzioni, anche tutte le formule che si ottengono da esse usando i connettivi booleani lo è.

L’unico caso interessante è quello di formule della forma ∃yϕ(y, x_{1}, …, x_{n}) per le quali possiamo usare le nostre ipotesi:

A ⊧ ∃yϕ(y, a⃗)

se e solo se esiste c ∈ A tale che A ⊧ ϕ(c, a⃗)

se e solo se, per ipotesi induttiva (poiché ϕ ha meno connettivi di ∃yϕ), esiste c ∈ A tale che B ⊧ ϕ(c, a⃗)

se e solo se, per le ipotesi, B ⊧ ∃yϕ(y, a⃗). QED

In modo simile si dimostra:

Esercizio 9.10 Una condizione necessaria e sufficiente affinché A sia una sottostruttura elementare di B è che le formule esistenziali siano preservate verso il basso (cioè in direzione opposta rispetto a quella in cui sono naturalmente preservate).

Definizione 9.11 (Chiusura di un insieme rispetto ad una famiglia di funzioni). Sia A un insieme, e sia F una collezione di funzioni tali che ogni f ∈ F è una funzione da A^{n} ad A per qualche n ∈ N (se n = 0, f è un elemento di A). Sia B un sottoinsieme di A. Diciamo che B è chiuso rispetto alle funzioni di F se per ogni funzione f ∈ F e per ogni b_{1}, …, b_{n} ∈ B (dove n è il numero degli argomenti di f), si ha f(b_{1}, …, b_{n}) ∈ B. Sia X un sottoinsieme di A. La chiusura di X rispetto a F, denotata ⟨X⟩^{F}, è l’intersezione della famiglia di tutti i sottoinsiemi di A che contengono X e sono chiusi rispetto alle funzioni di F (tale famiglia non è vuota in quanto A stesso vi appartiene). L’insieme ⟨X⟩^{F} è il più piccolo (nel senso che è incluso in tutti gli altri) sottoinsieme B di A che contiene X ed è chiuso rispetto alle funzioni di F.

Lemma 9.12 ⟨X⟩^{F} coincide con l’unione ⋃_{k∈ω} X_{k} dove X_{0} = X e X_{k+1} è l’insieme di tutti gli elementi a ∈ A che si ottengono applicando ad elementi di ⋃_{i=0}^{k} X_{i} una delle funzioni di F.

Dim. L’inclusione X_{k} ⊆ ⟨X⟩^{F} si mostra facilmente per induzione su k usando, per il passo induttivo, il fatto che ⟨X⟩^{F} è chiuso rispetto alle funzioni di F . Ne consegue che ⋃_{k∈N} X_{k} ⊆ ⟨X⟩^{F}. Per l’inclusione inversa ⟨X⟩^{F} ⊆ ⋃_{k∈N} X_{k} è sufficiente dimostrare che ⋃_{k∈N} X_{k} è chiuso rispetto alle funzioni di F (essendo ⟨X⟩^{F} contenuto in tutti gli insiemi chiusi per F e contenenti X). Se f ∈ F ha arità n e a_{1}, …, a_{n} ∈ ⋃_{n∈N} X_{k}, per vedere che f(a_{1}, …, a_{n}) appartiene a ⋃_{n∈N} X_{k} usiamo il fatto che, essendo in numero finito, gli elementi a_{1}, …, a_{n} apparterranno tutti ad una certa unione finita Y_{k} = ⋃_{i=0}^{k} X_{i}, e pertanto f(a_{1}, …, a_{n}) apperterrà a Y_{k+1} = ⋃_{i=0}^{k+1} X_{i}, che è incluso in ⋃_{n∈N} X_{k}. QED

Lemma 9.13 La cardinalità di ⟨X⟩^{F} è minore o uguale al massimo tra la cardinalità di X, la cardinalità di F, ed ℵ_{0}.

Dim. Scriviamo ⟨X⟩^{F} = ⋃_{k∈N} X_{k} come sopra e sia α il massimo tra la cardinalità di X, la cardinalità di F, ed ℵ_{0}. Mostriamo per induzione su k che Card(X_{k}) ⊆ α. Il caso k = 0 è ovvio. Per il passo induttivo useremo il fatto che il prodotto e la somma di due numeri cardinali infinity β, γ coincide con il massimo dei due. In particolare che se X_{k} ha cardinalità ≤ α, anche qualsiasi prodotto cartesiano finito (X_{k})^{n} ha cardinalità ≤ α (qui usiamo il fatto che α è almeno ℵ_{0}). Ne segue che se f è una funzione di F di arità n, l’insieme Im(f_{|X_{k}}) dei valori che f può assumere quando viene applicata ad n argomenti in X_{k} ha cardinalità ≤ α (in quanto l’immagine di una funzione ha cardinalità minore o uguale alla cardinalità del suo dominio). Ora per definizione X_{k+1} è l’unione ⋃_{f∈F} Im(f_{|X_{k}} delle immagini delle varie f ristrette ad X_{k}, e possiamo limitare la cardinalità di tale unione con il prodotto |F| × α, che è uguale a α. QED

Teorema 9.14 (Teorema di Lowenheim-Skolem verso il basso) Se A è una Lstruttura e X ⊆ A è un sottoinsieme del suo dominio, allora esiste una sottostruttura elementare B ≺ A con dominio B ⊇ X e tale che B ha cardinalità minore o uguale al massimo tra |X|, |L|, ed ℵ_{0}.

Dim. Possiamo associare ad ogni formula della forma ∃yϕ(y, x_{1}, …, x_{n}) una funzione f_{∃yϕ}: A^{n} → A, detta funzione di Skolem della formula, nel modo seguente (l’esistenza di f sarà garantita dall’“assioma della scelta”). Dati a_{1}, …, a_{n} ∈ A, se esiste un a ∈ A tale che A ⊧ ϕ(a, a_{1}, …, a_{n}), allora scegliamo un tale a (se ne esiste più di uno facendo una scelta arbitraria) e poniamo f(a_{1}, …, a_{n}) = a. Se invece un tale a non esiste, definiamo f(a_{1}, …, a_{n}) come un arbitrario elemento di A. In entrambi i casi, se f(a_{1}, …, a_{n}) = a, si avrà A ⊧ ∃yϕ(y, a_{1}, …, a_{n}) → ϕ(a, a_{1}, …, a_{n}). Sia F l’insieme di tutte le funzioni di Skolem, una per ogni formula. La cardinalità di F è minore o uguale alla cardinalità delle L-formule, che è il massimo tra |L| ed ℵ_{0}. Sia B = ⟨X⟩^{F} la chiusura di X rispetto alle funzioni di Skolem (per assicurarci che B non sia vuota, possiamo prendere, senza perdita di generalità, X non vuoto). Ne segue che B è chiusa in particolare rispetto alle funzioni h^{A} che interpretano i simboli di funzione h della segnatura L. Infatti se h ∈ L è un simbolo di funzione di arità n, la funzione di Skolem associata alla formula ∃y(y = h(x_{1}, …, x_{n})) coincide con h^{A}. Similmente, ponendo n = 0, si mostra che B contiene le interpretazioni dei simboli di costante di L. Pertanto B è il dominio di una sottostruttura di A. Per vedere che B è una sottostruttura elementare si applica il criterio di Tarski - Vaught osservando che le funzioni di Skolem f_{∃yϕ} forniscono quei testimoni a = f_{∃yϕ}(a_{1}, …, a_{n}) ∈ ⟨X⟩^{F} dei quantificatori esistenziali che sono richiesti nel criterio. QED

Corollario 9.15 Se la teoria degli insiemi di Zermelo-Fraenkel ha un modello, ne ha anche uno numerabile.

Esempio 9.16 Per il teorema di Lowenheim - Skolem il campo ordinato dei numeri reali R = (R; +, ·, 0, 1, <) ha una sottostruttura elementare numerabile. Una tale sottostruttura è il campo F dei numeri reali algebrici.

10 Cenni di teoria della calcolabilità

10.1 Algoritmi e funzioni calcolabili

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

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

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

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

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

Un esempio classico di funzione calcolabile è dato dalla funzione da N^{2} a N che dati due numeri x e y fornisce il massimo comun divisore di x ed y (usiamo l’algoritmo di Euclide delle divisioni successive). Probabilmente tutte le funzioni da N ad N conosciute da uno studente che non abbia seguito un corso di logica sono calcolabili. Chiaramente può esistere più di un algoritmo per calcolare la stessa funzione, alcuni più efficienti altri meno.

10.2 Funzioni calcolabili parziali

L’esecuzione di un algoritmo procede per passi discreti. Certi algoritmi, come l’algoritmo di Euclide per trovare il massimo comun divisore, terminano dopo un numero finito di passi per qualsiasi dato di ingresso. Altri algoritmi terminano dopo un numero finito di passi solamente per certi valori dei dati di ingresso, mentre per altri valori vanno avanti all’infinito senza fermarsi mai.

Esempio 10.1 Consideriamo il problema di stabilire, dato un polinomio p(x_{1}, …, x_{n}) a coefficienti interi, se l’equazione p(x_{1}, …, x_{n}) = 0 ha soluzioni intere (non ci interessa trovare la soluzione, solo stabilire se esista o no). È certamente possibile progettare un algoritmo che, preso in ingresso un polinomio p(x⃗), prova a sostituire alle variabili del polinomio tutti i possibili valori interi l’uno dopo l’altro in qualche ordine, fermandosi se e quando si trova una soluzione intera di p(x⃗) = 0. Chiaramente tale algoritmo si ferma in un numero finito di passi se la soluzione c’è, ma va avanti all’infinito senza fornire alcuna risposta, nè positiva nè negativa, se la soluzione non c’è. Abbiamo qui un esempio di algoritmo che non si ferma per certi dati di ingresso (in questo caso il dato di ingresso è il polinomio).

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

Ci si può ovviamente chiedere se si può far di meglio, ovvero se sia possibile progettare un algoritmo che fornisca sempre dopo un numero finito di passi una risposta positiva o negativa alla domanda se p(x⃗) = 0. Se ci limitiamo a polinomi in una variabile, o ad altri casi particolari, ciò è possibile, ma per polinomi arbitrari si può dimostrare che un algoritmo che termini sempre non c’è. L’analogo problema in cui si chiede la soluzione di soluzioni reali anzichè intere, può invece sempre essere risolto in un numero finito di passi grazie al cosiddetto “algoritmo di Sturm”.

Il concetto di algoritmo che può non fermarsi su alcuni dati di ingresso, conduce in modo naturale alla considerazione di “funzioni parziali”. L’idea è di introdurre una distinzione tra il dominio dei possibili valori di ingresso, e il sottodominio di quei valori per i quali l’algoritmo termina.

Definizione 10.2 Una funzione parziale da A a B può essere definita come una funzione da A a B∪{↑} (unione disgiunta). Possiamo associare ad ogni algoritmo M una funzione parziale f_{M} nel modo seguente. Supponiamo che l’algoritmo M prenda in ingresso elementi dall’insieme A (in una fissata rappresentazione) e fornisca in uscita, nei casi in cui la computazione termina dopo un numero finito di passi, elementi di un insieme B (in una fissata rappresentazione). La funzione parziale f_{M}: A → B ∪ {↑} è così definita:

f_{M}(a) = b se M con input a fornisce in uscita b,

f_{M}(a) =↑ se M con input a non si ferma mai.

Una funzione parziale f: A → B ∪ {↑} si dice calcolabile parziale se esiste un algoritmo M tale che f = f_{M}. Useremo anche la notazione f: A ⇀ B per indicare il fatto che f è una funzione parziale da A a B. Una funzione parziale che non assume mai il valore ↑ si dice totale.

10.3 Macchine di Turing

Un tentativo di formalizzare il concetto di funzione calcolabile senza far riferimento al concetto intuitivo di algoritmo è stato compiuto da Alan Turing nel 1936. Una macchina di Turing è un calcolatore ideale fornito di due tipi di memoria: interna ed esterna. Ad ogni dato momento entrambi i tipi di memoria possono contenere una quantità finita di informazione, ma mentre la memoria esterna è potenzialmente illimitata, la memoria interna ha una fissata capacità massima che non può essere superata nell’intero processo di elaborazione. La macchina è inoltre fornita di un puntatore che scandisce l’area della memoria esterna sotto esame in un dato momento e di un “programma” che determina come deve essere alterata la memoria e la posizione del puntatore durante un passo di esecuzione. Più precisamente, in funzione del contenuto della memoria interna e della parte della memoria esterna scandita dal puntatore, il programma specifica: 1) come deve essere modificato il contenuto della memoria esterna scandito in quel momento; 2) dove si deve spostare il puntatore (deve essere una zona contigua); 3) come deve essere alterata la memoria interna. A partire dalla configurazione iniziale della memoria la macchina esegue ripetutamente le operazioni specificate dal programma arrestandosi se, e quando, viene raggiunto un determinato stato della memoria interna, detto stato di arresto.

Questa è l’idea e diamo ora la definizione formale. Nelle clausole che seguono la memoria esterna è rappresentata dal contenuto delle celle di un nastro, mentre l’insieme finito Q rappresenta i possibili stati della memoria interna. Una macchina di Turing è costituita da:

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

1. Un nastro diviso in celle che formano una successione infinita nei due versi. Ogni cella contiene uno dei simboli di Σ. In ogni dato momento il nastro conterrà solamente un numero finito di simboli diversi da #.

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

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

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

10.3.1 Funzione parziale calcolata da una macchina di Turing.

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

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

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

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

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

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

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

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

10.4 Tesi di Church

Nella seconda metà degli anni trenta vari autori, tra cui Turing, Post, Church e Kleene, hanno indipendentemente cercato di rendere rigoroso il concetto di funzione calcolabile in senso intuitivo (si tenga presente che non esistevano ancora i calcolatori). A tal fine Turing ha introdotto il concetto di “macchina di Turing”, Kleene ha definito le funzioni “μ-ricorsive”, e Church le funzioni “λ-calcolabili”. È stato successivamente dimostrato che le funzioni Turing calcolabili, μ-ricorsive, e λ-calcolabili coincidono. Questi tre concetti individuano dunque una unica classe di funzioni, dette funzioni parziali ricorsive. La coincidenza di questi diversi tentativi di rendere rigoroso il concetto di funzione calcolabile ha portato all’accettazione della:

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

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

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

10.5 Insiemi decidibili e semidecidibili

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

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

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

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

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

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

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

Proposizione 10.3 Ogni insieme decidibile è anche semidecidibile.

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

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

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

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

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

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

Esiste una importante differenza tra gli insiemi numerabili e quelli ricorsivamente numerabili: mentre ogni sottoinsieme di un insieme numerabilie è numerabile, un sottoinsieme di un insieme ricorsivamente enumerabile non è necessariamente ricorsivamente enumerabile. Ad esempio N è ricorsivamente enumerabile, ma vedremo che N possiede sottoinsiemi non ricorsivamente enumerabili.

Teorema 10.6 Un insieme A ⊆ N è semidecidibile se e solo se è ricorsivamente enumerabile.

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

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

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

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

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

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

10.6 Ricorsiva enumerabilità dei teoremi

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

Teorema 10.10 L’insieme dei teoremi di una teoria del primo ordine con un numero finito di assiomi, o più in generale con un insieme decidibile di assiomi, è semidecidibile.

Dim. Una formula ϕ appartiene all’insieme T h(T) dei teoremi di T se e solo se esiste una dimostrazione formale d di ϕ da T. Data una stringa di simboli d possiamo controllare se essa è una dimostrazione formale verificando che essa è costituita da una successione di formule ben formate ognuna delle quali è un assioma di T, o un assioma logico, o segue da formule precedenti tramite una regola di inferenza. Il controllo se una data formula sia una assioma logico o segua da altre formule tramite una singola applicazione di una regola di inferenza è decidibile. Il controllo che una data formula sia un assioma di T è decidibile per ipotesi. Ne segue che possiamo decidere in un numero finito di passi se una data stringa d è una dimostrazione. Per mostrare che T h(T) è semidecidibile consideriamo la seguente procedura: data una formula ϕ, enumeriamo tutte le possibili stringhe di simboli d, controllando di volta in volta se siano dimostrazioni di ϕ, e fermandoci con risposta positiva appena ne si trovi una che sia effettivamente una dimostrazione di ϕ. Questa procedura termina se e solo se ϕ è un teorema di T, mostrando dunque che l’insieme dei teoremi di T è semidecidibile. QED

Teorema 10.11 Sia T una teoria del primo ordine coerente e completa con un insieme decidibile di assiomi. Allora i teoremi di T sono un insieme decidibile.

Dim. Per teorie T coerenti e complete per ogni enunciato ϕ nel linguaggio della teoria, o ϕ o la sua negazione è dimostrabile in T ma non entrambi. Ne segue che se enumeriamo tutte le dimostrazioni, prima o poi ne troveremo una di ϕ o della sua negazione, e a quel punto avremo stabilito se ϕ è un teorema. QED

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

Esercizio 10.13 Nei due teoremi precedenti si possono indebolire le ipotesi: basta che l’insieme di assiomi di T sia semidecidibile.

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

11 Eliminazione dei quantificatori

Definizione 11.1 Sia T una L-teoria. Due formule θ, ϕ sono equivalenti in T, o T -equivalenti, se T ⊢ θ ↔ ϕ. Osserviamo che ciò equivale a dire T ⊢ ∀y⃗(θ ↔ ϕ), dove y⃗ è la lista delle variabili libere in θ o ϕ.

Esercizio 11.2 Rimpiazzando, in una formula ϕ, una sottoformula α con un’altra formula T -equivalente ad α, si ottiene una formula ϕ′ T -equivalente a ϕ.

Definizione 11.3 Sia T una L-teoria. T ammette eliminazione dei quantificatori se per ogni formula θ esiste una formula ϕ senza quantificatori T -equivalente a θ.

Esempio 11.4 La formula ∃x(x^{2} = y) equivale, nella teoria dei numeri reali (come campo ordinato), alla formula senza quantificatori y ≥ 0.

Il seguente semplice risultato mostra sostanzialmente che per eliminare i quantificatori basta eliminarne “uno alla volta”.

Lemma 11.5 Sia T è una L-teoria. Supponiamo che ogni formula esistenziale della forma ∃xθ, con θ senza quantificatori, equivalga in T ad una formula ϕ senza quantificatori. Allora T ammette eliminazione dei quantificatori.

Dim. Mostriamo per induzione sul numero dei connettivi e quantificatori che ogni formula γ in cui non occorra il quantificatore ∀ equivale in T ad una formula senza quantificatori. Ciò basta ai nostri fini in quanto il quantificatore ∀ è eliminabile usando le equivalenze logiche ∀xA ↔ ¬∃x¬A. Sia dunque γ una formula in cui non occorre il ∀ e distinguiamo i seguenti tre casi. Se γ è già senza quantificatori non c’è nulla da dimostrare. Se γ è una combinazione booleana di altre formule, per ipotesi induttiva possiamo rimpiazzare queste ultime con formule T -equivalenti senza quantificatori, e usando l’Esercizio 11.2 otteniamo una formula senza quantificatori T -equivalente a γ. L’unico caso rimasto è allora quando γ ha la forma ∃xθ (essendoci premurati di escludere il caso ∀xθ). In questo caso le nostre ipotesi ci dicono che γ equivale in T ad una formula senza quantificatori, completando il passo induttivo. QED

Definizione 11.6 Sia D un insieme di L-enunciati. Date due L-strutture A e B scriviamo A ≡_{D} B per indicare il fatto che A e B verificano gli stessi enunciati di D. Se D = {θ} consiste di un singolo enunciato scriviamo anche A ≡_{θ} B. Ciò significa che θ è vero in entrambe le strutture, o falso in entrambe.

Diamo ora un criterio, non costruttivo in quanto basato sul teorema di compattezza, affinché un dato enunciato θ sia T -equivalente ad uno senza quantificatori.

Lemma 11.7 Sia T una L-teoria, sia D un insieme di L-enunciati chiuso per connettivi booleani (ad esempio l’insieme di tutti gli enunciati senza quantificatori), e sia θ un L-enunciato. Supponiamo che per ogni coppia A, B di modelli di T tali che A ≡_{D} B si abbia A ≡_{θ} B. Allora T ⊢ θ ↔ δ per qualche δ ∈ D.

Dim. Sia H = {φ ∈ D | T ⊢ θ → φ} l’insieme di tutti gli enunciati di D implicati da θ nella teoria T. È sufficiente motrare che esiste un enunciato di H che implica θ (sempre in T). Per il teorema di compattezza e il fatto che T è chiuso per congiunzioni, ciò equivale a dire che θ è deducibile da T ∪ H. Se ciò non fosse, esisterebbe un modello A di T ∪ H che non verifica θ. Per le nostre ipotesi, ogni modello B ≡_{D} A coincide con A sul valore di verità di θ, e quindi non verifica θ. Indicando con D_{A} ⊇ H l’insieme degli enunciati di D veri in A, ciò significa che ¬θ è deducibile T ∪ D_{A}. Per compattezza ed il fatto che D_{A} è chiuso per congiunzioni, esiste una singola formula δ ∈ D_{A} che implica ¬θ (in T). Ciò equivale a dire che T ⊢ θ → ¬δ, cioè ¬δ ∈ H (osservando che D, essendo chiuso per negazione, contiene ¬δ). Ciò è assurdo in quanto A verifica sia δ che tutte le formule di H. QED

Definizione 11.8 Una teoria T ha la proprietà dell’isomorfismo se ogni isomorfismo f: B → B′ tra sottostrutture B ⊂ A e B′ ⊂ A′ di due modelli A ed A′ di T, si estende ad un isomorfismo f̃: C → C′ di modelli di T con B ⊆ C ⊆ A e B′ ⊆ C′ ⊆ A′. In breve: ogni isomorfismo tra sottostrutture si estende ad un isomorfismo tra sottomodelli.

Esempio 11.9 Vedremo che la teoria dei campi algebricamente chiusi ha la proprietà dell’isomorfismo: se due campi algebricamente chiusi hanno sottostrutture isomorfe, i più piccoli sottocampi algebricamente chiusi che contengono tali sottostrutture sono isomorfi, con un isomorfismo che estende quello dato. Simile discorso vale per i campi reali chiusi.

Esercizio 11.10 La teoria degli ordini lineari densi senza massimo e minimo ha la proprietà dell’isomorfismo.

Definizione 11.11 Una teoria T ha la proprietà del sottomodello se per ogni A ⊂ B modelli di T, e per ogni enunciato esistenziale della forma ∃xθ(x, a⃗), dove θ(x, a⃗) è una formula senza quantificatori con parametri a⃗ da A, se B verifica l’enunciato anche A lo verifica.

Esempio 11.12 Vedremo che la teoria dei campi algebricamente chiusi ha la proprietà del sottomodello: ciò dipende dal fatto che se un sistema di equazioni e disequazioni polinomiali in una variabile, a coefficienti in un campo algebricamente chiuso, ha soluzione in una estensione del campo, esso ha soluzioni anche nel campo stesso. Stesso discorso vale per i campi reali chiusi.

Esercizio 11.13 La teoria degli ordini lineari densi senza massimo e minimo ha la proprietà del sottomodello.

Ci sarà utile il seguente lemma tecnico la cui dimostrazione dettagliata è lasciata come esercizio.

Lemma 11.14 Sia T una L-teoria con la proprietà dell’isomorfismo (o del sottomodello), sia c⃗ una n-upla di nuovi simboli di costanti non in L, e sia T [c⃗] è la teoria con gli stessi assiomi di T ma formulata nel linguaggio ampliato L ∪ {c⃗}. Allora T [c⃗] ha anch’essa la proprietà dell’isomorfismo (o rispettivamente del sottomodello).

Dim.(Cenno) La dimostrazione si basa sul fatto che un modello di T [c⃗] può essere visto semplicemente come una coppia (A, a⃗) costituita da un modello A di T e una n-pla a⃗ di elementi di A arbitrariamente fissata che serve a interpretare le c⃗ (n è la lunghezza di c⃗). Il concetto di sottostruttura e di isomorfismo nel linguaggio ampliato si caratterizzano nel modo seguente. Dati due modelli (A, a⃗) e (B, b⃗) di T [c⃗], si ha che il primo è una sottostruttura del secondo se e solo se A è una sottostruttura di B nel liguaggio L, e b⃗ = a⃗. Notiamo anche che f è un isomorfismo tra le L ∪ {c⃗}-strutture (A, a⃗) a (B, b⃗), se f manda A isomorficamente in B come L-strutture, e inoltre f(a_{i}) = b_{i} (dove a_{i} è l’i-esimo elemento di a⃗ e b_{i} l’i-esimo elemento di b⃗). Con queste osservazioni la fine della dimostrazione si ottiene in modo del tutto automatico applicando le definizioni. QED

Teorema 11.15 Se T è una L-teoria con la proprietà del sottomodello e la proprietà dell’isomorfismo, e il linguaggio L ha almeno un simbolo di costante, allora T ammette eliminazione dei quantificatori.

Dim. Per il Lemma 11.5 basta dimostrare che ogni L-formula esistenziale della forma ∃xθ, con θ senza quantificatori, equivale in T ad una formula senza quantificatori.

Consideriamo d’apprima il caso speciale in cui ∃xθ è chiusa, ovvero θ non contiene altre variabili libere oltre la x.

Per trovare una enunciato equivalente a ∃xθ senza quantificatori useremo il Lemma 11.7. Sia D l’insieme degli L-enunciati senza quantificatori (D è non vuoto in quanto L ha almeno un simbolo di costante) e siano A, A′ modelli di T con A ≡_{D} A′. Dobbiamo mostrare che A ≡_{∃xθ} A′. L’ipotesi A ≡_{D} A′ (cioè A ed A′ rendono veri gli stessi enunciati senza quantificatori) implica (e in effetti equivale) al fatto che le sottostrutture B ⊆ A e B′ ⊆ A′ costituite dalle interpretazioni dei termini chiusi, sono isomorfe tramite l’isomorfismo f: B → B′ che manda t^{A} in t^{A′}, dove t è un L-termine chiuso e t^{A} e t^{A′} sono le sue interpretazioni rispettivamente in A e in A′. Questa mappa è ben definita in quanto se t_{1}^{A} = t_{2}^{A}, l’enunciato senza quantificatori t_{1} = t_{2} è vero in A e dunque in A′, da cui t_{1}^{A} = t_{2}^{A′}. Lo stesso ragionamento con i ruoli di A e A′ scambiati mostra che la funzione è iniettiva. Il fatto che sia surgettiva dipende dal fatto che il dominio di B′ è costituito dalle intepretazioni dei termini chiusi. Il fatto che preserva ogni funzione h del linguaggio è ovvio: h^{A}(t_{1}^{A}, …, t_{n}^{A}) = h(t_{1}, …, t_{n})^{A} ↦ h(t_{1}, …, t_{n})^{A′} = h^{A′}(t_{1}^{A′}, …, t_{n}^{A′}). La proprietà dell’isomorfimo ci permette di estendere l’isomorfismo di L-strutture f: B → B′ così stabilito ad un isomorfismo f̃: C → C′ di modelli di T, con B ⊆ C ⊆ A e B′ ⊆ C′ ⊆ A′. Per mostrare che A ≡_{∃xθ} A′ supponiamo che A soddisfi ∃xθ e mostriamo che anche A′ la soddisfa (il viceversa segue simmetricamente). La proprietà del sottomodello ci garantisce innanzitutto che l’enunciato ∃xθ è vero nel sottomodello C ⊆ A. Essendo C′ isomorfo a C esso sarà vero anche in C′ e poiché gli enunciati esistenziali veri in una struttura sono veri in qualsiasi sua estensione, esso sarà vero in A′.

Abbiamo così concluso il caso in cui ∃xθ è una formula chiusa. Se invece θ contiene delle variabili libere y⃗ oltre la x, cioè θ = θ(x, y⃗), ci ricondurremo al caso precedente ampliando il linguaggio L con nuove costanti c⃗ che andremo a sostituire al posto delle y⃗. A tal fine osserviamo che dalla proprietà dell’isomorfismo e del sottomodello per la teoria T, segue che anche la teoria T [c⃗] ha queste proprietà, dove T [c⃗] è la teoria con gli stessi assiomi di T ma formulata nel linguaggio ampliato L∪{c⃗}. Possiamo ora concludere la dimostrazione considerando la formula chiusa ∃xθ(x, c⃗) del linguaggio ampliato ottenuta sostituendo le y⃗ con le c⃗. Per il caso speciale precedentemente dimostrato, applicato però alla teoria T [c⃗], esiste un enunciato senza quantificatori ϕ(c⃗) del liguaggio ampliato tale che T [c⃗] ⊢ ϕ(c⃗) ↔ ∃xθ(x, c⃗). Visto che T [c⃗] non contiene assiomi sulle constanti c⃗, possiamo dedurne che T ⊢ ∀y⃗(ϕ(y⃗) ↔ ∃xθ(x, y⃗)) (a condizione che ϕ(c⃗) non contenga quantificazioni sulle y⃗, cosa che possiamo assumere con un cambio di variabili vincolate). QED

12 Decidibilità della teoria dei campi algebricamente chiusi e della teoria dei numeri complessi

Si veda [van der Waerden, Algebra]. Un campo è algebricamente chiuso se ogni polinomio non nullo in una variabile, a coefficienti nel campo, ha uno zero nel campo. L’esempio più importante di campo algebricamente chiuso è dato dai numeri complessi. Non è difficile scrivere degli assiomi del primo ordine, in un linguaggio con 0, 1, +, ·, i cui modelli siano tutti e soli i campi algebricamente chiusi. La condizione di esistenza di zeri per i polinomi non nulli richiede infiniti assiomi, uno per ogni grado. La teoria dei campi estesa con questi assiomi si chiama teoria dei campi algebricamente chiusi.

Lemma 12.1 La teoria ACF dei campi algebricamente chiusi ha la proprietà del sottomodello.

Dim. Siano A ⊆ B campi algebricamente chiusi. Sia θ(x, a⃗) una formula senza quantificatori con parametri a⃗ in A, e sia b ∈ B tale che θ(b, a⃗). Dobbiamo mostrare che esiste a^{∗} ∈ A tale che θ(a^{∗}, a⃗). Possiamo assumere che b ∉ A altrimenti non c’è nulla da dimostrare. Usando gli assiomi dei campi possiamo dimostrare che θ(x, a⃗) equivale, in A, ad una combinazione booleana di formule f_{1}(x) = 0, …, f_{k}(x) = 0, dove gli f_{i} sono polinomi non nulli a coefficienti nel sottoanello generato dai parametri a⃗. Gli assiomi dei campi garantiscono che ogni f_{i} ha un numero finito di radici. Sia S ⊂ A un insieme finito che contiene le radici di ogni f_{i}. Poichè A è algebricamente chiuso, A è infinito. Ciò è ovvio se A ha caratteristica zero, poiché in quel caso A contiene una copia isomorfa dei razionali. Nel caso generale basta osservare che dato un sottoinsinsieme finito {a_{1}, …, a_{k}} di A possiamo sempre trovare un elemento di A che non vi appartiene considerando uno zero del polinomio (x−a_{1})(x−a_{2})·. . .·(x−a_{k})+1. Tale zero esiste in quanto A è algebricamente chiuso. Essendo dunque A infinito, possiamo fissare un elemento a^{∗} ∈ A, a^{∗} ∉ S. Dobbiamo avere f_{i}(a^{∗}) ≠ 0 e f_{i}(b) ≠ 0 per ogni i. Abbiamo quindi f_{i}(b) = 0 ↔ f_{i}(a^{∗}) = 0, e pertanto θ(b, a⃗) ↔ θ(a^{∗}, a⃗), essendo θ(x, a⃗) una combinazione booleana delle formule f_{i}(x) = 0. Ciò conclude la dimostrazione. QED

Data una estensione B ⊆ C di campi, diciamo che c ∈ C è algebrico su B, se c è uno zero di un polinomio a coefficienti in B. L’insieme degli elementi si C algebrici su B è un sottocampo F di C. Ogni elemento di C algebrico su F appartiene a F. Ne segue che se C è algebricamente chiuso anche F lo è: infatti dato un polinomio a coefficienti in F, questo ha uno zero in C, ed essendo tale zero algebrico su F deve appartenervi.

Definizione 12.2 Una chiusura algebrica di un campo B è un campo algebricamente chiuso C ⊇ B tale che ogni elemento di C è algebrico su B.

Teorema 12.3 (Esistenza e unicità della chiusura algebrica) Ogni campo ha una chiusura algebrica. Dato un isomorfismo f tra due campi, e considerate due chiusure algebriche dei campi dati, l’isomorfismo f si estende ad un isomorfismo delle due chiusure. In particolare due chiusure algebriche di uno stesso campo sono isomorfe, tramite un isomorfismo che fissa ogni elemento del campo base.

Corollario 12.4 La teoria ACF dei campi algebricamente chiusi ha la proprietà dell’isomorfismo.

Dim. Useremo il teorema di unicità della chiusura algebrica. Sia f: D → D′ un isomorfismo tra sottostrutture di campi algebricamente chiusi A ed A′. Poiché il linguaggio della teoria contiene 0, 1, −1, +, ·, D e D′ sono anelli, ed essendo sottoanelli di un campo sono domini di integrità (cioè verificano xy = 0 → x = 0 ∨ y = 0). Possiamo estendere f ad un isomorfismo f_{1}: B → B′ tra i campi dei quozienti B ⊆ A e B′ ⊆ A′ di D e D′ rispettivamente, ponendo f_{1}(x/y) = f_{1}(x)/f_{1}(y) (x, y ∈ B). Sia ora C l’insieme dei punti di A algebrici su B e sia C′ l’insieme dei punti di A′ algebrici su B′. Segue dalle proprietà generali dei campi che C e C′ sono campi. Inoltre, poiché A ed A′ sono algebricamente chiusi, anche C e C′ lo sono. Possiamo concluderne che C e C′ sono chiusure algebriche di B e B′, e per l’unicità della chiusura algebrica l’isomorfismo f_{1}, e quindi anche f, si estende ad un isomorfismo tra C e C′. QED

Corollario 12.5 La teoria dei campi algebricamente chiusi ammette eliminazione dei quantificatori.

Corollario 12.6 La teoria ACF_{0} dei campi algebricamente chiusi di caratteristica zero fornisce una assiomatizzazione ricorsiva e completa della teoria dei numeri complessi. La teoria dei numeri complessi è quindi decidibile.

Dim. Basta dimostrare che una formula chiusa ϕ è vera in un modello di ACF_{0} se e solo se è vera in tutti i modelli. Osserviamo che ogni modello di ACF_{0} contiene una sottostruttura isomorfa ai numeri razionali. Poiché ACF_{0} contiene ACF, ϕ equivale, in ACF_{0}, ad una formula chiusa θ priva di quantificatori. Essendo priva di quantificatori θ vale in una struttura se e solo se vale in una sottostruttura. Possiamo concludere che ϕ vale in un modello di ACF_{0} se e solo se θ vale nei razionali. QED

13 Decidibilità della teoria dei campi reali chiusi e della teoria dei numeri reali

Si veda [van der Waerden, Algebra]. Un campo ordinato è reale chiuso se ogni polinomio in una variabile che cambia segno, a coefficienti nel campo, ha uno zero nel campo. L’esempio più importante di campo reale chiuso è dato dai numeri reali (dove ogni funzione continua che cambia segno, non necessariamente polinomiale, ha uno zero). Non è difficile scrivere degli assiomi del primo ordine, in un linguaggio con 0, 1, +, ·, ≥, i cui modelli siano tutti e soli i campi reali chiusi. La condizione di esistenza di zeri richiede infiniti assiomi, uno per ogni grado. La teoria dei campi ordinati estesa con questi assiomi si chiama teoria dei campi reali chiusi.

Proposizione 13.1 Se F è un campo reale chiuso, l’estensione algebrica F(\sqrt{−1}) è un campo algebricamente chiuso. Ne segue che in un campo reale chiuso F, ogni polinomio monico f(x) si fattorizza in fattori lineari o quadratici della forma (x − α), (x − β)^{2} + c, con α, β, c ∈ F, c > 0.

Corollario 13.2 Data un’estensione di campi ordinati reali chiusi A ⊆ B, e un polinomio f(x) ∈ A[x], f(x) ha gli stessi zeri in A e in B. Inoltre dati due elementi b, b′ ∈ B situati nello stesso intervallo determinato dagli zeri di f(x), i segni di f(b) e di f(b′) devono coincidere.

Dim. I fattori quadratici (x − β)^{2} + c, c > 0, della scomposizione di f(x) in A non possono avere degli zeri in B in quanto in ogni campo ordinato i quadrati sono non negativi. Questo dimostra la prima affermazione. Per la seconda basta osservare che tra due punti che determinano un cambiamento di segno di f(x) ci deve essere uno zero di f(x). QED

Lemma 13.3 La teoria dei campi ordinati reali chiusi ha la proprietà del sottomodello.

Dim. Siano A ⊆ B campi ordinati reali chiusi. Sia θ(x, a⃗) una formula senza quantificatori con parametri a⃗ in A, e sia b ∈ B tale che θ(b, a⃗). Dobbiamo mostrare che esiste a^{∗} ∈ A tale che θ(a^{∗}, a⃗). Poiché θ(x, a⃗) è senza quantificatori, essa equivale ad una combinazione booleana di formule atomiche, ovvero uguaglianze e disuguaglianze tra termini. Usando gli assiomi dei campi ordinati possiamo dimostrare che ogni termine definisce una funzione polinomiale, e pertanto θ(x, a⃗) equivale, in A, ad una combinazione booleana di espressioni della forma “f(x) = 0” con f(x) ∈ A[x], oppure “g(x) ≤ 0” con g(x) ∈ A[x]. Esiste un insieme finito S ⊆ A che contiene le radici di tutti questi polinomi. Poiché in ogni campo ordinato l’ordine è denso e senza massimo e minimo, possimo certamente trovare un punto a^{∗} di A tale che a^{∗} e b sono situati nello stesso intervallo determinato dai punti di S (se b ∈ S prendiamo a^{∗} = b). Per il corollario 13.2 a^{∗} e b verificheranno le stesse uguaglianze e disuguaglianze polinomiali, rispetto all’insieme finito di polinomi considerato, ed essendo θ(x, a⃗) una combinazione booleana di tali uguaglianze e disuguaglianze, si avrà θ(a^{∗}, a⃗) ↔ θ(b, a⃗). Ne segue θ(a^{∗}, a⃗), come desiderato. QED

Definizione 13.4 Una chiusura reale di un campo ordinato B è un campo ordinato reale chiuso C ⊇ B (estensione di campi ordinati) tale che ogni elemento di C è algebrico su B.

Teorema 13.5 (Esistenza e unicità della chiusura reale di un campo ordinato) Ogni campo ordinato A ha una chiusura reale. Dato un isomorfismo f: A → A′ tra due campi ordinati, e considerate due loro rispettive chiusure reali B e B′, l’isomorfismo f si estende ad un isomorfismo f̃: B → B′ delle chiusure. In particolare, prendendo come f l’identità, due chiusure reali di un campo ordinato sono isomorfe.

Dim. (Cenno) Dato un campo ordinato A, consideriamo un sottocampo B della chiusura algebrica \overline{A} di A che contiene tutte le radici quadrate degli elementi positivi di A (ciò garantisce che ogni ordine di campo su B deve estendere quello di A) ed è massimale rispetto alla proprietà che −1 non è somma di quadrati (un campo è ordinabile se e solo se ha questa proprietà). Tale B ammette un unico ordine, e con tale ordine è una chiusura reale di A.

Dato ora un isomorfimo f: A → A′ tra due campi ordinati, e considerate due loro rispettive chiusure reali B e B′, l’isomorfismo f si estende ad un isomorfismo f̃: B → B′ che manda l’n-sima radice (nell’ordine di B) di un polinomio p(x) = Σ_{i}a_{i}x^{i} a coefficienti in A, nell’n-esima radice (nell’ordine di B′) del polinomio p^{f}(x) = Σ_{i}f(a_{i})x^{i} (un teorema di Sturm ci garantisce che il numero delle radici di p(x) e p^{f}(x) è lo stesso). QED

Teorema 13.6 La teoria dei campi reali chiusi ha la proprietà dell’isomorfismo.

Dim. Useremo il teorema di unicità della chiusura reale. Sia f: D → D′ un isomorfismo tra sottostrutture di campi algebricamente chiusi A ed A′. Poiché il linguaggio della teoria contiene 0, 1, −1, +, ·, ≥, D e D′ sono anelli ordinati ed f è un isomorfismo di anelli ordinati. Essendo sottoanelli di un campo D e D′ sono domini di integrità (cioè verificano xy = 0 → x = 0 ∨ y = 0). Possiamo estendere f ad un isomorfismo f_{1}: B → B′ tra i campi dei quozienti B ⊆ A e B′ ⊆ A′ di D e D′ rispettivamente, ponendo f_{1}(x/y) = f_{1}(x)/f_{1}(y) (x, y ∈ B). Osserviamo che f_{1} deve rispettare l’ordine in quanto il segno di un quoziente è univocamente determinato dal segno del numeratore e denominatore. Sia ora C l’insieme dei punti di A algebrici su B e sia C′ l’insieme dei punti di A′ algebrici su B′. Segue dalle proprietà generali dei campi che C e C′ sono campi. Inoltre, poiché A ed A′ sono reali chiusi, anche C e C′ lo sono. Possiamo concluderne che C e C′ sono chiusure reali di B e B′, e per l’unicità della chiusura reale l’isomorfismo f_{1}, e quindi anche f, si estende ad un isomorfismo tra C e C′. QED

Corollario 13.7 La teoria dei campi ordinati reali chiusi ammette eliminazione dei quantificatori.

Corollario 13.8 La teoria RCF dei campi ordinati reali chiusi fornisce una assiomatizzazione completa della teoria dei numeri reali. La teoria dei numeri reali è quindi decidibile.

Dim. Basta dimostrare che una formula chiusa ϕ è vera in un modello di RCF se e solo se è vera in tutti i modelli. Osservarviamo ora che ogni modello di RCF contiene una sottostruttura isomorfa ai numeri razionali come campo ordinato. Poiché RCF elimina i quantificatori, ϕ equivale, in RCF, ad una formula θ priva di quantificatori. Essendo priva di quantificatori θ vale in una struttura se e solo se vale in una sottostruttura. Possiamo concludere che ϕ vale in un modello di RCF se e solo se θ vale nei razionali. QED

14 Esercizi

Alcuni esercizi possono essere eccessivamente difficili. Non ci si scoraggi e si provi comunque a pensarci.

Esercizio 14.1 Fare tutti gli esercizi menzionati in classe o scritti nelle note.

Esercizio 14.2 Si mostri nel sistema di Hilbert Frege che ⊢ ∃xα → ¬∀x¬α.

Esercizio 14.3 Sia Γ il seguente insieme di assiomi:

1) ∀x(x + 0 = x),

2) ∀xy(x + s(y) = s(x + y)),

3) ∀xy(s(x) = s(y) → x = y),

4) ∀x¬(s(x) = 0),

5) ∀x(x ≠ 0 → ∃y(x = s(y)).

Stabilire se:

a) Γ ⊧ ∀x(x + x = s(0) → x ≠ 0).

b) Γ ⊧ ¬∃y[y + y = s(0)].

c) Γ ⊧ ∀xy(x + y = y + x).

Esercizio 14.4 Sia L = (0, s, R, min) dove 0 è un simbolo di costante, s è un simbolo di funzione unaria, R è un simbolo di predicato binario, min è un simbolo di predicato ternario.

Sia Γ il seguente insieme di L-formule:

∀xy(R(x, y) → min(x, y, x)

∀xyz(R(x, y) ∧ R(y, z) → R(x, z))

∀xR(x, x)

∀xR(x, s(x))

Nella interpretazione che abbiamo in mente R è la relazione di minore o uguale, ma ci potrebbero essere altre interpretazioni. Trovate l’insieme di tutti i termini chiusi t tali che:

a) Γ ⊧ min(s0, sss0, t).

Trovate l’insieme di tutti i termini chiusi t tali che:

b) Γ ⊧ min(s0, t, s0).

Giustificate la risposta.

Esercizio 14.5 Si dimostri in modo dettagliato che ogni formula ϕ in un linguaggio del primo ordine è logicamente equivalente ad una formula ψ in forma normale prenessa (ovvero con tutti i quantificatori all’inizio).

Esercizio 14.6 Si dimostri che la teoria degli ordini lineari densi senza nè massimo nè minimo elemento è completa, e pertanto equivale alla teoria completa dei numeri razionali come insieme ordinato. Se ne deduca che la teoria degli ordini lineari densi ha esattamente quattro estensioni complete non equivalenti. Suggerimento: per dimostrare la completezza si usi la proprietà dell’isomorfismo e del sottomodello.

Esercizio 14.7 Usare il teorema di compattezza per dimostrare che se un grafo infinito non può essere colorata con 3 colori in modo da avere nodi adiacenti di colore diverso, allora anche un suo sottografo finito non può essere colorato con 3 colori.

Suggerimento: si trovi una teoria i cui modelli corrispondono alle colorazioni del grafo.

Esercizio 14.8 Usare il teorema di compattezza per mostrare che non esiste alcuna formula del primo ordine ϕ nella segnatura {≤} tale che M ⊧ ϕ se e solo se M è un buon ordine, dove un buon ordine è un ordine lineare senza successioni decrescenti infinite. In altre parole la classe dei buoni ordini non è una classe elementare.

Esercizio 14.9 Mostrare che se A è una L-struttura finita e B è una L-struttura che soddisfa gli stessi L-enunciati di A, allora A è isomorfa a B. Mostrare che ciò non è vero se non si assume la finitezza.

Esercizio 14.10 Sia T = ED(R) il diagramma elementare di (R; ≤) (nella segnatura L = {≤} ∪ {c_{a} | a ∈ R}). Sia c un nuovo simbolo di costante. Si determini quante sono le teorie complete nella segnatura L ∪ {c} i cui assiomi includono quelli di T .

Esercizio 14.11 Una teoria si dice decidibile se l’insieme dei suoi teoremi è un insieme ricorsivo. Si dimostri che ogni teoria coerente decidibile ha una estensione completa decidibile.

Esercizio 14.12 Si dimostri che esiste un campo ordinato M elementarmente equivalente al campo ordinato dei numeri reali ma contenente degli elementi non nulli minori in modulo di ogni razionale (possiamo supporre che M contenga i razionali, essendo i razionali isomorficamente immergibili in ogni campo ordinato).

Esercizio 14.13 Si dimostri per induzione sul numero degli elementi che su ogni insieme finito è possibile dare un ordine totale. Si usi poi il teorema di compattezza per il calcolo dei predicati per estendere il risultato ad insiemi infiniti.

Esercizio 14.14 Si assuma il seguente fatto: T h(N, 0, s, +) è una teoria decidibile mentre T h(N, 0, s, +, ·) non lo è.

1) Dedurre che non esiste nessuna L-formula ϕ(x, y, z), con L = {0, s, +}, tale che N ⊧ ϕ(a, b, c) se e solo se a · b = c.

Quindi la moltiplicazione non è definibile al primo ordine a partire da zero successore e addizione.

2) Mostrare che la moltiplicazione è definibile al secondo ordine a partire da zero successore e addizione. (In effetti è definibile a partire dal nulla!).

Esercizio 14.15 Dimostrare che esistono 2^{ℵ_{0}} modelli numerabili, a due a due non isomorfi, e ciascuno elementarmente equivalenti alla struttura dei numeri naturali (con +, ·).

Suggerimento: si consideri un sottoinsieme S dei numeri primi, si ampli il linguaggio con un simbolo di costante c, e si consideri una teoria che estende la teoria completa dei numeri naturali con degli assiomi che dicono che c è divisibile per tutti i primi di S e non è divisibile per i primi non in S. Si usi il teorema di compattezza per mostrare la coerenza della teoria.

Esercizio 14.16 (Difficile) Ogni tautologia si può dedurre dai quattro schemi di tautologia A0 - A4 (definiti in queste note nella sezione sugli assiomi logici proposizionali), usando solamente la regola di Modus Ponens.