Aspetti semantici della logica proposizionale modale

1. Introduzione
3. Dimostrazioni di completezza
Si consideri una logica normale S ⊇ K. Dato un qualunque insieme Γ ⊆ S,
diremo che Γ è S-coerente se e solo se esiste almeno una formulaϕ non S-derivabile
da Γ, cioè tale per cui dati ϕ
1
...ϕ
n
∈ Γ non si ha (ϕ
1
...ϕ
n
)→ϕ∈S.
Un insieme di formule Γ di dice S-coerente massimale se e solo se è S-coerente e
non esiste un insieme S-coerente Δ tale che Δ⊃ Γ. In altre parole, Γ non può essere
esteso mantenendo la coerenza.
Diremo inoltre che una logica S è completa se, per ogni formula ϕ, si ha
 S
ϕ⇒
S
ϕ
Il seguente teorema mostra che ogni insieme S-coerente può essere esteso ad un
insieme S-coerente massimale.
Lemma 1.20 (Lindenbaum) Se L è numerabile e Γ è S-coerente, allora esiste un
Γ
∗
S-coerente e massimale tale che Γ⊆ Γ
∗
.
Dimostrazione. Si è suppostoL numerabile, quindi è possiile disporre le formule
del linguaggio in una successione. Si definisce quindi per recursione una successione
di insiemi {Γ
i
}
i∈ω
ponendo:
Γ
0
= Γ e Γ
i+1
=
¢
¤
¤
ƒ
¤
¤
⁄
Γ
i
∪{ϕ} se Γ
i
∪{ϕ} è coerente,
Γ
i
altrimenti.
Si noti che la successione è una catena. Poniamo quindi Γ
∗
=  {Γ
i
}. Allora
per induzione su ω si vede che ogni Γ
i
è coerente. Occorre dimostrare che anche
Γ
∗
lo è. Si procede per assurdo: supponiamo che esista una formula ϕ tale che
Γ
∗
 ϕ e Γ
∗
 ¬ϕ. Poiche Γ
∗
è dato dall’unione di (eventualmente infiniti) Γ
i
, allora
esistono Δ
0
⊆ Γ e Δ
1
⊆ Γ, entrambi finiti, tali che Δ
0
 ϕ e Δ
1
 ¬ϕ. Ne consegue
che anche Δ = Δ
0
∪ Δ
1
⊆ Γ
∗
, quindi Δ ϕ e Δ ¬ϕ. Essendo Γ
∗
una catena e
Δ
0
, Δ
1
⊆ Γ
∗
, esiste un Γ
i
tale che Δ
0
, Δ
1
⊆ Γ
i
e quindi per monotonia otteniamo
Γ
i
 ϕ e Γ
i
 ¬ϕ, il che rende Γ
i
incoerente, contrariamente all’ipotesi. Resta da
dimostrare la massimalità di Γ
∗
. Supponiamo che esista un Δ coerente e massimale,
tale quindi che Γ
∗
⊂ Δ. Dato ϕ ∈ Δ− Γ
∗
, per qualche i dovremo avere ϕ = ϕ
i
e
Γ
i
∪{ϕ
i
} incoerente, altrimenti sarebbe ϕ
i
∈ Γ
∗
. Ma Γ
i
∪{ϕ
i
}∈ Δ, quindi anche Δ
sarebbe incoerente, contrariamente all’ipotesi.  Il seguente teorema enuncia alcune proprietà degli insiemi coerenti massimali.
Teorema 1.21 Sia Γ un insieme di formule S-coerente massimale. Allora valgono:
a) Γ ϕ⇔ϕ∈ Γ;
b) ϕ∈ Γ⇔¬ϕ∉ Γ;
c) ϕ∧ψ ∈ Γ⇔ϕ∈ Γ e ψ ∈ Γ
Dimostrazione. (a)Se ϕ∈ Γ, allora c’è una derivazione ϕ
1
...ϕ
n
 ϕ. Ma poichè
ϕ
1
...ϕ
n
∈ Γ, anche ϕ ∈ Γ. Viceversa, sia Γ ϕ, e si supponga ϕ ∉ Γ. Allora per
16