Proposizionali
Corso di Logica (1)
a.a. 2005-2006
Prof.ssa Giovanna Corsi
Appunti redatti da
Wilmer Ricciotti - ricciott@cs.unibo.it
Francesco Spegni - spegni@cs.unibo.it
Alessia Tosi - verderba@yahoo.it
1 Logiche modali proposizionali 9
1.1 Livello sintattico. . . 9
1.1.1 Definizioni e dimostrazioni per induzione . . . 9
1.2 Livello semantico . . . 13
1.2.1 I modelli . . . 13
1.2.2 Verità e validità . . . 14
1.3 Formule sempre valide . . . 14
1.4 Regole che conservano la validità . . . 15
1.5 Esercizi . . . 16
2 Corrispondenza 17 2.1 Corrispondenza e Validità . . . 17
2.2 Chiusura riflessiva e transitiva . . . 17
2.3 Teoremi di corrispondenza. . . 18
2.4 Esercizi . . . 25
3 Manipolazione di modelli 27 3.1 Sottomodelli generati . . . 27
3.2 P-morfismi . . . 28
3.3 Proprietà non esprimibili. . . 30
4 Teoria della dimostrazione 33 4.1 Logiche modali normali . . . 33
4.2 Insiemi massimali e consistenti . . . 34
4.3 Il modello canonico . . . 36 5 Completezza 39 5.1 Strumenti. . . 39 5.2 Metodo . . . 39 5.3 Logiche . . . 40 5.4 Esercizi . . . 46 6 Modelli finiti 49 6.1 Filtrazione . . . 49
6.2 Proprietà del Modello Finito. . . 52
4 INDICE
7.3.2 Dimostrazione . . . 56
A Relazioni ed ordini 57
A.1 Relazioni . . . 57
A.2 Ordini. . . 57
A.3 Induzione transfinita . . . 58
B Mappe concettuali 61
C Licenza 65
1.1 Tre semplici strutture relazionali d’esempio . . . 13
2.1 Corrispondenza e validità in breve . . . 18
2.2 Il sottomodello di riferimento . . . 25
3.1 La simmetria della condizione 2. . . 28
3.2 Back-condition. . . 28
3.3 Un p-morfismo da N a {0} . . . 30
3.4 Un p-morfismo da N a {a, b}. . . 31
5.1 Una gerarchia delle logiche . . . 40
5.2 Relazione densa debole. . . 42
5.3 Relazione diretta debole . . . 44
A.1 Proprietà e relazioni d’ordine - una topologia riassuntiva . . . 59
A.2 L’insieme 2 × N . . . 59
B.1 Manipolazioni di modelli . . . 61
B.2 Teoria della dimostrazione e modello canonico . . . 62
B.3 Filtrazioni . . . 63
A.1 Le comuni proprietà di una relazione. . . 57
Logiche modali proposizionali
Le logiche modali proposizionali che noi considereremo sono estensioni della logica classica proposizio-nale che assumiamo già nota. Lo studio delle logiche modali avverrà sotto due aspetti: sintattico e semantico.
1.1
Livello sintattico
1.1.1
Definizioni e dimostrazioni per induzione
Definizione 1.1. L’alfabeto di un linguaggio enunciativo modale LΦ
Aè costituito da:
• un insieme Φ al massimo numerabile di variabili enunciative: p0, p1, p2. . .
• la costante logica 0-aria ⊥,
• costanti logiche unarie ¬ e2, per ogni a ∈ A, ove A è insieme non vuoto, al massimo numerabile,a
di indici ,
• costanti logiche binarie ∨, ∧, → • le parentesi (, ).
Definizione 1.2. Definizione induttiva dell’insieme FmΦA, delle formule ben formate di LΦA.
1. pi∈ FmΦA, i ∈ N,
2. ⊥ ∈ FmΦA,
3. se A ∈ FmΦAe a ∈ A, allora (¬A), (2A) ∈ Fma Φ A
4. se A ∈ FmΦAe B ∈ FmΦA, allora (A ∨ B), (A ∧ B), (A → B) ∈ FmΦA
5. nient’altro è in FmΦA.
Le prime due clausole stabiliscono quali sono gli elementi iniziali di FmΦA, le seconde due clausole
10 Logiche modali proposizionali Definizione 1.3. > , ¬⊥ a 3A , ¬2¬Aa A ↔ B , (A → B) ∧ (B → A).
Dato un insieme X definito per induzione, possiamo dimostrare proprietà degli elementi di X facendo appello a come tali elementi sono stati costruiti.
Teorema 1.4(Principio di induzione sulla costruzione delle formule). Sia φ una proprietà (espressa nel metalinguaggio). Allora φ[A] vale per ogni A ∈ FmΦA, se
φ[pi], per ogni i ∈ N,
φ[⊥],
se φ[A], allora φ[(¬A)] e φ[(2A)]a
se φ[A] e φ[B], allora φ[(A ∨ B)], φ[(A ∧ B)] e φ[(A → B)]. Dimostrazione.
Sia X = {A ∈ FmΦA : φ(A)}. Banalmente X ⊆ Fm Φ
A. X soddisfa tutte le condizioni della definizione
1.2, pertanto FmΦA⊆ X, quindi X = FmΦA.
Chiameremo una applicazione del teorema appena enunciato, una dimostrazione per induzione su A o sulla costruzione di A.
Diamo ora un esempio banale di dimostrazione per induzione sulla costruzione di A. In pratica verificheremo solo le clausole della dimostrazione per induzione e lasciamo la conclusione al lettore.
Teorema 1.5. Ogni formula ben formata ha un numero pari di parentesi.
Dimostrazione.
1. Ogni atomo ha zero parentesi e zero è pari 2. ⊥ ha zero parentesi e zero è pari.
3. Supponi che A abbia 2n parentesi, allora (¬A), (2A) hanno 2n + 2, ovvero 2(n + 1) parentesi.a
4. Supponi che A abbia 2n parentesi e B abbia 2m parentesi, allora (A ? B) ha 2(n + m + 1) parentesi, ove ? ∈ {∧, ∨, →}.
Per il teorema1.4, ogni fbf ha un numero pari di parentesi.
Dato un insieme X definito per induzione, possiamo definire funzioni sugli elementi di X facen-do appello a come tali elementi sono stati costruiti. Siffatte funzioni sono dette definite per ricorsione. Seguono alcuni esempi.
Esempio 1. Definiamo la funzione π[A] che computa quante sono le parentesi di A. Basta porre: π[pi] = 0, per ogni atomo pi,
π[⊥] = 0,
.
Esempio 2. Definiamo la funzione che ad ogni formula A associa il suo l’albero di formazione (parsing tree) T [A].
T [pi] = •, per ogni atomo pi
T [⊥] = • T [(¬A)]= (¬A) • T [A] T [(2A)] = (2A) • T [A] T [(A ? B)] = (A?B) • yyyyyy yy E E E E E E E E T [A] T [B]
Esempio 3. La lunghezza (size) di una formula A è così definita: lg[pi] = 0, per ogni atomo pi,
lg[⊥] = 0,
lg[(¬A)] = lg[(2A)] = lg[A] + 1, lg[(A ? B)] = lg[A] + lg[B] + 1.
Esempio 4. La profondità (height) di una formula A è così definita: h[pi] = 0, per ogni atomo pi,
h[⊥] = 0,
h[(¬A)] = h[(2A)] = h[A] + 1, h[(A ? B)] = max[h(A), h(B)] + 1.
Esempio 5. L’insieme delle sottoformule di una formula A è così definito: Sf[pi] = {pi}, per ogni atomo pi,
Sf[⊥] = {⊥},
12 Logiche modali proposizionali
Sf[(A ? B)] = Sf[A] ∪ Sf[B] ∪ {(A ? B)}.
Diciamo che B è sottoformula di A se B ∈ Sf(A).
Osservazione 1. Che questa definizione sia matematicamente ben fondata è garantito dalla teoria delle funzioni ricorsive.
L’introduzione delle funzioni lunghezza e profondità non è una mera illustrazione della “defini-zione per ricorsione”: ci permette anche di dimostrare fatti sulle formule per mezzo del principio di induzione matematica. Infatti grazie alla nozione di lunghezza siamo in grado di suddividere tutte le formule in una successione infinita di insiemi di formule: l’insieme delle formule di lunghezza 0, l’insieme delle formule di lunghezza 1, l’insieme delle formule di lunghezza 2, ... Analogamente per la profondità.
Proposizione 1.6(Principio di induzione sulla lunghezza delle formule). Sia φ una proprietà sulle formule ben formate (d’ora in avanti: fbf). Se:
• φ(B) vale per tutte le fbf B tali che lg(B) = 0;
• supponendo che φ(B) valga per tutte le fbf B tali che lg(B) < lg(A), segue che vale anche φ(A); allora φ(A) vale per ogni A ∈ FmΦA.
Proposizione 1.7(Principio di induzione sulla profondità delle formule). Sia φ una proprietà sulle fbf. Se:
• φ(B) vale per tutte le fbf B tali che h(B) = 0;
• supponendo che φ(B) valga per tutte le fbf B tali che h(B) < h(A), segue che vale anche φ(A); allora φ(A) vale per ogni A ∈ FmΦA.
Si può mostrare facilmente che il principio di induzione sulla costruzione di A ed il principio di induzione sulla profondità di A sono equivalenti (vedi [vD], p.13).
Convenzione notazionale sulle parentesi Per semplificare la notazione economizziamo sulle parentesi sulla base delle seguenti regole:
1. non scriviamo le parentesi più esterne
2. non scriviamo le parentesi nel caso di ¬ e di2 3. ∧ e ∨ legano più fortemente di →
4. ¬ e2 legano più fortemente di ogni altro connettivo.
Esempio 6.
¬p ∨ p sta per ((¬p) ∨ p)
¬(¬¬¬p ∧ ⊥) sta per (¬((¬(¬(¬p))) ∧ ⊥)) p ∨ q → p sta per ((p ∨ q) → p)
Definizione 1.8(sostituzione uniforme). Sia p una lettera enunciativa e D una formula. Definiamo per ricorsione l’operazione A[D/p](sostituzione uniforme di p in D):
p[D/p] = D q[D/p] = q, se q 6= p ⊥[D/p] = ⊥ (¬A)[D/p] = ¬(A[D/p]), (2A)[D/p] =2(A[D/p]), (A ? B)[D/p] = A[D/p] ? B[D/p].
A[D/p]denota quindi la formula ottenuta per sostituzione uniforme da A, ove ogni occorrenza di p
1.2
Livello semantico
Iniziamo con l’introdurre la cosiddetta semantica relazionale (a volte detta anche semantica dei mondi possibili), introdotta da Kripke nel 1959 e che si è dimostrata subito un modello naturale per attribuire un significato ai linguaggi modali.
Definizione 1.9. (struttura relazionale)Chiamiamo struttura relazionale una coppia del tipo: hW, {Ra}a∈Ai
ove la prima componente è un insieme non vuoto, chiamato universo dei mondi W, mentre la seconda componente è un insieme di relazioni di accessibilità (o più semplicemente: insieme di relazioni)Ra, ove
a ∈ Ae A è un insieme di indici, al massimo numerabile.
Se w ∈ W diciamo che w è un mondo dell’universo W o che w è un punto dell’universo (o spazio) W.
Per ragioni storiche, chiameremo frame una struttura che contenga una sola relazione R, e la indi-cheremo come:
hW,Ri.
1.2.1
I modelli
Data una struttura hW, {Ra}a∈Ai, un modello basato su essa è una tripla:
hW, {Ra}a∈A, Ii
ove I è una funzione di interpretazione che associa ad ogni variabile enunciativa un sottoinsieme di W: I : Φ →P(W)
doveP è l’operatore che, dato un insieme, ritorna l’insieme delle sue parti (ovvero: l’insieme dei suoi sottoinsiemi possibili). w • w• w1 • ))w•2 ''w• ss3 w•4 a) b) c)
Figura 1.1: Tre semplici strutture relazionali d’esempio Vediamo ora alcune strutture molto semplici. La prima è:
F = h{w}, ∅i,
graficamente rappresentata dalla Figura1.1(a). Il secondo caso è molto simile al primo, dove però la relazioneR è riflessiva. Formalmente la struttura che abbiamo in mente è così descritta:
F = h{w}, {hw, wi}i,
graficamente essa sarà rappresentata come in fig.1.1(b). Una terza struttura è quella rappresentata nella fig.1.1(c), ed è formalmente definita da:
14 Logiche modali proposizionali
1.2.2
Verità e validità
Esplicitiamo ora la semantica delle formule modali. Per indicare che un enunciato A è vero in un mondo wdel modello M, scriviamo
M wA.
Definizione 1.10. (verità in un mondo)La nozione di verità in un mondo è definita per induzione come segue: M wpi sse w ∈ I(pi) M 2w⊥ sse M w¬B sse M 2 B M wB1∧ B2 sse M B1 ed M wB2 M wB1∨ B2 sse M B1 oppure M wB2 M wB1⇒ B2 sse M 2 B1 oppure M wB2 M w2Ba sse ∀v ∈ W.wRa v ⇒ M v B]
Possiamo introdurre un ulteriore operatore modale, l’operatore di possibilità, da intendersi come segue:
M w3Ba sse ∃v ∈ W.wRav e M v B]
Preferiamo però considerare, da qui in avanti, l’operatore di possibilità come derivabile da quello di necessità, e cioè:
M w3Ba sse M w¬2¬Ba
Definizione 1.11. (verità in un modello)Diciamo invece che una formula A è vera in un modello M se e solo se essa è vera in ogni punto del modello stesso. Formalmente:
M A sse ∀w ∈ W [M wA].
Definizione 1.12. (validità)Infine, una formula è valida su una struttura F se e solo se essa è vera in ciascun modello basato su di essa:
F A sse ∀M basato su F [M A]. Con l’espressione F-modello indichiamo un modello basato su F.
1.3
Formule sempre valide
Teorema 1.13. (formula di Kripke)
Teorema 1.15. (distributività di3 su ∨)
F 3(A ∨ B) ↔ 3A ∨ 3B Dimostrazione.
Esercizio.
1.4
Regole che conservano la validità
Facciamo vedere ora che le regole di Modus Ponens, Necessitazione e Sostituzione conservano la validità su una struttura. Cominciamo dalla prima.
Teorema 1.16. (MP conserva la validità) In qualsiasi struttura relazionale F , vale quanto segue:
F A F A → B F B (MP ) Dimostrazione.
È facile vedere, sulla base della definizione di verità delle formule implicative, che la regola del Modus Ponens conserva la verità in un punto di un modello:
M wA M wA → B
M wB
Ne segue che per ogni M
M A M A → B M B
e per ogni F
F A F A → B F B
Teorema 1.17. (NEC conserva la validità) In qualsiasi struttura relazionale F vale quanto segue:
F A
F 2A (N EC) Dimostrazione.
È possibile dimostrare (esercizio) che N EC conserva la verità in un modello, ovvero per ogni M vale: M A
M 2A Generalizzando, per ogni F
F A F 2A
Osservazione 2. N EC non conserva la verità in un punto di un modello, infatti possiamo avere che M w Ae contemporaneamente M 2w 2A. Lasciamo come esercizio al lettore il trovare un modello
16 Logiche modali proposizionali Teorema 1.18. (la sostituzione uniforme conserva la validità) In qualsiasi struttura relazionale F vale
quanto segue:
F A F A[B/p],
Dimostrazione.
La dimostrazione procede per assurdo. Supponiamo che si abbia F A e F 2 A[B/p].
Questo equivale ad affermare le seguenti due cose:
A M.M A (†) E M. E w ∈ M.M 2wA[B/p]
Consideriamo il sottoinsieme di W così definito:
HB = {w ∈ W : M wB}.
Costruiamo ora il seguente F-modello M?= hW,R, I?i, ove:
I?(q) =
I(q) se q 6= p HB se q = p
È possibile dimostare (esercizio) che per ogni fbf D e per ogni w, M wD[B/p] sse M?wD
Poiché per ipotesi M 2wA[B/p], segue che M?2wA. Questo è in contraddizione con quanto affermato
in (†) perché M?è un modello di F.
Osservazione 3. La regola di sostituzione non conservi la verità in un modello (e quindi tanto meno in un mondo). Possiamo infatti avere che:
M p e M 2 p[p/q]
Anche in questo caso, lasciamo come esercizio al lettore il trovare un modello che evidenzi questo.
1.5
Esercizi
Esercizio 1.1. Completare le dimostrazioni dei seguenti Teoremi:1.13,1.14e1.15.
Esercizio 1.2. Completa la dimostrazione1.4e fornisci il contro-esempio come suggerito nell’osserva-zione2.
Corrispondenza
2.1
Corrispondenza e Validità
In questo capitolo ci chiediamo se una classe di strutture relazionaliH opportunamente scelta corri-sponda ad una formula modale, ovvero se per qualche fbf A, si abbia che
A F[F A sse F ∈ H ]
La classeH può in molti casi lasciarsi descrivere da condizioni sulle relazioni di accessibilità, esempio H = {hW, {Ra}a∈Ai :Ra è riflessiva}
nel qual caso ci chiediamo se esiste qualche A per cui valga: A F[ F A sse F ∈ H ] Se ciò accade, potremo esprimere quanto sopra anche in questo modo:
A F[F A sse F ∀x.x R x]
Definizione 2.1. (corrispondenza)Generalizziamo quanto detto sopra per qualsiasi predicato P di nostro interesse. Se riusciamo a dimostrare che:
A F[F A sse F P ] diremo allora che A corrisponde a P.
La proprietà P può essere una qualunque formula di un linguaggio del primo ordine con identità contenente simboli per le relazioni di accessibilitàRa, a ∈ A.
Definizione 2.2. (validità)Diciamo che A è valida su P se vale l’implicazione: A F[F P ⇒ F A]
2.2
Chiusura riflessiva e transitiva
Definizione 2.3. (elevamento a potenza di2) La definizione procede per induzione:
a
20A=A
a
18 Corrispondenza ' & $ % ' & $ % corrispondenza validità
Figura 2.1: Corrispondenza e validità in breve
Definizione 2.4. (elevamento a potenza di3) Ancora induttivamente, definiamo:
a
30A = A
a
3n+1A =2(a 2anA)
Definizione 2.5. (elevamento a potenza diR) Sia data la relazione binaria R. Definiamo:
sR0t ⇔ s = t
sRn+1t ⇔ ∃z.sRnz ∧ zR t
Definizione 2.6. (chiusura riflessiva e transitiva diR) Data una relazione binaria R, la relazione R?
resta così definita:
sR?t ⇔ ∃n.sRnt R?è detta chiusura riflessiva e transitiva di R.
Lemma 2.7. SiaR1una relazione riflessiva e transitiva tale cheR⊆R1. AlloraR?⊆R1.
Dimostrazione.
Dobbiamo mostrare che se wR? sallora wR
1 s. Sia w R? s, allora per qualche n, wRn s. Per
indu-zione su n, fai vedere che wR1s. (esercizio).
Osservazione 4. Il lemma ci dice cheR?è la più piccola relazione riflessiva e transitiva che estendeR.
Lemma 2.8. M w2anB sse ∀v ∈ W [ wRnav ⇒ M vB] M w3anB sse ∀v ∈ W [ wRnav ⇒ M vB] Dimostrazione. Esercizio.
2.3
Teoremi di corrispondenza
Dimostreremo di seguito alcuni teoremi di corrispondenza fra proprietà strutturali note dall’algebra ed opportune formule modali. Per comodità, le definizioni circa le proprietà che andremo ad analizzare sono state riassunte in AppendiceA.
Teorema 2.9. (riflessività)
F 2B → B sse F ∀s.s Ra
as
M s2Ba (ipotesi) ∀t.sRa t : M tB M sB (poiché sRas) M s2B → Ba F 2B → Ba ⇒)
Procediamo per assurdo:
F 2B → Ba
∃s.¬(sRas) († −ipotesi assurda)
Consideriamo ora un F-modello: M = hW, {Ra: a ∈ A}, Isi, tale che:
Is(p) = {t ∈ W : sRat}.
Questo equivale a dire che:
M tpsse sRat (?)
Allora
M s2pa
M s2p → pa poiché F 2B → Ba
M sp per MP
Per (?) dobbiamo concludere che w Ra w, in contraddizione con (†). Possiamo dunque
conclu-dere che ∀w.wRaw. Teorema 2.10. (transitività) F 2B →a 2a2B sse F ∀s, t, u.s Ra a t ∧ tRau → sRau Dimostrazione. ⇐) ∀s, t, u.sRa t ∧ tRau → sRau Ms2Ba M tB (∀t.sRa t) M uB (∀u.tRau ⇒ sRa u) Mt2Ba Ms2a2Ba Ms2B →a 2a2Ba F 2B →a 2a2Ba ⇒)
Procediamo per assurdo:
F 2B →a 2a2Ba
∃s, t, u.sRa t ∧ tRau ∧ ¬(sR u) († - ipotesi assurda)
Consideriamo ora un F-modello M = hW, {Ra: a ∈ A}, Isi, tale che:
20 Corrispondenza
Questo equivale a dire che:
M tp ⇔ sRat (?) Allora M s2pa M s2p →a 2a2p poiché F a 2B →a 2a2Ba M s2a2pa per MP M t2pa (sRa t) M up (tRau)
Per (?) segue che s Ra u, in contraddizione con (†). Possiamo dunque concludere che F è
transitiva. Teorema 2.11. (serialità) F 2B →a 3B sse F ∀s∃t.s Ra a t Dimostrazione. ⇐) Esercizio. ⇒)
Procediamo per assurdo:
F 2B →a 3Ba ∃s∀t.¬(sRa t) (†- ipotesi assurda) Allora: M s2pa M s2p →a 3pa M s3pa ∃t ∈ W.sR t e M tA
contrariamente a quanto affermato da (†). Possiamo dunque concludere che la struttura è seriale.
Teorema 2.12. (simmetria) F B →2a3B sse F ∀s, t.s Ra at ⇒ tRas Dimostrazione. ⇐) Esercizio. ⇒)
Procediamo anche in questo caso per assurdo: F B →2a3Ba
∃s, t.sRat ∧ tRas (†- ipotesi assurda)
Consideriamo ora un F-modello: M = hW, {Ra: a ∈ A}, Isi, tale che:
Questo equivale a dire che: M tp ⇔ s = t (?) Allora: M sp M sp →2a3pa M s2a3pa per MP ∀t : sRa t.M t3pa ∃u.tRaue M up u = s (per ?) ∀t.sRat ⇒ tRas
Ma quest’ultima affermazione è in contraddizione con (†), per cui possiamo concludere che F è simmetrica. Teorema 2.13. (euclidea) F 3B →a 2a3B sse F ∀s, t, u.s Ra at ∧ sRau ⇒ tRau Dimostrazione. ⇐) Esercizio. ⇒)
Procediamo per assurdo:
F 3B →a 2a3Ba
∃s, t, u.sRa t ∧ sRa u ∧ ¬(tRau) (†- ipotesi assurda)
Costruiamo il “solito” (contro)modello su F ponendo: Iu= {v : v = u}
che equivale a dire:
M vp ⇔ v = u (?) Allora: sRa u ∧ sRat M s3pa M s3p →a 2a3pa M s2a3pa M t3pa ∃v ∈ W : tRa ve M v p v = u (per ?) tRau
Ma quest’ultima conclusione contraddice quanto affermato in (†). Possiamo dunque concludere che F è euclidea.
Teorema 2.14. (convergenza debole)
F 3a2B →a 2a3B ssea
22 Corrispondenza
Dimostrazione. ⇐)
Esercizio. ⇒)
Procediamo per assurdo: F 3a2B →a 2a3Ba
∃s, t, u.sRa t ∧ sRau ∧ ∀v.¬(tRa v ∧ uRav) (†- ipotesi assurda)
Costruiamo il seguente (contro)modello su F in cui: Iv(p) = {s : vRas}.
Questo equivale a dire che
M sp ⇔ vRas (?) Allora: sRat ∧ sRa u M t2pa M s3a2pa M s3a2p →a 2a3pa M s2a3pa M u3pa ∃v1.uRav1∧ M v1 p M t3pa ∃v2.tRav2∧ M v2 p v1= v2= v (per ?) uRav ∧ tRav
Quest’ultima affermazione, ancora una volta, contraddice (†). Possiamo perciò concludere che F è de-bolmente convergente.
Teorema 2.15. (connessione debole)
F 2(a 2B ∧ B → C) ∨a 2(a 2C ∧ C → B) sse F connessione debolea
Dimostrazione. ⇐)
Esercizio. ⇒)
Supponiamo che F non sia debolmente lineare. Allora
∃w, v, z[wR v ∧ w R z ∧ ¬v R z ∧ ¬z R v ∧ z 6= v] Costruiamo l’F-modello M per cui
• Se M w2(2p ∧ p → q) allora
M v 2p ∧ p → q.
Valgono inoltre
M vp (perché v ∈ I(p))
M v2p (perché t ∈ I(p) per ogni mondo t relato a v)
Ma allora per MP ricaviamo
M vq
pertanto zR v ∨ z = v, contro le ipotesi.
• Se M 2(2q ∧ q → p), si procede simmetricamente al caso precedente, scambiando p e q.
Teorema 2.16. (funzionalità parziale)
F 3B →a 2B sse F ∀s, t.s Ra at ⇒ ∃!u.sRa u Dimostrazione. ⇐) Esercizio. ⇒)
Supponiamo per assurdo che F non sia parzialmente funzionale. Allora ∃w, v, u[wR v ∧ w R u ∧ v 6= u]
Poiché F 3B →a 2B, per ogni F-modello M vale M a
w3B →a 2B.a
Sia I(p) = {v}. Allora
M vp
⇒ M w3pa
⇒ M w2p (per MP)a
⇒ M up
Ma allora u ∈ I(p), contro le ipotesi.
Teorema 2.17. (funzionalità) F 3B ↔a 2B sse F ∀s∃!t.s Ra a t Dimostrazione. ⇐) Esercizio. ⇒)
Supponiamo per assurdo che Fnon sia funzionale. Allora per qualche w: ¬∃v(wRa v) ∨ ∃u, v(u 6= v ∧ wRau ∧ wRa v)
24 Corrispondenza
1. se ¬∃v(wRa v)allora per ogni F-modello Mvale M w2B. Dalla formula data ricaviamoa
quindi M w3B. Ma alloraa
∃v(wRav ∧ M vB)
il che contraddice l’ipotesi;
2. se ∃u, v(u 6= v ∧ wRa u ∧ wRav)si procede come nel caso della funzionalità parziale.
Teorema 2.18. (proprietà di Sahlqvist)
F 3am2anB →2ak3ajB sse F s Rmt ∧ sRku → ∃v.tRnv ∧ uRjv Dimostrazione. ⇐) Esercizio. ⇒)
Procediamo per assurdo: sRm
a t ∧ sRak u
∀v.¬(tRn
a v ∧ uRaj v) (†- ipotesi assurda)
Costruiamo il seguente F-(contro)modello M = hW, {Ra}a∈A, Iti, ponendo:
It(p) = {v : tRanv}
Questo equivale a dire che:
M vp ⇔ tRanv (?) Allora M t2anp M s3am2anp M s3am2anp →2ak3ajp M s2ak3ajp M u3ajp ∃v : uRj a v ∧ M vp ∃v : uRj a v ∧ tRanv (per ?)
Ma questo contraddice quanto affermato in (†), per cui possiamo concludere che F soddisfa la proprietà di Sahlqvist.
Esercizio Si faccia vedere che tutte pe proprietà considerate in questo capitolo sono casi particolari della proprietà di Sahlqvist.
Teorema 2.19. (ordine dualmente ben fondato)
F 2(2B → B) → 2B sse F dualmente ben fondato Dimostrazione.
⇐)
Figura 2.2: Il sottomodello di riferimento
⇒)
Procediamo come al solito per assurdo. F 2(2B → B) → 2B
F non è dualmente ben fondata († - ipotesi assurda)
Se Ra non è dualmente ben fondata esiste una successione infinita crescente. Sia X l’insieme di
tali elementi e sia w ∈ X tale che wRv per ogni v ∈ X, v 6= w. Consideriamo il seguente modello in cui
IX(p) = {v : v /∈ X}.
Equivale a dire:
v 6∈ X ⇔ M v p.
Si veda la Figura2.2.
Poiché M 2w2p per definizione di I, segue che:
M 2w2(2p → p)
M w3(2p ∧ ¬p)
∃x.wRax ∧ M x2p ∧ M x¬p
Per definizione di X (e per il fatto che M x ¬p), possiamo affermare che x ∈ X. Ma allora per
tutti gli elementi y ∈ X tali che xRy M y¬p, in contraddizione col fatto che M x2p.
Adesso mostriamo invece che:
F 2(2p → p) → 2p =⇒ F è transitiva.
Per farlo, definiamo un’interpretazione I ad hoc, come segue. Chiamiamo x un generico mondo in cui valga l’enunciato p, e prendiamo poi un secondo punto, che chiameremo a (definito come?). Sapendo che R?denota la chiusura riflessiva e transitiva di R, relazioniamo i punti ad a come segue:
Ia(p) = {x : ∀y.xR?y → aR y}
Ovvero, per ogni x in cui valga l’enunciato p, stabiliamo che tutti i punti ad esso relati (diretta-mente o indiretta(diretta-mente) sono relati anche al punto a. Notiamo che l’interpretazione permette ad adi essere relato anche ad altri mondi.
Si dimostra quindi che a2(2p → p) da cui a2p quindi bpper un generico b tale che aRb. Da
questo deriviamo che b è uno degli x usati nella definizione del diagramma (perché in esso vale p). Ne consegue che bRc (chi è c?) quindi, per cui c p(da cosa?). Da ciò deriviamo che c è uno
degli y relati ad x per cui (per costruzione) aRc.
2.4
Esercizi
26 Corrispondenza a 21A=2Aa a 31A=3Aa a 2n(2amA)=2an+mA a 3n(3amA)=3an+mA
Esercizio 2.2. Dimostrare che:
sR1t ⇔ sR t
sRn t ∧ tRmy ⇒ sRn+m
Esercizio 2.3. Mostra cheR?è riflessiva e transitiva. (Suggerimento: sfrutta l’ esercizio2.2)
Esercizio 2.4. Completa la dimostrazione del seguenti Lemmi :2.7e2.8.
Esercizio 2.5. Completa le dimostrazioni dei teoremi di caratterizzazione: da Teorema2.9a Teorema
Manipolazione di modelli
Presentiamo sotto due tecniche per trasformare modelli o per metterli in relazione con altri che po-tremmo dire “simili”. Queste due tecniche prendono il nome di generazione di sottomodelli e p-morfismi fra modelli.
3.1
Sottomodelli generati
Un sottomodello è una “restrizione” di un modello, creata ad-hoc per valutare la verità di una for-mula in un singolo punto t. Per fare questo, dunque, possiamo concentrare l’attenzione sui soli punti collegati al punto t cui siamo interessati attraverso una o più “salti” delle relazioniRa.
Definizione 3.1. (A-chiusura)Sia A un insieme di indici di relazioni, diciamo che un sottinsieme X ⊆ W è A-chiuso se soddisfa la seguente condizione:
u ∈ X ⇒ (∃a ∈ A, v ∈ W.uRav ⇒ v ∈ X)
Proposizione 3.2. Sottolineiamo che l’intersezione di due insiemi A-chiusi è a sua volta un insieme A-chiuso. Definizione 3.3. (sottomodello generato)Dato un generico modello:
M = hW, {Ra}a∈A, Ii,
chiamiamo suo sottomodello generato da t il seguente modello: Mt= hWt, {Rt
a}a∈A, Iti,
dove:
• Wtè il più piccolo sottoinsieme A-chiuso di W che contenga t;
• Rt
a=Ra ∩(Wt× Wt)
• It(p) = I(p) ∩ Wt
Lemma 3.4. (del sottomodello generato) Dati A ∈ FmΦAe s ∈ Wt, allora:
Mt
sA ⇔ M sA
Dimostrazione.
Esercizio. (Suggerimento: si proceda per induzione sulla struttura di A).
28 Manipolazione di modelli
3.2
P-morfismi
In questa sezione limitiamo la nostra discussione a strutture relazionali contenenti una sola relazione di accessibilità. Date due tali strutture relazionali, vogliamo definire una procedura per metterle a confronto sí da poter stabilire se e come viene conservata la validità delle formule in tali strutture.
Definizione 3.5. Date due strutture relazionali F1 = hW1, Rie F2 = hW2, Si, chiamiamo p-morfismo1
una funzione f che goda delle seguenti proprietà: 1. f : W1→ W2
2. ∀w, z ∈ W1[wRz =⇒ f (w)Sf (z)]. Questa proprietà è descritta graficamente dalla Figura3.1.
z f // f(z) w R OO f // f(w) S OO
Figura 3.1: La simmetria della condizione 2. 3. (back condition)
∀w ∈ W1, ∀y ∈ W2[f (w)Sy =⇒ ∃v ∈ W1.[wRv ∧ f (v) = y]]. Questa proprietà è descritta
graficamente dalla Figura3.2.
w f (w) y -6 B B ZZ R S Figura 3.2: Back-condition
La condizione 3. dice che y è immagine sotto la funzione f di almeno un mondo relato a w. Ov-viamente possono esserci altri mondi relati allo stesso w che non vengono mappati sull’elemento y del codominio, come possono esserci mondi di W1non relati a w che vengono mappati su y.
Definizione 3.6. Un p-morfismo f è un p-morfismo fra modelli se vale anche la seguente condizione: dati i due modelli M =< W1, R, I1>e M2=< W2, S, I2>,
4. ∀w ∈ W [w ∈ I1 2
Lemma 3.7. Dati M1 = hW1,R1, I1i e M2 = hW2,R2, I2i ed un p-morfismo f : M1 → M2, allora per
ogni w ∈ W1, vale che:
M1wA sse M2f (w) A
Dimostrazione.
Procediamo per induzione sulla costruzione della formula A.
• A = p: è il caso banale perché deriva direttamente dalla condizione 4 del p-morfismo; • . . . (completare la dimostrazione, v. pag 11 libro Goldblatt)
Osservazione 5. Quando il lemma vale i due modelli conservano la verità punto per punto e quindi li possiamo considerare a tutti gli effetti indistinguibili.
Osservazione 6. La condizione 4. è molto forte ed in genere l’esistenza di un p-morfismo fra due strut-ture non implica che possa essere esteso ad un p-morfismo fra modelli basati sulle strutstrut-ture stesse.
Richiamiamo alla mente la definizione di funzione suriettiva, dall’algebra.
Definizione 3.8. (funzione suriettiva)Data una funzione f : A → B, diciamo che essa è suriettiva se vale quanto segue:
∀y ∈ B.∃x ∈ A.f (x) = y
Definizione 3.9. (p-morfismo suriettivo)Dati i due modelli M1 = hW1,R1, I1i e M2 = hW2,R2, I2i
ed un p-morfismo f : M1→ M2fra loro, diciamo che f è suriettivo se la funzione f : W1→ W2su cui
esso si basa è a sua volta suriettiva.
Definizione 3.10. (immagine p-morfa)Se f : F1 → F2è un p-morfismo suriettivo tra due strutture,
allora diremo che F2è un’immagine p-morfa di F1.
Lemma 3.11. (lemma del p-morfismo suriettivo su modelli) Dati due modelli ed un p-morfismo f : M1→
M2fra loro, se f è suriettivo vale che:
M1 A ⇔ M2 A
Dimostrazione. Esercizio.
Lemma 3.12. (lemma del p-morfismo suriettivo su strutture) Dati due modelli ed un p-morfismo f : F1→
F2fra loro, se f è suriettivo vale che:
F1 A ⇒ F2 A
Dimostrazione.
La dimostrazione procede per contrapposizione, ovvero mostriamo che: F22 A ⇒ F12 A. Vale che: F2= hW2,R2i F22 A ∃t ∈ W2, M2.M22tA (M2è un F2-modello) ∃s ∈ W1.t = f (s) (f è suriettivo) M22f (s)A M12sA (per il lemma3.7)
30 Manipolazione di modelli
3.3
Proprietà non esprimibili
Vedremo in questa sezione alcune proprietà che non sono esprimibili (ovvero che non sono carat-terizzabili) per mezzo di formule modali. Per farlo utilizzeremo gli strumenti appena introdotti: i sottomodelli generati ed i p-morfismi.
Teorema 3.13. (la direzione non è esprimibile) La seguente congettura è falsa: per qualche A ∈ FmΦA,
F A ⇒ F diretta Dimostrazione.
Chiamiamo RD la classe delle relazioni dirette e RDD la classe delle relazioni debolmente dirette. È ovvio che RD ⊆ RDD. Inoltre, è possibile
Teorema 3.14. (la connessione non è esprimibile) a
Dimostrazione. d
Teorema 3.15. (l’irriflessività non è esprimibile) La seguente congettura è falsa:
per qualche fbf A, F A sse F è irriflessiva. Dimostrazione.
Rè irriflessiva =df: ∀x.¬(xRx)
Si consideri la struttura F2 = h{0}, {h0, 0i}i che è immagine p-morfa di hN, <i secondo la funzione
f (n) = 0, per qualsiasi n ∈ N.
Verifichiamo che le tre proprietà dei p-morfismi siano soddisfatte: • f : N → {0}
• ∀n, m ∈ N.n < m ⇒ f(n) R f(m) ⇔ 0 R 0 • la back-condition vale, poiché banalmente
f (n)Ry
∃m.(n < m ∧ f (m) = y) La situazione è sintetizzata graficamente nella Figura3.3.
0 • // )) 1 • // %% 2 • // 3 • // 4 • // . . . xx 0 •XX Figura 3.3: Un p-morfismo da N a {0}
Supponiamo che per qualche fbf A, F A sse F è irriflessiva. Ma hN, <i è irriflessiva, dunque hN, <i A, allora F2 A (per l’esistenza del p-morfismo), per cui F2 sarebbe irriflessiva, in
con-traddizione con la definizione data di F2. Da qui l’assurdo.
Teorema 3.16. (l’antisimmetria non è esprimibile) La seguente congettura è falsa: per qualche A ∈ FmA:
F A sse F è antisimmetrica. Dimostrazione.
Si consideri la struttura:
F2= h{a, b}, {ha, ai, ha, bi, hb, bi, hb, ai}i,
che è immagine p-morfa della struttura hN, <i (la quale è antisimmetrica) attraverso la funzione se-guente:
f (n) =
a, se n è pari b, se n è dispari
Anche in questo caso si può verificare semplicemente (esercizio) come f soddisfi i tre criteri che defini-scono un p-morfismo. Graficamente la situazione è descritta dalla Figura3.4.
Supponiamo che per qualche fbf A, F A sse F è antisimmetrica. Ma hN, <i è antisimmetri-ca, dunque hN, <i A, allora F2 A (per l’esistenza del p-morfismo), da cui deriviamo che F2 è
antisimmetrica. Questo però contraddice la definizione data di F2e genera l’assurdo che dimostra il
teorema.
Osservazione 8. Notiamo che nella Figura3.4non sono disegnate le frecce n → m dove n ed m differi-scono di 2 o più. Tali frecce sono comunque da intendersi come presenti, e non rappresentate solo per non “sporcare” il diagramma.
Osservazione 9. Sempre nella Figura3.4, notiamo che la freccia riflessiva a → a (risp. b → b) in F2è
ancora necessaria, perché corrisponde alla freccia n < m in F1dove n ed m sono entrambi pari (risp.
dispari). 0 • // %% 1 • // %% 2 • // 3 • // 4 • // yy 5 • // yy . . . • aXXoo //EE•b
Teoria della dimostrazione
4.1
Logiche modali normali
Definizione 4.1. 7.1Si definisce logica modale normale in un linguaggio LΦ
A qualunque insieme L di
formule tale che
• L contiene tutte le tautologie,
• L è chiuso rispetto al modus ponens (MP),
• L contiene le formule Ka:2(A → B) → (a 2A →a 2B) con a ∈ A,a
• L è chiuso rispetto alla regola di necessitazione NEC : B `2B con a ∈ A.a
La definizione di logica modale normale data sopra suggerisce immediatamente di formalizzare le dimostrazioni in sistemi deduttivi alla Hilbert. Si tratta quindi di adattare l’assiomatizzazione della logica proposizionale al caso delle logiche modali normali: sarà sufficiente aggiungere agli assiomi classici l’assioma K. Inoltre assumeremo come regola d’inferenza primitiva non soltanto il MP , ma anche la necessitazione NEC . In questo modo otteniamo l’assiomatizzazione della logica KA:
(1.1) A → (B → A) (1.2) (A → (B → C)) → ((A → B) → (A → C)) (2.1) A ∧ B → A (2.2) A ∧ B → B (2.3) (A → B) → (A → C) → (A → B ∧ C) (3.1) A → A ∨ B (3.2) B → A ∨ B (3.3) (A → B) → (C → B) → (A ∨ C → B) (4.1) (A → B) → ((A → ¬B) → ¬A) (4.2) A → (¬A → B) (4.3) ¬¬A → A (5.1) ⊥ → (A ∧ ¬A) (Ka) 2(A → B) → (a 2A →a 2B) con a ∈ Aa
Definizione 4.2. (L-deduzione)Sia Γ un insieme di enunciati. Si scrive Γ `LB
e diciamo che da Γ si deduce B in L se e solo se B: • appartiene a Γ; oppure
34 Teoria della dimostrazione
• è stata ottenuta partendo da due formule deducibili da Γ in L e applicando MP; oppure • è stata ottenuta partendo da una formula deducibile da Γ in L e applicando NEC .
Definizione 4.3. (teorema) Bè un teorema di L se e solo se `LB, cioè se B si deduce dall’insieme vuoto
in L.
Si mostra facilmente che l’insieme dei teoremi di KAè una logica modale normale: in particolare, si
tratta della più piccola logica normale.
Osservazione 10. Nel seguito, con L si indicherà una qualunque logica nel linguaggio LΦ
Ache estenda
KA(vale a dire: qualunque logica normale).
4.2
Insiemi massimali e consistenti
Definizione 4.4. (L-consistenza)Sia L una logica. Γ è un insieme di formule L-inconsistente se e solo se esistono enunciati B1, . . . , Bn∈ Γ tali che
`LB1∧ . . . ∧ Bn→ ⊥
Γè L-consistente se e solo se non è L-inconsistente.
Definizione 4.5. (insieme massimale)Un insieme Γ di formule di FmΦAsi dice massimale se e solo se
per ogni enunciato B in FmΦAsi ha B ∈ Γ oppure ¬B ∈ Γ.
Proposizione 4.6. Si mostra facilmente (esercizio) che se Γ è L-consistente e massimale, allora • B 6∈ Γ ⇒ Γ ∪ {B} è L-inconsistente.
• se Γ ⊆ ∆ e ∆ è L-consistente, allora Γ = ∆ (da cui l’uso dell’aggettivo “massimale”). • L ⊆ Γ • ⊥ 6∈ Γ • ¬B ∈ Γ ⇔ B 6∈ Γ • (B → C) ∈ Γ ⇔ (B ∈ Γ ⇒ C ∈ Γ) • (B ∧ C) ∈ Γ ⇔ (B ∈ Γ e C ∈ Γ) • (B ∨ C) ∈ Γ ⇔ (B ∈ Γ oppure C ∈ Γ) • (B ↔ C) ∈ Γ ⇔ (B ∈ Γ ⇔ C ∈ Γ)
Lemma 4.7. (di Lindenbaum) Sia Γ un qualunque insieme L-consistente,
Γ ⊆ ∆, dove ∆ è un insieme L-consistente e massimale.
Dimostrazione.
Mostriamo costruttivamente che un tale insieme L-consistente e massimale esiste sempre, partendo da qualsiasi insieme L-consistente.
Si enumerano le formule di FmΦA1
B0, B1, . . . , Bn, . . .
Si costruisce induttivamente la seguente catena di insiemi di formule: ∆0 = Γ
∆n+1 =
∆n∪ {Bn} se questo è L-consistente
∆n∪ {¬Bn} altrimenti
Si pone infine ∆ =S{∆n: n ≥ 0}. Mostriamo che ogni ∆nè L-consistente. Per induzione su n:
: ∆0 , e Γ è L-consistente per ipotesi
n = k + 1: se ∆k+1 = ∆k ∪ {Bk}, allora ∆k+1 è L-consistente per costruzione; se invece ∆k+1 =
∆k∪ {¬Bk}, allora per costruzione ∆k∪ {Bk} non è L-consistente, quindi
`LD1∧ . . . ∧ Dj∧ Bk → ⊥ con {D1, . . . , Dj} ⊆ ∆k
`LD1∧ . . . ∧ Dj→ (Bk → ⊥)
Se ∆k∪ {¬B} fosse L-inconsistente avremmo, per qualche {E1, . . . , Ei} ⊆ ∆k:
`LE1∧ . . . ∧ Ei∧ ¬Bk→ ⊥
`LE1∧ . . . ∧ Ei→ (¬Bk → ⊥)
`LD1∧ . . . ∧ Dj∧ E1∧ . . . ∧ Ei→ [(B → ⊥) ∧ (¬B → ⊥)]
`LD1∧ . . . ∧ Dj∧ E1∧ . . . ∧ Ei→ ((B ∨ ¬B) → ⊥)
`LD1∧ . . . ∧ Dj∧ E1∧ . . . ∧ Ei→ ⊥
contrariamente al fatto che ∆kè L-consistente per ipotesi induttiva.
Bisogna ora mostrare che ∆ è L-consistente. Se non lo fosse, esisterebbero formule {D1, . . . , Dj} ⊆ ∆
tali che `LD1∧. . .∧Dj→ ⊥. Siano ∆f (1), . . . , ∆f (j)gli insiemi della catena tali che D1∈ ∆f (1), . . . , Dj∈
∆f (j). Sia k = max{f (1), . . . , f (j)}. Poiché ∆k ⊇ ∆f (i)per ogni i ≤ j, ∆k è L-inconsistente contro
quanto fatto vedere precedentemente.
Si mostra infine che ∆ è massimale. Sia B ∈ FmΦA. B occorrerà con un certo indice, diciamo k,
nell’enumerazione delle formule data all’inizio. Dunque B ∈ ∆k+1oppure ¬B ∈ ∆k+1. Ne segue che
B ∈ ∆oppure ¬B ∈ ∆.
Corollario 4.8. Per ogni formula A vale quanto segue:
`LA ⇔ ∀w ∈ WL, A ∈ w.
Dimostrazione. • ⇐)
Si vede subito che se 6`LAallora {¬A} è L-consistente, infatti se così non fosse avremmo
`L¬A → ⊥
⇒ `L¬¬A
⇒ `LA
contro l’ipotesi che A non sia dimostrabile. Poiché {¬A} è L-consistente, per il lemma di Linden-baum esiste un w ∈ WLtale che ¬A ∈ w, quindi A 6∈ w perché Γ è L-consistente.
• ⇒)
36 Teoria della dimostrazione
4.3
Il modello canonico
Definizione 4.9. (modello canonico)Il modello canonico di una logica L è indicato con: ML= hWL,RL, ILi,
dove:
• WLè la classe di tutti gli insiemi Γ che siano sottinsiemi L-consistenti massimali di FmΦ A. • sRLt ⇔ (∀2B ∈ s.∃B ∈ t) • ILè tale che IL(p) = {w ∈ WL: p ∈ w}. Lemma 4.10. (box-lemma) ∀s, t ∈ WL, C ∈ FmΦ A.(2C ∈ s ⇔ s RaLt ⇒ C ∈ t) Dimostrazione. ⇒)
Si può mostrare (esercizio) che deriva direttamente dalla definizione diRL a.
⇐)
Per contrapposizione: supponiamo che2C 6∈ s e costruiamo un t ∈ WLtale che C /∈ t. Poniamo
Γ = {D ∈ FmΦA:2D ∈ s}
Mostriamo che Γ ∪ {¬C} è L-consistente: se non lo fosse, esisterebbero formule D1, . . . , Dn ∈ Γ
tali che `LD1∧ . . . ∧ Dn∧ ¬C → ⊥ `LD1∧ . . . ∧ Dn→ (¬C → ⊥) `LD1∧ . . . ∧ Dn→ C `L2D1∧ . . . ∧2Dn→2C 2D1, . . . ,2Dn∈ s
2C ∈ s (s è massimale, per def. di modello canonico) Quello che abbiamo derivato, però, contraddice l’ipotesi, da cui l’assurdo.
Per il lemma di Lindenbaum segue che esiste t ∈ WLtale che Γ ∪ {¬C} ⊆ t. Allora essendo anche
Γ ⊆ t, si ha sRLted essendo ¬C ∈ t, concludiamo che C 6∈ t, come desiderato.
Lemma 4.11. (diamond-lemma)
∀s, t ∈ WL.sRLt ⇔ ∀B ∈ t.∃3B ∈ w
Dimostrazione. ⇒)
Supponiamo che w RL v e C ∈ v: per il lemma fondamentale4.14, ML
v C e quindi, per
definizione (di modello canonico) ML
w 3C. Ma allora, di nuovo per il lemma fondamentale,
Per contrapposizione, dimostriamo che ¬(wRLv) ⇒
E C ∈ v : 3C /∈ w
Per definizione diRL, se ¬(wRLv), esiste una formula B tale che2B ∈ w e B /∈ v. Essendo w e
vmassimali, segue che ¬2B /∈ w e ¬B ∈ v. Equivalentemente, 3¬B /∈ w e ¬B ∈ v. Ma allora ¬B è proprio la proposizione C che cercavamo.
Osservazione 11. Notiamo quanto la formulazione del diamond-lemma sia simile alla definizione della relazione canonica (a parte la posizione invertita degli operatori modali).
Definizione 4.12. (valida, completa, determinata)Sia H una classe di frame o di modelli. Una logica Lè valida su H se per ogni A:
`LA ⇒ H A.
Una logica L è completa rispetto a H se per ogni A:
H A⇒ `LA.
Lè determinata da H se è sia valida sia completa rispetto a H, ossia: H A⇔ `LA.
Definizione 4.13. (strutture per la logica)Diciamo che la struttura F è una struttura per la logica L se e solo se L è valida su F.
Vorremmo ora dimostrare che una logica L è determinata dal corrispondente modello canonico. Questo risultato è immediata conseguenza del seguente lemma.
Lemma 4.14. (fondamentale del modello canonico) Per ogni B ∈ FmΦAed ogni w ∈ WL:
ML
wB ⇔ B ∈ w
Dimostrazione.
Per induzione sulla costruzione di B.
B ≡ p: il lemma vale per la definizione di ML.
B ≡ ¬C: ML
w¬C ⇔ ML6wC ⇔ C /∈ w ⇔ ¬C ∈ w.
B ≡ C ∧ D: ML
wC ∧ D ⇔ MLwCe MLwD. Per ipotesi induttiva, questo equivale a dire che
C ∈ we D ∈ w: ma allora anche C ∧ D ∈ w, essendo w massimale. B ≡ C ∨ D: ML
wC ∨ D ⇔ ML w Coppure ML w D. Per ipotesi induttiva ciò equivale a dire
che C ∈ w oppure D ∈ w: ma allora anche C ∨ D ∈ w, essendo w massimale. B ≡ C → D: ML
w (C → D) ⇔ ML 6w Coppure ML w D ⇔ C /∈ w oppure D ∈ w ⇔ (C →
D) ∈ w
B ≡2C: ML
w2C ⇔ A v : wRLv, MLvC. Per ipotesi induttiva, questo è equivalente a dire che
A
38 Teoria della dimostrazione Corollario 4.15. Ogni logica L è determinata dal modello canonico, ossia per ogni A ∈ FmΦA
`LA ⇔ ML A.
Dimostrazione.
Le seguenti affermazioni sono equivalenti: `LA A ∈ w (Corollario4.8) ∀w.ML wA (Lemma4.14) ML A
Osservazione 12. Dal corollario segue che L è completa rispetto alla struttura FL= hWL,RLi, cioè
FL
A ⇒`LA
Ma L non è necessariamente valida rispetto a FL: infatti nulla ci autorizza a dire che una proposizione
Completezza
Abbiamo introdotto il concetto di completezza con la Definizione4.12. In questo capitolo ci concentria-mo su come possiaconcentria-mo diconcentria-mostrare che alcune logiche sono complete rispetto a certe classi di strutture. Per farlo, inizieremo introducendo alcune definizioni che risulteranno utili. In un secondo momen-to delineiamo il memomen-todo che utilizzeremo per condurre la maggior parte delle dimostrazioni. Infine presenteremo la carrellata dei teoremi di completezza.
5.1
Strumenti
Definizione 5.1. (logica canonica)Una logica L è canonica se la struttura relazionale FLsui cui è basato
il modello canonico MLè una struttura per L, ovvero tale che
`LA ⇒ FL A
Se indichiamo con CLla classe delle strutture relazionali per L, ed inoltre L è canonica, allora L è
determinata dalla classe CLdelle strutture per L:
CL A ⇔ `LA
Osservazione 13. Si noti che esistono logiche canoniche che non sono complete rispetto ad alcuna classe di strutture relazionali: in questo caso si ha che per qualche fbf A
CL A e 6`LA
Definizione 5.2. Introduciamo qui due operatori insiemistici che utilizzeremo ampiamente in seguito. Per ciascun w ∈ WL:
2−(w) = {B ∈ FmΦ
A:2B ∈ w}
3+(w) = {3B ∈ FmΦ
A: B ∈ w}
Nelle dimostrazioni successive, potremo quindi dire che wRLvse e solo se v ⊇2−(w)(per come
abbiamo definito la relazione canonica nella Definizione4.9) oppure, equivalentemente, se e solo se w ⊇3+(v)(per il Lemma4.11).
5.2
Metodo
40 Completezza
1. vogliamo dimostrare che C A⇒ `LA;
2. per contrapposizione, mostriamo che 0LA ⇒ C 2 A;
3. da 0LAricaviamo ML2 A e quindi FL2 A; 4. Cerchiamo di dimostrare che FL∈ C;
5. FL
∈ C ⇒ C 2 A.
Pertanto per dimostrare la completezza di una logica rispetto a una certa classe di strutture, è sufficiente dimostrare che la struttura su cui è basato il modello canonico appartiene a quella classe (passo 4). Gli altri passi del metodo appena delineato, sono garantiti veri dalle proprietà già presentate del modello canonico.
Quanto appena detto dimostra il seguente teorema:
Teorema 5.3.
FL∈ C ⇒ L è completa o, equivalentemente:
Lè incompleta ⇒ FL6∈ C
5.3
Logiche
In questa sezione presentiamo gerarchicamente alcune logiche, mostrate nella Figura5.1, e per ciascuna di esse ricaveremo un teorema di completezza rispetto ad opportune classi di strutture.
Teorema 5.4. La logica K è completa rispetto alla classe delle strutture relazionali, ossia per qualunque C
C A⇒ `KA. Triv S5 OO S4.3 ccFFFF FFFF S4.2 OO S4 OO KW D B KK T ;;x x x x x x x x x X K4 OO K ggPPPPPPPPPPPP PPP aaCCCC CCCC OO xxxxx;;x x x x 55k k k k k k k k k k k k k k k k k
Dimostrazione.
In questa dimostrazione non faremo uso del metodo presentato, ma mostreremo per contrapposizione come: 6`KA ⇒ C 6 A.
6`KB
MK6 B
FK6 B
C 6 B (FKè una struttura relazionale)
Teorema 5.5. T è completa rispetto alla classe delle strutture riflessive.
Dimostrazione.
Procediamo nel modo canonico dimostrando che MTè riflessivo, ossia che w ∈ WT⇒ w RT a w, o in
altre parole che2C ∈ w ⇒ C ∈ w. Si ricordi l’assioma: Ta :2C → Ca
Per ogni w ∈ WT, è vero quanto segue:
a 2C → C ∈ w (w è massimale) a 2C ∈ w (ipotesi) C ∈ w (w è massimale, e vale T) a 2C ∈ w ⇒ C ∈ w wRTw (def. diRT a)
Questo conclude la dimostrazione.
Teorema 5.6. D è completa rispetto alle strutture seriali.
Dimostrazione.
Procediamo nel modo canonico: occorre mostrare che nel modello canonico di D,RDè seriale. Si ricordi
l’assioma
Da :2A →a 3Aa
Anzitutto notiamo che vale quanto segue, per ciascun w ∈ WD:
`D> (def. di w)
`D2>a (NEC)
`D3>a (per D)
∀w ∈ WD.3> ∈ w (†)a
Ora prendiamo un qualunque w ∈ WDe mostriamo che esiste un v ad esso relato. Evidentemente, dalla
definizione di relazione canonica, è necessario che v sia un’estensione massimale di2−(w)(cfr. Defini-zione4.9e Definizione5.2). A questo punto non ci rimane che mostrare che2−(w)è D-consistente, ed il Lemma di Lindenbaum ci garantirà che tale estensione esiste.
Procediamo per assurdo. Per qualunque w ∈ WD:
2−(w)è D-inconsistente (ip. assurda)
∃A1, . . . , An ∈2−(w). `DA1∧ . . . ∧ An→ ⊥ `D2(Aa 1∧ . . . ∧ An→ ⊥) (NEC) `D2(A → B) →a 2A →a 2Ba (assioma K) `D2(Aa 1∧ . . . ∧ An) →2⊥a a 2(A1∧ . . . ∧ An) →2⊥ ∈ wa
A1∧ . . . ∧ An∈ w (per ipotesi e perché w è cons. e mass.)
2(A1∧ . . . ∧ An) ∈ w (w è cons. e mass.)
42 Completezza
Ma questo contraddice (†), da cui l’assurdo.
Riassumendo:2−(w)è D-consistente e per il Lemma di Lindenbaum esso può essere esteso ad un insieme v consistente e massimale (esistenza). Segue dalla definizione diRD che w RD
a v. Pertanto,
dato che ogni punto w del modello canonico ha un punto relato, il modello è seriale.
Teorema 5.7. X è completa rispetto alle strutture debolmente dense.
Dimostrazione.
Consideriamo la logica X = K + X, dove
X :22A → 2A
Procediamo nel modo usuale, dimostrando cioè che il modello canonico è basato su una struttura debolmente densa. La relazione densa debole è così definita:
A w A v[wRXv → E z(w RXz ∧ zRX v)]. w // A A A A v z ??~ ~ ~ ~
Figura 5.2: Relazione densa debole
Avendo supposto che w RX v, mostriamo che esiste un mondo z che rispetti la suddetta
for-mula e per farlo seguiamo la tecnica usata nel precedente teorema: z esiste, se e solo se vale che z ⊃ eq2−(w) ∪3+(v). Ma se riusciamo a dimostrare che2−(w) ∪3+(w)è X-consistente, allora dal
Lemma di Lindenbaum deduciamo che ∃z.z è consistente e massimale e z ⊇ {2−(w) ∪3+(w), il che
concluderebbe la nostra dimostrazione.
Procediamo dunque per assurdo per dimostrare che2−(w) ∪3+(w)è X-consistente. Supponiamo
che non lo sia: allora
`XA1∧ . . . ∧ An∧3C1∧ . . .3Ck → ⊥
dove2A1, . . . ,2An∈ w e C1, . . . , Ck∈ v. Possiamo derivare:
`XA1∧ . . . ∧ An∧3(C1∧ . . . ∧ Ck) → ⊥ `XA1∧ . . . ∧ An→ ¬3(C1∧ . . . Ck) `X2A1∧ . . . ∧2An→2¬3(C1∧ . . . ∧ Ck) `X2A1∧ . . . ∧2An→22¬(C1∧ . . . ∧ Ck) 2A1, →,2An∈ w 22¬(C1∧ . . . ∧ Ck) ∈ w 2¬(C1∧ . . . ∧ Ck) ∈ w (per assioma X) ¬(C1∧ . . . ∧ Ck) ∈ v (per ipotesi wRXv)
Ma questo contraddice l’ipotesi secondo cui (C1∧ . . . ∧ Ck) ∈ v, da cui l’assurdo.
2−(w) ∪3+(v)è quindi X-consistente, pertanto prendendo come z una sua estensione massimale
(la cui esistenza è garantita dal Lemma di Lindenbaum) otteniamo wRXzRXv, come richiesto.
Dimostrazione.
Consideriamo la logica K4 = K + 4, dove
4 :2A → 22A.
Per dimostrare che K4 è completa rispetto alle strutture transitive, dimostriamo che MK4 è basato
su una struttura transitiva. Ogni punto di MK4 contiene le istanze dell’assioma 4. Pertanto, fissati
x, y, z ∈ WK4tali che x RK4 y e y RK4 z, si ha, per ogni A tale che2A ∈ x, anche 22A ∈ x. Allora
2A ∈ y e di conseguenza A ∈ z.
Avendo dimostrato che, qualunque sia A, se2A ∈ x allora A ∈ z, e cioè che z ⊇ 2−(x), segue che
xRK4zcome richiesto.
Vedremo nella Sezione ?? che la logica K4 gode anche della proprietà della struttura finita.
Teorema 5.9. B è completa rispetto alle strutture simmetriche.
Dimostrazione.
Sia B = K + B, dove B è lo schema di assioma così definito: B : A →23A.
Si tratta di dimostrare che il modello canonico MB è simmetrico. Come al solito, ogni istanza di B
appartiene a ogni mondo del modello canonico: pertanto per ogni w ∈ WB, se A ∈ w allora anche
23A ∈ w (essendo w B-consistente massimale).
Supponiamo che wRBve che A ∈ w. Allora23A ∈ w e quindi 3A ∈ v. Allora v ⊇ 3+(w)e quindi
v RB w. Pertanto, poiché per ogni coppia di mondi relati in un verso vale anche la relazione in verso
opposto, il modello è simmetrico, come richiesto.
Teorema 5.10. S4 è completa rispetto alle strutture riflessive e transitive.
Dimostrazione.
La logica S4 è definita dai seguenti assiomi:
T :2A → A 4 :2A → 22A
Questi assiomi sono gli stessi delle logiche T e K4, pertanto il teorema segue direttamente dalla com-pletezza di T rispetto alle strutture riflessive e di K4 rispetto alle strutture transitive.
Teorema 5.11. S4.2 è completa rispetto alle strutture riflessive, transitive e debolmente dirette.
Dimostrazione.
Della logica S4.2 (nota talvolta col nome di logica G) sappiamo che essa è definita dai seguenti schemi
di assiomi: T :2A → A 4 :2A → 22A G :32A → 23A
Avendo già trattato le proprietà riflessiva e transitiva all’interno di S4, ci sarà sufficiente mostrare che il modello canonico di S4.2 è debolmente diretto. La proprietà diretta debole (Figura 5.3) è così definita:
∀s, t, u∃v.(sR t ∧ s R u → t R v ∧ u R b).
Avendo fissato s, t e u tali che s RS4.2 t e s RS4.2 u, dimostriamo l’esistenza di v che soddisfi la
condizione sopra. Questo equivale a dire che:
44 Completezza v t ?? u __? ? ?? s __>>>> >>>> ??
Figura 5.3: Relazione diretta debole
pertanto, analogamente alle logiche precedenti, si tratta di mostrare che2−(t)∪2−(u)è S4.2-consistente.
Anzitutto notiamo che è vero quanto segue:
2B1∧ . . . ∧2Bn ∈ u (per definizione)
32B1∧ . . . ∧32Bn∈ s
23B1∧ . . . ∧23Bn∈ s (per assioma G)
3B1∧ . . . ∧3Bn∈ t (‡)
Poi procediamo per assurdo:
2−(t) ∪2−(u)è S4.2-inconsistente (ip. assurda)
{A :2A ∈ t} ∪ {B : 2B ∈ u} è S4.2-inconsistente `S4.2A1∧ . . . ∧ Am∧ B1∧ . . . ∧ Bn→ ⊥
`S4.2A1∧ . . . ∧ Am→ ¬(B1∧ . . . ∧ Bn)
`S4.22(A1∧ . . . ∧ Am) →2¬(B1∧ . . . ∧ Bn)
`S4.22(A1∧ . . . ∧ Am) →2(¬B1∨ . . . ∨ ¬Bn) (†)
Ma (†) contraddice (‡), perché non può essere vero che, per qualche i, MS4.2
t3Bi∧2¬Bi. Da cui
l’as-surdo che dimostra come l’insieme2−(t) ∪2−(u)è S4.2-consistente, e da cui possiamo dedurre (come al solito per il Lemma di Lindenbaum) l’esistenza di v che soddisfa la proprietà diretta debole.
Teorema 5.12. S4.3 è completa rispetto alle strutture riflessive, transitive e debolmente connesse.
Dimostrazione.
La logica S4.3 è definita dai seguenti assiomi: T :2A → A 4 :2A → 22A L :2(A ∧ 2A → B) ∨ 2(B ∧ 2B → A)
Le dimostrazioni di completezza rispetto alle strutture riflessive e transitive sono in tutto e per tutto equivalenti a quelle date per le logiche T e K4. Perciò ci rimane da dimostrare solo che il modello canonico è debolmente connesso. La proprietà di connessione debole è così definita:
∀wtv.(wR t ∧ w R v → t R v ∨ t = v ∨ v R t).
Supponiamo per assurdo che il modello canonico non sia debolmente connesso: allora ∃wtv.(wRS4.3t ∧ wRS4.3v ∧ ¬(tRS4.3v) ∧ ¬(vRS4.3t) ∧ t 6= v).
In altre parole:
Essendo2A ∈ v non è difficile convincersi che 2(A ∨ C) ∈ v. Inoltre, poiché C ∈ v, anche A ∨ C ∈ v e quindi abbiamo:
2(A ∨ C) ∧ (A ∨ C) ∈ v. D’altra parte, poiché ¬C /∈ v e B /∈ v, si ha ¬C ∨ B /∈ v e quindi:
2(A ∨ C) ∧ (A ∨ C) → (¬C ∨ B) /∈ v. Ricordando infine che wRS4.3votteniamo:
2(2(A ∨ C) ∧ (A ∨ C) → (¬C ∨ B)) /∈ w. Istanziamo ora l’assioma L ponendo:
A 7→ A ∨ C B 7→ ¬C ∨ B. Otteniamo:
2(2(A ∨ C) ∧ (A ∨ C) → (¬C ∨ B)) ∨ 2(2(¬C ∨ B) ∧ (¬C ∨ B) → (A ∨ C)). Allora per ogni mondo x:
2(2(A ∨ C) ∧ (A ∨ C) → (¬C ∨ B)) ∈ x oppure 2(2(¬C ∨ B) ∧ (¬C ∨ B) → (A ∨ C)) ∈ x.
Avendo dimostrato che la prima delle due formule non appartiene a w, ne segue che: 2(2(¬C ∨ B) ∧ (¬C ∨ B) → (A ∨ C)) ∈ w
⇒ 2(¬C ∨ B) ∧ (¬C ∨ B) → (A ∨ C) ∈ t.
Ora consideriamo t. Poiché ¬C ∈ t, anche ¬C ∨B ∈ t; d’altra parte, essendo2B ∈ t, è facile convincersi che anche2(¬C ∨ B) ∈ t. Quindi anche la loro congiunzione:
2(¬C ∨ B) ∧ (¬C ∨ B) ∈ t. Per MP otteniamo allora:
A ∨ C ∈ t
⇒ A ∈ toppure C ∈ t. Ma in (†) e (‡) avevamo supposto A /∈ t e C /∈ t, da cui l’assurdo.
Teorema 5.13. S5 è completa rispetto alle strutture riflessive, transitive e simmetriche.
Dimostrazione.
La logica S5 è definita dagli assiomi: T :2A → A 4 :2A → 22A B : A →23A
La dimostrazione del teorema segue direttamente da quelle delle logiche T,K4 e B.
46 Completezza Teorema 5.14. La logica: T :2A → A 4 :2A → 22A E :3A → 23A
è completa rispetto alla classe di strutture basate su relazioni di equivalenza. Dimostrazione.
Esercizio
Teorema 5.15. Triv è completa rispetto alle strutture di punti isolati.
Dimostrazione.
Sia Triv = K + Triv, dove Triv è così definito:
Triv : A ↔2A.
Dobbiamo dimostrare che il modello canonico consiste di punti isolati, cioè che ∀xy.xRTriv y ↔ x = y. ⇒) Supponiamo xRTrivy. A ∈ x 2A ∈ x (per Triv) A ∈ y A ∈ x ⇒ A ∈ y (†) y ⊇ x
Ora dimostriamo che è vero anche il contrario, y ⊆ x, ovvero A ∈ y ⇒ A ∈ x. Lo facciamo per assurdo: per qualche formula B,
B ∈ y ∧ B 6∈ x (ip. assurda) ¬B ∈ x (x è massimale) ¬B ∈ y (per †)
y ⊇ {B, ¬B}
Ma ciò significa affermare che y non è consistente, da cui l’assurdo che prova il teorema. ⇐)
Dovremmo dimostrare che xRTriv xper ogni x, ma questo è immediato: notiamo infatti che da
Trivsi ricava subito2A → A, che è l’assioma T. È sufficiente, quindi, ricondursi alla completezza di T rispetto alle strutture riflessive.
Osservazione 14. Esistono tutta una serie di logiche che estendono K senza l’assioma T: KB,Ky,KW (che vedremo nel Capitolo ??) e infine Verum (che ha l’assioma2A, per ogni A). Verum è la logica dei mondi che non vedono niente, neanche se stessi. In una tale logica si dimostra2⊥.
5.4
Esercizi
Esercizio 5.1. Mostrare che i seguenti sono teoremi di KA:
Esercizio 5.2. Si dimostri la validità delle proprietà mostrate nella Proposizione4.6
Esercizio 5.3. Si completi la dimostrazione del Corollario4.8. Esercizio 5.4. Si completi la dimostrazione del Lemma4.10.
Modelli finiti
Ogni modello canonico è infinito, nel senso che, per come è stato costruito, WLcontiene infiniti elementi.
Questa caratteristica di WLè collegata a quello che potremmo chiamare “difetto per eccesso” di ML.
Come scrive Goldblatt: nel suo essere capace di falsificare ogni particolare non-teorema A, ML fornisce una
buona dose di informazione superflua (v. [Gol], p.31). Il valore di verità di una specifica fbf A in un mondo wdi WL è determinato unicamente dai valori di verità assunti dalle sole sottoformule di A stessa nel
mondo w ed in quelli ad esso relati.
L’idea che sta dietro il concetto di filtrazione è quella di raggruppare in una stessa classe X ⊆ WL
tutti i punti che assegnano gli stessi valori di verità a tutte le sottoformule di A. In altre parole: in X “collassano” tutti quei mondi che danno gli stessi valori di verità a ciascuna formula, e che quindi sono indistinguibili. Questo processo porta alla costruzione di un nuovo modello, che è basato su quello canonico e quindi continua a falsificare A, ma a differenza di questo ha una struttura finita.
Come si può osservare il modello così ottenuto per filtrazione è altamente ”specialistico”, costruito ad hoc per un preciso non-teorema A. Ovviamente dall’unico modello canonico per L sono possibili infiniti modelli filtrati, uno per ciascuna fbf presa in considerazione.
Tipicamente utilizzeremo il modello filtrato per condurre dimostrazioni di completezza di alcune logiche nei confronti di strutture con determinate proprietà e che siano finite.
6.1
Filtrazione
Sia ML il modello canonico per L e sia B un arbitrario non-teorema di L. Ciò che il metodo delle
filtrazioni ci permette di fare è costruire da MLun modello basato su una struttura relazionale finita in
cui B è falsa.
Sia Γ = Sf(B) l’insieme delle sottoformule di B. Chiaramente Γ è finito ed è chiuso per sottoformu-le, in quanto
C ∈ Γ ∧ C0 ∈ Sf(C) ⇒ C0 ∈ Γ Definiamo ora una relazione di equivalenza ∼Γtra mondi di WL.
Definizione 6.1. (relazione di equivalenza)Siano w, v ∈ WL
w ∼Γ v ⇔ w ∩ Γ = v ∩ Γ.
In altre parole
w ∼Γ v ⇔ ∀B ∈ Γ, (MLwB ⇔ MLv B).
Definizione 6.2. (classe di equivalenza)Sia
|w| = {v ∈ WL: w ∼ Γv}
50 Modelli finiti
|w| comprende tutti quei mondi di WLin cui ogni enunciato di Γ assume lo stesso valore di verità
che riceve in w. Sottolineiamo ancora che per ogni v, z ∈ |w| non c’ è alcuna fbf A ∈ Γ tale che ML
v A ∧ ML2zA.
Il risultato di questo processo è che WL viene ripartito in un certo numero di classi di equivalenza
rispetto a ∼Γdisgiunte.
È importante osservare che se Γ è finito anche il numero delle classi di equivalenza è finito ed ha al massimo 2nelementi, dove n è la cardinalità di Γ.
Ad esempio, supponiamo che Γ contenga tre elementi Γ = {p, q, p ∧ q}, allora n = 3 e le classi di equivalenza sono al massimo otto, ovvero:
|x1| = {w ∈ WL: ML wp e ML2wq e ML2wp ∧ q} |x2| = {w ∈ WL: ML wp e ML2wq e MLwp ∧ q} |x3| = {w ∈ WL: ML wp e MLwq e ML2wp ∧ q} |x4| = {w ∈ WL: ML wp e MLwq e MLwp ∧ q} |x5| = {w ∈ WL: ML 2wp e ML2wq e MLwp ∧ q} |x6| = {w ∈ WL: ML 2wp e ML2wq e ML2wp ∧ q} |x7| = {w ∈ WL: ML 2wp e MLwq e MLwp ∧ q} |x8| = {w ∈ WL: ML 2wp e MLwq e ML2wp ∧ q}
Osservazione 15. Sottolineiamo che di classi di equivalenza possono essercene meno di 2n, come nel
nostro esempio per cui non esiste un w in cui ML
wp e ML2wq e MLwp ∧ q.
Definizione 6.3. (il modello filtrato)Definiamo il modello MΓ= hWΓ,RΓ, IΓi:
• WΓ = { |w| : w ∈ WL}
WΓè dunque finito poiché ogni suo membro è una classe di equivalenza.
• ∀p ∈ Γ, ∀|w| ∈ WΓ
|w| ∈ IΓ(p) ⇔ w ∈ IL ⇔ p ∈ w .
• RΓè adeguata (è una Γ-filtrazione diRL) ovvero soddisfa le seguenti condizioni:
– F1) ∀|s|, |t| ∈ WΓ sRLt ⇒ |s|RΓ|t| – F2) ∀|s|, |t| ∈ WΓ |s|RΓ|t| ⇒ (∀B ∈ Γ, ML s2B ⇒ MLtB).
Osservazione 16. F1 corrisponde alle frecce che obbligatoriamente si devono mettere in MΓ. F2,
inve-ce, rappresenta il limite massimo di frecce inseribili nel modello filtrato. Difatti in MΓnon possiamo
aggiungere frecce da un mondo |s| a un mondo |t| se nel modello originario MLesiste una fbf B, t.c.
ML
s2B e ML2tB.
Introduciamo di seguito due filtrazionie, che chiamiamo rispettivamente minima e massima. La minima filtrazione è così definita:
sRLt ⇔ |s|RΓ|v|
Dimostrazione. |s|RΓ|t| (per ip.) ML s2B sRLte ML s2B ML tB |s|RΓ|t| ⇒ (ML s2B ⇒ MLtB)
Che verifica proprio la condizione F2.
Introduciamo invece sotto quella che chiamiamo la massima filtrazione: |s|RΓ|t| ⇔ (∀2B ∈ Γ, ML
s2B ⇒ MLtB)
Notiamo come F2 coincida con ⇒. Mostriamo quindi che F1 è implicata da ⇐. Dimostrazione. sRLt (ipotesi) ML s2B ML tB ∀B.ML s⇒MLtB |s|RΓ|t|
Teorema 6.4. (lemma della filtrazione) Sia MΓ= hWΓ,RΓ, IΓi una Γ-filtrazione di WL= hWL,RL, ILi.
Per ciascuna formula B ∈ Γ e per ogni mondo w del modello canonico, allora MΓ
|w|B ⇔ WLwB.
⇔ B ∈ w. Dimostrazione.
Procediamo per induzione sulla lunghezza di B: (i) B = p MΓ |w|p ⇔ MLwp per definizione IΓ : (ii) B =2C Dimostriamo che MΓ 2|w|2C ⇔ ML2w2C. (ii.i) ⇒ Supponiamo ∃|w| ∈ WΓ, MΓ 2|w|2C. ∃|v| ∈ WΓ, |w|RΓ|v| & MΓ 2|v|C
per ipotesi di induzione ML
2vC pertanto ML 2w2C grazie a F2 *1 (ii.ii) ⇐ Supponiamo ML 2w2C ∃v ∈ WL, wRLv & ML 2vC
per ipotesi di induzione MΓ
2|v|C
quindi MΓ
2|w|2C grazie a F1
*2.
1RΓè una filtrazione, |w|RΓ|v| e 2
