1• edizione, settembre 2010 © copyright 2010 by Carocci editore S.p.A., Roma

Editing e impaginazione Fregi e Majuscole, Torino

Finito di stampare nel settembre 2010 da Eurolit, Roma

Riproduzione vietata ai sensi di legge. (art.171 della legge 22 aprile 1941, n. 633)

Senza regolare autorizzazione, è vietato riprodurre questo volume anche parzialmente e con qualsiasi mezzo, compresa la fotocopia, anche per uso interno o didattico.

I lettori che desiderano informazioni sui volumi pubblicati dalla casa editrice possono rivolgersi direttamente a:

Carocci editore

Via Sardegna 50 00187 Roma. TEL 06 42 81 84 17 FAX 06 42 74 79 31

Visitateci sul nostro sito Internet: http://www.ca rocci. it

Andrea lacona Stefano Cavagnetto

Teoria della logica del prim'ordine

Carocci editore

Ringraziamenti Ringraziamo Umberto Cavasinni, Donatella Donati, Pierdaniele Giaretta, Diego Marconi e Maurizio Negri, che hanno sottratto tempo alle loro occupazioni per leggere versioni precedenti dell'intero testo o di alcune sue parti. I loro commenti sono stati di grande aiuto. Ringra­ziamo in particolare Aldo Antonelli e Dario PaUadino, che hanno scovato numerosi errori e suggerito miglioramenti sostanziali. La versione finale risente molto della loro revisione accurata e costruttiva. Un pensiero a parte è per Paolo Casalegno, che ci ha incoraggiato a scrivere questo libro e ci ha dato consigli preziosi sulla scelta dei conte­nuti. Il libro è dedicato a lui, perché per noi è stato un esempio. Tante volte, scrivendo, abbiamo cercato di immaginare che cosa avrebbe detto, o che faccia avrebbe fatto, se lo avesse letto.

Attribuzioni Questo volume, tanto nel disegno quanto nella realizzazione, è il risulta­to di una stretta collaborazione tra i due autori. Ogni sua parte è stata oggetto di numerose discussioni e revisioni reciproche. Le responsabili­tà finali, tuttavia, devono essere distinte come segue: l'Introduzione e il paragrafo 1. 5 sono comuni; i restanti paragrafì del capitolo 1 e i capitoli 2-8 sono di Andrea Iacona; i capitoli 9e10 sono di Stefano Cavagnetto.

Indice Introduzione 7

1. Nozioni fondamentali 11

1.1. Linguaggio formale 11

1.2. Sistema formale 13 1.3. Linguaggio oggetto e metalinguaggio 15 1.4. Simboli e nozioni di teoria degli insiemi 16 1.5. Metodi dimostrativi 20

2. li linguaggio L 31

2.1. Vocabolario e regole di formazione 31 2.2. Nozioni semantiche di base 33 2.3. Soddisfacimento 38 2.4. Verità 42 2.5. Conseguenza logica e validità 43

3. 11 sistema S 47

3.1. Assiomi 47 3.2. Derivabilità e dimostrabilità 48 3.3. Coerenza 52 3.4. Teorema di coerenza 53

4. Alcune proprietà sintattiche di S 59

4.1. Teorema di deduzione 59 4.2. Pseudo Scoto 60 4.3. Doppia negazione 62 4.4. Contrapposizione 63 4.5. Riduzione all'assurdo 65

5. S e le sue estensioni 68

5.1. Linguaggi del prim'ordine 68

5

5.2. Teorie del prim'ordine 69 5.3. Due lemmi che vertono sulla coerenza 71

5.4. Lemma di Lindenbaum 74

6. Teorie e modelli 77

6.1. 6.2. 6.3. 6.4.

Modello di una teoria 77

Chiusura 78 Prima parte della dimostrazione Seconda parte della dimostrazione

7. Correttezza 87

79 81

7.1. Corrispondenza tra sintassi e semantica 87

7.2. Teorema di correttezza 88 7.3. Correttezza e insiemi di strutture 89

8. Completezza 92

8.1. Teorema di completezza 92 8.2. Completezza e insiemi di strutture 94 8.3. Il "significato" dei teoremi di correttezza e di -completezza

g. Modelli e cardinalità 101

9.1. Numeri cardinali 101 9.2. Teorema di Uiwenheim-Skolem 103

9.3. Teorema di compattezza 105

10. Relazioni tra modelli 110

10.1. Isomorfismo 110

10.2. Categoricità 113 10.3. Teoria degli insiemi 116

10.4. Teorie dell'ordinamento 119 10.5. Geometria euclidea elementare 123

Bibliografia 128

6

95

Introduzione

Questo libro è un'introduzione alla teoria della logica del prim'ordi­ne. In dieci capitoli, intende presentare in modo accessibile un nucleo essenziale di conoscenze sulla logica del prim'ordine che costituiscono lo sfondo di molte delle questioni filosofiche e matematiche che la riguardano. Siccome questo obiettivo conferisce al libro un'impronta caratteristica, è meglio chiarire subito le differenze rispetto agli altri testi di logica, invece di perdere tempo con il solito sillogismo. Tanto per cominciare, non si tratta di un manuale di logica elementa­re, cioè di un testo che spiega per la prima volta come rappresentare in un linguaggio formale ragionamenti espressi in una lingua naturale e come verificarne la correttezza mediante metodi semantici o sintatti­ci. Per apprezzare i temi che il libro affronta occorre aver già acquisito una certa familiarità con i contenuti di un manuale di logica elemen­tare, o perlomeno con i rudimenti della logica enunciativa. Come testo avanzato, d'altra parte, non è molto ortodosso. In primo luogo, si discosta da una tradizione consolidata che prescrive di illustra­re prima le proprietà di un sistema di logica enunciativa e poi quelle di un sistema di logica predicativa. Infatti tratta solo proprietà del secon­do tipo, assumendo che la logica predicativa sia talmente interessante e ricca di implicazioni da meritare un libro tutto per sé. Un tradizio­nalista, pur concordando su questa assunzione, potrebbe ritenere che un'esposizione preliminare della teoria della logica enunciativa sia didatticamente utile, poiché permette di introdurre nel caso più semplice teoremi e metodi dimostrativi che trovano impiego nel caso più complesso. Non avrebbe torto. Malo spazio che quella esposizio­ne richiederebbe può essere occupato in modo altrettanto utile, offren­do gli strumenti necessari per accedere direttamente alla teoria della logica predicativa. In secondo luogo, questo libro lascia fuori alcuni temi ben noti che generalmente sono inclusi nei manuali avanzati. In particolare, non affronta la questione della decidibilità e non dice niente sul celebre teorema di Godel. L'indecidibilità della logica predicativa e fincom-

7

pletezza dell'aritmetica sono risultati di enorme portata, che hanno segnato il progresso della logica. Ma una spiegazione sufficientemen­te dettagliata di questi risultati richiederebbe o di allungare il libro a dismisura, oppure di sacrificarne qualche parte rinunciando a trattare temi altrettanto centrali. Nessuna delle due opzioni sembra molto allettante. In terzo luogo, lo stile espositivo adottato non è quello caratteristico dei testi avanzati. Il più delle volte in quei testi non si spiega tutto per filo e per segno: si forniscono "abbozzi" di dimostrazioni invece di dimostrazioni vere e proprie, si enunciano principi e teoremi senza chiarirne il contenuto, si assegnano esercizi difficili omettendonè le soluzioni. Le cause possono essere diverse: forse le spiegazioni detta­gliate sono reputate poco "eleganti", superflue o offensive per l'intelli­genza del lettore, o forse non si ha spazio per darne. Ma qualunque sia la causa, un effetto che sicuramente si ottiene è quello di alimentare le insicurezze degli studenti, privandoli in molti casi della sensazione di aver capito davvero. L'idea che ispira questo libro, invece, è che la chia­rezza venga prima di tutto, quindi che sia preferibile rischiare di dire cose superflue, essere poco "eleganti" oppure offendere qualche letto­re intelligente, piuttosto che rischiare di non spiegare e giustificare adeguatamente ciò che si asserisce. Molti testi di logica hanno l'ambizione di fornire una panoramica che sia sufficientemente ampia da includere tutto o buona parte di ciò che i loro autori ritengono indispensabile sapere sulla materia. Ma questa ambizione si scontra con un dato incontrovertibile: per poter capire a fondo ogni singolo "pezzo" di logica si deve dedicare una dose conside­revole di attenzione solo a quel pezzo. Dunque, tanto maggiore è il numero di pezzi presentati, quanto minore è la probabilità che venga­no pienamente compresi nel tempo a disposizione. Qui saranno presentati in modo dettagliato pochi pezzi fondamentali, con la speranza che il lettore possa farli propri e possa servirsene per ulteriori approfondimenti. Immaginiamo di trovarci davanti a un grande museo, ad esempio la Galleria Borghese. L'edificio ha diversi piani, ciascun piano è ripartito in sale variamente collegate e ognuna di esse contiene numerose opere

·8

d'arte: sarcofagi, mezzi busti romani, statue barocche, dipinti del Cinquecento e del Seicento. Immaginiamo ora di poter scegliere, dati il tempo e le energie a nostra disposizione, tra due visite guidate: una prevede un giro completo dell'edificio con una breve descrizione di ciascuna opera, mentre l'altra è interamente dedicata a un insieme ristretto di opere giudicate imperdibili. Se scegliamo la prima, ci fare­mo un'idea del contenuto del museo, ma rischiamo di andare via con l'impressione di non aver visto bene le cose più interessanti. Se optia­mo per la seconda, invece, finiremo per non vedere tante opere, ma può darsi che qualcosa di bello magari una scultura di Bernini o un quadro di Caravaggio - rimanga impresso nella nostra memoria.

9

1. Nozioni fondamentali

1.1. Linguaggio formale Una lingua naturale, come l'italiano, è un insieme organizzato di espressioni dotate di signifìcato che permet­te di fare asserzioni e formulare inferenze. Una persona può fare un'as­serzione proferendo un enunciato di una lingua naturale, cioè una frase dichiarativa di senso compiuto che si conforma alle regole grammati­cali della lingua. Ad esempio, "Piove", "Non nevica'' e "Se piove allora non nevica" sono enunciati. Una persona può formulare un'inferenza in una lingua naturale proponendo un argomento, cioè un insieme di enunciati uno dei quali, la conclusione, è presentato come conseguenza degli altri, le premesse. Un esempio di argomento è il seguente: "Se piove allora non nevica, piove; non nevica''. Il punto e virgola, che sta per "quindi", separa le premesse dalla conclusione. Un linguaggio formale è unalingua artificiale che permette di descrive­re alcune proprietà strutturali degli enunciati e degli argomenti di una lingua naturale, proprietà che sono rilevanti per la verità delle rispetti­ve asserzioni e per la legittimità delle rispettive inferenze. In altri termi­ni, un linguaggio formale rappresenta la forma degli enunciati e degli argomenti di unalingua naturale. Un tipo di linguaggio formale noto a chiunque abbia un minimo di familiarità con la logica è quello che trova impiego nella logica enunciativa. In un linguaggio del genere - un linguaggio enunciativo - si può "tradurre" "Piove" con p, "Non nevica'' con~ q e "Se piove allora non nevica" con p :J~ q. Dunque l'argomen­to considerato può essere rappresentato così: p :J~ q, p; ~ q. Un linguaggio formale è definito per stipulazione delimitando l' insie­me di espressioni che gli appartengono e specificando un insieme di signifìcati per queste espressioni. Per prima cosa si fornisce un vocabo­lario, cioè una lista di simboli, e una serie di regole di formazione, cioè di regole che determinano quali sequenze di simboli del vocabolario sono formule. Poi si specifica un insieme di interpretazioni. Un'inter­pretazione è un'assegnazione di oggetti ad alcuni simboli del vocabola­rio, sulla base della quale si assegnano altri oggetti alle formule in cui questi simboli figurano. L'oggetto assegnato a un simbolo o ad unaformu-

11

L'inferenza è il processo con il quale da una proposizione accolta come vera si passa a una seconda proposizione la cui verità è derivata dal contenuto della prima.Inferire è quindi trarre una conclusione.

Un linguaggio formale è una lingua artificiale che permette di descriverealcune proprietà strutturali degli enunciati e degli argomenti di unalingua naturale, rappresenta la forma degli enunciati e degliargomenti di unalingua naturale.

Poi si specifica un insieme di interpretazioni. Un'interpretazioneè un'assegnazione di oggetti ad alcuni simboli del vocabolario,sulla base della quale si assegnano altri oggetti alle formule in cuiquesti simboli figurano.

Principio di bivalenza Esistono due valori di verità reciprocamenteesclusivi e unitamente esaustivi: vero e falso.

Quando il valore di una formula in un'interpretazione è 1, si dice chel'interpretazione è modello della formula

Analogamente, quando un insieme di formule è tale che ogni formula che contiene ha valore 1 in un'interpretazione, si dice che l'interpretazione è modello dell'insieme.

la può essere pensato come il significato del simbolo o della formula, se "significato" è inteso come sinonimo di "estensione". Infatti, l'assegnazio- · ne si fonda sul presupposto che il simbolo o la formula rappresenti un'e­spressione dotata di estensione, cioè un'espressione in relazione con elementi della realtà exrralinguistica. Il caso più importante è quello degli enunciati. Dato che l'estensione di un enunciato viene normalmente identificata con il suo valore di verità, le formule che rappresentano enun­ciati sono associate a valori di verità.

Principio di bivalenza Esistono due valori di verità reciprocamente esclusivi e unitamente esaustivi: vero e falso.

In accordo con questo principio, che è alla base della logica classica, i valo­ri di verità saranno indicati rispettivamente con 1 e O. Pertanto, qualsiasi formula che rappresenti un enunciato riceverà 1 o O in un'interpretazio­ne. Quando il valore di una formula in un'interpretazione è 1, si dice che l'interpretazione è modello della formula. Analogamente, quando un insieme di formule è tale che ogni formula che contiene ha valore 1 in un'interpretazione, si dice che l'interpretazione è modello dell'insieme. D'ora in poi si userà "linguaggio" come sinonimo di. "linguaggio formale" per riferirsi a unalingua artificiale definita mediante i due tipi di stipulazione considerati. Le proprietà sintattiche di un linguaggio derivano dalle stipulazioni del primo tipo, cioè sono proprietà che il linguaggio possiede indipendentemente dal fatto che ai simboli o alle formule che lo costituiscono siano assegnati certi significati. Le proprietà semantiche di un linguaggio, invece, derivano dalle stipula­zioni del secondo tipo, cioè sono proprietà che il linguaggio possiede in quanto certi significati sono assegnati ai simboli o alle formule che lo costituiscono. Solitamente si parla di "sintassi" di un linguaggio per indicare l'insieme delle proprietà sintattiche che lo caratterizzano e di "semantica" di un linguaggio per indicare l'insieme delle proprietà semantiche che lo caratterizzano.

Nota Spesso si parla di "formule ben formate" invece che di formule, usando la qualificazione "ben formata" per distinguere una sequenza

12

di simboli che soddisfa le regole di formazione da una sequenza di simboli qualsiasi. Per abbreviare "formula ben formatà: che risulta un po' ingombrante, si usa normalmente la sigla "fbf". La scelta termino­logica qui adottata sottintende la stessa distinzione, in quanto "formu­la" si applica solo a sequenze di simboli che soddisfano le regole di formazione. In questo modo si evita di introdurre un'espressione più lunga per poi doverla abbreviare.

Nota Il termine "modello" è talvolta usato come sinonimo di "inter­pretazione" invece che nel senso più ristretto chiarito sopra.

1.2. Sistema formale UnapparatodeduttivoperunlinguaggioL può essere definito per mezzo di due tipi di stipulazione, ciascuno dei quali prescinde da qualsiasi riferimento a interpretazioni di L. In un caso si specifica un insieme di assiomi, cioè di formule di L che hanno uno status speciale. Nell'altro si specifica un insieme di regole di infe­renza, cioè di regole che fissano relazioni di conseguenza diretta tra formule di L. I due tipi di stipulazione non si implicano né si escludo­no a vicenda: un apparato deduttivo può contenere solo assiomi, solo regole di inferenza o entrambe le cose. Se si definisce un apparato deduttivo per un linguaggio L si ottiene un sistema formale in L. In altri termini, un sistema formale è costituito da un linguaggio e da un apparato deduttivo per il linguaggio. Qui saranno considerati solo sistemi formali, il cui apparato deduttivo include sia assiomi sia regole di inferenza, pertanto d'ora in poi si userà il termine "sistema" per indicare un sistema formale di questo genere. Dato un sistema S, una derivazione in S di una formula a da un insieme di formule f è una sequenza di n formule (per n maggiore di O) che termina con a e tale che ciascuna delle formule è un assioma o è conse­guenza diretta di altre formule che la precedono o fa parte di f. Le formule in f sono assunzioni a partire dalle quali a è derivata. La sequenza di formule equivale a una sequenza di passi, cioè i passi che costituiscono il ragionamento mediante il quale in S si giustifica a sulla base delle assunzioni in r. Una dimostrazione in S di una formula a è una sequenza di n formule

13

(per n maggiore di O) che termina con a e tale che ciascuna delle formule è un assioma o è conseguenza diretta di altre formule che fa. precedono. Anche in questo caso la sequenza di formule equivale a una sequenza di passi, cioè i passi che costituiscono il ragionamento mediante il quale si giustifica a in S. Una dimostrazione di a è ipso facto una derivazione di a da un insieme qualsiasi r di assunzioni. Al contrario, una derivazione di a da un insie­me f non è una dimostrazione di a, a meno che f sia vuoto o nessuna delle formule in r figuri nella derivazione. In una dimostrazione ciascuna formula risulta giustificata in virtù del solo apparato dedutti­vo del sistema, senza assunzioni ulteriori. La di~stinzione tra sintassi e semantica vale anche per i sistemi. Le proprietà sintattiche fondamentali di un sistema S riguardano le deriva­zioni che S permette di formulare. Quando in S si può costruire una derivazione di a da f, si dice che a è derivabile da fin S. Nel caso speci­fico in cui si possa costruire una dimostrazione di a in S, si dice che a è dimostrabile in S. Una formula dimostrabile si chiama teorema. Le proprietà semantiche fondamentali di un sistema dipendono dalla verità o falsità delle formule del suo linguaggio nelle varie inter­pretazioni, quindi dalle relazioni tra formule che ne.risultano. In particolare, si dice che a è conseguenza logica di f quando ogni modello di f è modello di a. Se ogni interpretazione è modello di a, si dice che a è valida. La validità è un caso speciale di conseguenza logica, così come la dimostrabilità è un caso speciale di derivabilità: una formula valida è conseguenza logica di qualsiasi insieme di assunzioni. I sistemi sono architettati in modo tale da rendere conto della cogen­za di certi argomenti e della verità di certi enunciati. Ad esempio, in un sistema di logica enunciativa q è sia derivabile dall'insieme formato da p ~ q e p sia conseguenza logica dello stesso insieme. Il motivo è che p ~ q, p; q esprime la forma di un insieme di argomenti in cui le premes­se implicano la conclusione. Allo stesso modo, la formula p ~ p è sia dimostrabile sia valida. Il motivo è che p ~ p esprime la forma di un insieme di enunciati veri. Un argomento in cui la relazione di implica­zione tra premesse e conclusione può essere spiegata in termini forma-

14

li, cioè sulla base dell'esemplificazione di una forma, è un argomento "deduttivamente valido". Un enunciato la cui verità può essere spiega­ta in termini formali è una "verità logica''.

Nota La n che compare nelle definizioni di derivazione e di dimo­strazione è una variabile che indica un numero naturale qualsiasi. I numeri naturali sono O, 1, 2, 3 e così via. D'ora in poi, quando non diversamente specificato, n e variabili analoghe si riferiranno a nume­ri naturali.

Esercizio 1 Una dimosrrazione può essere costituita da una sola for­mula?

Esercizio 2 Una dimostrazione può includere formule che non sono teoremi?

1.3. Linguaggio oggetto e metalinguaggio La teoria che si oc­cupa dei sistemi di logica - o teoria della logica - è formulata per mezzo di espressioni, coµie qualsiasi teoria. A differenza di altre teorie, però, la teoria della logica comprende enunciati che vertono su questo o quel linguaggio. Quindi è opportuno distinguere tra il linguaggio su cui verte la teoria e il linguaggio in cui la teoria è formulata: il primo è il linguaggio oggetto, il secondo è il metalinguaggio. Se la teòria è formu­lata per mezzo di espressioni italiane, come nel nostro caso, e verte su un sistema S che si basa su un linguaggio L, allora il linguaggio ogget­to è L, mentre il metalinguaggio è una versione opportunamente modificata dell'italiano. Con" opportunamente modificata'' si intende dire che il metalinguag­gio include abbreviazioni e simboli supplementari che non fanno parte dell'italiano. Una delle abbreviazioni che qui saranno usate è "sse", che sta per "se e solo se". Tra i simboli supplementari, invece, ci saranno<,>,::;;, 2!, =e -::t=, che significano rispettivamente "minore", "maggiore': "minore o uguale", "maggiore o uguale", "uguale" e "non uguale". Gli ultimi due simboli saranno usati non solo in riferimento a numeri, ma per esprimere identità e diversità tra oggetti qualsiasi.

15

Un'altra convenzione che si adotta nel metalinguaggio riguarda il modo di riferirsi al linguaggio oggetto. Siccome il metalinguaggio è impiega­to per parlare del linguaggio oggetto, le espressioni del linguaggio oggetto compaiono nel metalinguaggio. Queste espressioni non sono usate, ma menzionate. La distinzione tra uso e menzione può essere chiarita con un esempio. Nell'enunciato "C'è un gatto sul tappeto': la parola "gatto" è usata. Nell'enunciato "'Gatto' è una parola di cinque lettere': invece, la parola "gatto" è menzionata. Le virgolette permet­tono di formare un termine che si riferisce alla parola stessa. Non sempre, tuttavia, è necessario usare le virgolette per chiarire che un'e­spressione è menzionata. Ad esempio,"'~' è un simbolo" può essere abbr_eviato con "~ è un simbolo". Questa è la convenzione che sarà adottata. Ogni simbolo del linguaggio oggetto sarà inteso come abbre­viazione di un termine che si riferisce al simbolo stesso.

Nota I simboli a e r usati nel paragrafo i.2 sono variabili che apparten­gono al metalinguaggio: a sta per una formula qualsiasi del linguaggio oggetto, r sta per un insieme di formule qualsiasi del linguaggio oggetto.

1.4. Simboli e nozioni di teoria degli insiemi Moltideitermi­ni e dei simboli supplementari adottati nel metalinguaggio provengo­no dalla teoria degli insiemi. La nozione che questa teoria assume come primitiva è appunto quella di insieme, una collezione qualsiasi di oggetti che può essere pensata a sua volta come un oggetto. Gli ogget­ti che costituiscono un insieme sono i suoi elementi. Per dire che un oggetto a è elemento di un insiemeA si usa la notazione a EA. In alter­nativa, si può dire che a appartiene adA, o cheA contiene a. L'identità di un insieme è determinata dai suoi elementi, come stabilisce il seguente principio:

Principio di estensionalità Se A e B sono insiemi con gli stessi elementi, allora A= B.

Non vi possono essere insiemi diversi i cui elementi siano gli stessi. Vale anche l'inverso, cioè se A B allora A e B hanno gli stessi elementi.

16

Questo consegue da una legge universale nota come indiscernibilita degli identici: oggetti identici non possono avere proprietà diverse. Un insieme può essere rappresentato elencando i suoi elementi tra parentesi graffe. Data una collezione di oggetti x I' ... , x,,, si indica con {x1, ••• , x } l'insieme che contiene esattamentex

1, ••• ,x . Siccome ciò che n n

conta per l'identità di un insieme sono i suoi elementi, l'ordine delle espressioni all'interno delle parentesi non è rilevante. Ad esempio, {l, 2} e {2, 1} designano lo stesso insieme. Se un insieme contiene un solo elemento x, si indica con {x}. Ad esempio, { 1} è l'insieme che contiene 1 come unico elemento. Il simbolo 0, invece, designa l'insieme vuoto, cioè l'insieme al quale n,essun oggetto appartiene. Dati due insiemi A e B, l'unione diA e B, che si indica conA U B, è l'in­sieme di tutti gli oggetti che sono elementi diA o diB (o di entrambi). Adesempio,{1,2, 3} U {2, 3,4} = {1,2, 3,4}. Dati due insiemiA eB, si dice cheA è sottoinsieme diB se ogni elemen­to diA è elemento di B. Per indicare questa relazione si scrive A <;;,B. Ad esempio, {1} <;;, {l, 2}. Allo stesso modo, 0 <;;, {1, 2} e {1, 2} <;;, {l, 2}. Quando A è sottoinsieme di B ma alcuni elementi di B non sono elementi diA, si dice che A è sottoinsieme proprio di B. In altri termi­ni,A è sottoinsieme proprio diB sseA <;;,Be A -.:t: B. Così, mentre 0 e { 1} sono entrambi sottoinsiemi propri di {1, 2}, {1, 2} non è sottoinsieme proprio di { 1, 2}. L'insieme che ha come elementi tutti i sottoinsiemi di un insieme A è chiamato insieme potenza diA, e si indica conP(A). Ad esempio, seA = {2, 3, 6} alloraP(A)= {{2}, {3}, {6}, {2, 3}, {2, 6}, {3, 6}, {2, 3, 6}, 0}. In base al principio di estensionalità, l'identità di un insieme non implica alcun vincolo sull'ordine in cui i suoi elementi possono essere disposti. Questo è il motivo per cui non fa nessuna differenza che si scriva {l, 2} o {2, l}. Tuttavia, vi sono casi in cui può essere utile parla­re di oggetti disposti in sequenza. Il caso più semplice è quello in cui si intenda far riferimento a due oggetti disposti in modo tale che uno venga per primo e l'altro per secondo. Per soddisfare questa esigenza si parla di coppia ordinata. Dati due oggettixe y, si indica con ((x,y) la coppia ordinata dix e y. La condizione di identità di una co ~A: nata è la seguente: (x,y) = (u, v) ssex = u ey = v. Quindi · ·to

!ll C,qG, I~ o..fAC~J. ~ .,:_i

"lf / ,!::;' q,.,::,_ ~ ~)I

ordinata, a differenza di un semplice insieme di due oggetti, implica una relazione di ordine trai due oggetti. Ad esempio, (1, 2)::;:. (2, 1). In· generale, si chiama n-upla (si legge "ennupla") un insieme ordinato caratterizzato dalla seguente condizione di identità: (x

1, ••• ,x,,) = (y 1, ••• ,

y11

) ssex1 = yl' ... ,x,, = y11

• Dato uninsiemeA, siindicaconA" l'insieme di tutte le n-uple di elementi di A. Una relazione è un insieme di coppie ordinate. Un esempio di relazio­ne è l'insieme delle coppie ordinate (n, m) tali che n = 2m, come (2, 1), ( 4, 2), ( 6, 3) e così via. Il significato dell'espressione "essere il doppio di" può essere identificato con questa relazione. Un altro esempio è l' insie­me delle coppie ordinate (n, m) tali chen > m, come (2, 1), (3, 1), (7, 5) e così_via. Il significato dell'espressione "essere maggiore di" può essere identificato con questa relazione. Il dominio di una relazione R è l'in­sieme deglix tali che (x,y) ER per qualche y. Il codominio diR è l'in­sieme degli y tali che (x,y) E R per qualche x. Più in generale, si chia­ma relazione n-aria un insieme di n-uple. Quando si parla di una relazione n-aria su un insieme A si intende dire che la relazione è un insieme di n-uple di elementi di A. Unafanzione è una relazione che associa a ogni elemento del dominio esattamente un elemento del codominio. In altri terminj, una funzio­neF è una relazione tale che, per ognix nel dominio diF, c'è esattamen­te un y tale che (x, y) E F. Ad esempio, la relazione che associa a ogni numero naturale il suo doppio è una funzione, mentre la relazione che associa a ogni numero naturale un numero maggiore non è una funzio­ne. Gli elementi del codominio di una funzioneF sono i valori di F. Si indica con F(x) il valore che F associa a x, mentre x è chiamato argo­mento. La notazione F: A - B è usata per indicare una funzioneF che ha come dominio A e come codominio un sottoinsieme di B. Si espri­me la stessa cosa dicendo cheF è una funzione daA in B. Quando inve­ce si dice che F è una funzione daA su B, si intende dire che il codomi­nio diF non solo è sottoinsieme diB, ma è identico a B. Le funzioni possono essere distinte in varie categorie. Una differenza importante è quella tra funzioni che associano valori distinti ad argo­menti distinti e funzioni che non soddisfano questo requisito. Una funzione del primo tipo si chiama iniettiva. In altri termini, F è iniet-

18

tiva nel caso in cui per ognix e y nel dominio, sex::;:. y alloraF(x) ::;:. F(y). Dati due insiemi A e B, se esiste una funzione iniettiva daA suB si dice che A è in corrispondenza biunivoca con B. Intuitivamente,A è in corri­spondenza biunivoca con B se si può associare a ciascun elemento di A esattamente un elemento diB in modo che ogni elemento diB sia asso­ciato esattamente a un elemento di A. Supponiamo infatti cheF sia una funzione iniettiva da A su B. Allora si può associare a ogni elemento x diA esattamente un elemento diB, cioèF(x). Inoltre, si può associare a ogni elemento y diB esattamente un elemento di A, cioè l'unicox tale chey=F(x). Le funzioni possono es.sere distinte anche in base al numero di argo­menti. Una funzione binaria da A in B è una funzione che associa un elemento di B non a ciascun elemento di A preso singolarmente, ma a ciascuna coppia ordinata di elementi di A. Allo stesso modo, si può parlare di funzione ternaria, quaternaria e così via. In generale, una funzione n-aria daA in B, con n > 1, si indicaF :A" - B. Un' operazio­ne n-aria su un insieme A è una funzione n-ariaF che associa a ogni n­upla di elementi di A un elemento di A. In altri termini, F: A" - A. Ad esempio, l'addizione di due numeri naturali è un'operazione bina­ria sull'insieme dei numeri naturali, che si indica con cv, poiché è una funzioneAd che associa elementi di cv a coppie di elementi di w. Quin­di si può esprimere con Ad: al- cv. Appartengono aAd coppie ordi­nate come ((1, 2), 3), ((2, 2), 4) e così via. Il caso della moltiplicazione tra due numeri naturali è analogo, poiché si tratta di una funzione Mo che associa elementi di cv a coppie di elementi di cv. Appartengono a Mo coppie ordinate come ((1, 2), 2), ( (2, 2), 4) e così via. Restano da chiarire alcune distinzioni che si adottano di solito quando si parla della grandezza degli insiemi. Un insieme A è finito se, per qual­che n, A contiene esattamente n elementi. Ovviamente, se n O allora A= 0. Nel caso in cui n > O, basta pensare che A sia in corrispondenza biunivoca con {l, ... , n}. Ad esempio, {2, l} è finito, perché contiene esattamente due elementi. Un insieme A è infinito se non è finito, cioè se per nessun n si può dire che A contenga esattamente n elementi. Ad esempio, un insieme infinito è w. Un insieme infinito è numerabile se è in corrispondenza biunivoca con cv. Ad esempio, l'insieme dei numeri

19

pari è numerabile, e lo stesso vale per l'insieme dei numeri dispari. Un insieme infìnito è non numerabile se non è numerabile. Ad esempio, un insieme non numerabile è l'insieme dei numeri reali, che si indica con R JR comprende tutti i numeri razionali, cioè quelli che possono essere espressi in forma frazionaria, come t. e tutti i numeri irrazionali, cioè quelli che non sono razionali, come {1. Distinzioni analoghe valgono per gli insiemi ordinati. Una sequenza è un insieme ordinato esattamente nel senso in cui una n-upla è un insieme ordinato. Gli oggetti che figurano in una sequenza si chia­mano termini. Una sequenza di n termini, quindi, non è altro che una n-upla. Ad esempio, (1, 2) è una sequenza che ha come primo terfi1ine 1 e come secondo termine 2. In generale, dato un insiemeA, una sequenza finita di elementi di A può essere pensata come una funzione da {l, ... , n} in A per qualche n. Una sequenza infinita di elementi di A, invece, può essere pensata come una funzione da w in A. In entrambi i casi si parla di enumerazione se la funzione è su A. Un'enumerazione di A è una sequenza finita o numerabile tale che ogni elemento diA è un termine della sequenza e ogni termine della sequenza è elemento diA. .

Nota Una funzioneF daA suB è chiamata anche "suriettiva". Una funzione iniettiva daA suB è chiamata anche "biiettivà'.

Esercizio 3 Perché 0 E {l, 2}?

Esercizio 4 Perché ha senso usare I' articolo determinativo quando si parla dell'insieme vuoto?

Esercizio 5 Se A è in corrispondenza biunivoca con Be B è in corri­spondenza biunivoca con C, alloraA è in corrispondenza biunivoca con C. Perché?

1.5. Metodi dimostrativi Analogaalladistinzionetralinguaggio oggetto e metalinguaggio è quella tra dimostrazione in un sistema e dimostrazione su un sistema. Dato un sistema S oggetto della teoria,

20

una dimostrazione in S è una sequenza di formule del linguaggio di S -il linguaggio oggetto - che soddisfa i requisiti sintattici fissati dalla defi­nizione di dimostrazione in S. Una dimostrazione su S, invece, è un ragionamento corretto formulato nel metalinguaggio, cioè un insieme strutturato di argomenti deduttivamente validi che si fonda su premes­se vere e quindi permette di ricavare la verità di un enunciato su Sa parti­re dalla verità di altri enunciati. Qui saranno illustrati alcuni metodi dimostrativi ampiamente usati nella teoria della logica. Il primo è il metodo della dimostrazione per costruzione. Questo metodo si adotta quando si vuole dimostrare che esistono oggetti che hanno certe proprietà, e consiste nella costruzione di un oggetto che ha quelle proprietà. Infatti, se un oggetto dato ha certe proprietà allora esiste almeno un oggetto che ha quelle proprietà. Supponiamo di voler di dimostrare che per ogni insieme esiste una funzione iniet­riva dall'insieme su sé stesso. Un modo di procedere è il seguente. Dato un insieme A, sia id A la funzione che àssegna a ogni elemento di A lo stesso elemento. In altri termini, MA è la funzione identità su A, cioè la funzione tale che, per ognix,y EA, (x,y) E idAssex = y. È evidente che id A è iniettiva: non esistono argomenti distinti ai quali id A assegna lo stesso valore, essendo i valori identici agli argomenti. È altrettanto evidente che id A è una funzione daA suA, dato che A risul­ta essere sia dominio sia codominio. Dunque esiste una funzione iniettiva daA su A. Ovviamente, non sempre è così facile giustificare l'esistenza di un oggetto o il possesso di un insieme di proprietà. Per questo una dimostrazione per costruzione può essere molto più lunga e complessa. Il secondo metodo è quello della dimostrazione per casi. In una dimo­strazione per casi si assume una disgiunzione la cui verità è garantita, e si mostra che un enunciato consegue da ciascuno dei suoi disgiunti. In questo modo si può inferire che l'enunciato è vero. Infatti, in una disgiunzione vera almeno uno dei disgiunti anche se non sappiamo quale - deve essere vero. Supponiamo di voler dimostrare che, per ogni n, 3n2 + n + 14 è un numero pari. I casi possibili sono due. Caso 1: n è pari. In questo caso n = 2k per qualche k. Quindi, si posso­no svolgere i seguenti passaggi:

21

3n2 +n+ 14 3(2k)2 +2k+ 14 3(2k)2 + 2k + 14 = 12k2 + 2k + 14

12k2 +2k+ 14=2(6k2 +k+7)

Questo significa che 3n2 + n + 14 è pari. Caso 2: n è dispari. In questo caso n = 2k + 1 per qualche k. Quindi, si possono svolgere i seguenti passaggi:

3n2 +n+ 14=3(2k+ 1)2+2k+ 1+14 3(2k + 1)2 + 2k + 1 + 14 = 12k2 + 12k + 3 + 2k + 1 + 14

12k2 + 12k+ 3+2k+1+14 12k2+ 14k+ 18 12k2+14k + 18 = 2(6k2 + 7k + 9)

Quindi anche in questo caso 3n2 + n + 14 è pari, il che conclude la dimostrazione. Il terzo metodo è quello della dimostrazione per assurdo. Questo meto­do si fonda su un principio elementare che esprime una relazione tra negazione e contraddizione. Che cosa sia la negazione è abbastanza chiaro. Se un enunciato si usa pe~ asserire che le cose stanno in un certo modo, la sua negazione è un enunciato che si usa per as~erire che le cose non stanno in quel modo. Ad esempio, la negazione di "La neve è bian­ca" è "La neve non è bianca". Un enunciato e la sua negazione si contraddicono, in quanto non possono essere né entrambi veri né entrambi falsi. Infatti, la negazione di un enunciato è falsa se l'enuncia­to è vero, mentre è vera se l'enunciato è falso. Il principio, noto anche con il nome latino reductio ad absurdum, è il seguente:

Principio della riduzione all'assurdo Se un enunciato - insieme ad altri enunciati la cui verità è garantita - implica una contraddizione, allora la negazione dell'enunciato è vera.

Supponiamo che un enunciato implichi una contraddizione. Se l'enunciato fosse vero, anche la contraddizione dovrebbe essere vera, il che è impossibile. Dunque la negazione dell'enunciato è vera. Ci sono due modi in cui il principio della riduzione all'assurdo può

22

essere impiegato in una dimostrazione. Nel primo caso si parte dall'i­potesi che un enunciato sia vero e si ricava una contraddizione da questa ipotesi, concludendo così che la negazione dell'enunciato è vera. Nel secondo caso si parte dall'ipotesi che la negazione di un enunciato sia vera e si ricava una contraddizione da questa ipotesi, concludendo così che l'enunciato è vero. Il secondo tipo di ragionamento, che è quel­lo più comunemente noto come dimostrazione per assurdo, può esse­re derivato dal primo se si assume che la doppia negazione di un enun­ciato equivalga all'enunciato stesso. Infatti, in base al primo tipo di ragionamento, se la negazione di un enunciato implica una contrad­dizione, allora la sua doppia negazione è vera. Un esempio paradigmatico di dimostrazione per assurdo è la dimostra­zione dell'esistenza di infiniti numeri primi fornita da Euclide (fi. 300 a.C.). Un numero primo è un numero naturale maggiore di 1 che non ammette divisori diversi da sé stesso e da 1. Supponiamo che l'insieme dei numeri primi sia finito, cioè che per qualche n i numeri primi siano esattamente p 1, ••• , p n· Allora qualsiasi numero intero diverso da p 1,

... , p,, non è primo, pertanto ammette come divisore qualche numero intero diverso da sé stesso e da 1. Siccome ogni numero intero maggio­re di 1 equivale a un prodotto di numeri primi, qualsiasi numero inte­ro diverso da p 1, ••• ,p,,ammettecomedivisorequalchepfcon 1:;:; i:;:; n. Ora si consideri il numero m tale che m = (p1 • ••• ·P,,) + L Da un lato, m risulta maggiore di ciascun pi' quindi per ipotesi non può essere primo. Questo significa che m deve essere divisibile per qualche Pr Dall'altro, però, ogni divisione di m per qualche P; dà come resto 1, quindi m non può essere divisibile per qualche Pr La supposizione che l'insieme dei numeri primi sia finito implica una contraddizione. Il quarto metodo è quello della dimostrazione per induzione. Il principio sul quale si fonda questo metodo risulta comprensibile se si tiene presen­te un tipo di definizione piuttosto comune in matematica. Una definizio­ne induttiva di un insieme A è una definizione in cui si costruisce A mediante un procedimento che si articola in tre fasi. Per prima cosa si stabilisce che alcuni oggetti appartengono ad A. Chiamiamo questi oggetti "elementi iniziali". Poi si specifìcano alcune operazioni che, appli­cate a elementi diA, producono elementi diA, cioè tali che il risultato

23

della loro applicazione a ciascuno degli elementi iniziali, al risultato della loro applicazione a ciascuno degli elementi iniziali e così via, è ancora un elemento diA. In altri termini, A risulta chiuso rispetto alle operazioni specificate, cioè tale che, se certi oggetti appartengono adA, qualsiasi oggetto ottenuto da quegli oggetti mediante una delle operazioni speci­ficate appartiene adA. Infine, si chiarisce che nessun altro oggetto è elemento diA. In questo modo risultano essere elementi diA gli elemen­ti iniziali più tutti quelli che si ottengono a partire da essi iterando un numero qualsiasi di volte le operazioni specificate:A è costruito come il più piccolo insieme contenente gli elementi iniziali e chiuso rispetto alle operazioni specificate. Una definizione induttiva si divide quindi in tre pa.rti: la base dell'induzione fissa gli elementi iniziali, il passo induttivo specifica le operazioni che permettono di ottenere altri elementi a parti­re da questi e una clausola finale stabilisce che l'insieme non ha altri elementi. Ad esempio, la definizione induttiva di OJ è la seguente: 1. O è un numero naturale; 2. se n è un numero naturale, allora il successore di n è un numero naturale; 3. nient'altro è un numero naturale. La clausola 1 stabilisce che O è elemento di OJ. La clausola 2 specifica un'operazione Su di passaggio al successore, che consiste nell'addizio­ne di 1. Questa operazione, applicata a un elemento qualsiasi di OJ dà come risultato un altro elemento di OJ. In altri termini, Su : OJ _..,. OJ. La clausola 3 assicura che OJ non contenga altri elementi. In questo modo, w è definito come il più piccolo insieme contenente O e chiuso rispet­to a Su. Normalmente, una definizione induttiva viene formulata enunciando solo la base dell'induzione e il passo induttivo, perché la clausola finale è data per sottintesa. Anche qui si adotterà questa convenzione.

Se si dice induttivo un insieme per il quale esiste una definizione indut­tiva, il principio sul quale si fonda il metodo della dimostrazione per induzione può essere enunciato come segue:

Principio di induzione DatouninsiemeinduttivoA,seunacondizio­ne e vale per un insieme di oggetti che include gli elementi iniziali di

24

A ed è chiuso rispetto alle operazioni mediante le quali A è costruito, allora C vale per tutti gli elementi diA.

In base a questo principio, per dimostrare che e vale per tutti gli elemen­ti diA è sufficiente dimostrare che C vale per gli elementi iniziali e che le operazioni mediante le qualiA è costruito a partire dagli elementi inizia­li preservano C. La dimostrazione si articola quindi in due parti. Nella base si dimostra che e vale per gli elementi iniziali, che costituiscono il caso più semplice. Nel passo si assume che C valga per certi oggetti e se ne ricavala conclusione che e vale anche per altri oggetti ottenuti appli­cando a quelli le operazi~ni mediante le quali A è costruito. L'assunzio­ne si chiama ipotesi di induzione. Nel caso dei numeri naturali c'è un solo elemento iniziale, O, e una sola operazione, Su. Quindi nella base si dimo­stra che C vale per O, mentre nel passo si dimostra che Su preserva C. In una dimostrazione per induzione che contempli Su come unica operazione, il modo più semplice di formulate il passo è il seguente: se C vale per n, allora vale pern + 1. Un altro modo è il seguente: se C vale per ogni numero minore o uguale an, allora vale pern + 1. Nel secondo caso l'ipotesi di induzione è più forte, in quanto si assume non solo che C valga per un numero qualsiasi n, ma pure che C valga per tutti i numeri che precedono n. Per questo si parla di induzione debole nel primq caso e di induzione forte - o "completa" - nel secondo. L'induzione debole giustifica l'induzione forte. Supponiamo che sia stato diinostrato che e vale per o e che, se e vale per ogni numero minore o uguale a n, allora vale per n + 1. Sia C* la condizione che vale per un numero m sse C vale per ogni numero minore o uguale am. Dato che C vale per O, C*vale per O. Inoltre, se C* vale per n, allora vale per n + 1. Infatti, se C vale per ogni m minore o uguale a n, allora e vale per n + 1, dunque per ogni m minore o uguale a n + 1. Per induzione debole, quindi, si ottiene che C* vale per qualsiasi n. Da questo consegue che C vale per qualsiasi n. Ecco un esempio di induzione debole. Supponiamo di voler dimo­strare che, per ogni n > O:

n(n + 1) l+ ... +n=---

2

25

Il lato sinistro dell'uguaglianza consiste nell'addizione di tutti i numeri compresi tra 1 e n. La dimostrazione può essere formulata come segue. Base. Assumiamo che n = 1. In questo caso l'uguaglianza vale sicura­mente, poiché si riduce a 1 = 1. Passo. Assumiamo che l'uguaglianza valga per n. Ora consideriamo il lato sinistro dell'uguaglianza per n + 1, cioè 1 + ... + n + (n + 1 ). Raggrup­pando i primi n addendi si ottiene:

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

Per ipotesi di induzione, la prima espressione tra parentesi del lato destro può essere sostituita come segue:

n(n + 1) 1 + ... + n + (n + 1) = + (n + 1)

2

A partire da questo si possono svolgere i seguenti passaggi:

n(n+l) 2(n+l) ---+---

2 2 l+ ... +n+(n+l)

n2 +3n +2 · 1+ ... +n+(n+1)=----

2

(n + l)(n + 2) l+ ... +n+(n+l)=----

. 2

Questo significa che l'uguaglianza vale per n + 1. Come esempio di induzione forte, si consideri il fatto, richiamato nella dimostrazione di Euclide, che ogni n > 1 è un prodotto di numeri primi. Questo fatto può essere dimostrato come segue. Base. Assumiamo che n = 2. In questo caso è evidente che n è un prodotto di numeri primi: 2 è un numero primo e ogni numero è multiplo di sé stesso.

Passo. Assumiamo che n > 1 e che ogni numero minore o uguale a n sia un prodotto di numeri primi. Ora consideriamo n + 1. Se n + 1 è un numero primo, allora ovviamente è un prodotto di numeri primi. Se non

26

lo è, allora ammette come divisore qualche numero diverso da sé stesso e da 1, dunque è il prodotto di due numeri i e k maggiori di 1. Siccome i e k sono minori di n + 1, per ipotesi di induzione sono entrambi prodotti di numeri primi. Questo significa che n + 1 è un prodotto di prodotti di numeri primi, quindi un prodotto di numeri primi. Si noti che nella seconda dimostrazione l'induzione forte è necessa­ria. Infatti, se si assumesse come ipotesi di induzione solo che n sia un prodotto di numeri primi, l'ipotesi non potrebbe essere applicata a i e k. Si noti inoltre che nella seconda dimostrazione, a differenza che nella prima, il numero considerato nella base è 2. Il motivo è che l'in­sieme sul quale verte la s~conda dimostrazione non è w ma un sottoin­sieme proprio di w, cioè l'insieme dei numeri naturali maggiori di 1. In generale, in una dimostrazione per induzione debole o forte che sia - il numero considerato nella base varia in funzione di ciò che si vuole dimostrare. I metodi dimostrativi che sono stati illustrati costituiscono un insieme altamente rappresentativo, anche se non esaustivo, di modi in cui si possono formulare dimostrazioni nel metalinguaggio. I prossimi capi­toli forniscono un campionario piuttosto vario di esempi di applica­zione di questi metodi. Alcune dimostrazioni che si incontreranno si fondano interamente su uno di essi, altre ne includono più di un(). Indipendentemente dal metodo impiegato, per indicare che una dimostrazione è conclusa si userà il simbolo O, allineato a destra dopo l'ultima riga. Gli enunciati dimostrati saranno chiamati lemmi o teore­mi. Generalmente si usa il termine "lemma'' per designare un risultato preliminare che svolge un qualche ruolo nella dimostrazione di un risultato più importante al quale si riserva l'etichetta di "teorema". In realtà non c'è una distinzione chiara tra lemmi e teoremi. Tutti gli enunciati chiamati "lemmi" potrebbero essere chiamati "teoremi': così come molti enunciati chiamati "teoremi" - anche se non tutti -potrebbero essere chiamati "lemmi". Nonostante questo, la distinzio­ne risulta utile in qualche misura. Dato che il termine "teorema" può designare tanto una formula del linguaggio oggetto quanto un enunciato del metalin~aggio, è opportu­no distinguere tra teorema in un sistema e teorema su un sistema. La

27

distinzione è analoga a quella tra dimostrazione in un sistema e dimo­strazione su un sistema. Mentre un teorema in un sistema S è una formu­la del linguaggio di S dimostrabile in S, un teorema su S è un enunciato del metalinguaggio che verte su S ed è dimostrabile nella teoria su S.

Nota L'induzione forte è chiamata anche induzione completa.

Nota La teoria della logica è chiamata anche "metateoria della logi­cà: o semplicemente "metalogicà'. Analogamente, si chiama "metateo­rema" un teorema su un sistema, per distinguerlo da un teorema del sistema. Qui si farà a meno del prefisso "meta-", assumendo che la distinzione sia sufficientemente chiara.

Esercizio 6 Si consideri la seguente definizione induttiva dell'insie­me delle formule di un linguaggio enunciativo: I. le variabili p, q, r ... sono formule; 2. se a è una formula, allora~ a è una formula; 3. se a e f3 sono formule, allora (a=> {3) è una formula. Qual è la base e qual è il passo?

Esercizio 7 Dimostrare per induzione che, per ogni n > O,

n(n + l)(n + 2)

3 1·2 + ··· + n(n + 1)

Il lato sinistro dell'uguaglianza è costituito dall'addizione dei prodot­ti di tutti i numeri compresi tra 1 e n con i rispettivi successori.

Esercizio 8 Se si dimostra che ogni assioma di un sistema S è una formula valida, si ottiene un teorema di S o un teorema su S?

28

Soluzioni degli esercizi

1. Sì. 2. No. Data una formula a che figura in una dimostrazione, si consi­deri la parte della dimostrazione costituita dalla sequenza di formule che termina con a. Quella sequenza è una dimostrazione di a. 3. Per ogni insieme A, 0 çA. Infatti, per nessunx è possibile chex sia elemento di 0 ma non sia elemento di A, per il semplice fatto che nessunx è elemento di 0. La relazione vale in modo vacuo. 4. Esiste un solo insieme vuoto. Supponiamo che A e B siano vuoti. In questo caso A è sott?insieme di qualsiasi insieme, e lo stesso vale per B. Quindi,AçBeBçA.NeconseguecheA =B. 5. SiaFuna funzione inietti va daA su B. F associa a ogni elemento x

di A esattamente un elemento di B, cioè l'elemento y tale che y = F(x). Sia G una funzione iniettiva da B su C. G associa a ogni elemento y di B esattamente un elemento di C, cioè l'elemento z tale che z = G(y ). Come è facile verificare, la funzione che associa a ciascun elemento x di A l'elemento z di C così ottenuto è una funzione iniettiva da A su c. 6. La clausola 1 è la base. Le clausole 2 e 3 costituiscono il passo. 7. La dimostrazione è per induzione debole, come nel primo dei due esempi considerati. Base. Nel caso in cui n = I, l'uguaglianza si riduce a 2 2. Passo. Assumiamo che l'uguaglianza valga per ne consideriamo il lato sini­stro dell'uguaglianza pern + l,cioè 1 ·2+ ... +n(n + 1) + (n+ l)(n + 2). Raggruppando i primi n addendi si ottiene:

1 ·2+ ... +n(n+ 1) + (n+ l)(n+2) = (1 ·2+ ... +n(n + 1)) + (n+ l)(n+ 2)

Per ipotesi di induzione, la prima espressione tra parentesi del lato destro può essere sostituita come segue:

n(n + l)(n + 2) 1 ·2+ ... +n(n+ 1) + (n+ l)(n+2) = + (n+ l)(n+2)

3

A partire da questo si possono svolgere i seguenti passaggi:

29

· ( ) ( )( )-(n+l)(n+2) 3(n+l)(n+2) l-2+ ... +nn+l + n+l n+2 - + .

3 3

( ) ( )( ) (n+l)(n2 +2n)+(n+l)(3n+6)

l-2+ ... +n n+l + n+l n+2 =------------3

(n+l)(n2 +5n+6) l ·2+ ... +n(n+ l)+(n+ l)(n+2)=------

3 .

Dato che (n2 + Sn + 6) = (n + 2)(n + 3),siha:

·(n+l)(n+2)(n+3) 1·2 + ... + n(n + 1) + (n + I)(n + 2) = ------

3

Questo significa che l'uguaglianza vale per n + I. 8. Un teoremasuS.

30

2. Il linguaggio l

2.1. Vocabolario e regole di formazione Questo capitolo presenta un linguaggio predicativo chiamato L. I simboli di L sono i seguenti:

::J \;/

( ) x,y,z ... a,b,c ... P,2R ... fi,fi,fr·

I primi tre sono connettivi. ~ e ::J si trovano normalmente in un linguaggio enunciativo. \:I è il quantificatore universale, caratteristi­co di un linguaggio predicativo. Le parentesi servono a comporre i simboli di L in modo non ambiguo. x,y, z ... sono variabili. I cop.net­tivi, le parentesi e le variabili sono costanti logiche, gli altri simboli sono espressioni non logiche. a, b, c ... sono costanti individuali. P, 2 R ... sono costanti predicative. Ciascuna costante predicativa han posti, per qualche n.fi,fi,fy .. sono simboli di funzione, anche in questo caso ciascuno con n posti. L'insieme delle variabili è numera­bile. Lo stesso vale per le costanti individuali, le costanti predicative e i simboli di funzione. Le regole di formazione di L richiedono innanzitutto che si defini­sca un insieme di termini come il più piccolo insieme che contiene tutte le costanti individuali, tutte le variabili e tale che, se t 1, ... , tn appartengono all'insieme, un simbolo di funzione/ a n posti seguito da t 1, ... , tnappartiene all'insieme. Successivamente si definiscono le formule di L:

31

Definizione 1 1. Se P e una costante predicativa a n posti et 1, ••• , tn sono termini,,allo-

ra Pt1, ... , tll e una formula; 2. se a e una formula, allora ....., a e una formula; 3. se ae f3sonoformule, allora (a:=) /3) e una formula; 4. se a e una formula e X e una variabile, allora V xa e una formula.

D'ora in poi si userà l'espressione Dn per indicare la definizione n. Così, la definizione appena esposta sarà chiamata D l, la successiva D2 ecc. La stessa convenzione sarà adottata per i lemmi e i teoremi. I lemmi saranno indicati con la lettera L, i teoremi con la lettera T. D 1 caratterizza linsieme delle formule di L per via induttiva. Gli elementi iniziali dell'insieme sono le formule introdotte mediante D 1.1, che costituisce la base dell'induzione. Queste formule possono essere chiamate atomiche, in quanto non sono composte da altre formule. Le operazioni mediante le quali l'insieme è costruito a parti­re dalle formule atomiche sono le regole di formazione specificate in D 1.2-D 1.4, che costituiscono il passo induttivo. In una formula V xa costruita sulla base di D 1.4, a costituisce lambi­to del quantificatore. Ad esempio, nella formula V çc "'Px lambito del quantificatore è ....., Px. Siccome V xa è una formula per qualsiasi a, in V xa l'ambito del quantificatore può non contenere x o altre variabili. Ad esempio, V x ....., Py è una formula, e lo stesso vale per V x "'Pa. Un'occorrenza di una variabile è vincolata in una formula quando la variabile segue direttamente un quantificatore oppure è nell'ambito di un quantificatore seguito direttamente dalla variabile stessa. Un'occorrenza di una variabile è libera in una formula quando non è vincolata nella formula. Se tutte le occorrenze di una variabile in una formula sono vincolate, si dice che la variabile è vincolata nella formu­la. Se invece alcune occorrenze di una variabile in una formula sono libere, si dice che la variabile è libera nella formula. Così, x è vincolata in V x....., Px, mentre y è libera in V x....., Py. Una formula che contiene occorrenze libere di variabili è aperta. Una formula che non è aperta è chiusa. Ad esempio, Px è una formula aper­ta, mentre V xPx è una formula chiusa. Le formule chiuse si chiama-

32

no enunciati, perché corrispondono a enunciati delle lingue naturali. La distinzione tra aperto e chiuso può essere applicata anche ai termi­ni. Un termine aperto è un termine che contiene variabili. Un termine chiuso è un termine che non è aperto. Ad esempio,fix è un termine aperto, mentre a è un termine chiuso.

Nota I simboliP, t 1, ••• , tn, ae f3 che compaiono in DI sono variabili metalinguistiche. Il caso è analogo a quello della definizione presenta­ta nell'esercizio i.6 (cioè nell'esercizio 6 del capitolo 1).

Nota Per semplificarel~notazione, si ometteranno le parentesi ester­ne. Ad esempio, invece di scrivere (V xPx::::) (Py::::) Px)) si scriverà semplicemente V xPx::::) (Py::::) Px).

Esercizio 1 SiaA linsieme delle costanti individuali di L eB linsieme delle variabili di L. L'insieme A U B è numerabile?

Esercizio 2 L'insieme dei termini chiusi di L è numerabile?

Esercizio 3 Formulare una definizione induttiva di "termine di L".

Esercizio 4 Una variabile può essere vincolata in una formula ato­mica?

2.2. Nozioni semantiche di base La sintassi di un linguaggio predicativo è più complessa di quella di un linguaggio enunciativo. In un linguaggio enunciativo le formule atomiche sono variabili che stan­no per enunciati, e le altre formule sono costruite a partire da queste per mezzo di connettivi. Un linguaggio predicativo è dotato di un apparato simbolico più ricco che permette di rappresentare la struttu­ra degli enunciati semplici, cioè degli enunciati che non contengono al loro interno altri enunciati. Questo apparato impone una maggiore complessità a livello semantico. In particolare, rende più articolata la specificazione delle condizioni alle quali una formula del linguaggio può essere detta vera in un'interpretazione.

33

Nel caso di un linguaggio enunciativo si definisce un'interpretazione come un'assegnazione di valori di verità alle formule atomiche e si specifica, per ogni connettivo, il modo in cui il valore di verità di una formula che lo contiene è determinato dai valori di verità delle formu­le più semplici che figurano al suo interno. Si ottiene così una seman­tica rigorosamente composizionale, cioè tale che il significato di ogni formula - il suo valore di verità- risulta determinato dai significati assegnati alle unità sintattiche più semplici a partire dalle quali la formula è costruita mediante le regole di formazione. Ad esempio, il valore di verità di p :::::> q può essere calcolato sulla base dei valori di veri­tà assegnati a p e q, dato il significato di:::::>. Nel caso di un linguaggio predicativo, invece, la situazione è più complicata. In questo caso non si può definire un'interpretazione come un'assegnazione di valori di verità alle formule atomiche. Infat­ti, non tutte le formule atomiche sono enunciati, cioè unità sintattiche alle quali ha senso attribuire valori di verità. L include sia formule atomiche che sono traducibili con espressioni delle lingue naturali alle quali sembra corretto attribuire verità o falsità, come Pa, sia formule atomiche che non lo sono, come Px: si può dire che "Felix è un gatto" è vero, ma non che "x è un gatto" è vero. Di cons~guenza, non si può assumere che i valori di verità delle formule che contengono connetti­vi siano determinati dai valori di verità delle formule più semplici che figurano al loro interno. V xPx è una formula di L alla quale ha senso assegnare un valore di verità: si può certamente dire che "Ogni cosa è un gatto" è falso. Ma l'unica formula che figura come costituente di V xPx è Px, alla quale non ha senso assegnare un valore di verità. Resta quindi il problema di come specificare le condizioni alle quali un enunciato è vero in un'interpretazione. Alfred Tarski ( 1902-1983) ha suggerito un metodo che permette di venire a capo di questo problema. Le condizioni alle quali un enuncia­to è vero in un'interpretazione possono essere specificate nei termini di una nozione semantica diversa da quella di verità- la nozione di soddi­sfacimento - che è definita per tutte le formule. L'idea di fondo è piut­tosto semplice. Si consideri la formulaPa. La costante individuale a sta per un'espressione che denota un oggetto, come "Felix': mentre la

34

costante predicativaP sta per un predicato che si applica a un insieme di oggetti, come "gatto". Dunque, è naturale pensare che Pa sia vera nel caso in cui a denoti un oggetto che appartiene all'insieme di oggetti ai quali si applica F. Ora si consideri la formulaPx. La variabilex non sta per un nome o qualcosa di simile, quindi non ha senso assumere che denoti un oggetto. Per questo non ha senso attribuire un valore di veri­tà a Px. La differenza tra "Felix è un gatto" e "x è un gatto" è che nel secondo caso non c'è un oggetto denotato del quale possiamo chieder­ci se è un gatto. Ma se supponiamo che ci sia un tale oggetto, allora da quella supposizione possiamo ricavare un valore di verità da attribuire all'espressione "x è un g~tto". Ad esempio, immaginare che x denoti Felix significa immaginare un caso in cui l'espressione è vera, mentre immaginare che denoti Fido significa immaginare un caso in cui l'espressione è falsa. In altri termini, "x è un gatto" è vera relativamente alla supposizione chex si riferisca a Felix, falsa se si suppone chex si rife­risca a Fido. Il soddisfacimento di una formuia da parte di un'assegna­zione di valori alle variabili consiste in questo. Px è soddisfatta da un'as­segnazione in base alla quale x denota un certo oggetto se Px è vera relativamente alla supposizione chex denoti quell'oggetto, cioè se quel­l'oggetto appartiene all'insieme di oggetti ai quali si applica F. Il metodo di Tarski consente di assegnare valori di verità agli enuncia­ti quantificati sulla base del significato di unità sintattiche più sempli­ci che figurano al loro interno. Infatti, la verità o falsità di un ènuncia­to quantificato, come V xPx, risulta determinata dalle condizioni di soddisfacimento della formula che costituisce lambito del quantifica­tore.Tuttavia, questo non implica che una semantica fondata sul meto­do di Tarski sia rigorosamente composizionale. Se un enunciato è costruito mediante una regola di formazione mettendo insieme due espressioni più semplici, il requisito della composizionalità richiede che il valore di verità dell'enunciato si ottenga dalla combinazione del significato di una delle due espressioni con il significato dell'altra. Quindi, nel caso in cui un enunciato V xa sia formato aggiungendo V x a a, come prescrive D 1.4, si richiede non solo che il significato di a contribuisca a determinare il valore di verità di V xa, ma che il valo­re di verità di V xa si ottenga combinando questo significato con quel-

35

lo di V x. La seconda condizione è più forte della prima, in quanto

implica la prima ma non ne è implicata. Certamente, si può abbandonare del tutto l'idea che la semantica di un linguaggio come L debba soddisfare il requisito della composizionali­tà, e sostenere che V x, così come V, è un'espressione priva di signifi­cato. Usando un termine un po' desueto, si può asserire che V x, così come V, è un'espressione sincategorematica, cioè un'espressione che non ha significato presa isolatamente, ma che contribuisce insieme ad altre espressioni a generare unità sintattiche complesse dotate di signi­ficato. Pertanto, un enunciato V xa risulta composto da due parti di cui solo una, a, è dotata di significato. Questa è un'opzione compatibi­le con il metodo di Tarski. Ma non è l'unica. Un'altra opzione si ispira a una tesi sulla quantificazione che risale a Gottlob Frege (1848-1925). L'idea di Frege è che le espressioni quan­tificate, come "ogni cosa", designino funzioni di tipo particolare, le "funzioni di secondo livello". I significati dei predicati sono per Frege "funzioni di primo livello", che associano valori di verità a oggetti. Ad esempio, il significato di "gatto" è una funzione G che associa 1 a Felix e O a Fido. Una funzione di secondo livello, invece, è una funzione che prende come argomenti funzioni di primo livç:llo. Il significato di "ogni cosà' è per Frege una funzione di secondo livello O che associa valori di verità a funzioni di primo livello. Per ogni funzione di primo livello F, O(F) 1 se F(x) 1 per ogni x, altrimenti O(F) = O. In questo modo il valore di verità di "Ogni cosa è un gatto" risulta deter­minato dalla combinazione dei significati delle sue parti, poiché si ottiene applicando O a G: O( G) = 1 sse G(x) = 1 per ogni x. In base all'idea di Frege, dunque, un eunciato V xa è composto da una parte che esprime una funzione di secondo livello e da una parte che esprime una funzione di primo livello, e il suo valore di verità risulta dalla combinazione delle due funzioni. Sebbene questa seconda opzione sia per certi versi più attraente della prima, non è chiaro come possa essere tradotta in una semantica rigoro­samente composizionale che si conformi a D 1.4. Per rendersene conto basta riflettere sulla formula V xPx. Si può essere tentati di dire che V x designala funzione di secondo livello O e che Px designa una funzione

di primo livello che associa 1 a tutti gli oggetti di un certo insieme. Ma questa via non è praticabile. Si consideri una variabile y diversa dax. V x e V y designano la stessa funzione? Da un lato, sembra che la rispo­sta debba essere affermativa. Se due funzioni associano gli stessi valori agli stessi argomenti, come si presume che sia in questo caso, allora sono la stessa funzione, cioè O. Dall'altro, tuttavia, una risposta affermativa appare inaccettabile. Se V x e V y hanno lo stesso significato, allora il significato di V y si deve poter combinare con quello di altre espressio­ni nello stesso modo in cui si combina il significato di V x. Ma V yPx non ha lo stesso significato di V xPx. Di fatto V yPx non è nemmeno un enunciato, quindi non è ~uscettibile di attribuzioni di verità. Conside­razioni analoghe valgono per Px ePy. Quindi, si deve scartare l'ipotesi che V x designi O e Px designi la funzione di primo livello. Forse si può sostenere che non è V x ma V l'espressione che designa O, così come non è Px maP l'espressione che designa la funzione di primo livello. Le variabili possono essere considerate espressioni sincatego­rematiche che - qualora certe condizioni sintattiche siano soddisfat­te - contribuiscono a formare enunciati rendendo possibile la combi­nazione di due funzioni. In altri termini, V xPx è un'espressione in cui la doppia occorrenza dellax rende possibile la combinazione del signi­ficato di V con quello di P, mentre V yPx è un'espressione in cui non c'è combinazione, quindi continua a valere solo il significato di P. Questa seconda maniera di intendere la tesi di Frege permette non solo di assumere in modo coerente che ci sia un'unica funzione di secondo livello che si può combinare con diverse funzioni di primo livello negli enunciati quantificati, ma pure di spiegare con facilità come le funzio­ni di primo livello contribuiscano a determinare il valore di verità degli enunciati non quantificati. Ad esempio, il valore di verità di Pa può essere spiegato dicendo che si ottiene applicando la funzione di primo livello designata daP alla denotazione di a. Si noti, però, che in questo caso si deve accettare il fatto che V e P non siano espressioni diretta­mente combinabili. L'ausilio di espressioni sincategorematiche diven­ta necessario per la formazione degli enunciati, proprio come nel caso della prima opzione. Quindi si torna al punto di partenza: la semanti­ca non è rigorosamente com posizionale.

37

In sostanza, una definizione di verità costruita nel modo indicato da Tarski non garantisce la composizionalità, almeno non nel senso rigoroso in cui una definizione di verità per un linguaggio enunciati­vo garantisce la composizionalità. Non è detto che questo sia un problema. Il requisito della composizionalità potrebbe essere inteso in un senso diverso ma altrettanto interessante. O addirittura, si potrebbe argomentare che non c'è ragione di pensare che un requisi­to del genere debba essere imposto sulla definizione. In ogni caso, qui interessa solo il fatto che il metodo di Tarski permette di definire la verità per gli enunciati di un linguaggio predicativo superando le difficoltà generate dall'apparato simbolico della quantificazione. Nei paragrafi seguenti sarà presentata una semantica per L che si fonda su questo metodo.

2.3. Soddisfacimento Per interpretare L si specifica innanzitut­to un dominio, cioè un insieme di oggetti che costituisce l'universo di discorso. Poi si definisce una funzione interpretazione che, facendo riferimento al dominio, assegna significati alle costanti individuali, alle costanti predicative e ai simboli di funzione. Si ottiene così una strut­tura. Una struttura A è definita più precisament.e come segue.

Definizione 2 Ae una coppia ordinata (D, I) tale che: 1. D e un insieme non vuoto; 2. I e una funzione che assegna

(a) a ciascuna costante individuale un elemento di D; (b) a ciascuna costante predicativa a n posti una relazione R tale che Rc;;;,D11

;

( c) a ciascun simbolo di funzione a n posti una funzione F tale che F:D"-D.

L'insiemeD in D2.1 è il dominio di A. Questo insieme può essere fini­to o infinito. Nel primo caso A si dice finita, nel secondo si dice infi­nita. Se D è infinito, può essere numerabile o non numerabile. Nel primo caso A si dice numerabile, nel secondo si dice non numerabile. La funzione I in D2.2 è la funzione interpretazione di A. In base a

D2.2( a), I fornisce una denotazione inD a tutte le costanti individua­li. Da D2.2(b) risulta che a ciascuna costante predicativa a n posti I assegna una relazione n-aria su D. Infine, D2.2( c) stabilisce che a ciascun simbolo di funzione a n posti I assegna un'operazione n-aria su D. D'ora in poi si adotterà la seguente convenzione. Data una struttura .A; la lettera latina corrispondente A sarà usata per indicare il dominio di A. In altri termini, se A= (D, I) alloraA =D. Le parentesi quadre con pedice .A; invece, saranno usate per indicare il risultato dell'applicazione della funzione interpretazione di A. Ad esempio, se A= (D, I) e tè un termine, allora [t]A =l(t). Data una struttura .A; si chiama assegnazione di valori alle variabili di Luna funzione v che associa a ciascuna variabile di L un elemento diA. La denotazione di un termine t inA relativamente a v, in simboli [t ]A,v' è definita come segue:

Definizione 3 I. Set e una costante individuale, allora [t]A,v = [t]A; 2. set e una variabile, allora [t]A,v = v(t); 3. set ha la forma ftl' .. ., t11 allora [t]A,v = [fJA([t1]A,v' ... , [t,,]A,)

D3 fissala denotazione dei termini in A relativamente a v. D3.1 è banale: la denotazione assegnata alle costanti individuali in .A resta la stessa. Le costanti individuali sono simboli la cui denotazione non varia al variare delle assegnazioni. D3.2 si limita a enunciare che la denotazione di una variabile in A relativamente a v è l'oggetto che v associa alla variabile. D3.3 specifica la denotazione di un termine complesso formato da un simbolo di funzione a n posti J e un insieme di termini t 1, ••• , t,, in base al valore assegnato a/in Ae alla denotazio­ne di t 1, .•• , t .

Jl

Sulla base di D3 si può definire per via induttiva la relazione di soddi-sfacimento di una formula da parte di vin A: ·

Definizione 4 I. vsoddisfaPt1, ••• , t

11sse([tJA,v' ... , [t

11]A,) E [P]A;

39

2. v soddisfa ~ asse v non soddisfa a; 3. vsoddisfa a:) f3sse v non soddisfa ao vsoddisfa {3; 4. v soddisfa \;/ xa sse ogni x-variante div soddisfa a.

D4.1 definisce il soddisfacimento di una formula atomica da parte di vin A. D4.2 e D4.3 estendono la definizione alle formule contenenti ~ e:=). D4.4 è la clausola cruciale. Per capirla occorre tenere presente che v assegna oggetti del dominio a tutte le variabili, mentre la sola variabi­le pertinente nel caso di \;/ xa è x. Quindi, tutto ciò che conta ai fini del soddisfacimento di \;/ xa è che a risulti soddisfatta per qualsiasi valore dix. Questo equivale a dire che a deve essere soddisfatta da qual-

- siasi assegnazione v' che differisce da val massimo per il valore dix, cioè tale che v' (y) = v(y) perogni y :;t: x. Unax-variante div è appunto un'as­segnazione che differisce da val massimo per il valore dix. Quando una formula a è tale che almeno in una struttura c'è qualche assegnazione che la soddisfa, si dice che a è soddisfacibile. Allo stesso modo, quando un insieme di formule r è tale che almeno in una strut­tura c'è qualche assegnazione che soddisfa tutte le formule che contie­ne, si dice che r è soddisfacibile. Da D4 risulta che, in una struttura .A, la questi on.e se un'assegnazione v soddisfi o meno una formula a dipende esclusivamente dai valori che v assegna alle variabili libere in a. In altri termini, se v soddisfa (o non soddisfa) a, allora qualsiasi assegnazione v' che concordi con v sui valori assegnati alle variabili libere in a soddisfa (o non soddisfa) a. Per convincersi di questo fatto, si consideri innanzitutto il seguente

lemma:

Lemma 1 Dato un termine t, se ve v' sono tali che v(x) = v'(x) per ogni variabile x in t, allora [t]A.v = [t]A,vi·

Dimostrazione L1 si dimostra per induzione sulla complessità dit, cioè sul numero di simboli di funzione che contiene. Un termine di comples­sità n è un termine che contiene esattamente n simboli di funzione. Base. Assumiamo che t sia un termine di complessità O. I casi possibili

sono due.

40

Caso 1: tè una costante individuale. In questo caso ve v' non possono differire rispetto al valore di t, poiché la denotazione delle costanti individuali è fissata indipendentemente dalle assegnazioni. Quindi

[t]A,v = [t].A;v1· Caso 2: tè una variabile. In questo caso [t]A.v = [t]A.v1per ipotesi. Passo. Assumiamo che l'uguaglianza da dimostrare valga per tutti i termini di complessità minore o uguale a n e che t sia un termine di complessità n +I. In questo caso t ha la forma.fil' ... , t,,,, dove/è un simbolo di funzione a m posti e t1, ••• , t,,, sono termini. Dato che t

1, ••• ,

t,,, hanno al massimo complessità n, per ipotesi di induzione hanno la stessa denotazione in ve v'. Ma anche la denotazione di /in ve v'è la

stessa. Quindi [fi1, ••• , t11JA,v [fil' ... , t,JA.v'·

D Sulla base di Ll si può dimostrare quanto segue:

Lemma 2 Sevev' sono tali che v(x) = v'(x)perogni variabilexlibera in a, allora v soddisfa asse v' soddisfa a.

Dimostrazione L2 si dimostra per induzione sulla complessità di a, cioè sul numero di connettivi che contiene. Una formula di comples­sità n è una formula in cui n simboli sono connettivi. Base. Assumiamo che a sia una formula di complessità O, cioè una formula atomicaPt1, ••• , t,,. Supponiamo che v(x) = v'(x) per ogni variabilex libera inPtl' ... , t,,, cioè per ogni variabilex inPt1, ... , t,,. Da L1 risulta che, per ogni i tale che 1 :::; i:::; n, [tJ.A;v [tJ.A;v•' Ma v soddi­sfa asse ([t1].A;v' .. ., [t,,].A;) E [P]A e v' soddisfa asse ([t1]A.v'' ... , [t,,]A.) E [P]A. Quindi, v soddisfa asse v' soddisfa a. Passo. Assumiamo come ipotesi di induzione che per ogni formula di complessità minore o uguale a n valga il condizionale enunciato nel teorema: se ve v' sono tali che v(x) = v'(x) per ogni variabile libera x, allora la formula è soddisfatta da v sse è soddisfatta da v'. Assumia­mo poi che a sia una formula di complessità n + 1 e che v e v' siano tali che v(x) v'(x) per ogni variabile x libera in a. I casi possibili sono tre. Caso 1: a ha la forma~ {3. Siccome f3 ha complessità n, per ipotesi di

41

induzione v soddisfa f3 sse v' soddisfa {3. Quindi, v non soddisfa asse v' non soddisfa a. Questo significa che v soddisfa asse v' soddisfa a. Caso 2: a ha la forma f3 ::J y. Siccome f3 e r hanno al massimo comples­sità n, per ipotesi di induzione v soddisfa f3 sse v' soddisfa {3, e v soddi­sfar sse v' soddisfa y. Quindi, se v non soddisfa f3 o soddisfa y, lo stes­so vale per v', e viceversa. Questo significa che v soddisfa asse v' soddisfa a. Caso 3: a ha la forma\:/ xf3. In questo caso f3 è una formula di comples­sità n che contiene come variabili libere tutte quelle che sono libere in a con l'aggiunta (al massimo) dix. Sia v. unax-variante div che asso­cia un certo oggetto ax. Sia v~ unax-variante div' che associa quello stesso oggetto ax. v. e v~ concordano sui valori delle variabili libere in {3. Infatti, ve v' concordano sui valori delle variabili libere in a, e l'uni­ca variabile libera che f3 può avere in più di a è x. Per ipotesi di indu­zione, ne risulta che v. soddisfa f3 sse v'. soddisfa {3. In generale, ogni x-variante div soddisfa f3 sse ognix-variante div' soddisfa {3. Quindi, v soddisfa asse v' soddisfa a.

o

2.4. Verità Dalla definizione di soddisfacimento si può ricavare una definizione di verità per gli enunciati. Dato un enunciato a e una struttura A, sia [a] A il valore di verità che a ha in A. Allora:

Definizione 5 [a]A = 1 sseogniassegnazionein Asoddisfa a.

Definizione 6 [a ]A= O sse nessuna assegnazione in Asoddisfa a.

Data una struttura A, ogni enunciato è soddisfatto da tutte le assegnazio­ni in A o non è soddisfatto da nessuna. Questo si deve al fatto che gli enunciati non contengono variabili libere. Supponiamo infatti che un'as­segnazione v soddisfi un enunciato a e consideriamo un'assegnazione qualsiasi v' diversa da v. Se v' non fosse tale da soddisfare a, allora sareb­be falso che v soddisfa asse v' soddisfa a. Di conseguenza, in base a L2 si potrebbe inferire che a contiene almeno una variabile liberax tale che v(x) =t:- v'(x). Ma questo è impossibile, essendo aun enunciato. Con un

42

ragionamento analogo si può concludere che, se un'assegnazione qualsia­si non soddisfa a, allora nessuna delle altre soddisfa a. Di conseguenza, [ a]A = 1 o [ a]A =O, come prescrive il principio di bivalenza. Anche una formula aperta, come un enunciato, può essere soddisfatta da tutte le assegnazioni in una struttura, o non essere soddisfatta da nessuna. In una struttura che assegna aP l'intero dominio, Px è soddi­sfatta da tutte le assegnazioni, mentre~ Px non è soddisfatta da nessu­na. Il motivo per cui formule aperte come queste non sono chiamate vere o f<!_lse è che non corrispondono a espressioni di una lingua natu­rale alle quali ha senso attribuire verità o falsità. Si noti, tuttavia, che per ciascuna formula aperta soddisfatta da nitte le assegnazioni in una struttura, L contiene un enunciato corrispondente che è vero nella struttura. Infatti, data una formula a che contiene una variabile libera x, a è soddisfatta da tutte le assegnazioni in Asse \:/ xa è soddisfatta da tutte le assegnazioni in A. Il caso della falsità è analogo.

Esercizio 5 Spiegare perché a è soddisfatta da tutte le assegnazioni in Asse \:/ xa è soddisfatta da tutte le assegnazioni in A.

2.5. Conseguenza logica e validità Nel paragrafo i.2 si è visto che conseguenza logica e validità possono essere definite in termini di verità. Le definizioni che seguono sono in termini di soddisfacimento, quindi valgono indistintamente per qualsiasi formula a e per qualsia­si insieme di formule r.

Definizione 7 f f= asse, in ogni struttura, ogni assegnazione che soddi­sfa tutte le formule in r soddisfa a.

Il simbolo F indica che a è conseguenza logica dir. Se r contiene /31' ... , /3,, e si vogliono elencare queste formule, invece di scrivere {/31' ... , f3 } si scrive semplicemente /31' ... , f3,,. Allo stesso modo, se f contiene sol~ una formula {3, invece di scrivere {/3} si scrive semplicemente {3.

Definizione 8 f= asse a e soddisfatta da tutte le assegnazioni in tutte le strutture.

43

Il simbolo f= indica che a è valida. Si noti che nel caso degli enunciati, D7 e D8 coincidono con le definizioni fornite nel paragrafo 1.2. Se un enunciato a e un insieme di enunciati f sono tali che, in ogni struttu­ra, ogni assegnazione che soddisfa tutti gli enunciati in f soddisfa a, allora ogni modello di f è modello di a, e viceversa. Se un enunciato a è soddisfatto da tutte le assegnazioni in tutte le strutture, allora ogni struttura è modello di a, e viceversa. L'idea alla base di D7 è che, se a è un enunciato di L, f è un insieme di enunciati di Le r F a, tutti gli argomenti della formar; a sono dedut­tivamente validi. Ad esempio, D7 implica che V x(Px ::J Qx), Pa f= Qa. Questo rende conto del fatto che tutti gli argomenti della forma _V x(Px ::J 0 ), Pa; Qa, come il seguente, sono deduttivamente validi: "Ogni balena è bianca, Mo by Dick è una balena; Mo by Dick è biancà'. Dunque, la relazione di conseguenza logica tra enunciati di L fornisce una caratterizzazione di un insieme di argomenti deduttivamente vali­di che hanno una forma esprimibile in L. Il caso della validità è analogo. D8 si fonda sull'idea che un enunciato valido di L esprima la forma di un insieme di enunciati veri di una lingua naturale. Ad esempi~, V x(Px ::J Px) esprime la forma dell'e­nunciato "Ogni cosa bianca è bianca". Dunque, l'insieme degli enun­ciati validi di L fornisce una caratterizzazione di un insieme di verità logiche che hanno una forma esprimibile in L.

Esercizio 6 Perché D8 implica che V x(Px ::J Q?c), Pa f= Qa?

Esercizio 7 Spiegare perché vale quanto segue:

Lemma 3 Se r F a, allora r u b. F a.

Lemma 4 Se F a, allora r F a.

44

Soluzioni degli esercizi

1. Sì. Per rendersi conto di questo fatto bisogna capire che l'unione di due insiemi numerabili è sempre un insieme numerabile. Siano A e B insiemi numerabili. Data un'enumerazione (a1, a2, ar.) diA, si può associare a1 a O, a2 a 2, a 3 a 4 e così via per gli altri numeri pari. Allo stesso modo, data un'enumerazione (b1, b2, br.) diB, si può associare b1 a1, b2 a3, b

3 a 5 e così via per gli altri numeri dispari. Di conseguen­

za, esiste una funzione iniettiva daA U B su w, cioè la funzione che associa a

1 a O, b 1 a 1, a2 a 2 e così via. Questo significa che A U B è in

corrispondenza biunivqca con w. Nel caso specifico in cui A è l'insie­me delle costanti individuali di L e B è l'insieme delle variabili di L, basta supporre che a1 sia la prima costante individuale, b 1 sia la prima variabile e così via. 2. Sì. Data un'enumerazione (a, b, c ... ) delle costanti individuali di L, supponiamo che a sia associato a O, b a 2, e a 4 e così via per gli altri numeri pari. Data un'enumerazione ifi,fi,fr.) dei simboli di funzio­ne di L, supponiamo chefr sia associato a l ,fi a 3,h a 5 e così via per gli altri numeri dispari. Siccome i termini chiusi di L sono sequenze fini­te di simboli ciascuno dei quali è una costante individuale o un simbo­lo di funzione, esiste una funzione iniettivaF che assegna a cia,scun termine chiuso il numero ottenuto sostituendo i simboli che contiene con i rispettivi numeri. Ad esempio, F assegna 10 afia, 12 afib e così via. Chiamiamo A il dominio di F e B il suo codominio. A è un insie­me infinito, poiché sono infiniti i simboli che possono essere combi­nati per formare un termine chiuso. Lo stesso vale per B, dato che A è in corrispondenza biunivoca con B. DunqueB è un sottoinsieme infi­nito di w. Ma ogni sottoinsieme infinito di w è numerabile. Per convincersi di questo fatto basta ragionare su un esempio di sottoinsie­me infinito di w, come l'insieme dei numeri pari: si associ O a O, 2 a 1, 4 a 2 e così via. Dunque B è numerabile. Lo stesso vale per A, essendo A in corrispondenza biunivoca con B. 3. Base. Le costanti individuali e le variabili sono termini di L. Passo. Se ti' ... , tn sono termini di Le /è un simbolo di funzione a n posti, allora.ft1, .•• , tn è un termine di L.

45

4. No. Le formule atomiche non contengono quantificatori. 5. Supponiamo che a sia soddisfatta da tutte le assegnazioni.in .A. Allora per qualsiasi assegnazione v, a è soddisfatta da tutte lex-varian­ti div. Di conseguenza, V xa è soddisfatta da v. Il caso del condiziona­le inverso è analogo. 6. Supponiamo che v soddisfi V x(Px ::J 0) ePa. Sia v' unax-varian­te di v che assegna a x la denotazione di a. Dato che v soddisfa V x(Px ::J 0), v' soddisfaPx ::J Qx. Dato che v (e quindi ogni assegna­zione) soddisfaPa, v' soddisfaPx. Ne risulta che v' soddisfa Q.?:. Ma se v' soddisfa Qx allora v (così come ogni assegnazione) soddisfa Qa. 7. L3 vale perché in una struttura non ci possono essere assegnazio­ni che soddisfano r U Di. ma non soddisfano r (al massimo può valere il contrario). Ogni assegnazione che soddisfar U Di. soddisfar. Pertan­to, se ogni assegnazione che soddisfar soddisfa a, allora ogni assegna­zione che soddisfar U Di. soddisfa a. L4 vale perché in ogni struttura, se a è soddisfatta da tutte le assegnazio­ni, è soddisfatta in particolare da quelle che soddisfano r. Un caso inte­ressante è quello in cui r = 0. Normalmente si assume che 0 sia soddi­sfatto da tutte le assegnazioni in tutte le strutture. Infatti, non esiste una struttura in cui un'assegnazione può mancare di ~oddisfare qualche formula in 0, non essendoci formule in 0. Quindi, f= asse 0 f= a.

3. Il sistema S

3.1. Assiomi Questo capitolo presenta un apparato deduttivo per L, specificando un insieme di assiomi e una regola di inferenza. Il siste­ma così ottenuto si chiama S. Gli assiomi di S sono le formule di L che esemplificano i seguenti schemi:

Al a::J (f3::J a) A2 (a ::J (/3 ::J ì')) ::J ( (a ::J /3) ::J (a ::J ì')) A3 ( ~ a ::J~ /3) ::J (/3 ::J <!) A4 V xa::J a(tlx), se tè sostituibile ax in a. AS a ::J V xa, sex non è libera in a. A6 V x( a::J /3) ::J (V xa::J V xf3) A7 V xa, se a è un assioma.

Gli assiomi di S sono divisi in due gruppi. Il primo è costituito dalle formule di L che esemplificano Al-A3. Questi schemi valgono per qualsiasi sistema di logica enunciativa. Il secondo è costituito dalle formule di L che esemplificano A4-A7. Questi sono gli schemi carat­teristici di S, poiché vertono sulla quantificazione. A4 richiede chiarimenti. Data una formula a, un termine te una varia­bile x, a(tl x) è la formula che si ottiene sostituendo t ax in a per tutte le occorrenze libere dix, qualora ce ne siano. I casi in cui tè sostituibile ax in a sono definiti per induzione come segue:

Definizione 9 1. Se a e una formula atomica, allora te sostituibile a X in a; 2. te sostituibile a x in ~ asse e sostituibile a x in a; 3. tesostituibileaxin a::J f3sse esostituibile axin ae in f3; 4. t esostituibile a X in V yasse, se X e/ibera in \j ya, allora t esostitui­bile a x in a e non contiene y.

D9.1 contemplal'eventualitàche anoncontengax, pertanto a(tlx) =a. Lo stesso si può dire di D9.2 e D9.3. In D9.4, il caso in cui V ya non

47

c~ntiene x è uno dei due casi in cui non vale l'antecedente del lato destro. L'altro è quello in cui x è vincolata in V ya. In entrambi i casi, Vya(tlx) = Vya. Quando vale l'antecedente del lato destro, invece, la condizione che t non contenga y ha lo scopo di evi tare che sostituen­do t ax si vincoli una variabile in t per effetto del quantificatore. La regola di inferenza di S è la seguente:

MP Date due formule a e f3, f3 è conseguenza diretta di a e a--:J f3.

Le lettere Me P sono le iniziali di Modus Ponens, che è il nome tradi­zionale della regola.

Esercizio 1 La sequenza di simboli a--:J (/3--:J a) è un assioma di S?

Esercizio 2 Per spiegare la notazione a(tl x) che compare in A4 si è detto che a(tl x) è la formula che si ottiene sotituendo t ax in a per tutte le occorrenze libere dix, qualora ve ne siano. Fornire una defini­zione induttiva che possa essere usata al posto di questa spiegazione.

Esercizio 3 Spiegare perché MP preserva il so4disfacimento, cioè perché vale quanto segue per qualsiasi assegnazione v:

Lemma 5 Se v soddisfa a--:J f3 e a, allora v soddisfa f3.

3.2. Derivabilità e dimostrabilità L'apparato deduttivo di S permette di definire una derivazione in S nel modo illustrato nel para­grafo 1.2:

Definizione 10 Una derivazione di a da f è una sequenza finita di formule che termina con a ciascuna delle quali esemplifica Al-A7 o è ricavata per mezzo di MP da formule che la precedono o appartiene a[.

Una sequenza di formule così intesa equivale a una sequenza dipassi, cioè i passi che costituiscono il ragionamento mediante il quale in S si giustifica a a partire da f. Ecco un esempio:

48

1. Pa 2. Pa--:JPb 3. Pb l,2MP

Questa derivazione è una sequenza di tre passi. Per rendere esplicito l'ordine dei passi la derivazione si scrive in verticale. Il numero a sinistra di ciascuna formula indicala posizione che essa occupa nella sequenza, quindi può essere usato per riferirsi alla formula stessa. L'annotazione che compare a destra nella terza riga indica che 3 è ricavata da 1 e 2 mediante MP. Nel caso di 1 e 2 non c'è annotazione, perché si tratta di

assunzioni. Per indicare la derivabilità in S si usa il simbolo ~·Ad esempio, per dire chePb è derivabile in S da{Pa,Pa--:JPb} si scrivePa,Pa--:JPb ~Pb. Come nel caso del simbolo f=, anche in questo caso non è necessario usare le parentesi graffe per indicare l'insieme di formule a sinistra del simbolo. In generale, si può sempre derivare una formula f3 da due formule a e a --:J f3 in virtù della regola MP. Quindi, per due formule

qualsiasi a e f3 vale quanto segue:

Lemma 6 a, a--:J f3 ~ f3

Anche una dimostrazione in S può essere definita sulla base dell' appa­rato deduttivo di S nel modo illustrato nel paragrafo i.2:

Definizione 11 Una dimostrazione di a è una sequenza finita di formu­le che termina con a ciascuna delle quali esemplifìcaAJ-A7 o è ricavata per mezzo di MP da formule che la precedono.

La sequenza di formule equivale a una sequenza di passi, cioè i passi che costituiscono il ragionamento mediante il quale si giustifica a in S. Ecco un esempio: .

1. Px--:J ((Px--:JPx)--:JPx) Al 2. (Px--:J((Px--:JPx)--:JPx))--:J((Px--:J(Px--:JPx))--:J(Px--:JPx)) A2 3. (Px--:J (Px--:JPx))--:J (Px--:JPx) l, 2MP

49

4. Px~ (Px~Px) 5. Px~Px

Al 3,4MP

Come una derivazione, una dimostrazione si scrive in verticale con numerazione progressiva sulla sinistra e annotazioni sulla destra. L'unica differenza consiste nel fatto che una dimostrazione non può contenere assunzioni, quindi ogni riga include un'annotazione. Il simbolo che si usa per indicare la dimostrabilità in S è lo stesso. Ad esempio, per dire chePx ~ Px è dimostrabile in S si scrive 1-Px ~ Px. Una formula dimostrabile è un teorema. Quindi si può dire che Px ~ Px è teorema di S. In generale, come risulta chiaro dalla dimostrazione considerata, per qualsiasi formula a vale quanto segue:

Lemma 7 I- a~ a

DIO e DII hanno qualcosa in comune con D7 e D8. DIO si fonda sull'idea che, se un enunciato a è derivabile da un insieme di enuncia­ti f, allora c'è un insieme di argomenti deduttivamente validi che hanno in comune la forma f i a. Ad esempio, V x(Px ~ Qx ), Pa I-Qa. Infatti:

1. Vx(Px~0) 2. Pa 3. V x(Px~ Qx) ~ (Pa ~ Qa) A4 4. Pa~Q_f, 1,3MP s. Q_f, 2,4MP

Questo rende conto della correttezza dell'argomento "Ogni balena è bianca, Moby Dick è una balena; Mo by Dick è bianca': In generale, la relazione di derivabilità in Sfornisce una caratterizzazione di un insie­me di argomenti deduttivamente validi che hanno una forma esprimi­bile in L. Il caso della dimostrabilità è analogo. L'idea alla base di D 11 è che un enunciato dimostrabile esprima la forma di un insieme di enunciati veri di una lingua naturale. Se I- a, allora c'è un insieme di enunciati

50

veri che hanno in comune la forma a. Un esempio di teorema di S è V x(Px ~Px), che rappresenta enunciati come "Ogni cosa bianca è bianca''. Per rendersi conto che 1- V x(Px ~ Px) è sufficiente riconosce­re che vale quanto segue:

Lemma 8 Se I- a, allora I- V xa.

Dimostrazione L8 si dimostra per induzione sulla lunghezza della dimostrazione di a, cioè sul numero di passi che include. A differenza che nel caso della complessità delle formule, qui l'induzione parte da 1, non essendoci dimostr~zioni di lunghezza O. Base. Assumiamo che esista una dimostrazione di a di lunghezza 1. In questo caso a è un assioma, quindi per A7 anche V xa è un assioma. Ne risulta che I- V xa. Passo. Assumiamo come ipotesi di induzione che, per ogni numero minore o uguale a n, se esiste una dimostràzione di a di lunghezza n, allora esiste una dimostrazione di V xa. Supponiamo ora che esista una dimostrazione di a di lunghezza n + 1. I casi possibili sono due. Caso 1: a è un assioma. In questo caso I- V xa, come risulta dalla base. Caso 2: a è ottenuta per MP da due formule f3 e f3 ~ a che la precedo­no. Siccome f3 e f3 ~ a sono teoremi la cui dimostrazione deve.avere lunghezza minore o uguale a n, per ipotesi di induzione si ottiene:

1. I- V xf3 2. I- V x(f3~ a)

DaA6 risulta pure che:

In virtù della regola MP, da 2 e 3 si ottiene:

Da 1e4 si ottiene:

51

S. I- 'v' xa o

Ora risulta chiaro che I- 'v' x(Px:::) Px). Infatti, basta mettere insieme L8 e il fatto già assodato che I-Px:::) Px. In generale, l'insieme degli enunciati che sono teoremi di S fornisce una caratterizzazione di un insieme di verità logiche che hanno una forma esprimibile in L.

Esercizio 4 Spiegare perché vale quanto segue:

Lemma 9 al-a

Lemma 10 Se f I- a, allora f U t:,. I- a.

Lemma 11 Se a, 13 l-Y e a, y l-3, allora a, /3 l-3.

Lemma 12 Se f I- a e f I- a:::) f3, allora f I- f3.

Lemma 13 Se I- a, allora f I- a.

Lemma 14 f 1-asseceunsottoinsiemefinito !::,. di_f tale che t:,. !-a.

3.3. Coerenza La contraddittorietà è intesa come una relazione semantica a livello informale (si veda PAR. 1.5). Ma può essere rappre­sentata sintatticamente in un linguaggio che contenga, per ogni formula a, una formula che esprime la negazione di a. L è appunto un linguaggio del genere, poiché contiene "'. Questo permette di defini­re in termini sintattici una proprietà, la coerenza, che pure è intesa in termini semantici a livello informale. Dire che un insieme di enuncia­ti è coerente significa dire che è possibile che tutti gli enunciati dell'in­sieme siano veri. Ad esempio, l'insieme formato da "La neve è bianca'' e "Il mare non è blu" è coerente. Invece, l'insieme formato da "La neve non è bianca'' e "La neve è bianca e il mare non è blu" è incoerente. La differenza tra un insieme coerente e un insieme incoerente consiste nel fatto che un insieme coerente non implica contraddizioni. Questo risulta ovvio se si pensa ai due esempi considerati. Pertanto, la coeren-

52

za di un insieme di formule r può essere definita in modo sintattico se "implica'' è inteso in termini di derivabilità.

Definizione 12 f e coerente in S sse per nessuna formula a si da il caso

che r 1-s a e r h"' a.

Qui 1-s indica la derivabilità in un sistema qualsiasi S. In generale, il simbolo I- sarà accompagnato da un indice ogni volta che si parlerà di

sistemi senza dare per scontato S. La coerenza può essere attribuita a un intero sistema, invece che a UI}

insieme di formule del s~o linguaggio. Dato un sistema S il cui linguag­gio contenga"', la coerenza di S è definita come segue: ·

Definizione 13 Se coerente sse per nessuna formula a, 1-s a e h"' a.

A volte si usa il termine "coerente" per qualificare un sistema in cu~ non tutte le formule sono teoremi. Questo uso può risultare poco familiare. Ma in realtà la coerenza così intesa equivale alla proprietà definita in D 13, se il sistema soddisfa due requisiti minimi. Uno è quello considerato, doè che il linguaggio contenga "'. L'altro è che qualsiasi formula sia derivabile da {a, "' a}. Per un sistema S che spddi­sfi il primo requisito vale il seguente condizionale: se S è coerente, allora qualche formula non è teorema di S. Supponiamo infatti che S sia coerente. Allora, data qualsiasi formula a, a e "' a non sono entrambe dimostrabili in S, quindi almeno una delle due non è teore­ma di S. Per un sistema S che soddisfi il secondo requisito vale il condizionale inverso: se qualche formula non è teorema di S, allora S è coerente. Supponiamo infatti che S non sia coerente. Allora per qualche formula a, 1-s a e 1-s"' a. Ma {a, "' a} permette di derivare qualsiasi formula, pertanto qualsiasi formula è teorema di S. Dunque, un sistema S che soddisfi entrambi i requisiti è coerente sse qualche

formula non è teorema di S.

3.4. Teorema di coerenza Ora si dimostrerà che S è un sistema coerente. Per farlo, si dimostrerà prima che tutti i teoremi di S sono

53

validi, ragionando su ogni singolo assioma. La coerenza di S può esse­re facilmente ricavata da questo risultato:

Lemma 15 Ognifonnula a:J (f3:J a) e valida.

Dimostrazione Si consideri unaformula a:J (f3:J a). Date una strut­tura qualsiasi e un'assegnazione qualsiasi, ciascuna delle due formule a e f3 è soddisfatta o non soddisfatta dall'assegnazione. Quindi è suffi­ciente considerare quattro casi: a e f3 sono entrambe soddisfatte, solo a è soddisfatta, solo f3 è soddisfatta, nessuna delle due è soddisfatta. In ciascuno di questi casi, a :J (/3 :J a) risulta soddisfatta.

D Lemma 16 Ognifonnula ( a:J (/3:Jy)) :J ((a:J /3) :J ( a:Jy)) e valida.

Dimostrazione Come nel caso di LI 5, basta considerare le possibili combinazioni di soddisfacimento e non soddisfacimento per le formule alle quali si riferiscono le variabili metalinguistiche in A2.

Lemma 17 Ognifonnula ( ~ a:J~ /3) :J (/3:J a) e valida.

Dimostrazione Come per LI 5 e LI 6. D

Lemma 18 Sia t un tennine sostituibile a una variabile x in una fonnu­la a. Data un'assegnazione vin una struttura .A: e una x-variante v' di v tale che [x].A,u• [t].A,u' vsoddisfa a(t/x) sse v' soddisfa a.

Dimostrazione Ll8 si dimostra per induzione sulla complessità di a, assumendo che t sia sostituibile ax in a e che v' sia unax-variante di

vtaleche [x].A,u•= [t].A,u' Base. Assumiamo che a sia una formula atomica Ptl' .. ., tn. Per ogni i tale che 1 ~i~ n, sia t'.il risultato della sostituzione in t. dix con t.

l l

Questo significa che vsoddisfa a(t/x) sse ([t~].A,u' .. ., [<J.A:,) E [P]A e v' soddisfa asse ([t1].A,u•' .. ., [tn].A,u•) E [P]A. Siccome [t;J.A:,u = [tJ.A,u•' v soddisfa a(tlx) sse v1 soddisfa a. Passo. Assumiamo che il bicondizionale da dimostrare valga per tutte

54

le formule di complessità minore o uguale a n e che a sia una formula di complessità n + 1. Caso 1: a ha la forma~ {3. In questo caso tè sostituibile a x in /3 e a(tlx) = ~{3(tlx). v soddisfa a(tlx) sse non soddisfa /3(t/x). Per ipotesi di induzione, v non soddisfa /3(tl x) sse v' non soddisfa {3. Ma v' non soddisfa f3 sse v' soddisfa a. Quindi v soddisfa a(tl x) sse v' soddisfa a. Caso2: ahalaformaf3:J y. In questo caso tè sostituibile axsiain {3sia in y e a(tlx) f3(tlx) :J y(t/x). v soddisfa a(tlx) sse non soddisfa f3(tl x) o soddisfa y(tl x ). Per ipotesi di induzione, v non soddisfa /3(tl x) sse v' non soddisfa f3 e 1! soddisfa y(tl x) sse v' soddisfa y. Ma v' soddi­sfa asse non soddisfa f3 o soddisfa y. Quindi v soddisfa a(tl x) sse v' soddisfa a. Caso 3: a ha la forma 'ef y/3. In questo caso tè sostitubile a x in /3 e a(t/x) = 'ef y{3(tlx). Supponiamo chexsialiberain a, quindichex:;t:y. v soddisfa 'ef y/3(tl x) sse ogni y-variante div soddisfa /3(tl x ). Peri pote­si di induzione, una y-variante v. div soddisfa /3(tl x) sse unax-varian­te v~ di v. tale che [ x ]A = [t] ,, soddisfa {3. Siccome v~ è una y-

.v'* .n;,V*

variante di v 1, si ottiene che una y-variante di vsoddisfa{3(tlx) sse una

y-variante div' soddisfa {3. Quindi v soddisfa a(tlx) sse v' soddisfa a. Supponiamo ora che x non sia libera in a. Allora o x non occorre in a o x è vincolata in a, cioè x = y. In entrambi i casi, a(tl x) = a e per L2 v soddisfa asse v' soddisfa a.

Lemma 19 Ogni formula 'ef xa:J a(tlx), contsostituibileaxin a, e valida.

Dimostrazione Siat sostituibile ax in a. Assumiamo che in una strut­tura .A: un'assegnazione v soddisfi 'ef xa. Allora unax-variante v' div tale che [x].A,u• = [t].A,usoddisfa a. MadaLI8 risulta che v' soddisfa a sse v soddisfa a(tlx). Quindi, v soddisfa a(tlx).

o Lemma 20 Ogni fonnula a :J 'ef xa, con x non libera in a, e valida.

Dimostrazione Assumiamo che x non sia libera in a e che v soddi-

55

sfi a. Per ognix-variante v' div, da L2 risulta che v' soddisfa a. Quin­di v soddisfa V xa.

D Lemma 21 Ogni formula V x( a~ f3) ~ (V xa ~ \;/ xf3) e valida.

Dimostrazione Assumiamo che v soddisfi \;/ x( a~ {3) e \;/ xa. Ne risulta che ognix-variante div soddisfa a~ {3 e a. Da LS si ottiene che ognix-variante div soddisfa {3. Quindi, v soddisfa\;/ x{3.

D Lemma 22 Se una formula a e valida, allora V xa e valida.

~imostrazione Se a è soddisfatta da tutte le assegnazioni in una struttura À, anche V xa è soddisfatta da tutte le assegnazioni in A.

D Lemma 23 Se f- a, allora != a.

Dimostrazione Da Ll5-LI7 e LI9-L22 risulta che tutte le formule che esemplificano AI-A7 sono valide. A questo si aggiunge che MP preserva la validità. Infatti, da LS risulta che, se a e a~ {3 sono valide, anche f3 è valida. Siccome ogni teorema di S è otten.uto mediante AI­A7 e MP, ogni teorema di S è valido.

D Teorema 1 Se coerente.

Dimostrazione Da D4 e D8 risulta che, se != a, allora non si dà il caso che !=~ a. Quindi si può ragionare come segue. Supponiamo che f- a. Per L23 ne consegue che != a. Ma allora non si dà il caso che !=~ a. Quindi, sempre per L23, non si dà il caso che f-~ a.

D Esercizio 5 Nella base della dimostrazione di LI8 si asserisce che in una formula atomicaPt1, •• ., t

11 in cui tè sostituibile ax, per ogni i tale

che I:::;; i:::;; n risulta che [t~]A,v = [tJA.v'' dove t'è il risultato dellasosti­tuzione in t; dix con te v'è unax-variante di vtale che [x]A.v' = [t]A.v' Dimostrare questa asserzione per via induttiva.

56

Soluzioni degli esercizi

1. No. Non può essere un assioma di S, perché non è una formula di L. Si tratta piuttosto di uno schema di assioma. 2. 1. Nel caso in cui a sia atomica, sex occorre in a allora a(tl x) è ottenuta sostituendo t ax, altrimenti a(t/ x) = a;

2. (~ a)(tlx) =~ (a(tlx)); 3. (a~ {3)(tlx) a(tlx) ~ f3(tlx); 4. (Vya)(tlx) = Vy(a(tlx)) sex:;t: y, altrimenti (Vya)(tlx) Vya.

3. Assumiamo che v. soddisfi a~ {3. Allora v non soddisfa a o soddisfa {3. Assumiamo ora che soddisfi a. Ne consegue che soddi­sfa {3. 4. L9. Data una formula a, la sequenza che contiene a come unico termine è una derivazione di a dall'insieme {a}. LI O. Se esiste una sequenza di formule che è una derivazione di a da f, quella stessa sequenza di formule è anche una derivazione di a da un insieme qualsiasi di cui r è sottoinsieme. Quindi è una derivazione di adaf U/J... Ll 1. Sia duna derivazione dir da a e {3 e sia d'una derivazione di 3 da a e r. Se si tolgono ad' le assunzioni a e r e si aggiunge la parte rima­nente di d' ad, si ottiene una derivazione che include a e {3 come assun­zioni e termina con 3. Ll 2. Se r f- a e r f- a~ {3 allora si può costruire una derivazione dar che contiene a e a~ {3 e che termina con {3. Infatti, {3 può essere ricava­ta dalle prime due formule applicando MP. L13. Ogni dimostrazione di una formula a è una derivazione di a da qualsiasi insieme di formule. Si noti che, come per L4, nel caso in cui r = 0 risulta che f- asse r f- a. LI 4. Per definizione, una derivazione è una sequenza finita di formu­le. Quindi, se c'è una derivazione di a da f, allora c'è una derivazione di a da un sottoinsieme finito /J.. dir. Inversamente, se c'è una deriva­zione di a da un sottoinsieme finito /J.. dir, allora per Ll O c'è una deri­vazione di a dar. 5. L'induzione è sulla complessità di t,. come nella dimostrazione di LI.

57

Base. Assumiamo che ti sia un termine di complessità O. Caso 1: ti è una costante individuale. In questo caso [t'JA,v = [tJA,v•' poiché t'. = t. e la denotazione di t. è la stessa in ve v'. ·

t t t

Caso 2: t. è una variabile. In questo caso t. = x o t. * x. Set.= x, allora l l l l

t'.=tev' assegna[t] À. axJ1 uindi[t'.] À. = [t.] À. .Set.-:t:x,allorat'. t. l ..n,V ~ l .n;,V t .n;,V' l l l

e v' assegna a t)o stesso valore che gli assegna v, dunque [<J A, v = [tJ A, v•· Passo. Assumiamo che l'uguaglianza da dimostrare valga per qualsiasi termine di complessità minore o uguale a n e che ti sia un termine di complessità n + 1. In questo caso t.ha la formaft

1, ••• , t , mentre t'. è

z m z

dt . d . '''.ft' 'M. ottenuto a . sost1tuen o t ax m t1, ••• , t , eroe t. =

1, ••• , t . a sicco-

' m t m me, per ogni k tale che I ::;; k ::;; m, tk ha al massimo complessità n, per !potesi di induzione [t~]A,v = [tk]A,v•· Se a questo si aggiunge che la funzione assegnata a/è la stessa, si ottiene che (fa~, ... , t:JA,v [fil' ... , tm]A,v•"

58

4. Alcune proprietà sintattiche di S

4.1. Teorema di deduzione Sia f, a un'abbreviazione dir U {a}. Il seguente teorema, chiamato teorema di deduzione, esprime una proprietà sintattica di S:

Teorema 2 Se f, a I- {3, allora f I- a:) f3.

Un teorema di questo tipo è stato dimostrato per la prima volta da Jacques Herbrand ( l 90?-1931 ). Tarski è arrivato allo stesso risultato seguendo un percorso indipendente.

Dimostrazione T2 si dimostra per induzione sulla lunghezza della derivazione di f3 da f, a, cioè sul numero di passi che include. Come nel caso della lunghezza di una dimostrazione, in questo caso l'induzione parte da 1. Base. Assumiamo che esista una derivazione di /3 da f, a di lunghezza 1. I casi possibili sono tre. Caso 1: /3 è un assioma. In questo caso esiste una derivazione di a:) /3 da f:

1. /3 2. /3:) (a:) /3) 3. a:) f3

Al l,2MP

Caso 2: /3 E f. In questo caso esiste una derivazione di a:) /3 da f, cioè la stessa considerata nel caso 1. Caso 3: f3 a. In questo caso a:) f3 =a:) a. Per L7 e L13 esiste una derivazione di a:) a dar. Passo. Assumiamo che il condizionale da dimostrare valga per tutte le derivazioni di lunghezza minore o uguale a ne che esista una derivazio­ne di f3 da f, a di lunghezza n + 1. I casi possibili sono quattro. I primi tre sono quelli già trattati nella base, il quarto è il caso in cui /3 è conse­guenza diretta di due formule 'Y e 'Y:) f3. Si consideri dunque il quarto caso. Dato che 'Y precede {3, esiste una derivazione di 'Y da f, a che ha al

59

massimo lunghezza n. Allo stesso modo, dato che r :::J /3 precede f3, . esiste una derivazione dir :::J /3 dar, a che ha al massimo lunghezza n.

Per ipotesi di induzione, quindi,

1. n-a:::J r 2. r ~a:::J (y:::J /3)

A questo possiamo aggiungere che da A2 risulta:

3. ~ ( a:::J (y:::J /3)) :::J (( a:::Jy) :::J ( a:::J /3))

Ma se vale 3, allora per L13 vale anche:

4. r ~ (a :::J ( r :::J /3)) :::J ( (a :::Jr) :::J (a :::J /3))

Da 2, 4e112 risulta:

s. r~(a:::Jy):::J(a:::Jf3)

Sempre per Ll2, da I e S si ottiene:

6. r ~a:::Jf3

D Nota Il condizionale inverso di T2 è ovviamente vero: se f ~ a :::J f3, allora si può derivare /3 da f, a usando MP. Quindi, risulta chef, a~ f3 ssef ~a:::J f3.

Esercizio 1 Dimostrare il seguente lemma usando T2:

Lemma24 a::Jf3,f3::Jy~a::Jy

4.2. Pseudo Scoto llteoremadideduzionepermettedidimostrare risultati di grande interesse. Per apprezzarne l'importanza, occorre innan­zitutto riconoscere che sulla base di T2 si possono giustificare alcuni te~rerni sulla sintassi di S che esprimono principi fondamentali dellalogi-

60

ca classica. Successivamente, si vedrà che T2 e questi teoremi possono essere impiegati per stabilire risultati ulteriori di maggiore complessità . L24 permette di dimostrare il seguente lemma:

Lemma25 ~~a:::J(a:::Jf3)

Dimostrazione 1. ~~ a:::J (~ f3::J~ a) 2. ~ ( ~ f3 ::J~ a) :::J (a :::J /3) 3. ~~ a:::J (a:::J /3)

Al

A3 l,2L24

D Si noti che questa non è una dimostrazione in S, sebbene la sua veste grafica possa indurre a pensare al contrario. È una dimostrazione su S, in quanto verte sulla dimostrabilità in S di tutte le formule della forma ~ a :::J (a :::J /3). Non bisogna lasciarsi fuorviare dalle annotazioni che compaiono sulla destra. Ad esempio, l'annotazione nella riga I non indica che una certa formula di L è un assioma in quanto esemplifica Al (di fatto non c'è nessuna formula di L nella riga I), ma piuttosto che qualsiasi formula della forma Al è un assioma di S. Le dimostrazioni che seguono sono simili. Sulla base di L25 si può dimostrare il seguente teorema:

Teorema 3 a, ~ a ~ f3

Dimostrazione 1. a~a L9 2. ~a~~a L9 3. a,~a~a ILIO 4. a,~a~~a 2110 s. ~~ a:::J (a::Jf3) L25 6. a,~a~~a::J(a::Jf3) 5113 7. a,~a~a::Jf3 4,6Ll2

8. a,~a~/3 3, 7Ll2 D

T3 esprime la legge dello Pseudo Scoto, secondo cui una contraddizio-

61

ne implka qualsiasi cosa. Nella tradizione scolastica questa legge era nota come ex contradictione sequitur quodlibet.

Esercizio 2 Spiegare perché S è coerente sse qualche formula non è teorema di S.

4.3. Doppia negazione Sulla base di L24 e L25 si dimostra una proprietà della negazione:

Teorema 4 f-~~ a:J a

Dimostrazione -i. f-~~ a:J ( ~ a:J~~~ a) 2. f-(~a:J~~~a):J(~~a:Ja) 3. f-~~ a:J ( ~~ a:J a) 4. f-(~~ a:J(~~ a:Ja)):J((~~ a:J~~a):J(~~ a:Ja)) S. f-(~~a:J~~a):J(~~a:Ja) 6. f-~~ a:J~~ a 7. f-~~ a:Ja

Teorema 5 f- a:J~~ a

Dimostrazione 1. f-~~~ a:J~ a 2. f-(~~~a:J~a):J(a:J~~a)

3. f-a:J~~ a

L25 A3 l,2L24 A2 3,4Ll2 L7 5,6Ll2

D

T4 A3 l,2Ll2

D Dunque a e~~ a sono interderivabili. L'idea espressa da T 4 e TS è che una doppia negazione equivalga a un'affermazione. Questo risulta chiaro se si pensa che la logica classica si fonda sul principio di biva­lenza. Supponiamo che sia vero l'enunciato "Non si dà il caso che la neve non sia bianca''. Allora "La neve è bianca'' non può essere falso. Se lo fosse, infatti, "La neve non è bianca'' sarebbe vero. Per il principio di bivalenza, l'unica opzione rimanente è che "La neve è bianca'' sia vero. Il ragionamento nella direzione inversa è analogo.

62

Sulla base di T 4 e TS si dimostra invece il seguente lemma, che può esse­re considerato una variante di L6, dato che ~~ a equivale a a e ~~ /3 equivale a /3:

Lemma 26 ~~a, a:J f3 f-~~ /3

Dimostrazione 1. ~~a

2. a:Jf3 3. f-~~a:Ja

4. a s. /3 6. f-f3:J~~ /3 7. ~~ /3

Esercizio 3 Dimostrare il seguente lemma usando L26:

Lemma 27 f-( a:J /3) :J ( ~~ a:J~~ /3)

T4 l,3MP 2,4MP TS 5,6MP

D

Si noti che L27, come L26, presuppone l'equivalenza di una formula con la sua doppia negazione. Per rendersene conto basta riflette!e sul fatto che L7 implica f- (a :J /3) :J (a :J /3), e che sostituendo a con ~~a e f3 con~~ f3 si ottiene L27.

4.4. Contrapposizione DaL27 si ottiene il seguente teorema:

Teorema 6 f-( a:J /3) :J ( ~ f3:J~ a)

Dimostrazione I. f-( a:J /3) :J (~~ a:J~~ /3) 2. f-( ~~ a:J~~ /3) :J (~ f3:J~ a) 3. f-( a:J /3) :J ( ~ f3:J~ a)

T6 esprime un principio fondamentale:

L27 A3 l,2L24

D

Principio di contrapposizione Ogni condizionale implica il condi­zionale che ha come antecedente la negazione del suo conseguente e come conseguente la negazione del suo antecedente.

T 6 può essere considerato una variante di A3. Infatti, ( a::J {3) ::J ( ~ {3::J~ a) si ottiene da ( ~~ a::J~~ {3) ::J ( ~ {3::J~ a), che risultadaA3, sostituendo ~~ a con a e~~ f3 con {3. Lo stesso vale per il seguente teorema:

Dimostrazione 1. ~~ a::J a, a::J~ f3 f-~~ a::J~ f3 2. f-( ~N a::J~ {3) ::J ({3::J~ a) 3. ~~ a::J a, a::J~ f3 f-[3::J~ a 4. ~~ a::J a f-( a::J~ {3) ::J (f3::J~ a) S. f- ( ~~ a::J a) ::J ( ( a::J~ {3) ::J ({3::J~ a)) 6. f-~~ a::J a 7. f-( a::J~ {3) ::J ({3::J~ a)

L24 A3 l,2Ll2 3T2 4T2 T4 S,6Ll2

D Per vedere che T7, come T 6, è una variante di A3 si oss.ervi che ( a::J~ {3) ::J ({3::J~ a) si ottiene da ( ~~ a::J~ {3) ::J ({3::J~ a), cherisultadaA3, sosti­tuendo ~~ a con a. Il principio di contrapposizione, espresso in forme diverse daA3, T6 e T7, costituisce uno strumento dimostrativo importante nella teoria della logica. Ad esempio, fa leva su questo principio il ragionamento mediante il quale TI è stato dimostrato a partire daL23. In generale, vi sono casi in cui un condizionale non può essere facilmente dimostra­to per via diretta, cioè assumendo il suo antecedente e ricavando il suo conseguente. In alcuni di questi casi il condizionale può essere dimo­strato per via indiretta, cioè assumendo la negazione del suo conse­guente e ricavando la negazione del suo antecedente.

Esercizio 4 Applicando due volte T2 a L6 si ottiene che ogni formu­la a ::J ( (a ::J f3) ::J {3) è un teorema. Sulla base di questo fatto si può dimostrare il seguente lemma, usando prima T6 e poi L24:

64

Formulare la dimostrazione.

4.5. Riduzione all'assurdo S si conforma al principio della riduzio­ne all'assurdo. Per rendersene conto, occorre prima considerare trelemmi.

Lemma 29 f-( ~ a::J a) ::J (f3::J a)

Dimostrazione 1. f- ~ a ::J (a ::J~ f3) . L25 2. f-( ~ a::J (a::J~ {3)) ::J (( ~ a::J a) ::J ( ~ a::J~ {3)) 3. f-(~a::Ja)::J(~a::J~{3)

4. f-( ~ a::J~ {3) ::J (f3::J a) 5. f-( ~ a::J a) ::J (f3::J a)

A2 l,2Ll2 A3 3,4L24

D Lemma 30 f-( ~ a::J a) ::J a

Dimostrazione 1. f-(~a::Ja)::J((~a::Ja)::Ja) L29 2. f- ( ( ~ a ::J a) ::J ( (~ a ::J a) ::J a)) ::J ( ( ( ~ a ::J a) ::J ( ~ a ::J a)) ::J ((~a::Ja)::Ja)) A2 3. f-((~a::Ja)::J(~a::Ja))::J((~a::Ja)::Ja) l,2Ll2 4. f-( ~ a::J a) ::J (~ a::J a) L7 5. f-(~a::Ja)::Ja 3,4Ll2

Dimostrazione 1. ( a::J~ a) ::J ( ~~ a::J~ a), ( ~~ a::J~ a) ::J~ a f- ( a::J~ a) ::J~ a

L24

D

2. ( a::J~ a) ::J ( ~~ a::J~ a) f-(( ~~ a::J~ a) ::J~ a) ::J (( a::J~ a) ::J~ a) 1T2

3. f- ((a ::J~ a) ::J (~~a ::J~ a)) ::J (((~~a ::J~ a) ::J~ a) ::J ((a::J~ a) ::J~ a)) 2T2

65

4. f-( a::J~ a) ::J ( ~~ a::J~ a) S. f-(( ~~ a::J~ a) ::J~ a) ::J ((a::J~ a) ::J~ a) 6. f-( ~~ a::J~ a) ::J~ a 7. f-( a::J~ a) ::J~ a

Teorema 8 I- (a ::J /)) ::J ( (a ::J~ /)) ::J~ a)

Dimostrazione 1. a ::J~ /3 I- a ::J~ f3 2. a ::J f3, a ::J~ /31- a ::J~ f3 3. f-( a::J~ /3) ::J (f3::J~ a) 4. a ::J f3, a ::J~ /3 I- f3 ::J~ a S. a::J {3, f3::J~ a I- a::J~ a 6. f-( a::J~ a) ::J~ a 7. a::J f3, f3::J~ a f-~ a 8. a::J {3, a::J~ [3 f-~ a 9. a::J /3 f-(a::J~ /3) ::J~ a

10. f-(a::J /3) ::J ((a::J~ /3) ::J~ a)

T6 3,4.Ll2 L30 S,6Ll2

D

L9 1 LlO T7 2,3Ll2 L24 L31 S,6Ll2 4, 7Lll 8T2 9T2

D T8 esprime il primo dei due tipi di ragionamento c~msiderati nel para­grafo i.5: se a implica f3 e~ {3, allora si ottiene~ a. Per esprimere il secondo, invece, occorre il seguente teorema:

Se~ a implica f3 e~ {3, allora si ottiene a. Nel paragrafo 1. 5 si è visto che i due tipi di ragionamento risultano equivalenti se si assume che~~ a equivalga a a. Dato che S garantisce questa assunzione, come mostra il paragrafo 4.3, anche T9 è dimostrabile.

Esercizio 5 Dimostrare T9 tenendo presente la dimostrazione di T8.

66

Soluzioni degli esercizi

1. y è derivabile dall'insieme { a::J f3, f3::Jy, a}: 1. a 2. a::J f3 3. /3 1, 2MP 4. f3::Jy S. y 3,4MP

Quindi a ::J {3, f3 ::J y, a f-y. Da questo e T2 si ottiene L24. 2. S soddisfa i due requisiti considerati nel paragrafo 3.3: il primo perché L contiene~, il S<:condo perché vale T3. 3. L27 si ottiene da L26 applicando due volte T2. 4. 1. a, a::J /3 l-/3 L6

2. a I- (a ::J /3) ::J f3 1 T2 3. f-a::J ((a::J /3) ::J /3) 2 T2 4. I- ( ( a::J /3) ::J /3) ::J (~ f3::J~ ( a::J /3)) T6 S. I- a::J ( ~ {3::J~ ( a::J /3)) 3, 4 L24

5. La prima parte è come la dimostrazione di T8 fino alla riga 8, ma con~ a al posto di a. Quindi, si ottiene:

A questo si aggiunge che, in base a T 4:

Quindi, per Ll2 si ottiene:

Applicando due volte T2 si ottiene:

I- ( ~ a ::J /3) ::J ( ( ~ a ::J~ /3) ::J a)

67

5. S e le sue estensioni

5.1. Linguaggi del prim'ordine Il vocabolario di L può essere ampliato o ristretto in vari modi. Si possono aggiungere costanti indi­viduali, costanti predicative, simboli di funzione, o definire altri connettivi. I connettivi A, ve=, che stanno per "e", "o" e "se e solo se", sono definiti in termini di ~ e ::J: a A f3 equivale a~ (a ::J~ {3), a V f3 equivale a~ a::J f3e a= {3equivale a~ ((a::J {3) ::J~ (f3::J a)). Analoga­mente, il quantificatore esistenziale 3 può essere introdotto stipulando che 3xa equivalga a~ "i/ x ~ a. Così come alcuni simboli possono esse­_re aggiunti, altri possono essere sottratti: le costanti predicative posso­no essere ridotte, le costanti individuali e i simboli di funzione posso­no essere eliminati in parte o del tutto. Ciascuna delle modifiche considerate può essere motivata da qualche ragione. Mentre le aggiunte rispondono all'esigenza di aumentare le capacità espressive del linguaggio, le sottrazioni permettono di evita­re di usare simboli che risultano superflui rispetto agli scopi che il linguaggio intende soddisfare. Per semplificare, chiamiamo variante di L un linguaggio ottenuto da L mediante una o p~ù delle modifiche considerate, assumendo che l'insieme dei simboli aggiunti, se non è vuoto, sia finito o numerabile. Un esempio piuttosto semplice di variante di L è il linguaggio che si ottiene aggiungendo al vocabolario di L, oltre a A, V e 3, il simbolo=. Chiamiamo Lid questa variante. Il simbolo= è una costante predicati­va a due posti che permette di esprimere la relazione di identità. Altri esempi di variante di L sono i linguaggi che contengono simboli arit­metici. Sia LAI il linguaggio ottenuto da Lid togliendo le costanti indi­viduali, le costanti predicative (tranne = ), i simboli di funzione e aggiungendo la costante individuale O, il simbolo di funzione a un posto s - che sta per "successore" - e il simbolo di funzione a due posti +. Sia L A2 il linguaggio ottenuto aggiungendo al vocabolario di LAI il simbolo di funzione a due posti .. Varianti di L ancora più ricche di simboli aritmetici possono essere costruite in modo analogo. Le le sue varianti sono linguaggi del prim'ordine, cioè linguaggi le cui

68

uniche variabili sono variabili individuali che si riferiscono a oggetti. I linguaggi di ordine superiore contengono, oltre alle variabili di questo tipo, variabili predicative che si riferiscono a proprietà, altre variabili che si riferiscono a proprietà di proprietà e così via.

Nota Normalmente, per semplificare l'uso dei simboli=, + e ., si inse­riscono i simboli stessi tra i rispettivi termini. Ad esempio, invece di scrivere =xy si scrivex = y. Analogamente, si scrivex :;t: y invece di ~=xy. Lo stesso vale per+ xy e· xy, che sono sostituiti dax+ y ex ·y. Qui si adot­terà la stessa convenzione.

Esercizio 1 Tradurre in Lid "Ogni cosa è identica a sé stessa".

Esercizio 2 Tradurre in Lid "Esistono almeno due oggetti".

Esercizio 3 Tradurre in Lid "Esistono esattamente due oggetti".

5.2. Teorie del prim'ordine Dato che L è un linguaggio del prim'ordine, S è un sistema del prim'ordine. Lo stesso vale per qualsiasi sistema in L, o in qualche variante di L, che abbia le stesse proprietà sintattiche fondamentali di S. Normalmente, quando si parla di logi­ca del prim'ordine si fa riferimento a un sistema del prim'ordine. Un sistema del prim'ordine può essere parte di un sistema più ampio. Infatti, gli assiomi di un sistema del prim'ordine possono essere combi­nati con altri assiomi che esprimono verità di qualsiasi tipo. Dati un sistema S e un insieme f di formule del linguaggio di S, chiamiamo S + f il sistema che si Ottiene aggiungendo le formule in f a S come assiomi. In questo caso ogni teorema di s è teorema di s + r. In generale, dato un sistema S, si chiama estensione di S un sistema S' tale che tutti i teoremi di S sono teoremi di S'. L'importanza della logica del prim'ordine risiede non solo nelle conseguenze che si posso­no trarre sulla base di un sistema del prim'ordine preso isolatamente, ma anche in quelle generate dalle estensioni di tale sistema. Quindi, invece di ragionare in termini di S, è opportuno ragionare in termini di estensioni di S. La seguente definizione risponde a questa esigenza:

69

Definizione 14 Una teoria del prim'ordine è un sistema che soddisfa le

seguenti condizioni: 1. il suo linguaggio è Lo una variante diL; 2. l'insieme dei suoi assiomi è l'unione dell'insieme delle formule che esemplificano Al -A7 e un insieme finito o numerabile di fonnule chiuse; 3. la sua unica regola di inferenza è MP.

D'ora in poi "teoria del prim'ordine" sarà abbreviato con "teorià' e la variabile T sarà usata per indicare una qualsiasi teoria del prim'ordine. Gli assiomi aggiuntivi che una teoria può includere sono chiamati propri, in quanto dipendono dalla materia specifica sulla quale verte la teoria. Un esempio di sistema che soddisfa D 14 è la teoria dell'identita, detta anche "logica del prim'ordine con identità". Questo sistema è una teoria in Lid ottenuta aggiungendo ad Al-A7 i seguenti assiomi propri:

AB \i x(x=x) Ag \ix \i y(x = y ::J (a ::J a')), se a' differisce da a al massimo in quan­to J sostituisce X in qualche occorrenza libera.

A8 è un assioma che enuncia il fatto considerato nell'esercizio 5.1:

ogni cosa è identica a sé stessa. A9, invece, è uno schema di assioma che esprime la legge dell' indiscernibilità degli identici: sex è identico a y, allora tutto ciò che si può dire dix si può dire di y.

Un altro esempio è l'aritmetica di Presburger, che prende il nome da Mojzesz Presburger ( 1904-1943). Questo sistema è una teoria in LAI che si ottiene aggiungendo ad Al-A9 i seguenti assiomi:

Alo \ix(sx:;t:O) All \i x\iy(sx=sy::Jx= y) A12 \ix(x+O=x) A13 \i x\iy(x+sy =s(x+ y)) A14 ( a(O) A \ix( a(x) ::J a(sx))) ::J \i ya(y), per ogni formula a(x) in cui x occorre libera.

70

AIO stabilisce che non c'è alcun numero di cui O è successore, mentre Al 1 garantisce che la funzione denotata das è iniettiva, cioè che i successori di due numeri diversi sono diversi. Al2 e Al3 definiscono l'addizione. Al 4 enuncia il principio di induzione per i numeri. Infat­ti, a esprime la condizione e menzionata nella formulazione del prin­cipio nel paragrafo i.5. Una teoria in LA2 è l'aritmetica di Peano, che si abbrevia con PA. Questo sistema, che prende il nome da Giuseppe Peana ( 18 5 8-1932), è ottenuto aggiungendo i seguenti assiomi ali' aritmetica di Presburger:

A15 \i x(x · O = O) . A16 \ix\iy(x·sy=x+x·y)

Al 5 e Al 6 definiscono la moltiplicazione. Se si elimina Al 4 da PA e si aggiunge il seguente assioma si ottiene l'aritmetica di Robinson, formulata da Raphael Mitchel Robinson ( 1911-1995):

A17 \i x(x :;t: O ::J .3y(x = sy))

Le tre teorie considerate sono assiomatizzazioni diverse dell'aritmeti­ca, cioè sistemi differenti che permettono di derivare un insieme comune di verità aritmetiche.

Nota Nella formulazione di A9 si adotta il simbolo a' invece della notazione a(y Ix) definita nel paragrafo p. Il motivo è che quest'ulti­ma implica la sostituzione in a di tutte le occorrenze libere dix con y, diversamente da quanto A9 richiede.

Esercizio 4 Perché ogni teorema di S è teorema di S + f?

Esercizio 5 S è una teoria?

5.3. Due lemmi che vertono sulla coerenza Dato che per D 14 qualsiasi teoria include S, buona parte di ciò che è stato dimostra­to a proposito di S vale per qualsiasi teoria. Ll-L4 dipendono da

71

proprietà di L che appartengono a ogni sua variante. LS-L22 dipendo­no da proprietà di S che appartengono a ogni sistema che includaA1-A7 e MP. T2 può essere facilmente generalizzato. Le proprietà di S richieste dalla dimostrazione di T2, infatti, sono tre: ogni formula che esemplifica Al è un assioma, ogni formula che esemplificaA2 è un assioma, MP èl'unica regola di inferenza. Siccome D 14 implica queste tre proprietà, T2 vale per qualsiasi teoria. Lo stesso si può dire per gli altri lemmi e teoremi su S che sono stati dimostrati a partire da T2, cioè L24-L31 eT3-T9. La dimostrazione della coerenza di S, invece, non può essere estesa a qualsiasi teoria. La ragione è molto semplice: siccome una teoria può includere assiomi propri che non figurano in S, nulla vieta che quegli assiomi permettano alla teoria di generare contraddizioni che S non è in grado di generare. Quindi, dal fatto che S è coerente non si può concludere che una teoria qualsiasi è coerente. Lo stesso vale per la coerenza in S. Dal fatto che un insieme di formule è coerente in S non si può concludere che lo stesso insieme è coerente in una teoria qualsiasi. Questa limitazione, tuttavia, non impedisce di dimostrare risultati sulla coerenza che valgono per qualsiasi teoria. I duelemmt che seguono sono risultati di questo tipo. Il primo enuncia un fatto abbastanza ovvio, cioè che, se si aggiunge al linguaggio di una teoria coerente un insieme numerabile di costanti individuali, si ottiene un'altra teoria coerente:

Lemma 32 Se Tè coerente e T'è ottenuta aggiungendo al linguaggio di T un insieme numerabile di costanti individuali, allora T'è coerente.

Dimostrazione Assumiamo che Te T' siano tali che T'è ottenuta aggiungendo al linguaggio di T un insieme numerabile di costanti individuali. Supponiamo che T' sia incoerente. Allora per qualche a esiste sia una dimostrazione in T' di a sia una dimostrazione in T' di ~ a. Ciascuna delle due dimostrazioni è costituita da un insieme finito di formule, quindi contiene un numero finito di costanti individuali nuove. Siano a 1, ••• , an le costanti individuali in questione. Siano ul' ... ,

u variabili distinte che non compaiono in nessuna delle due dimostra-n

72

zioni. Se {31' ... , f3m èladimostrazionein T' di a (conf3m = a)e {3~, ... , /3,:, è la sequenza di formule che si ottiene sostituendo le nuove costanti individuali in {31, ••• , f3m con variabili della lista u1, ••• , u

11, risulta che {3~,

... , f3~, è una dimostrazione in T. Infatti, per ogni /3; compresa tra {31 e f3 ci sono tre possibilità. m

Caso I: /3; esemplifica Al-A7. In questo caso {3~ esemplifica Al-A?, quindi è un assioma di T. Caso 2: /3; è un assioma proprio di T'. In questo caso {3~ è un assioma pro­prio di T, dato che T' non contiene assiomi propri diversi da quelli di T. Caso 3: f3; è conseguenza diretta di due formule f3k e f3k-:J /3,- In questo caso ci sono due formule {3~ e. (f3k -:J /3) 1 che precedono {3:, con (f3k-:J /3) 1 = {3~-:J {3:. Quindi f3'; è conseguenza diretta di tali formule. Dai tre casi considerati risulta che {3'., ... , {31 è una dimostrazione in T di

l 1Jl

f3,:,. Con un ragionamento analogo si può concludere che, se /31' .. ., f3m ' d' · · T'di {3' {31 ' d' e ul e una rmostraz10ne m ~ a e ., ... , e una sequenza 1 rorm e

l 1lJ..

ottenuta sostituendo le nuove costanti individuali in /31' ... , {3111

con variabilidellalistau1, ••• , u , alloraf3'., ... , {31 è una dimostrazione in T di n 1 m

~ {31 • "uindi Tè incoerente. m '<:

D Il secondo lemma enuncia un fatto meno ovvio del primo, ma proprio per questo più interessante:

Lemma 33 Se~ a è una formula chiusa che non è teorema di T, allora T + {a} è coerente.

Dimostrazione Sia~ aunaformulachiusachenonèteoremadi Te sia T' la teoria T + {a}. Per qualsiasi formula {3, ~T' f3 sse a ~T {3. Supponia­mo ora che T' sia incoerente. Allora esiste una formula y tale che ~T'ì' e ~T'~y. Di conseguenza, a ~Tye a ~T~y. PerT2, ~Ta-:Jye ~Ta-:J~y. Ma da T8 risulta che ~T ( a-:J y) -:J ( ( a-:J~ y) -:J~ a). Applicando due volte L12 si ottiene che ~T~ a, contrariamente all'ipotesi di partenza.

D Esercizio 6 Dimostrare quanto segue:

73

Esercizio 7 Supponendo, come in L32, che al linguaggio di T si aggiun­ga un insieme numerabile di costanti individuali per formare T', l'insie­me delle costanti individuali del linguaggio di T' risulta numerabile?

5.4. Lemma di Lindenbaum Per concludere il discorso sulla coerenza si dimostrerà ora un risultato noto come lemma di Linden­baum, che prende il nome da Adolf Lindenbaum (1904-1941). Questo richiede la definizione di una proprietà sintattica distinta dalla coerenza, la massimalita:

Definizione 15 Tè massimale sse per ogni formula chiusa a, ~Tao

~T~a.

Dire che Tè massimale significa dire che l'insieme degli enunciati del linguaggio di T può essere ripartito in due sottoinsiemi: quelli dimo­strabili e quelli la cui negazione è dimostrabile. Il lemma di Linden­baum stabilisce che ogni teoria coerente ha un'estensione coerente e massimale nello stesso linguaggio:

Lemma 36 Se Tè coerente, allora esiste una teoria nel linguaggio di T che è un'estensione coerente e massimale di T.

Dimostrazione Assumiamo che T sia coerente. Data un'enumera­zione ( a 1, a2, a3".) delle formule chiuse del linguaggio di T, sia ( T0, Tl' T2 ... ) una sequenza infinita di teorie definita induttivamente come segue: 1. T0 = T 2. Per qualsiasi n:

T { T + {a +l} se~ a +l non è teorema di T _ n n n 11

11+1 - T se~ a è teorema di T Il 11+1 Il

In altri termini, la clausola 2 dice che, se a11+ 1 può essere coerentemen­

te aggiunta come assioma a T11

, allora si aggiunge a T11

per formare

74

T +l' altrimenti T +l è la stessa T. Sia T'una teoria che ha come assio-n n 11

mi tutti gli assiomi di tutte le teorie (T0, T1, Tr-.)· È evidente che T' ha lo stesso linguaggio di T. È altrettanto eviden-te che T'è un'estensio­ne di T. Quindi, è sufficiente dimostrare che T'è coerente e massima­le per arrivare alla conclusione desiderata. La coerenza di T' si dimostra come segue. T

0 è coerente per ipotesi.

Inoltre, per qualsiasi n, se T 11 è coerente, allora T,,+ 1 è coerente. Infatti, T +l ::/= T solo nel caso in cui T +l = T +{a 1} e~ a 1 non è teore-n n 11 n n+ n+ ma di T . Ma in quel caso T 1 è coerente per L33. Dunque, T è n n+ n coerente per qualsiasi n. Ora supponiamo che T' sia incoerente. Allo-ra per qualche a esiste sia una dimostrazione in T' di a sia una dimo­strazione in T' di~ a. Ciascuna delle due dimostrazioni contiene un insieme finito di formule chiuse che sono state aggiunte come assiomi a T per formare T'. Sia a

11 la formula tra queste che in base all'enume­

razione ( a 1, a2, a3 ... ) risulta avere il numero più alto nelle due dimo­

strazioni. Allora le due dimostrazioni possono essere formulate in T , Il

il che significa che T11

è incoerente, contrariamente a quanto appena dimostrato. Per rendersi conto che T'è massimale, si consideri una formula a

1 Il+

nell'enumerazione (a1, a2, a3

..• ). O~ a,,+1 è teorema di T,, o non lo è. Se è teorema di T , allora è teorema di T'. Infatti, ogni dimostrazione

Il

in qualche teoria della sequenza ( T0, T1, T2".) è una dimostrazione in T'. Se invece~ a +l non è teorema di T , allora T +l = T +{a

1},

11 n n n n+ quindi a,,+ 1 è teorema di T

11+ 1• Questo significa che a

11+ 1 è teorema di

T' per la stessa ragione. o

Nota La proprietà definita in D 1 S è talvolta chiamata "completezza''. Qui si adotta "massimalità" per non creare confusione con un'altra proprietà che sarà definita più avanti.

75

Soluzioni degli esercizi

1. La traduzione è V x(x = x). 2. Una traduzione ovvia è 3x3 y(x * y ), ma non è l'unica. Un enun­ciato equivalente è V x3y(y ;1:.x). 3. In questo caso basta modificare il primo dei due enunciati dell'e­sercizio 5.2 aggiungendo una condizione che esprime "al massimo due': cioè 3x3y(x;1:. y A V z(z =xv z=y)). 4. Assumiamo che a sia teorema di S. Questo significa che esiste una sequenza di formule che è una dimostrazione di a in S. La stessa sequenza di formule è una dimostrazione di a in s + r. 5.- Sì. L'insieme degli assiomi propri di una teoria può essere vuoto. 6. L34

1. 1-r~a::J(a::Jf3) 2. 1-r( ~ a::J ( a::J /3)) ::J ( ~ (a::J /3) ::J~~ a) 3. 1--r~ (a::J /3) ::J~~ a 4. 1--r~~ a::J a 5. 1-r~ (a::Jf3)::Ja

L35 1. 1-rf3::J ( a::J /3) 2. 1--r (/3 ::J (a ::J /3) ::J ( ~ (a ::J /3) ::J~ {3)

L25 T6 l,2L12 T4 3,4L24

Al T6

3. 1--r~ (a ::J /3) ::J~ /3 l, 2 L12 7. Sì. Il linguaggio di T ha al massimo un insieme numerabile di costanti individuali che non sono in L. Il linguaggio di T' ha un insie­me numerabile di costanti individuali che non sono nel linguaggio di T. Quindi, il linguaggio di T'ha al massimo un insieme numerabile di costanti individuali che non sono in L. Il caso è analogo a quello dell'e-sercizio 2.1.

76

6. Teorie e modelli

6.1. Modello di una teoria Il capitolo 5 fornisce una definizio­ne di teoria e presenta alcuni risultati sintattici sulle teorie. Questo capitolo, invece, tratta le teorie da un punto di vista semantico. I risul­tati che presenta vertono sulle relazioni tra teorie e modelli:

Definizione 16 A e modello di T, in breve A I= T, sse ogni teorema di Te soddisfatto da tutte le assegnazioni in A.

Per capire bene D 16 occorre tenere presente che teorie diverse avere gradi diversi di generalità. Ad esempio, la teoria dell'identità permette di rappresentare verità e inferenze esprimibili mediante il simbolo =. Queste verità e inferenze hanno un grado di generalità piuttosto alto, in quanto i principi dell'identità su cui si fondano valgono indistintamente per ogni oggetto. Una teoria aritmetica, invece, è costruita con l'intento di descrivere i numeri e le loro proprietà. Quindi le verità e le inferenze formulate nella teoria hanno un grado di generalità più basso, in quanto valgono per i numeri, o almeno per tutto ciò che è sufficientemente simi­le ai numeri da conformarsi alla descrizione fornita dalla teoria. Il grado di generalità di una teoria può essere reso esplicito specifican­do un insieme di strutture, cioè l'insieme delle strutture appropriate per la teoria. La differenza tra la teoria dell'identità e una teoria aritme­tica può dunque essere espressa in questi termini: tutte le strutture in cui il simbolo= è interpretato con il suo significato inteso sono appro­priate per la la teoria dell'identità, mentre solo certe strutture di tipo ancora più specifico sono appropriate per l'aritmetica, cioè quelle in cui i simboli +, ·, O es siano interpretati in un certo modo. Ma che cosa significa esattamente "appropriate"? D 16 fornisce una rispo­sta a questa domanda: le strutture appropriate per T sono i modelli di T. La risposta è plausible perché l'insieme dei teoremi di T fornisce una caratterizzazione sintattica del contenuto di T, vale a dire di ciò che T enuncia. Una struttura non può essere appropriata per T se non si conforma al contenuto di T.

77

Il grado di generalità di una teoria può dunque essere misurato sulla base del suo contenuto. Sia ll l'insieme di tutte le strutture, cioè delle coppie ordinate (D, I) che soddisfano D2. U è l'insieme dei modelli di S, come risulta da L23. L'insieme dei modelli della teoria dell'identità, invece, è un sottoinsieme proprio di U, cioè quello delle strutture (D,l) in cui I assegna a= la relazione di identità suD. Una struttura del gene­re è chiamata normale.L'insieme dei modelli di una teoria aritmetica è a sua volta un sottoinsieme proprio dei modelli della teoria dell'iden­tità, cioè quello delle strutture normali in cui i simboli aritmetici sono interpretati in accordo con gli assiomi della teoria. Questo significa che S ha il grado massimo di generalità, la teoria dell'identità è meno g~nerale di Se una teoria aritmetica è meno generale della teoria dell'i­dentità.

Nota Per esprimere la relazione enunciata in D 16 si usa il simbolo f=, cioè lo stesso che è stato impiegato per conseguenza logica e validi­tà. Ma non si deve fare confusione. In un caso, infatti, si tratta di una relazione tra insiemi di formule e formule, mentre nell'altro si tratta di una relazione tra strutture e teÒrie.

Esercizio 1 Se T'è un'estensione di T, ogni modello di T'è modello di T. Perché?

Esercizio 2 Sia A una struttura normale per L A2

tale che A = w, [O]A =O, [s]A =Su, [+]A =Ad e [·]A =Mo. Gli assiomi propri diPA sono veri in A?

Esercizio 3 Dimostrare che ogni struttura normale è modello della teoria dell'identità.

6.2. Chiusura Tra le cose che è importante sapere sulle proprietà semantiche delle teorie, c'è un fatto che merita particolare attenzione: ogni teoria coerente ha un modello numerabile. Il resto del capitolo sarà dedicato alla dimostrazione di questo fatto. Innanzitutto, occorre definire una proprietà sintattica, la chiusura:

78

Definizione 17 Te chiusa sse per ogni formula a che contiene occorren­ze libere di una sola variabile x, se f-T a(tl x) per ogni termine chiuso t, allora f-T V xa.

La chiusura può essere intesa come segue: se in Tè dimostrabile che una certa condizione vale per ogni oggetto del dominio di cui il linguaggio di T contiene un nome, allora è dimostrabile che quella condizione vale senza restrizioni per ogni oggetto del dominio. D 17 permette di formulare un ragionamento che si articola in due parti. Prima si dimostra, aggiungendo un lemma a quanto precede, che se Tè coerente allora esiste un'estensione T' di T che è chiusa, coerente e massimale. Poi si dim~stra che se T' è chiusa, coerente e massimale, allora T' ha un modello numerabile. In questo modo si ottiene il condizionale desiderato: se Tè coerente, allora T ha un modello numerabile.

6.3. Prima parte della dimostrazione

Lemma 37 Sia V xa una formula chiusa del linguaggio di T. Sia cuna costante individuale che non occorre in nessun assioma proprio di T o in a. Sia T' ottenuta aggiungendo a( clx) ::::) V xa a T come assioma proprio. Se Te coerente, allora T' e coerente.

Dimostrazione Supponiamo che T' sia incoerente. Siccome V xa è chiusa, a(clx) è chiusa, e lo stesso vale per a(clx) ::::)\;/ xa. Per L33 ne risulta che ~ (a( clx) j V xa) è teorema di T. Dunque si può ragionare come segue:

1. f-T~(a(clx)::::)'efxa) 2. f-T~(a(c/x)::::)'efxa)::::)a(clx)

3. f-Ta(clx) L34 l,2Ll2

Da3 risulta che c'è una dimostrazione in T di a(c/x). Sia/31' ... , /3,, tale dimostrazione. Sia u una variabile che non occorre in /31' ... , /3,, o in a. Sia f3~, ... , /3: il risultato della sostituzione di u a e in /31' ... , {3

11• /3~, ... , /3:,

79

è una dimostrazione in T. Infatti, per ogni /3; compresa tra {31 e /3,, ci sono tre possibilità. Caso I: f3;esemplificaAI-A7. In questo caso /3~ esemplificaAI-A7. Caso 2: /3; è un assioma proprio di T. In questo caso {3~ f3i' poiché per ipotesi e non occorre negli assiomi propri di T. Caso 3: /3; è conseguenza diretta di due formule /3k e f3k ::J /3,- In questo caso {3~ è conseguenza diretta di /3~e f3~::J {3~, dato che (f3k::J /3)' = f3~::J {3~. La formula dimostrata /31

,, è ottenuta sostituendo u a e in a( e/ x). Per ipotesi e non occorre in a, quindi {31

11 a(u!x). Da ~Ta(u!x) e L8

risulta che ~T Vua(u!x). Siccomexèsostituibileauina(u/x),perA4 ~TV ua( u/ x) ::J a. Applicando LI 2, ~T a. Per L8, ~TV xa. Ma allora ~è incoerente. Infatti si può ragionare come segue:

I. ~T~(a(c/x)::J\/xa) 2. ~T~(a(c/x)::J\/xa)::J~ Vxa L35

l,2Ll2 D

Lemma 38 Se Te coerente, allora esiste una teoria che e un'estensione coerente, chiusa e massimale di T.

3. ~T~Vxa

Dimostrazione Assumiamo che T sia coerente. Sia T0

ottenuta aggiungendo al linguaggio di T un insieme numerabile di costanti individuali. Sia ( a 1, a2, ar.) un'enumerazione delle formule del linguaggio di T0 in cui esattamente una variabile occorre libera. Sia (e

1,

c2, cr.) un'enumerazione delle costanti individuali aggiunte a T per formare T0• Sia /31 la formula a 1 (cj /x1) ::J V x 1 al' dove J è la prima costante individuale in (c1, c2, cr.) che non occorre in a

1 e.i-

1 è la varia­

bile libera in a 1• Pern> I, sia/3 la formula a (c. lx) ::J V x a, dove c. 11 11 ] 11 n n 11 Jn

è la prima costante individuale in (e 1, c2, cr.) clie non occorre in nessu-na delle formule /31' ... , /3,,_1 o in a,,. Sia T1 ottenuta aggiungendo /3

1 come assioma proprio a T0• Per n > I, sia T,, ottenuta aggiungendo /3,, come assioma proprio a T,,_1• Sia T' la teoria che risulta aggiungendo a T0 tutte le formule /3; come assiomi propri. T' risulta coerente in base al seguente ragionamento. T

0 è coerente per

L32. Inoltre, da L37 risulta che, per ogni n, se T è coerente, allora T 1 n n+

80

è coerente. Quindi, T,, è coerente per qualsiasi n. Supponiamo ora che T' sia incoerente. Allora per qualche a esiste sia una dimostrazione in T' di a sia una dimostrazione in T' di ~ a. Ciascuna delle due dimo­strazioni è costituita da un insieme finito di formule, quindi usa un numero finito di formule {3 .. Sia f3 la formula tra queste con il numero

l Il

più alto che compare nelle due dimostrazioni. Allora vi sono dimostra-zioni in T di a e ~ a, il che è impossibile.

Il

Dato che T'è coerente, per L36 esiste una teoria T" che è un'estensio-ne coerente e massimale di T' con lo stesso linguaggio di T'. Ora si dimostrerà che T" è chiusa. Sia a,, lan-esimaformulain (a1, a2, ar·>· Supponiamo che ~T'' a,, (ti x,,) per ogni termine chiuso t del linguaggio diT".Allora~T''a (e.lx ).Masiccomea (e.lx )::J\fx a èunassio-

11 Jn n n ln n n n madi T' eT" è un'estensione di T',risultache ~T''a (c. lx) ::J V x a.

1l 111 11 1l Jl

Per Ll2, 'r' V x a . Dunque, T" è coerente, chiusa e massimale. Dato r n n che T" è un'estensione di T' e T'è un'estensione di T, T" è un'esten-sione coerente, chiusa e massimale di T.

D 6.4. Seconda parte della dimostrazione

Lemma 39 Se Te coerente, chiusa e massimale, allora T ha un modello numerabile.

Dimostrazione Sia T una teoria coerente, chiusa e massimale il cui linguaggio L include un insieme numerabile di costanti individuali. Sia A una struttura definita come segue:

I. A è l'insieme dei termini chiusi di L; 2. La funzione interpretazione di A assegna:

(a) a ogni costante individuale la costante stessa; (b) a ogni costante predicativa a n posti P una relazione R tale che Rc;;;,.A11 e(t1, ••• , t) ERsse ~TPt1 , ••• ,t

11;

( c) a ogni simbolo di funzione a n postijla funzione F: A 11 - A

tale cheF(t1, ••• , t11

) =fil' ... , t,,.

A è numerabile, poiché l'insieme dei termini chiusi di L è numerabile

81

(si veda l'esercizio 2.2). Ora si dimostrerà che per qualsiasi enunciato

a, [a]A 1 sse f-Ta. Base. Assumiamo che n = O. In questo caso a è una formula atomica Pt

1, ••• , t

11 in cui t

1, ••• , t

11 sono termini chiusi. Per la clausola (b) della

definizione di Ane consegue che [a ]A= 1 sse f-T a. Passo. Assumiamo che il bicondizionale da dimostrare valga per qual­siasi enunciato di complessità minore o uguale a ne consideriamo un enunciato adi complessitàn + 1. Caso 1: a ha la forma~ (3. In questo caso f3 è un enunciato. Supponia­mo che [a]A =O. Allora [f3]A = 1. Per ipotesi di induzione, f-Tf3. Dato che Tè coerente, ne consegue che ~ f3 non è teorema di T. Quindi, se ~Ta,allora [a]A = 1. Supponiamo ora che [a]A =I.Allora [f3]A =O. Per ipotesi di induzione, f3 non è teorema di T. Dato che Tè massima­le, f-T~ (3. Quindi, se [a ]A= 1, allora f-T a. Caso 2: a ha la forma f3 ::J y. In questo caso f3 ey sono enunciati. Suppo­niamo che [a]A =O.Allora [f3]A = 1 e [y]A =O. Per ipotesi di induzio­ne, f-T f3 e y non è teorema di T. Siccome Tè massimale, f-T~ y. Ma da L28 risulta che f-T f3 ::J ( ~ y ::J~ ((3 ::J y ). Per L12, f-T~ ((3 ::J y ). Dato che Tè coerente, f3 ::J y non è teorema di T. Quindi, se f-T a allora [a]A 1. Supponiamo ora che a non sia teorema~i T. Allora f-T~ (f3::Jy), essendo T massimale. Per L34 e L35, f-T~ (f3::Jy) ::J f3 e f-T~ ((3 ::J y) ::J~ y. Per L12, f-T f3 e f-T~ y. Data la coerenza di T, y non è teorema di T. Per ipotesi di induzione [f3]A = 1 e [y]A =O, il che signi­fica che [a]A =O.Dunque, se [a]A = l,alloraf-Ta. Caso 3: a ha la forma 'if xf3. In questo caso f3 può essere chiusa o aper­ta, dunque consideriamo prima l'ipotesi che sia chiusa. Supponiamo che f-T a. Questo significa che f-T 'if xf3. Siccome f-T 'if xf3 ::J f3 per A4, applicando L12 si ottiene che f-T (3. Per ipotesi di induzione, [(3] A= 1, di conseguenza ['if xf3]A = 1. Quindi, se f-Ta, allora [a]A = 1. Inver­samente, supponiamo che [ a]A 1. Allora [f3]A = 1. Per ipotesi di induzione, f-T (3. Da questo e L8 si ottiene che f-T 'if xf3. Quindi, se [a ]A= 1, allora f-T a. Consideriamo ora fipotesi che f3 sia aperta. In questo caso l'unica variabile libera in f3 è x, perché a è chiusa. Suppo­niamo che f-Ta.Allora per A4eL12siottieneche f-Tf3(t/x), dove tè un termine chiuso. Per ipotesi di induzione, [f3(tl x)] A l. Siccome

82

questo vale per ogni termine chiuso, ne consegue che [a ]A= 1. Infat­ti, A è congegnata in modo tale da garantire la verità di 'if xf3 nel caso in cui f3(tlx) sia vera per qualsiasi t. Quindi, se f-Ta, allora [a]A = 1. Supponiamo ora che [ a]A = 1. Allora f3 è soddisfatta da tutte le asse­gnazioni in A. Quindi [f3(tlx)]A = 1 per qualsiasi termine chiuso t. Per ipotesi di induzione, f-Tf3(tlx) per qualsiasi termine chiuso t. Siccome T è chiusa, da questo si ottiene che 1-T 'if xf3. Quindi, se

[ a]A = 1, allora f-Ta. Da quanto precede risulta che per qualsiasi enunciato a, [a] A= 1 sse f-T a. Questo è sufficiente per concludere che per qualsiasi formula a, se f-T a, allora a è soddisfatta da tutte le assegnazioni in A. Infatti, se f-T a e a è una formula aperta, per L8 esiste un enunciato f3 tale che le variabili libere in a sono vincolate in f3 e f-T (3. Ne consegue che [(3] A= 1, quindi che a è soddisfatta da tutte le assegnazioni in A.

D Teorema 10 Se Tè coerente, allora T ha un modello numerabile.

Dimostrazione Assumiamo che T sia coerente. Allora per L38 esiste una teoria T' che è un'estensione coerente, chiusa e massimale di T. Ma per L39 T'ha un modello numerabile. Siccome T'è un'estensione di T, anche T ha un modello numerabile.

D Nota Nella dimostrazione di L39 si assume che L sia dotato di un insieme numerabile di costanti individuali. Ma dal paragrafo 5.1 risul­ta che il linguaggio di una teoria può avere costanti individuali in numero finito, o non averne affatto. Dunque viene da chiedersi perché la dimostrazione debba valere per qualsiasi teoria coerente, chiusa e massimale. A questa domanda si può rispondere come segue. Sia T una teoria coerente, chiusa e massimale il cui linguaggio non include un insieme numerabile di costanti individuali. Sia T' un'estensione di T ottenuta aggiungendo tale insieme al linguaggio di T. Per L32, T'è coerente. Per L38, esiste un'estensione T" di T' che è coerente, chiusa e massimale. T" è un'estensione coerente, chiusa e massimale di T. Siccome dalla dimostrazione risulta che T" ha un modello numerabi­le, lo stesso vale per T.

Esercizio 4 . Si consideri la dimostrazione di L39. Per concludere che A I= T basta dimostrare che, per qualsiasi enunciato a, se 1-r a allora [a] .A: I. Non sarebbe stato più semplice formulare la dimostrazione induttiva in termini di questo condizionale, invece che del bicondizio­nale 1-ra sse [ a].A: = I?

Esercizio S Nel caso 3 della dimostrazione di L39, considerando l'ipotesi che f3 sia chiusa, si assume che 1-r V xf3 :J f3 per A4. Perché questa assunzione è legittima?

Esercizio 6 Si può dimostrare che ogni estensione coerente della teoria dell'identità ha un modello normale numerabile?

Esercizio 7 Si può dimostrare che ogni estensione coerente della teoria dell'identità ha un modello normale?

84

Soluzioni degli esercizi

1. Assumiamo che T' sia un'estensione di T. Questo significa che, se 1-Ta' allora 1-T' a. Supponiamo ora che A I= T'. Ne risulta che, se 1-r a, allora a è soddisfatta da tutte le assegnazioni in A. Quindi, se 1-r a, allora a è soddisfatta da tutte le assegnazioni in A. 2. Sì. 3. Ogni formula che esemplifica Al-A7 è soddisfatta da tutte le assegnazioni in tutte le strutture (si veda PAR. 3.4), quindi è soddisfat­ta da tutte le assegnazioni in tutte le strutture normali. Anche A8, chiaramente, è soddisfarta da tutte le assegnazioni in tutte le struttu­re normali. Ora si consideri una formula che esemplifica A9. Suppo­niamo che x = y sia soddisfatta da vin una struttura normale A. In questo caso v assegna lo stesso oggetto ax e y. Quindi, se v soddisfa a e a' differisce da a al massimo in quanto y sostituisce x in qualche occorrenza libera, allora v soddisfa a'. Di conseguenza, v soddisfa x = y :J (a :J a'). Siccome v è un'assegnazione qualsiasi, Vy(x = y :J

(a :J a')) è soddisfatto da tutte le assegnazioni in A, e lo stesso vale per V x Vy(x = y :J (a :J a')). Dunque gli assiomi della teoria dell'i­dentità sono soddisfatti da tutte le assegnazioni in tutte le strutture normali. Se a questo si aggiunge che MP preserva il soddisfacimento in tutte le strutture normali, si ottiene che ogni teorema della teoria dell'identità è soddisfatto da tutte le assegnazioni in tutte k struttu­re normali. 4. No. Certamente non ci sarebbero stati problemi con la base. Ma se nel passo si assumesse solo il condizionale come ipotesi di induzione, non è ovvio come si potrebbe arrivare al risultato desiderato. Basta provare con il caso I per convincersi di questo fatto. 5. Se f3 è chiusa, allora non contiene occorrenze libere dix. Quindi, per qualsiasi termine t, tè sostituibile ax in {3 e {3(tl x) = {3. 6. No. Lid permette di formulare enunciati che sono falsi in ogni struttura normale infinita. Ad esempio, l'enunciato 3x3y(x * y A

V z(z=x v z = y)) considerato nell'esercizio 5.3 è vero in una struttura normale solo se il dominio della struttura contiene esattamente due oggetti. Aggiungendo un enunciato del genere come assioma proprio

85

alla teoria dell'identità si può ottenere un'estensione coerente della teoria dell'identità che non ha modelli normali infiniti. 7. Sì. Assumiamo che T sia un'estensione coerente della teoria dell'i­dentità. Da TIO risulta che T ha un modello A costruito seguendo il metodo impiegato nella dimostrazione di L39, cioè tale che A è l'insie­me dei termini chiusi del linguaggio di T. Per dimostrare che T ha un modello normale basta costruire un modello analogo A' in cui gli elementi del dominio A' siano insiemi ottenuti raggruppando gli elementi di A in base alla seguente condizione: te t' appartengono allo stesso insieme sse ~Tt = t'. In questo modo si rispetta il significato inteso di=, perché si esclude che termini distinti possano denotare ()ggetti diversi nel dominio quando la loro identità è dimostrabile.

86

7. Correttezza

7.1. Corrispondenza tra sintassi e semantica L'apparato deduttivo presentato nel capitolo 3 permette di fornire una caratteriz­zazione sintattica di un insieme di argomenti deduttivamente validi e di verità logiche. D 1 O e D 11 sono formulate in termini dell'apparato deduttivo di S, senza alcun riferimento a proprietà semantiche. D'altra parte, l'interpretazione di L presentata nel capitolo 2 permette di fornire una caratterizzazione semantica di un insieme di argomenti deduttivamente validi.e di verità logiche. D7 e D8 presuppongono solo le definizioni di struttura e di assegnazione, quindi non dipendo­no da questo o quell'apparato deduttivo. Lo stesso vale per qualsiasi teoria. Le definizioni di derivazione e di dimostrazione in una teoria sono sintattiche, mentre quelle di conseguenza logica e di validità per il suo linguaggio sono semantiche. Dati una teoria Te un insieme di strutture M, la conseguenza logica e la validità per il linguaggio di T possono essere definite in termini diM:

Definizione 18 r l=M asse in ogni struttura in M, ogni assegnazione che soddisfa tutte le formule in r soddisfa a.

Definizione 19 l=M asse in ogni struttura in M, ogni assegnazione soddisfa a.

D 18 e D 19 implicano una quantificazione su un insieme di strutture M che è sottoinsieme di U. Per questo il simbolo I= è accompagnato da un indice che fa riferimento aM D7 e D8, in cui il simbolo I= figura senza indice, possono essere viste come casi speciali diD18 eD19, cioè come i casi in cuiM = U. Laconseguenzalogicasimpliciterequivale alla conse­guenza logica rispetto a U, e la validitàsimpliciter equivale alla validità rispetto a U. Una volta definite la conseguenza logica e la validità per il linguaggio di T in termini diM, ci si può chiedere quale sia la relazione tra deriva-

87

bilità in Te conseguenza logica rispetto aM, o tra dimostrabilità in T e validità rispetto aM. Questa domanda è particolarmente interes­sante nel caso in cuiM sia l'insieme dei modelli di T. Si consideri S. Quanto è stato detto fin qui lascia aperta la questione se l'insieme di argomenti deduttivamente validi caratterizzato sintatticamente sulla base di DI O sia identico all'insieme di argomenti deduttivamente validi caratterizzato semanticamente sulla base di D7. Lo stesso vale per DII e D8. Si è visto cheQa è derivabile dall'insieme {V x(Px:J Q:c ), Pa} in S, oltre a essere conseguenza logica dello stesso insieme. Si è visto che l'enunciato V x(Px :J Px) è teorema di S, oltre a essere vali­do. Ma è legittimo chiedersi se una simile corrispondenza valga per q1:1alsiasi formula o insieme di formule. Le due proprietà che tratteremo ora vertono appunto sulla relazione tra sintassi e semantica. T si dice corretta rispetto aM nel caso in cui ogni deri­vazione in T esprima una relazione di conseguenza logica rispetto aM. Inversamente, T si dice completa rispetto aM nel caso in cui la conseguen-za logica rispetto aM implichi la derivabilità in T. .

Definizione 20 Te corretta rispetto aM sse, se r ~T a, allora r l=M a.

Definizione 21 T ecompletarispettoaMsse, se f l=Ma, allora f ~Ta.

Dato che ogni dimostrazione è una derivazione dall'insieme vuoto e ogni formula valida è conseguenza logica dell'insieme vuoto, la relazio­ne tra dimostrabilità e validità equivale al caso in cui f = 0. La corret­tezza simpliciter equivale alla correttezza rispetto a il, mentre la completezza simpliciter equivale alla completezza rispetto a il.

7.2·. Teorema di correttezza Ora si dimostrerà il teorema di correttezza per S:

Teorema 11 Se f ~a, allora r I= a.

Dimostrazione Assumiamo chef~ a. Per LI4, c'è un sottoinsieme finito !:::.. di f tale che!:::.. ~ a. I casi possibili sono due.

88

Caso 1: !:::.. = 0. In questo caso, ~ a. Per L23, I= a. Da questo e L4 risul­ta che r I= a. Caso 2: !:::.. * 0. In questo caso,!:::.. {/31, ••• , /3,,} e /31' ... , f3n ~a. Applican­donvolte T2siottieneche ~ /31 :J ( ... (/3,,:J a)). Per L23, I= /31 :J ( ... (f3,,:J a)). Quindi non esiste una struttura in cui un'assegnazione soddisfa f3

1,

... , /3,, ma non soddisfa a. Pertanto, b.. I= a. Da questo e L3 si ottiene che

r I= a.

7.3. Correttezza e insiemi di strutture Da Tll risulta che ogni derivazione in S esprime una relazione di conseguenza logica rispetto a il.Tuttavia, non vale lo stesso per qualsiasi teoria. Una teoria può includere assiomi propri che non sono validi simpliciter e pertan­to non essere correttasimpliciter. Se T include un assioma proprio f3 che non è valido rispetto a il, è possibile che in T si possa derivare a da r per mezzo di /3, pur non essendo a conseguenza logica dir rispetto a il. Il caso più semplice è quello in cui f 0 e a= f3. Ogni teoria del genere ha un contenuto specifico che è fissato dai suoi assiomi propri. Questo significa che c'è un sottoinsieme proprio di il rispetto al quale gli assiomi della teoria risultano validi. Per enunciare un teorema generale che valga per tutte le teorie, quindi, si deve tenere conto del fatto che in molti casi la relazione semantica rilevante non è la conseguenza logica simpliciter, ma piuttosto la conseguenza logica rispetto a un certo insieme di strutture. Si consideri il seguente lemma:

Lemma 40 Se A e una struttura in cui tutti gli assiomi propri di T sono veri, allora A I= T.

Dimostrazione Sia A una struttura in cui tutti gli assiomi propri di T sono veri. Ogni formula del linguaggio di T che esemplifica AI-A7 è soddisfatta da tutte le assegnazioni in .A. Dunque tutti gli assiomi di T sono soddisfatti da tutte le assegnazioni in .A. Ma per LS la regola MP preserva il soddisfacimento da parte di un'assegnazione in .A. Quindi, tutti i teoremi di T sono soddisfatti da tutte le assegnazioni in .A.

o

89

Sulla base di L40 si può dimostrare un teorema generale che verte sulla correttezza di qualsiasi teoria:

Teorema 12 Se gli assiomi propri di T sono validi rispetto aM, allora T e corretta rispetto a M

Dimostrazione SiaM un insieme di strutture rispetto al quale gli assio­mi propri di T sono validi. In ogni struttura inM, tutti gli assiomi propri di T sono veri. Pertanto, da L40 risulta che ogni strutturainM è modello di T. Quindi, si può dimostrare che se r ~T a allora r F .Ma nello stesso modo in cui TI I è stato dimostrato a partire daL23.

o T 12 può essere riformulato come segue: ogni teoria è corretta rispet­to all'insieme dei suoi modelli. Infatti, l'insieme delle strutture rispet­to al quale gli assiomi propri di una teoria sono validi e l'insieme dei modelli della teoria sono lo stesso insieme. SiaMl'insieme delle strut­ture rispetto al quale gli assiomi propri di T sono validi e siaM' l'in­sieme dei modelli di T. Da L40 risulta che per una struttura qualsiasi A, se A E M, allora A E M'. Supponiamo ora che A EM'. Allora ogni teorema di Tè soddisfatto da tutte le assegnaziqni in A. Quindi, gli assiomi propri di T sono soddisfatti da tutte le asegnazioni in A, il che significa che A EM.

Esercizio 1 Dimostrare che la teoria dell'identità è corretta rispetto all'insieme delle strutture normali.

Esercizio 2 Dimostrare che la teoria dell'identità è coerente usando L33.

Esercizio 3 Sia A come nell'esercizio 6.2. Aè modello diPA?

Soluzioni degli esercizi

1. A8-A9 sono validi rispetto all'insieme delle strutture normali (si veda l'esercizio 6. 3). Da questo e T 12 risulta che la teoria dell'identità è corretta rispetto all'insieme delle strutture normali. 2. Sia T la teoria ottenuta eliminando A8 e A9 dalla teoria dell'iden­tità. Ogni teorema di Tè teorema della teoria dell'identità, quindi è vali­do rispetto all'insieme delle strutture normali (si veda l'esercizio 6.3). Siccome ~V x(x = x) non è valido rispetto ali' insieme delle strutture normali, non è teorema di T. Per L33, ne consegue che T +{V x(x = x)} è coerente. Allo stesso II?-odo, qualsiasi enunciato che esemplifica A9 può essere aggiunto come assioma a T + {V x(x x)} formando una teoria coerente. 3. Sì. Questo risulta dall'esercizio 6.2 e da L40.

go 91

8. Completezza

8.1. Teorema di completezza La dimostrazione del teorema di completezza è più lunga e articolata di quella del teorema di correttezza. A partire dal lavoro di Kurt Go del (I 906-I 978 ), diversi metodi sono stati sperimentati per arrivare a questo risultato. Il metodo qui adottato, che risale a Leon Henkin (I92I-2006), permette di dimostrare la completezza di S sfruttando risultati già acquisiti nei capitoli preceden­ti. Innanzitutto si dimostrerà, grazie a TI O, che ogni insieme di formule chiuse coerente in una teoria ha un modello. Poi si userà questo risultato per dimostrare, con l'aiuto di due lemmi ulteriori, che ogni insieme di formule coerente in una teoria è soddisfacibile. Aggiungendo un lemma di carattere sintattico su S, si arriverà così al risultato desiderato.

Lemma 41 Se f è un insieme di formule chiuse coerente in una teoria T, allora r ha un modello.

Dimostrazione Sia f un insieme di formule chiuse coerente in T. Sia T' la teoria T +f. T' è coerente. Infatti, supponendo ~he sia incoeren­te, si ottiene che, per qualche a, 1-T' a e f-r~ a. Ma questo implica che f 1-T a ef f-T~ a, contrariamente all'ipotesi. Essendo T' coerente, da TI O risulta che T' ha un modello numerabile. Quindi, f ha un modello.

D Lemma 42 Siano Te T' tali che T' èottenutaaggiungendoallinguag­gio di T un insieme numerabile di costanti individuali. Se f è un insie­me di formule coerente in T, allora f è coerente in T '.

Dimostrazione. Supponiamo chef sia incoerente in T'. Allora per qualche a esiste sia una derivazione in T' di a da f sia una derivazione in T' di~ a da f. Sostituendo nelle due derivazioni ogni costante indi­viduale che non è nel linguaggio di T con una variabile appropriata si ottengono due derivazioni in T, con il risultato che Tè incoerente. Il ragionamento è analogo a quello impiegato per dimostrare L32.

D

92

Lemma 43 Sia a una formula del linguaggio di T in cui la variabile x è libera. Sia cuna costante individuale che non occorre in a né negli assio­mi propri di T. Se 1-T a( clx), allora 1-T a.

Dimostrazione Supponiamo che f-Ta(c/x). Allora esiste una dimo­strazione in T di a( clx) in cui c può essere rimpiazzata da una vàriabi­le che non occorre nella dimostrazione stessa o in a. A partire da questo fatto, con un ragionamento analogo a quello impiegato nella dimostrazione di L37 si può concludere che I- a.

D Lemma 44 Se f è un insteme di formule coerente in una teoria T, allo­ra r è soddisfacibile.

Dimostrazione Siafuninsiemediformulecoerentein T.Sianoxl'x2,

xr. le variabili che hanno occorrenze libere nelle formule di f. Sia T' ottenuta aggiungendo al linguaggio di T uh insieme numerabile di costanti individuali Cl, c2, C3··· Sia r' ottenuto sostituendo in r ogni variabile distinta x. con una costante individuale distinta c .. Per prima

I I

cosa si dimostra che f' è coerente in T'. Supponiamo che non lo sia. Allora per qualche a risulta chef' 1-r a e r' f-T,~ a. Da questo e LI 4 si ottiene che, per qualche sottoin,sie­me finito {/31' ... , /3) di f', /31' ... , [3

11 f-r a e /31' ... , [3

11 f-r~ a. Appli­

cando n volte T2 si ottiene che 1--T' /3 1 ::J ( ... (/3 11

::J a)) e 1-T' /31 ::J

( ... ([311 ::J~ a)). Per L43 ne consegue che 1-T' /31

1 ::J ( ... (/3~, ::J a')) e 1-r [3~ ::J ( ... (/3:, ::J~ a')), dove / indica che ogni costante individua­le ci è stata sostituita con la variabile corrispondentexr Da questo si ottiene che [3~, ... , [3: 1--T,a' e [3~, ... , /3: f-r~ a' (si veda la nota nel paragrafo 4.1). Siccome {[3~, ... , /3:} ç f, da LI O risulta chef f-T' a' e f f-r~ a'. Per L42, ne consegue che f è incoerente in T, contraria­mente all'ipotesi di partenza. Dato chef' è coerente in T' e che le formule in f' sono chiuse, per L4I ne consegue chef' ha un modello. Sia A tale modello. Sia v un'asse­gnazione alle variabili del linguaggio di T definita su A come segue: ogni variabilex. che è stata sostituita con una costante individuale c.

I I

ha la stessa denotazione di c;, ogni altro termine denota un elemento

93

qualsiasi diA. Essendo A modello dir', V soddisfa ogni formula in r. Quindi r è soddisfacibile.

D Lemma 45 Se[, ~ a e incoerente in S, allora r I- a.

Dimostrazione Assumiamo chef,~ a sia incoerente in S. Allora per qualche {3 risulta che r, ~ a I- {3 e r, ~ a I-~ {3. Per T2, r I-~ a ::J {3 e r I-~ a::J~ {3. Ma perT9, 1-(~ a::J {3) ::J ((~ a::J~ {3) ::J a).Applicando due volte L12 si ottiene che r I- a.

D Teorema 13 Se r F a, allora r I- a.

Dimostrazione Se non si dà il caso che r I- a, allora per L45 r, ~ a è coerente in S. Ma se r, ~ a è coerente in S, allora per L44 è soddisfaci­bile. Questo significa che in qualche struttura esiste un'assegnazione che soddisfar e non soddisfa a, quindi non si dà il caso che r f= a.

D Esercizio 1 Nella dimostrazione diL41 si assume che, se T + r ha un modello numerabile, allora r ha un modello. Perché questa assunzio­ne è legittima?

Esercizio 2 Dimostrare quanto segue:

Lemma 46 Se T ha un modello, allora Te coerente.

8.2. Completezza e insiemi di strutture Da T13 risulta che S è completo rispetto a il, cioè che la conseguenza logica rispetto a il implica la derivabilità in S. In generale, la completezza rispetto a il può essere dimostrata per qualsiasi teoria. Per rendersene conto basta pensare che T13 è ottenuto combinando L44 con L45. Dato che per qualsiasi teoria T vale L44 e si può dimostrare un lemma equivalente a L45, risulta che, se r F a, allora r 1-T a. Questo fatto non dovrebbe sorprendere: il "potere" deduttivo di ogni teoria è almeno pari a quel­lo di S, quindi tutto ciò che è derivabile in S è derivabile in ogni teoria. Si noti, tuttavia, che la completezza di T rispetto a il non implica la

94

completezza di T rispetto a qualsiasi sottoinsieme di il. Questo risul­tato è ovvio, se si pensa che un enunciato a del linguaggio di Tè vali­do rispetto a un sottoinsieme di il se è vero in qualche modello di T. Godel ha dimostrato che nel linguaggio di una teoria aritmetica si possono formulare enunciati che sono veri in qualche modello della teoria ma non sono dimostrabili nella teoria. Di questo tratta il celebre teorema, al quale si alludeva nell'Introduzione. I limiti del teorema di completezza, dunque, sono in un certo senso opposti a quelli del teorema di correttezza. Nel caso della correttezza l'attribuzione della proprietàsimpliciterè più impegnativa dell'attribu­zione della proprietà rispetto a un sottoinsieme proprio di il, in quan­to la prima implica la seconda ma non ne è implicata. La correttezza simplicitervale solo per una teoria del grado di generalità di S. Per una teoria più specifica si può dimostrare al massimo la correttezza rispet­to a un sottoinsieme proprio di il. Al contrario, nel caso della comple­tezza l'attribuzione della proprietà simpliciter è la meno impegnativa. Una teoria può essere completa rispetto a il pur non essendo comple­ta rispetto a questo o quel sottoinsieme proprio di il.

8.3. Il "significato" dei teoremi di correttezza e di completezza I teoremi di correttezza e di completezza mostrano che la rela'.?ione semantica di conseguenza logica e la relazione sintattica di derivabili­tà permettono di caratterizzare uno stesso insieme di coppie ordinate (f, a) in cui r è un insieme di enunciati e a è un enunciato. Assumen­do che ciascuna coppia (f, a) costituisca una rappresentazione forma­le di un insieme di argomenti deduttivamente validi - gli argomenti della formar; a -, conseguenza logica e derivabilità forniscono due modi diversi di caratterizzare uno stesso insieme di argomenti dedut­tivamente validi. Questo è senza dubbio un fatto interessante. Ma secondo molti non è tutto: il "significato" dei teoremi di correttezza e di completezza non si riduce a una mera equivalenza tra due caratteriz­zazioni formali. Spesso una teoria corretta viene descritta come una teoria il cui apparato deduttivo non permette di derivare cose che non vogliamo derivare, cioè legittima solo inferenze intuitivamente accet­tabili. Una teoria completa, invece, viene descritta come una teoria il

95

cui apparato deduttivo permette di derivare tutto ciò che vogliamo derivare, cioè legittima tutte le inferenze intuitivamente accettabili. In entrambi i casi si ritiene che il risultato garantisca che un dato appara­to deduttivo è adeguato, non che una data semantica è adeguata. L'as­sunzione tacita, quindi, è che la definizione semantica di conseguenza logica e la definizione sintattica di derivabilità non siano sullo stesso piano dal punto di vista teorico. Nel caso specifìco di S, si assume che D7 sia teoricamente prioritaria rispetto alla definizione di derivabili­tà fondata su D 1 O. Il motivo per cui si pensa che D7 meriti uno status privilegiato è che si tende a dare per scontato che una relazione importante, chiamiamola R, sussista tra D7 e una nozione intuitiva, chiamiamola N. In altri termini, N è la nozione di argomento deduttivamente valido che si adotta quando si dice che r; a rappresenta un insieme di argomenti deduttivamente validi. Assumendo che N sia di natura semantica in quanto concerne la verità-, è ragionevole pensare che un legame diret­to sussista tra D7 e N ma non tra Ne D 1 O, quindi che tra le due defi­nizioni sia D7 quella che poggia su una solida base intuitiva. Questo modo di pensare è piuttosto diffuso. La sua diffusione si deve princi­palmente all'opera di Tarsk.i, che per primo ha formulato una definizio­ne rigorosa di conseguenza logica. Tuttavia, è legitt~o chiedersi fino a che punto ci si possa spingere nella direzione indicata da Tarsk.i. Per rispondere a questa domanda, occorre qualche delucidazione a propo­sito di N e di R. Pur non essendo del tutto chiaro che cosa sia un argomento deduttiva­mente valido in senso intuitivo, è plausibile pensare che N includa almeno due condizioni. La prima è la condizione modale: in un argo­mento deduttivamente valido è impossibile che le premesse siano vere e la conclusione sia falsa. In altri termini, un argomento deduttivamen­tevalido preserva necessariamentela verità. La seconda è la condizione formale: un argomento deduttivamente valido esemplifica una forma valida. Qui "forma valida" può essere inteso come "forma esemplifica­ta solo da argomenti che preservano necessariamente la verità". L'idea di preservazione necessaria della verità è chiaramente preteorica, in quanto può essere compresa senza conoscere la logica. Basta riflettere

96

su una dimostrazione come quelle presentate nel paragrafo 1. 5 per rico­noscere che in alcuni argomenti è impossibile che le premesse siano vere e la conclusione sia falsa. L'idea di forma valida, invece, è teorica­mente più impegnativa, poiché presuppone una distinzione tra costan­ti logiche ed espressioni non logiche. Questo signifìca che N è intuiti­va al massimo in senso relativo, cioè più intuitiva di D7. D'altra parte, quale nozione è intuitiva in senso assoluto? Nel caso di R ci sono almeno due opzioni. Si potrebbe sostenere che R è lequivalenza estensionale, cioè la relazione che sussiste tra due predi­cati quando gli oggetti ai quali si applicano sono esattamente gli stessi. Ad esempio, "acqua'' e "H

2 O" sono predicati estensionalmente equiva­

lenti, poiché tutto ciò che cade sotto il primo cade sotto il secondo e viceversa. Oppure si potrebbe sostenere che R è l'analisi concettuale, cioè la relazione che sussiste tra due predicati quando uno dei due fornisce un'analisi del concetto espresso dall'altro, riducendolo ad altri concetti che sono più semplici o prioritari dal punto di vista esplicati­vo. Ad esempio, "uomo adulto non sposato" può essere considerato un'analisi concettuale di "scapolo". Il secondo modo di intendere R è più forte del primo: l'analisi concettuale implica l'equivalenza estensio­nale, ma non ne è implicata. Quindi, se D7 fornisce un'analisi concet­tuale di N, allora è estensionalmente equivalente a N, ma non vale l'inverso. La tesi secondo cui R sussiste tra D7 e N può ora essere esarriinata, assu­mendo che N contempli un insieme di forme esprimibili mediante le costanti logiche di L. Se R è intesa come equivalenza estensionale, sembra corretto dire che R sussiste tra D7 e N. Si consideri il seguente condizionale:

1. Se f; a è una forma valida, allora f I= a.

Supponiamo che il conseguente di 1 sia falso, cioè che esista una strut­tura A che è modello di f ma non di a. Allora esiste un argomento che esemplifica f; a e ha premesse vere ma conclusione falsa, cioè un argomento costruito rimpiazzando le costanti logiche che occorrono in f; a con le corrispondenti espressioni italiane, e le espressioni non

97

logiche che occorrono in f; a con espressioni italiane il cui significato è adeguatamente rappresentato in A. Dato che un argomento del genere non è valido, ne risulta che l'antecedente di 1 è falso. Per giusti­ficare il condizionale inverso è sufficiente assumere, come ha suggerito GeorgKreisel (n. 1923), che l'apparato deduttivo di S sia costruito in modo tale che tutte le derivazioni in S corrispondano a forme valide. In altri termini:

2. Se r ~ a, allora r; a è una forma valida.

Infatti, da 2 e T13 si ottiene:

-3. Se f I= a, allora f; a è una forma valida.

Da 1 e 3 risulta che D7 è estensionalmente adeguata rispetto a N. Se R è intesa come analisi concettuale, invece, non è ovvio che si possa a buon diritto asserire che Rsussiste traD7 e N. Innanzitutto, conside­razioni di carattere generale inducono a dubitare che N, così come qualsiasi altra nozione interessante, sia suscettibile di analisi concet­tuale. Pur assumendo che esistano casi non controversi di analisi concettuale, come quello di "scapolo", resta aperta la questione se esistano casi non controversi e allo stesso tempo non banali. La storia della filosofia è costellata di tentativi falliti di definire nozioni interes­santi in termini di altre nozioni, e forse il successo di un tentativo del genere è più un miraggio che un'eccezione. In secondo luogo, non è chiaro se D7 sia in grado di "catturare" la componente modale impli­cita in N. Nell'argomento "Ogni balena è bianca, Moby Dick è una balena; Moby Dick è bianca" la legittimità dell'inferenza sembra dipendere dal fatto che tutte le situazioni possibili che siamo in grado di immaginare in cui ogni balena è bianca e Mo by Dick è una balena sono situazioni in cui Mo by Dick è bianca. Ma D7 implica una quan­tificazione su strutture, quindi su significati che possono essere asse­gnati alle espressioni non logiche di L. Questo, come ha osservato John Etchemendy (n. 1952), sembra non avere un corrispettivo a livello preteorico. Quando pensiamo alla cogenza dell'argomento, non

98

pensiamo all'eventualità che "bianca'' significhi "rosa" e constatiamo che anche in quel caso la conclusione sarebbe vera se lo fossero le premesse. Chiunque voglia sostenere che D7 forn.isce un'analisi concettuale di N deve scontrarsi con questa differenza apparente. La tesi secondo cui R sussiste tra D7 e N, dunque, risulta facilmente sostenibile solo nel caso in cui R sia intesa come equivalenza estensio­nale. Questo non significa che la legittimità di D7 sia in pericolo. Non c'è motivo di pensare che qualcosa di diverso dall'adeguatezza estensio­nale sia necessario per giustificare D7. Il fatto importante, tuttavia, è che sulla base dell'adeguatezza estensionale non si può motivare lo status privilegiato attrib1:1-ito a D7. Infatti, quello che vale per la conse­guenza logica vale pure per la derivabilità in S. Da 1 e T13 si ottiene:

4. Se f; a è una forma valida, allora r ~ a.

Da 2 e 4 risulta che D 1 O è estensionalmente adeguata rispetto a N. Quindi le due definizioni sono esattamente sullo stesso piano. Si noti, inoltre, che il ragionamento che permette di concludere che D7 è estensionalmente adeguata, come quello appena considerato, fa uso del teorema di completezza. Pertanto, è difficile vedere come la tesi dell'adeguatezza estensionale di D7 possa essere invocata per attribui­re un senso al teorema stesso. Da quanto precede risulta dunque che alcune delle cose che si dicono di solito a proposito dei teoremi di correttezza e di completezza sono quantomeno controverse. Forse la definizione di derivabilità può esse­re giustificata sulla base di qualche nozione preteorica di natura semantica. Ma non è ovvio che la definizione di conseguenza logica esprima tale nozione, quindi non è ovvio che la definizione di conse­guenza logica possa giustificare la definizione di derivabilità senza aver bisogno essa stessa di giustificazione. Le due definizioni esprimono nozioni tecniche diverse nessuna delle quali coincide con la nozione preteorica, anche se quest'ultima permette di misurare la plausibilità di entrambe. I teoremi di correttezza e di completezza dicono che le due nozioni tecniche hanno la stessa estensione, quindi se una delle due è plausibile anche l'altra lo è. Non c'è nessun "significato" oltre questo.

99

Soluzioni degli esercizi

1. Sia Ail modello numerabile di T +f. Ogni teorema di T + r è soddisfatto da tutte le assegnazioni in A. Ma ogni elemento di f è un teorema, poiché r è costituito da formule chiuse aggiunte a T come assiomi. Quindi, ogni formula in f è vera in A. 2. Assumiamo che T abbia un modello A. Supponiamo che T sia incoerente. Allora per qualche a, ~T a e ~T~ a. Ne risulta che a e~ a sono soddisfatte da tutte le assegnazioni in .A, il che è impossibile.

100

9. Modelli e cardinalità

9.1. Numeri cardinali Unadelleragionidell'importanzadiTlO, come risulta dal paragrafo 8.1, è il ruolo cruciale che svolge nella dimo­strazione del teorema di completezza. Ma ce ne sono altre. In questo capitolo vengono presentati due risultati ben noti che si ottengono facilmente a partire da TI O. Siccome entrambi i risultati hanno conse­guenze che implicano la nozione matematica di cardinalita, è meglio prima chiarire questa nozione. Consideriamo il caso dçgli insiemi finiti. Nel paragrafo i.4 si è detto che un insieme finito è un insieme che contiene n elementi per qual­che n. Quindi, è naturale pensare che il numero n esprima la grandez­za dell'insieme. Ad esempio, {2, I, 3} è più grande di {2, l}, perché il primo insieme contiene tre elementi mentre il secondo ne contiene due. Se si identificano i numeri naturali con insiemi, come ha sugge­rito John von Neumann (1903-1957), si può formulare questo pensiero in modo rigoroso. Assumiamo che O= 0 e che, per ogni n> O, n ={O, ... , n - l}. Il numero cardinale di un insieme finito A può esse­re definito come il numero n tale che A è in corrispondenza biunivo­ca con n. Ad esempio, il numero cardinale di { 2, 1, 3} è 3, mentre quel­lo di { 2, 1} è 2. Consideriamo ora gli insiemi infiniti. In questo caso non si può espri­mere la grandezza di un insieme con un numero naturale. Infatti, come risulta dal paragrafo i.4, se A è infinito, allora per definizione non esiste un n tale cheA contiene esattamente n elementi. Ma un'a­nalogia importante rimane: anche in questo caso si può misurare la grandezza diA sulla base della corrispondenza biunivoca traA e qual­che insieme. La nozione di numero transfinito introdotta da Georg Cantar ( 1845-1918) risponde all'esigenza di esprimere una grandez­za del genere. Il numero transfinito assegnato a w si chiama N0•

Dunque ogni insieme che sia in corrispondenza biunivoca con w, cioè ogni insieme numerabile, ha come numero cardinale N0• Cantar ha dimostrato che N0 è il più piccolo numero transfinito, e che per ogni numero transfinito Nn ne esiste uno più grande Nn+l' cioè il cardinale

101

successivo. Un esempio di numero transfinito maggiore di X 0 è c, il numero che si assegna a l1t Questo numero è chiamato "cardinale del continuo". I numeri cardinali forniscono una scala di misurazione per la grandez­za degli insiemi. La cardinalità di un insieme qualsiasi è data dal nume­ro cardinale - naturale o transfinito - associato all'insieme. Dire cheA è più grande di B significa dire che la cardinalità di A è maggiore di quella di B. Ad esempio, R. è più grande di w. Dire che A e B hanno la stessa grandezza significa dire che hanno la stessa cardinalità. Ad esem­pio, l'insieme dei numeri pari e w hanno la stessa grandezza, poiché hanno entrambi cardinalità X0.

D;ill'ultimo esempio risulta chiaro che il senso di "grande" così precisato non coincide con quello che potrebbe venire in mente considerando la relazione di sottoinsieme proprio definita nel para­grafo 1+ Se A è sottoinsieme proprio di B, è naturale pensare che B sia più grande di A. Infatti, B contiene oggetti che A non contiene: il tutto è maggiore della parte. Ma il criterio della cardinalità non è questo. Non si può dire che A è sottoinsieme proprio di B sse la cardinalità di B è maggiore di quella di A. Sebbene l'equivalenza valga per gli insiemi finiti, non vale per quelli infiqiti. Un insieme infinito può essere sottoinsieme proprio di un altro insieme pur aven­do la stessa cardinalità. È il caso, appunto, dell'insieme dei numeri pari edi w. La nozione di cardinalità costituisce uno strumento teorico prima­rio, poiché può essere impiegata nella descrizione delle strutture. Siccome il dominio di una struttura .A è un insieme di oggetti A, si può parlare della cardinalità di .A facendo riferimento alla cardina­lità diA. Per rendere chiaro il discorso sulla cardinalità delle struttu­re, i numeri cardinali saranno indicati con lettere greche, e i simboli <, >, ~e;;::: saranno usati per i numeri cardinali così come per gli altri numeri.

Nota 0 è in corrispondenza biunivoca con O, poiché è in corrispon­denza biunivoca con 0. Per convincersi di questo fatto bisogna pensa­re che le definizioni di relazione, funzione, funzione iniettiva e corri-

102

spondenza biunivoca fornite nel paragrafo i.4 risultano soddisfatte in modo vacuo.

Esercizi o 1 Fornire una definizione di insieme finito in termini di cardi­nalità.

Esercizio 2 Se A eB sono insiemi di cardinalitàX0, qual èla cardina­litàdiA U B?

9.2. Teorema di Lowenheim-Skolem Il primo dei due risulta­ti che si ottengono a par~ire da T 1 O è un teorema che solitamente viene associato ai nomi di Leopold Lowenheim (1878-1957) e Thoralf Skolem (1887-1963):

Teorema 14 Se T ha un modello, allora T ha un modello numerabile.

Dimostrazione Tl4consegueda TlOeL46.

o Il teorema di Lowenheim-Skolem è interessante non solo per ciò che enuncia, ma anche per le conseguenze che permette di trarre. Una è la . seguente:

Teorema 15 Se T ha un modello di cardinalita maggiore di NO' allora T ha un modello di cardinalita X

0.

Dimostrazione Assumiamo che T abbia un modello di cardinalità maggiore di X0. Siccome T ha un modello, da T 14 si ottiene che T ha un modello di cardinalità X0.

o Un esempio di applicazione di Tl5 è il seguente. Supponiamo che T verta sui numeri reali, e pertanto che una struttura che abbia come domi­nio R. sia modello di T. Dato che e > X0, T ha un modello di cardinalità maggiore di X0• Per Tl S ne consegue che T ha un modello di cardinali­tàX0. Un esempio analogo è il seguente. Supponiamo che T sia una teoria geometrica e che una struttura che abbia come dominio un insieme non

103

numerabile di punti sia modello di T. Di nuovo, per Tl S esiste un model­lo numerabile di T. Esempi come questi mostrano che c'è un limite ben preciso alla capacità delle teorie di caratterizzare iloro modelli intesi. Una teoria non è in grado di fornire una descrizione adeguata del suo model­lo inteso nel caso in cui questo modello sia di cardinalità maggiore di N0•

La descrizione non è adeguata nel senso che si applica altrettanto bene a un modello di cardinalità N0 diverso dal modello inteso. Una generalizzazione ulteriore può essere ottenuta sulla base del

seguente lemma:

Lemma 47 Se K:;;; o e T ha un modello di cardinalita K, allora T ha un modello di cardinalita o.

Dimostrazione Sia .A un modello di T di cardinalità K. SiaA' un insieme di cardinalità o tale cheA ç;;A' e K:;;; o. Sia .A:' una struttura con dominio A' che concorda con .A: sui valori assegnati alle costanti indi­viduali ed è ottenuta nel modo seguente. Innanzitutto, chiamiamo A' - A l'insieme degli elementi diA' che non appartengono aA. Dato un elemento e diA, stabiliamo poi che tutti gli elementi di A' -A si comportino come c. Questo significa che, per ogni CO$tante predicati­va a n posti P e ogni n-upla (a

1, ••• ,a) di elementi di A', (al' ... , a) E

[P].Aisse (b1, .•• , b,,) E [P]A, dove

{a. sea.EA

b. I I z- I - e sea.EA -A

I

Lo stesso vale per i simboli di funzione. Chiaramente, ogni formula è soddisfatta da tutte le assegnazioni in .A:' sse è soddisfatta da tutte le

assegnazioni in .A. Perciò .A:' I= T. o

L47 permette di ottenere il teorema seguente, che generalizza T 14:

Teorema 16 Per ogn.i K ~ NO' se T ha un modello, allora T ha un model­lo di cardinalita K.

Dimostrazione Assumiamo che T abbia un modello e che K~ N0• Per

104

T 14, T ha un modello di cardinalità N0• Applicando L47, si ottiene che T ha un modello di cardinalità K.

Un corollario interessante di Tl6, esposto per la prima volta da Skolem, riguardale teorie aritmetiche. Si consideriPA. Un modello standard diPA è una struttura che rendeveriA8-Al6 in un dominio composto da elementi ciascuno dei quali si ottiene a partire da O appli­cando un numero fìnito di volte l'operazione di passaggio al successo­re (si veda l'esercizio 6.2). Un modello non standard diPA, invece, è un modello che non ha questa caratteristica. Il corollario di Tl6 è il seguente:

Teorema 17 Esistono modelli non standard di PA.

Dimostrazione PA ha un modello di cardinalità N0

, come si è visto. Per Tl6, questo implica l'esistenza di un modello non numerabile di cardinalità maggiore di N0• Siccome tale modello non è standard, esiste un modello non standard di PA.

o Nota La portata del teorema di Lowenheim-Skolem si estende anche in una direzione ulteriore che non è stata considerata in questo para­grafo. La formulazione di T 14 presuppone che il linguaggio della teoria sia di cardinalità N0, cioè sia un linguaggio il cui vocabolario è un insieme di simboli di cardinalità N0• Ma è possibile immaginare anche linguaggi di cardinalità maggiore di N0• Nel caso in cui si voglia consi­derare un insieme [di formule di un linguaggio di cardinalità N,,, con n> O, il teorema può essere riformulato come segue: se [ha un model­lo, allora ha un modello di cardinalità N .

Il

Esercizio 3 Tl 4 potrebbe essere dimostrato se si sostituisse "model­lo" con "modello normale"?

9.3. Teorema di compattezza llsecondorisultatochesiottiene a partire da TlO è un teorema che concerne una proprietà semantica chiamata compattezza:

105

Definizione 22 Te compattasse, se ogni sottoinsieme finito dell'insieme degli assiomi propri di T ha un modello, allora T ha un modello.

La prima dimostrazione della compattezza di un sistema risale a Godel. Qui il teorema di compattezza sarà giustificato per una teoria qualsiasi sulla base di quanto precede.

Teorema 18 Se ogni sottoinsieme finito dell'insieme degli assiomi propri di T ha un modello, allora Tha un modello.

Dimostrazione Assumiamo che T non abbia un modello. Allora T non ha un modello numerabile. Da Tl O ne risulta che Tè incoerente. Quindi, per qualche a esiste sia una dimostrazione in T di a sia una dimostrazione in T di~ a. Questo significa che, per qualche sottoin­sieme finito b.. di assiomi propri di T, le due dimostrazioni usano solo assiomi propri in b... Sia T'una teoria nel linguaggio di T che ha b.. come insieme degli assiomi propri. Allora 1-r a e 1-r~ a, dunque T'è incoerente. Per L46, ne consegue che T' non ha un modello. Da L40 si ottiene che non c'è una struttura in cui ogni assioma proprio di T'è vero. Quindi, esiste un sottoinsieme finito degli assiomi propri di T che non ha un modello, cioè b...

D L'importanza del teorema di compattezza può essere apprezzata consi­derando alcune sue applicazioni. Torniamo aPA. Come risulta dal paragrafo 9.2, T16 permette di dimostrare l'esistenza di modelli non standard diPA che non sono numerabili. Dunque, ci si potrebbe chie­dere se esistano anche modelli non standard numerabili. Il teorema di compattezza fornisce una risposta affermativa a questa domanda:

Teorema 19 Alcuni modelli non standard di PA sono numerabili.

Dimostrazione Sia L~2 un linguaggio ottenuto aggiungendo a L Al

una costante individuale c. Sia T una teoria in L~2 ottenuta aggiungen­do ad Al-Al 6 unalistainfinitadiassiomiO *e, 1 ;t:.c,2*- c ... , cioè uno per ogni numero naturale. Ora si consideri un sottoinsieme finito r

106

degli assiomi di T. f può includere al massimo un numero finito di assiomi nuovi. Quindi, una struttura che assegni a e un numero che non compare negli assiomi nuovi in f ma per il resto sia esattamente come un modello standard diPA sarà modello dir. Ad esempio, nel caso in cui f = {O * e, 1 * e, 2 ;t:.c}, una struttura che assegni 3 a e sarà modello dir. Ma se ogni sottoinsieme finito degli assiomi di T ha un modello, per T 18 anche T ha un modello. Di conseguenza, per T 14 ha un modello numerabile. Sia A tale modello. Sia A' un modello normale numerabile costruito a partire da A nel modo considerato nell'esercizio 6.7, cioè tale che gli elementi di A' siano insiemi di elementi diA che risult~no equivalenti rispetto alla relazione 1--Tt = t' per un insieme di termini chiusi t, t' ... appositamente definito. Dato che gli assiomi nuovi di T sono veri in A', in A' deve esserci almeno un elemento diverso da ogni numero naturale, cioè l'elemento deno­tato da c. Quindi A' non è standard. Siccome Tè un'estensione di PA, A' è modello diPA.

Un'altra conseguenza interessante del teorema di compattezza impli­ca la nozione di modello finito arbitrariamente grande. Per un insieme di enunciati r, affermare che r ammette modelli finiti arbitrariamen­te grandi significa dire che, per ogni n, esiste un m ;;::: n tale che r ha un modello di cardinalità K = m.

Lemma 48 Se f ammettemodellinormalifinitiarbitrariamentegran­di, allora r ha un modello infinito.

Dimostrazione Assumiamo che r ammetta modelli normali finiti arbitrariamente grandi. Per ogni n, sia a

11 l'enunciato della forma

Vx1Vx, ... Vx 13x (x ;t:.x1 A ... Ax *-X 1),dovex1,x2,x, ... siriferi-- n- 11 n 11 11- :J

scono alla prima variabile del linguaggio, alla seconda, alla terza e così via. a è vero in un modello normale solo se la cardinalità del modello

1l

è maggiore o uguale an (si veda l'esercizio 5.2). Sia f* r U { a 1, ar.} il risultato dell'aggiunta di tutti gli a,, a r. Ogni sottoinsieme finito di f* è un sottoinsieme dir u {al' ... , a111} per qualche m, quindi ha un modello normale di cardinalità maggiore o uguale a m. Per T18, una

107

teoria che abbia f* come insieme di assiomi propri ha un modello. Tale modello, rendendo vero an per ogni n, ha cardinalità infinita. Ne consegue che r ha un modello infinito.

o Un corollario diretto di L48 è il teorema che segue:

Teorema 20 Se gli assiomi propri di T ammettono modelli normali finiti arbitrariamente grandi, allora T ha un modello infinito.

Dimostrazione Sia f l'insieme degli assiomi propri di T. Assumiamo che r ammetta modelli normali finiti arbitrariamente grandi. Per L48, r ha un modello infinito. Da questo e L40 si ottiene che T ha un modello infinito.

o Nota T 17 e T 19 vertono su PA. Ma risultati analoghi possono esse­re dimostrati per altre teorie aritmetiche, come quelle considerate nel paragrafo 5.2. Questo significa che le conseguenze dei teoremi di Lowenheim-Skolem e di compattezza relative ai modelli non standard valgono per l'aritmetica in generale.

Esercizio 4 Fornire un esempio con dimostrazione di enunciato che ammette solo modelli infiniti.

108

Soluzioni degli esercizi

1. Un insieme A è fìnito sse la cardinalità di A è n per qualche n. 2. N0. Si veda l'esercizio 2.1.

3. No. Un teorema come TlO non è dimostrabile per i modelli normali (si veda l'esercizio 6.6). Quindi, lo stesso vale perT14. 4. Data una costante predicativa a due posti R, il seguente enunciato non ammette modelli finiti:

Vx3yRxy A VxVy~ (Rxy ARyx) A Vx'Vy'Vz((Rxy ARyz)~Rxz)

Si noti innanzitutto che l'enunciato ha un modello, basta pensare a una struttura con dominio OJ in cui R sia interpretata come <. Per vedere che non ammette modelli finiti, consideriamo una struttura finita .A Siano m 1, .•• , mkglielementi diA. Sian0 = m1• Per il primo congiunto, deve esserci almeno un elemento diA con il quale n0 è nella relazione R. Sia n1 il primo elemento della lista per cui questo vale. Quindi (n0,

n1) E [R]A. Per il secondo congiunto, non è possibile che (n0, n 1) E [R]A e (n 1, n0) E [R]A, dunque n 1 -:t= n0• Per il primo congiunto, di nuovo, deve esserci almeno un elemento diA con il quale n 1 è nella rela­zione R. Sia n2 il primo elemento della lista per cui questo vale. Quin­di, (n1, n2) E [R]A. Per il terzo congiunto, (n0, n2) E [R]A. Per il secon­do, di nuovo, n

2 -:t= n

1 e n2 -:t= n0• Continuando in questo modo si ottiene

chen3

è diverso dan0, nl' n2

e così via. Ma una volta arrivati ank, saran­no terminati gli elementi di A. Dunque, c'è bisogno di una struttura infinita.

109

10. Relazioni tra modelli

10.1. Isomorfismo Ci sono ancora due nozioni importanti che occorre chiarire per chiudere il discorso sulle proprietà semantiche delle teorie iniziato nel capitolo 6. La prima è quella di isomorfismo, che risponde a un'idea piuttosto chiara a livello intuitivo: due struttu­re possono avere la stessa forma, anche se differiscono nel contenuto. Questa idea può essere formulata in modo preciso se si definisce la seguente relazione tra due strutture A e 13 per un linguaggio L:

De_finizione 23 Un'immersione di A in 13 rispetto a Le una funzione inietti va F: A - B tale che: 1. per ogni costante individuale c, F([c]) = [c] i 2. per ogni costante predicativa a n posti P e ogni n-upla (a

1, .. ., a) di

elementi diA, (a1, .. ., a) E [P] Asse (F(a1), .. .,F(a,,)) E [P] i 3. per ogni simbolo di funzione a n posti f e ogni n-upla (a

1, .. ., a,,) di

elementi diA, [/] )a1, .. ., a,,)=[/] iF(a1), .. .,F(a,,)).

In sostanza, le espressioni non logiche di L si componano con i valori di F nello stesso modo in cui si comportano con i rispettivi àrgomen­ti. Se F è una funzione daA su B, si dice che F è un'immersione isomor-

fa. La nozione di isomorfismo può quindi essere precisata come segue:

Definizione 24 A e 13 sono isomorfe sse esiste un'immersione isom01fo di Ain 13 rispetto a L.

Dire che A e 13 sono isomorfe significa dire che esiste una corrispon­denza biunivoca tra A e B rispetto alla quale l'interpretazione delle espressioni non logiche di L resta invariata. Ora si dimostrerà un teorema fondamentale che verte sull'isomorfi­smo. Per farlo, occorre prima dimostrare il seguente lemma:

Lemma 49 Se F e un'immersione isomorfa di A in 13 rispetto a L, V e un'assegnazione in A e v' e un'assegnazione in 13 tale che, per ogni varia-

110

bile x di L, [x] 'B,v' = F( [x ]A)' allora v soddisfa una formula a di L sse v' soddisfa a.

Dimostrazione La dimostrazione è per induzione sulla complessità di a, assumendo che F sia un'immersione isomorfa di A in 13 e che ve v' soddisfino la condizione richiesta. Base.Assumiamo che a sia unaformulaatomicaPt1, .. .,tn. Per 1 $i$ n, [t.],,, , = F([t.] , ). Questo si può dimostrare per induzione sulla

l D,V I .rt,V

complessità di t .. Infatti, set. è una costante individuale vale D23. l, se è I I

una variabile vale la condizione richiesta dal lemma, mentre il caso dei termini complessi dipençl.e dai primi due per D23.3. Siano dunque al' .. .,

angli elementi diA denotati da t 1, .. ., tn relativamente a v eF(a1), .. .,

F(a ) gli elementi di B denotati da t 1, .. ., t relativamente a v'. Per n n

D23.2,(a1, .. .,a) E [P]Asse(F(a1), .. .,F(a,,))E [P]15

Quindi, vsoddi-sfa a sse v' soddisfa a. Passo. Assumiamo che ogni formula di complessità minore o uguale a n sia soddisfatta da v sse è soddisfatta da v'. Se a è una formula di complessità n + 1, i casi possibili sono tre. Caso 1: a ha la forma ~ {3. In questo caso v soddisfa asse non soddisfa {3. Per ipotesi di induzione, v non soddisfa f3 sse v' non soddisfa {3. Siccome v' non soddisfa f3 sse soddisfa a, ne risulta che v soddisfa a sse v' soddisfa a. Caso 2: a ha la forma f3 ~ r. In questo caso v soddisfa asse non soddi­sfa f3 o soddisfa y. Per ipotesi di induzione, v non soddisfa f3 sse v' non soddisfa f3 e v soddisfar sse v' soddisfa y. Siccome v' soddisfa a sse non soddisfa f3 o soddisfa y, ne risulta che v soddisfa asse v' soddisfa a. Caso 3: a ha la forma "il xf3. In questo caso v soddisfa asse ogni x­variante div soddisfa {3. Sia v. unax-variante div. Sia v: un'assegnazio­

ne tale che, per ogni variabile y, [y] 'B,v'. F([y ]A.u)' quindi tale che [ x] 'B,v'. = F( [x ]A.u). Per ipotesi di induzione, v. soddisfa f3 sse v~ soddi­sfa {3. Ma v~ non è altro che unax-variante div'. Dunque, per ognix­variante di vin A esiste una X-variante di v' in 13 che soddisfa f3 sse la prima soddisfa {3. SiccomeF è una funzione daA suB, in 13 non esisto­no x-varianti div' che non corrispondano a nessunax-variante div in

111

A. Quindi, ogni x-variante di v soddisfa f3 sse ogni x-variante di v' soddisfa {3. Questo significa che v soddisfa asse v' soddisfa a.

D Il teorema che può essere dimostrato sulla base di L49 è il seguente:

Teorema 21 Se A e 'E sono isomorfe, ogni formula a e soddisfatta da tutte le assegnazioni in Asse e soddisfatta da tutte le assegnazioni in 'B.

Dimostrazione SiaF un'immersione isomorfa di .Ain 13. Assumiamo che a non sia soddisfatta da tutte le assegnazioni in .A, cioè che in A esista un'assegnazione v che non soddisfa a. Allora anche in 'E deve esi~tere un'assegnazione che non soddisfa a. Infatti, se si considera un'assegnazione v' tale che, per ogni variabile x, [x J '8,v' = F([x ].A,)' per L49 si ottiene che v' non soddisfa a. Quindi, se a è soddisfatta da tutte le assegnazioni in 1?, allora è soddisfatta da tutte le assegnazioni in A. Il condizionale inverso si ottiene in modo analogo assumendo che a non sia soddisfatta da tutte le assegnazioni in 13.

D Una conseguenza diretta di T21 è che due strutture isomorfe assegna­no lo stesso valore di verità a ogni enunciato. Per esprimere questo fatto si usa la seguente definizione: A e 'E sono equivalenti, in simbo­li A= 13,sseperognienunciato a,[a]A = 1 sse [a]'B= I.Il teorema che si ottiene è il seguente:

Teorema 22 Se Ae 13sono isomorfe, allora A= 'B.

Dimostrazione Assumiamo che A e 13 siano isomorfe e che a sia un enunciato. Sappiamo che [a J A= 1 sse a è soddisfatto da tutte le asse­gnazioni in A. Ma per T21, a è soddisfatto da tutte le assegnazioni in Asse è soddisfatto da tutte le assegnazioni in 1?, cioè sse [a J '8 = 1.

L'isomorfismo riguarda non solo i singoli enunciati ma anche le teorie. Un'altra conseguenza di T21, infatti, è la seguente:

Teorema 23 Se Ae 13sono isomorfe, allora A I= T sse 131= T.

112

Dimostrazione Assumiamo che A e 'E siano isomorfe. Perogni a tale che f-T a, T21 implica che a è soddisfatta da tutte le assegnazioni in A sse è soddisfatta da tutte le assegnazioni in 13. Quindi, A I= T sse 1? I= T.

Nota La relazione fra strutture sulla quale verte T22 è spesso chiama­ta "equivalenza elementare": invece di dire che A e 'E sono equivalen­ti, si dice che sono "elementarmente equivalenti".

Esercizio 1 Se A e 1? sono strutture infinite di cardinalità diversa, è possibile che siano isomorfe?

Esercizio 2 Dati due linguaggi Le L' tali che L'è ottenuto aggiungen­do aL una costante individuale c, se esiste un'immersione isomorfa di .Ae 'E rispetto a L, esiste un'immersione isomorfa di A e 'E rispetto aL'?

10.2. Categoricità La seconda nozione da chiarire presuppone la prima: la categoricita è una proprietà di teorie definita in termini di isomorfismo. Il modo più semplice di definire la categoricità è il seguente:

Definizione 25 Te categorica sse tutti i modelli di T sono isomorfi.

D25 fornisce un criterio "assoluto" di categoricità, nel senso èhe impli­ca una quantificazione sui modelli di T senza restrizioni di alcun gene­re. Il limite di questa definizione, tuttavia, è che impone una condizio­ne talmente forte da rendere la nozione di categoricità praticamente inapplicabile. Si consideri il seguente teorema:

Teorema 24 PA non e categorica.

Dimostrazione PA ha un modello numerabile. Ma per Tl 7 ammette pure un modello non numerabile. Siccome non può esserci isomorfi­smo tra un modello numerabile e un modello non numerabile (si veda l'esercizio 10.1), PA non è categorica.

D

113

Si noti che T24 non dipende da qualche caratteristica specifica diPA, ma semplicemente dal fatto chePA ammette modelli numerabili. Infat­ti, T16 permette di inferire l'esistenza di un modello non numerabile per qualsiasi teoria con questa proprietà. Se si aggiunge che per Tl 4 qualsiasi teoria che abbia un modello ammette modelli numerabili, si può concludere che nessuna teoria che abbia un modello è categorica. Le cose non migliorano molto se si considerano solo i modelli norma­li. In quel caso non si può applicare T 14, quindi non si può conclude­re che nessuna teoria che abbia un modello normale è categorica. Infat­ti, esistono teorie categoriche con modelli normali finiti. Si consideri una teoria T con i seguenti assiomi propri: (i) .3x3y(x:;t:yA 'Vz(z=xv z=y)) (iif 3xPx A~ 'V xPx Siano A e 13 strutture normali. Supponiamo che A I= T. Allora A contiene esattamente due elementi, chiamiamoli a e b, perché rende vero (i). Inoltre, per rendere vero (ii) uno solo dei due elementi, ad esem­pio a, deve appartenere a [P]A.Pertanto,A ={a, b} e [P]A ={a}.Suppo­niamo ora che 13 j= T. AlloraB {a', b'} e [P]'B= {a'} o [P]'B= {b'}. Se B ={a', b'} e [P] 'B {a'}, allora esiste un'immersione isomorfa di Ain 13, cioè la funzione F tale che F(a) a' e F( b) = b'. AI.lo stesso modo, seB ={a', b'} e [P]'B= {b'}, allora esiste un'immersione isomorfa di A in 13,cioèlafunzione Gtaleche G(a) b' e G(b) =a'. Quindi, Tè cate­gorica. Una teoria del genere, tuttavia, non è molto interessante, alme­no non quanto PA. Una definizione diversa di categoricità è la seguente:

Definizione 26 Te categorica nella potenza K sse T ha qualche model­lo di cardinalita K e tutti i suoi modelli di cardinalita K sono isomorfi.

In questo caso il criterio di categoricità è "relativo". D26 implica una quantificazione su un insieme specifico di modelli di T, cioè l'insieme dei modelli di cardinalità K. La proprietà così definita, infatti, è chiama­ta anche K-categoricità. L'espressione "potenza'' indicala cardinalità del modello: un modello di potenza K è un modello di cardinalità K.

La differenza tra D25 e D26 risulta chiara se si pensa che per dimostrare

114

un risultato di non categoricità per PA in termini di D26 non è sufficien­te invocare il fatto che esistono modelli di cardinalità diversa, come nel caso di T24. Quello che si può dimostrare, invece, è il seguente teorema:

Teorema 25 PA non e categorica nella potenza X0•

Dimostrazione Sia A come nell'esercizio 6.2. Siano L~2, Te A' come nella dimostrazione di T19. A e A' sono modelli di PA e hanno entrambi cardinalità X

0• Eppure non sono isomorfi. Supponiamo

infatti che lo siano. Allora esiste un'immersione isomorfaF di Ain A' rispetto aL~2 (si vedal'~sercizio 10.2). Dato cheA = w, ne risultacheF associa l'elemento di A' denotato da ca qualche numero naturale n in A. Dunque l'enunciato c :;t: n è falso in A. Ma lo stesso enunciato è vero in A', essendo A' modello di T. Questo contraddice T22.

o Rispetto alla categoricità intesa nel senso di D26 si possono presenta­re diversi casi. Una congettura avanzata da Jerzy Los ( 1920-1998) è che i casi possibili siano i seguenti: 1. Tè categorica nella potenza K per ogni cardinale transfinito K (in questo caso Tè "totalmente categorica"); 2. Tè categorica nella potenza K sse K > X 0 (in questo caso Tè "non numerabilmente categorica'' ma non totalmente categorica); 3. Tè categorica nella potenza K sse K = X0 (in questo caso Tè "numerabilmente categorica''). La congettura di Los ha generato un ampio dibattito, contribuendo in modo significativo allo sviluppo della teoria dei modelli. I due maggiori programmi di ricerca in questo ambito, chiamati "teoria della classificazione" e "teoria geometrica dei modelli", nascono appunto da una risposta alla congettura di Los fornita da Michael Morley (n. 1930). La risposta è affermativa e poggia su un teorema, chiamato "teorema di categoricità'', che richiede una dimostrazione molto complessa: se Tè coerente, massimale e categorica in qualche potenza K tale che K > X

0, allora T è categorica in ogni potenza D tale

che D > X0

• In altri termini, se Tè categorica in qualche potenza più che numerabile, allora è categorica in ogni potenza più che numera-

115

bile. Il teorema di Morley esclude quindi la possibilità che esista una teoria coerente e massimale che, per due cardinali transfiniti K, o.> X0, sia categorica nella potenza K ma non nella potenza o. Per evitare di complicare troppo le cose, qui sarà dimostrato un teorema più acces­sibile che enuncia una relazione tra la categoricità e un'altra proprietà che figura nel teorema di Morley, ossia la massimalità:

Teorema 26 Se Te coerente e categorica nella potenza K per qualche K ~ XO' allora Te massimale.

Dimostrazione Sia T coerente e categorica nella potenza K per qual­che. K ~ X0• Supponiamo che T non sia massimale. Allora esiste un enunciato a tale che né a né ~ a sono teoremi di T. Sia T+ la teoria T + {a} e r-1a teoria T + {~ a}. T+ e r- sono entrambe coerenti. Quindi per T 1 o hanno un modello. Da T 16 si Ottiene che r+ e r­ammettono modelli infiniti di qualsiasi cardinalità. Siano A e 13 modelli infiniti di cardinalità K per T+ e r-. A e 13 sono modelli di T. Ma non sono isomorfi. Infatti, A rende vero a, mentre 13 rende vero ~ a. Questo contraddice l'ipotesi che T sia categorica nella potenza K.

D Esercizio 3 Fornire un esempio di teoria che non sia categorica nella potenza K per nessun cardinale transfinito K.

10.3. Teoria degli insiemi Aquestopuntosipuòritenereconclu­so il discorso sulle proprietà semantiche delle teorie. La parte rimanen­te di questo capitolo illustra alcuni esempi di teorie diversi da quelli presentati nel capitolo 5, per arricchire il campionario e allargare così la prospettiva sulle applicazioni della logica del prim'ordine. Il primo caso che sarà considerato è quello della teoria degli insiemi, che è essen­ziale per la teoria della stessa logica del prim'ordine. Almeno due assio­matizzazioni della teoria degli insiemi meritano attenzione. Una è il sistema classico conosciuto come teoria di Zermelo-Fraenkel, in breve ZF. Questo sistema prende il nome daErnst Zermelo (1871-1953), che fornì una prima lista di assiomi, e da Abraham Fraenkel ( 1891-1965 ), che aggiornò la lista successivamente. Sia LZF un linguaggio

116

predicativo ottenuto da Lid eliminando tutte le costanti individuali, tutte le costanti predicative tranne= e aggiungendo la costante predi­cativa a due posti E. Le formule atomiche di L2 Fhanno la formax = y o la formax E y, dovex e y sono variabili. Ecco gli assiomi di ZF:

A18 Vx'efy(Vz(zEx=zEy)-::>x=y) A19 Vy3z'efx(xEz=(xEyA a(x))) A20 Vx(3y(yEx)-::> 3y(yEx /\ ~ 3z(zEx /\ zEy))) A21 3x'efy~ (yEx) A22 Vx'efy3z'efu(uEz=(u=xv u=y)) A23 Vx3y'efz(zEy= 3_u(uExAzEu)) A24 Vx3y'ef z(zEy= Vu(uEz-:JuEx)) A25 3x(3y(Vu~ (uEy) AyEx) /\ Vy(yEx-:J 3z(Vu(uEz= (uE yv u=y)) AzEx))) A26 VuVv'efw(a(u,v) /\ a(u,w)-:Jv=w)-::> Vx3y'ef z(zEy= 3u(uE x /\ a(u,z)))

Al 8 enuncia il principio di estensionalità, pertanto è detto assioma di estensionalita. Al 9, chiamato assioma di separazione, è in realtà uno schema di assioma: a(x) sta per una formula in cui x è libera. Dato un insieme y e data una proprietà espressa da a(x ), esiste un insieme z i cui elementi sono esattamente gli elementi di y che godono della proprietà. A20, l'assioma di fondazione, asserisce che, se uri insieme contiene qualche insieme, allora contiene almeno un insieme con cui non ha nessun elemento in comune. A21 è l'assioma dell'insieme vuoto, in quanto implica l'esistenza di 0. A22 è l'assioma della coppia: per ogni x e ogni y esiste un insieme z i cui elementi sono x e y. A23 è l'as­sioma dell'unione. In base a questo assioma, per ogni insieme xi cui elementi siano insiemi, esiste un insieme y tale che, per ogni z, z appar­tiene a y sse appartiene a qualche elemento dix. In altri termini, y è l'unione degli elementi dix. A24 è l'assioma dell'insieme potenza in quanto implica, per ogni insiemex, l'esistenza di un insiemeP(x ). A25, l'assioma dell'infinito, implica l'esistenza di un insieme induttivo i cui elementi sono insiemi. A26, comeA19, è uno schema: a(u, v) è una formula in cui u e v sono libere, che in base ali' antecedente del condi-

117

zionale esprime una funzione. Quindi, dato un insieme e data una funzione F, esiste un insieme i cui elementi sono gli oggetti ottenuti applicando Fagli elementi del primo insieme. Questo schema è chia­mato assioma di rimpiazzamento, dato che in sostanza dice che, se si rimpiazzano gli elementi del primo insieme con gli oggetti associati ad essi da F, si ottiene di nuovo un insieme. Agli assiomi Al8-A26 si aggiunge normalmente l'assioma di scelta:

A27 "i/ x("i/ u "i/ v( (u Ex A v Ex A u * v) ::J~ 3z(z E u A z E v)) ::J 3y"i/ u(uEx::J 3w"if z((zEu A zEy) =z= w))

In base ad A27, sex è un insieme i cui elementi sono insiemi non vuoti a due a due disgiunti, cioè tale che, per ogni coppia di insiemi distinti u e v inx, u e v non hanno elementi in comune, esiste un insieme di scel­ta per x, cioè un insieme y che contenga un elemento preso da ciascun insieme inx. Un esempio è il seguente. Siax l'insieme {{2, l}, {3,4}, {S, 7}}. Chiaramente, x contiene insiemi che sono a due a due disgiunti. Un insieme di scelta per x è {2, 3, S}, poiché {2, 3, S} contiene un elemento preso da ciascuno degii elementi dix. A27 implica l'esisten­za di un insieme di questo genere. La teoria ottenuta aggiungendo A27 a ZF si indica con ZFC. La seconda assiomatizzazione della teoria degli insiemi è un sistema meno noto di ZF, ma non per questo meno interessante. Si tratta del sistema New Foundations, in breve NF, formulato da Willard Van Orman Quine (1908-2000) per sviluppare alcune idee precedente­mente espresse da Bertrand Russell ( 1872-1970) e Norman White­head ( 1861-194 7). Il linguaggio di NF è analogo a quello di ZF, con la differenza che una nozione caratteristica è definita per le sue formu­le, quella di stratifìcazione. Una formula è stratificata sse è possibile sostituire ogni variabile che contiene con un numero naturale rispet­tando le seguenti condizioni: I. la sostituzione è uniforme; 2. per ogni occorrenza del predicato E, il numero che segue E è il successore del numero che precede E. Con "uniforme" si intende dire che occorrenze diverse della stessa varia-

118

bile devono essere rimpiazzate dallo stesso numero. Ad esempio, la formula (xEy) ::J (yEz) è stratificata: basta sostituire 1ax,2a ye 3 az. Invece, "i/ x(x Ex) non è stratificata. Gli assiomi diNF sono i seguenti:

A28 "i/x"i/y(x=y= \fz(zEx=zEy)) A29 3x\f y(yEx= a)

A28 esprime il principio di estensionalità, comeA18. A29 è uno sche­ma che governa la stratificazione e solitamente viene chiamato "sche­ma di comprensione stratifìcatà'. Quello che si assume nello schema è che a sia stratificata, y non occorra in a ex sia libera in a. L'estrema semplicità dei due assiomi enunciati rende NF affascinante. Uno dei risultati più interessanti su NF è stato ottenuto da Ernst Specker (n. 1920): A27 è in contraddizione conNF. Un altro risultato è il seguente: A25 è dimostrabile inNF. Per il resto, NF è una teoria di cui non si sa ancora molto. Ad esempio, finora non è stata dimostratala sua coerenza.

10.4. Teorie dell'ordinamento Queste teorie vertono sui modi in cui gli elementi di un insieme possono essere ordinati. Lo studio di questi modi è strettamente legato alla teoria degli insiemi, perché concerne le relazioni. Si pensi, ad esempio, all'ordine che imponiamo mentalmente ai numeri naturali quando li pensiamo disposti in succes­sione dallo O in avanti. Questo ordine non è altro che la relazione che sussiste tra due numeri naturali quando il primo è minore del secon­do. Per chiarire la nozione di ordine occorre definire alcune proprietà delle relazioni. Sia A un insieme e Runa relazione su A.

Definizione 27 Reriflessivasse,perognixEA, (x,x) ER.

Definizione 28 R hransitivasse perognix,y,z EA, se (x,y) ER e (y, z) E R, allora (x, z) E R.

Definizione 29 R è antisimmetricasse in A non esistono x e y distinti tali che (x,y) E Re (y, x) E R.

119

Definizione 30 Re totalesse,perognix,yEA, (x,y) ERo (y,x) ER.

Un ordine parziale su A è una relazione su A che possiede le prime tre proprietà. Un ordine totale o lineare su A è una relazione su A che possiede tutte e quattro le proprietà. Le teorie dell'ordinamento vertono su relazioni di questo tipo. Sia L0 un linguaggio ottenuto da Lid aggiungendo il simbolo ~. La teoria dell'ordine parziale è costruita mediante i seguenti assiomi:

A30 V x(x ~ x) A31 \;/ x V y V z( (x ~ y A y ~ z) --:J x ~ z) A3~ V x\:/y((x ~y AJ ~x)--:Jx= y)

A30-A32 garantiscono infatti che ~sia una relazione riflessiva, tran­sitiva e antisimmetrica. La teoria dell'ordine lineare, invece, si ottiene aggiungendo ad A30-A32 un assioma che esprime la totalità di ~:

A33 V x V y(x ~ y v y ~ x)

Una nozione importante nelle teorie dell'ordinamento è quella di minimo: un insieme ordi!J.ato ha un minimo se esiste un elemento dell'insieme che è più piccolo di tutti gli altri. Ad esempio, w ha un minimo, in quanto O è più piccolo di ogni altro numero naturale. Per esprimere l'esistenza di un minimo si usa una costante a e si aggiunge alla teoria il seguente assioma:

A34 V x(a ~ x)

Naturalmente, non tutti gli insiemi ordinati hanno un minimo. L'insieme dei numeri interi, ad esempio, non ha un minimo, dato che contiene, oltre ai numeri naturali, i numeri negativi -1, - 2, - 3 e così via. La non esistenza di un minimo si esprime con il seguente assioma:

A35 Vx3y(y~xAx:;t:y)

120

La nozione di massimo è analoga a quella di minimo. Per esprimere l'esi­stenza o la non esistenza di un massimo occorrono assiomi simili adA34 e A35. Come si può facilmente constatare, una struttura normale che abbia w come dominio è modello di una teoria che abbia come assiomi A30-A34, mentre una struttura normale che abbia come dominio l'insie­me dei numeri interi è modello di una teoria che abbia come assiomiA30-A33, A35 e un assioma che esprime la non esistenza di un massimo. Un'altra nozione importante nelle teorie dell'ordinamento è quella di densita. Un ordine denso è caratterizzato dai seguenti assiomi:

A36 \;/X\;/ y( (x ~ y A X:;<: y) --:J 3z(x ~ z A z :;<:X A z ~ y A z :;<: y)) A37 3x3y(y~xAx:;t:y)

A36 enuncia la condizione caratteristica della densità: dati due elementi distinti x e y tale che x precede y, esiste sempre un terzo elemento z che si trova trax e y. Ad esempio, questa condizione è soddi­sfatta nell'insieme dei numeri razionali: tra 1 e 2 si trova t• tra 1 et si trovai e così via. A37 si limita a richiedere che esistano almeno due elementi distinti. La teoria dell'ordine lineare denso si ottiene aggiun­gendo A36 e A37 alla teoria dell'ordine lineare. Dunque, una struttu­ra normale che abbia come dominio l'insieme dei numeri razionali è modello di questa teoria. Sia OLD la teoria dell'ordine lineare denso senza minimo e senza massimo. Un risultato interessante, dimostrato per la prima volta da Cantor, è il seguente:

Teorema 27 OLD e categorica nella potenza N0•

Dimostrazione Siano .A e 13 modelli numerabili di OLD. Siano (a1, a2,

ar-) e(b1, b2, b3 ... ) enumerazioni degli elementi diA e B. Si costruisca

una sequenza di funzioni iniettive Fi : Ai - Bi tali che, per ogni i:

1. Ai e Bi sono sottoinsiemi propri finiti diA e B; 2. F

0<;;;,.F

1<;;;,. ••• ;

3. sex,yEA;ex <y,alloraFi(x) <Fh).

121

In altri termini, ogni~ è un'immersione parziale. La sequenza è costruita in modo tale che l'unione di tutti gliA. daràA, mentre l'unione di tutti iB.

I I

daràB. Di conseguenza, l'unione di tutte le immersioni parzialiF; darà la corrispondenza biunivoca traA eB e quindi l'isomorfismo desiderato. La costruzione si articola in due passi: prima si costruiscono le sequenze rispetto adA, usando i numeri dispari, poi quelle rispetto aB, usando i numeri pari. Nel caso in cui n = O, si stipula cheA0 = B0 = F0 = 0. Siconsiderin+ 1 =2m+ l.Sidovràgarantirechea EA +1.Sea EA, m n m n

alloraA +i=A ,B +i=B eF+1=F .Seinvecea nonappartienead n 11 n n n n m An, allora si può ragionare come segue per aggiungere am al dominio della nostra immersione parziale. Si deve trovare un elemento b di B che non appartiene a B tale che, per ogni elemento x di A , x < a sse _ n n m

F,,(x) <b. Si avrà uno dei seguenti casi. Caso 1: am è maggiore di ogni elemento contenuto inAn. In questo caso, dato che B è finito e B è numerabile, si può trovare un elemento

1l

b maggiore di ogni elemento diB,,, dato che non esiste un massimo. Caso 2: a è minore di ogni elemento diA . Questo caso è simile al caso

1ll 1l

precedente, poiché si può trovare un b in B minore di ogni elemento di B , dato che non esiste un miniillo.

1l

Caso 3: esistonoxey inA,, tali chex <y,z ~xox ~y perognizEA,, e x < a m < y. In questo caso F(x) < F,, (y) e si può scegliere un elemento b diB che non è inB,, tale cheF,,(x) < b < F

11(y).

A questo punto, siaA +l =A U {a } eB +l B U {b}. Si estenda n n 1n n n

adesso F aF +l : A +i~ B +l facendo corrispondere b ad a. Così si n n n n . m conclude la prima parte della costruzione. Si consideri ora n + 1 = 2m + 2. Si dovrà garantire che b E B +i· Si nz n

ragiona come nel caso precedente ma questa volta all'inverso, trovan-do un a EA che corrisponda a b

111 EB,,+l. In questo modo l'unione di

tutti gli insiemi A; corrisponde ad A, mentre l'unione di tutti gli insie­mi E; corrisponde a B. L'unione di tutte le immersioni parziali sarà quindi un isomorfismo tra A e 13.

D Nota La dimostrazione di T27 è un esempio di costruzione chiama­ta "avanti e indietro", poiché estende da un lato il dominio di una funzione (avanti) e dall'altro il suo codominio (indietro).

122

10.5. Geometria euclidea elementare Tarskilavorò a più ripre­se sulla formalizzazione della geometria, sia da solo sia insieme ad alcuni suoi studenti. Il risultato di questo lavoro fu un'assiomatizzazione di una parte della geometria euclidea. In particolare, si tratta del frammento della geometria euclidea che solitamente viene chiamato "elementare". Nel linguaggio del sistema di Tarski risultano cruciali due costanti predi­cative. La prima è una costante a tre posti G che sta per "giace tra'': Gxyz significa 'J giace trax e z". La seconda è una costante a quattro posti che esprime la relazione di congruenza e può essere sostituita dal simbolo "": xy"" wz significa "il segmento che ha come estremi x e y è congruente al segmento che ha come es~remi w e z': o semplicemente, "la distanza trax eyèlastessadi quella traw ez': Ecco gli assiomi di Tarski:

A38 'i/ x 'i/ y(xy ""yx) A39 'i/ xVyVz(xy""zz:Jx= y) A40 'i/ x 'i/ y 'i/ z 'i/ u 'i/ v 'i/ w( (xy ""zu /\ zu "" vw) :J xy "" vw) A41 'i/ x'if y( Gxyx:Jx= y) A42 'i/ x 'i/ y 'i/ u 'i/ v V z( ( Gxuz /\ Gyvz) :J 3 w( Guwy /\ Gvwx)) A43 3w 'i/ xVy(( </J(x) /\ 'ljJ(y)) :J Gwxy) :J 3v'if xVy(( </J(x) /\ 'ljJ(y)) :J Gxvz) A443x3y3z(~ GxyzA~ Gyzx/\~ Gzxy) A45 'i/ x V y V z 'i/ u 'i/ v( (xu ""xv /\ yu ""yv /\ zu ""zv /\ u * v) :J ( Gxyz V

Gyzx v Gzxy)) A46 'i/ x V y V z V u 'i/ v( ( Gxuv /\ Gyuz /\ x * u) :J 3 w 3 t( Gxyw /\ Gxzt /\ Gwvt)) A47 'i/ x'if u V z'if x''if u''if z''if y 'i/ y'((x * y /\ Gxyz /\ Gx'y'z' /\ xy"" x'y' AJZ""y'z' /\Xu""x'u' AJU""y'u'):Jzu""z'u') A48 'i/ x 'i/ y 'i/ z 'i/ w 3 v( Gwxv /\ xv ""yz)

A3 8 enuncia un fatto ovvio: la distanza trax e y è uguale alla distanza tra y ex. A39 fissa una condizione sufficiente di identità tra punti in termi­ni di congruenza: se il segmento xy è congruente con un segmento che inizia e finisce allo stesso punto z, allorax è identico a y. A40 implicala transitività della congruenza; sexy è congruente azu e zu è congruente a vw, xy è congruente a vw. A41 chiarisce un'assunzione di fondo della

123

geometria euclidea: il punto è indivisibile. Non può esserci un punto y diverso dax che giace trax ex. A42 è conosciuto come assioma diPasch. Infatti, Moritz Pasch ( 1843-1930) per primo inruì la necessità di adot­tarlo, in quanto è spesso presupposto nelle dimostrazioni ma non è deri­vabile dagli altri assiomi. L'assioma di Pasch può essere enunciato come segue: se si tracciano due segmenti a partire da due vertici di un triango­lo che congiungono tali vertici con i lati opposti ad essi, allora i due segmenti devono incontrarsi in qualche punto all'interno del triangolo. A43 è uno schema: </J(x) è una formula che non contiene occorrenze libere di w, ve y, mentre 1.jJ(y) è una formula che non contiene occor­renze libere di w, ve x. Supponiamo che le due formule definiscano due insiemi di punti tali che ogni punto del secondo sia alla destra di ogni punto del primo rispetto al punto w. Allora esiste un punto v che si trova tra i due insiemi di punti. A 44 implica l'esistenza di tre punti che non giacciono sulla stessa linea. A45, invece, afferma che tre puntix,y e z equidistanti da due punti distinti u e v sono allineati. A46 afferma che dato un angolo qualsiasi e un punto qualsiasi al suo interno, esiste un segmento che include il punto e ha estremi sui lati dell'angolo. A47, il cosiddetto assioma dei cinque segmenti, fornisce un criterio di congruen­za per i triangoli. Siano xuz ex' u 1 z' due triangoli. Si ~raccino ora due segmenti yu e y' u 1 che connettono un vertice di ogni triangolo a un punto sull'altro lato opposto al vertice. Il risultato che si ottiene è costi­tuito da due triangoli suddivisi in cinque segmenti ciascuno. Due dei cinque segmenti, infatti, sono le parti in cui il punto scelto divide il lato opposto al vertice. Se quattro segmenti di un triangolo sono congruen­ti ai quattro corrispettivi dell'altro triangolo, allora sono congruenti i restanti due. A48 permette di costruire segmenti a partire da segmenti. In particolare, dati due segmenti, il secondo può essere "esteso" con un segmento congruente al primo segmento. Il sistema di Tarski è interessante perché permette di esprimere una parte considerevole della geometria euclidea senza presupporre nozioni insie­mistiche. A differenza di altre assiomatizzazioni, come quelle di David Hilbert (1862-1943) e di George Birkhoff (1884-1944), il sistema di Tarski presuppone come unici oggetti primitivi i punti. Quindi non implica quantificazione su linee, piani o altri insiemi di punti.

124

Soluzioni degli esercizi

1. No, perché non può esserci corrispondenza biunivoca traA e B. 2. Sì. Se esiste un'immersione isomorfa di A in 15 rispetto a L, per ottenere un'immersione isomorfa di .Ain 15 rispetto a L'basta esten­dere la prima funzione assegnando [c]'Ba [c].A: 3. Sia T una teoria priva di assiomi propri in un linguaggio che ha come unica espressione non logica una costante predicativa a un posto P. Per qualche K, siano A in 15 strutture di cardinalità K. Essendo T priva di assiomi propri, .Ain 15 sono modelli di T, come qualsiasi altra struttura. Supponiamo ?ra che in A in 15 a P siano assegnati sottoin­siemi di A e B che non sono in corrispondenza biunivoca. In questo caso A e 15 non sono isomorfe.

125

ASSIOMI, DEFINIZIONI, LEMMI E TEOREMI CONTENUTI NEL TESTO L17 p.54 L38 p.80 Tg p.66 L18 p.54 L39 p.81 Tlo p.83 L19 p.55 L40 p.89 Tll p.88

Al p.47 A33 p. 120 016 p.77 L20 p.55 L41 p.92 T12 p.90 A2 p.47 A34 p. 120 017 p.79 L21 p.56 L42 p.92 T13 p.94 A3 p.47 A35 p. 120 018 p.87 L22 p.56 L43 p.93 T14 p.103 A4 p.47 A36 p. 121 019 p.87 L23 p.56 L44 p.93 T15 p.103 A5 p.47 A37 p. 121 020 p.88 L24 p.60 L45 p.94 T16 p.104 A6 p.47 A38 p. 123 021 p.88 L25 p.61 L46 p.94 T17 p.105 A7 p.47 A39 p. 123 022 p. 106 L26 p.63 L47 p.104 T18 p. 106 AB p.70 A40 p.123 023 p. llO L27 p.63 L48 p.107 T19 p. 106 Ag p.70 A41 p. 123 024 p. llO L28 p.65 L49 p. llO T20 p.108 A10 p.70 A42 p. 123 025 p.113 L29 p.65 T21 p. ll2 All p.70 A43 p. 123 026 p. 114 L30 p.65 Tl p.56 T22 p. ll2 A12 p.70 A44 p. 123 027 p. l19 L31 p.65 T2 p.59 T23 p. l12 A13 p.70 A45 p. 123 028 p.119 L32 p.72 T3 p.61 T24 p. ll3 A14 p.70 A46 p. 123 029 p. 119 L33 p. 73 T4 p.62 T25 p. 115 A15 p. 71 A47 p. 123 030 p. 120 L34 p.73 T5 p.62 T26 p. l16 A16 p.71 A48 p. 123 L35 p.74 T6 p.63 T27 p. 121 A17 p.71 Ll p.40 L36 p.74 T7 p.64 A18 p. 117 01 p.32 L2 p.41 L37 p.79 T8 p.66 A19 p. 117 02 p.38 L3 p.44 A2o p. 117 03 p.39 L4 p.44 A21 p. 117 04 p.39 L5 p.48 A22 p. 117 05 p.42 L6 p.49 A23 p. 117 06 p.42 L7 p.50 A24 p. 117 07 p.43 L8 p.51 A25 p. 117 08 p.43 Lg p.52 A26 p. 117 Dg p.47 LlO p.52 A27 p. l18 010 p.48 L11 p.52 A28 p. l19 011 p.49 L12 p.52 A29 P· l19 012 p.53 L13 p.52 A30 p. 120 013 p.53 l14 p.52 A31 p. 120 014 p.70 L15 p.54 A32 p. 120 015 p.74 L16 p.54

126 127

Bibliografia

Qui di seguito indichiamo alcuni libri che sono stati fonte di ispirazione per la realizzazione di questo testo. Tra essi in particolare segnaliamo Hunter (1971) e Chang, Keisler (1973). Alcuni testi contengono una gamma di temi più ampia di quella trattata in questo volume. Pertanto l'elenco seguente può costituire anche un buon punto di partenza per il lettore interessato ad appro­fondire ulteriormente alcune tematiche trattate nel testo.

BOOLOS s. G., BURGESS P. J ., JEFFREY c. R. ( 2002 ), Computability and Logie, Cambridge University Press, Cambridge (4th ed.).

~ASALEGNO P., MARIANI M. (2004), Teoria degli insiemi. Un'introduzione, Carocci, Roma.

CHANG C. C., KEISLER H.]. (1973), Model Theory, North Holland, Amster­dam-London.

ENDERTON H. B. (2001),AMathematicallntroduction toLogic, Academic Press, San Diego (2nd ed.).

HODGES w. (1997),A Shorter Model Theory, Cambridge University Press, Cambridge.

HRBACEK K.,JECH T. (1999 ), Introduction to Set Theory, Dekker, New York. HUNTER G. ( 1971), Metalogic: An Introduction to the Theory oJStandardFirst

Order Logie, University of California Press, Berkeley - Los Angeles -London.

MENDELSON E. ( 1997 ),Jntroduction to Mathematical Logie, Springer, Berlin. PALLADINO D. ( 2004),Logica e teorie formalizzate. Completezza, Incompletez­

za, Indecidibilita, Carocci, Roma. SHOENFIELD R.J. (2001),MathematicalLogic, AKPeters, Natick (MA).

128