Compattezza e risultati limitativi

1. Teorema di Compattezza e risultati limitativi
Il Teorema di Compattezza afferma che l’insoddisfacibilità di un insieme di enunciati dipende
sempre da un sottoinsieme finito di questi. Non è infatti possibile ottenere un insieme insoddisfacibile in cui tutti i sottoinsiemi finiti sono soddisfacibili. Questa proprietà vale per la Logica
Proposizionale e per la Logica Predicativa ed è dimostrabile semanticamente (utilizzando ad esempio
una costruzione nota come ultraprodotto) oppure facendo uso dei calcoli per le logiche in questione.
Teorema 1.1. (Teorema di Compattezza per la Logica Proposizionale e Predicativa ) Sia Γ un
insieme di enunciati (di formule proposizionali) di un linguaggio al prim’ordine (proposizionale).
Si ha:
Γ è insoddisfacibile ⇔ esiste un sottoinsieme finito Γ0 di Γ che è insoddisfacibile.
Dimostrazione. L’implicazione da destra a sinistra è banale, perché nessun insieme soddisfacibile
può contenerne un altro soddisfacibile.
Per l’implicazione opposta, utilizzeremo il calcolo della deduzione naturale che è corretto e
completo per la conseguenza logica: dato un insieme di enunciati Γ, F si ha
Γ |= F ⇔ esiste una deduzione naturale di F con ipotesi attive in Γ.
Ricordando che una deduzione naturale Γ . F di F con ipotesi attive in Γ è rappresentata da un
albero finito , in cui la radice è etichettata con F e le foglie sono etichettate da ipotesi scaricate o
da enunciati in Γ, si deduce che Γ . F implica Γ0 . F , dove Γ0 è l’insieme degli enunciati di Γ che
etichettano le foglie della deduzione naturale. Abbiamo quindi
Γ |= F ⇔ Γ . F ⇔ ∃Γ0 ⊆ Γ, Γ0 finito, Γ0 . F ⇔ ∃Γ0 ⊆ Γ, Γ0 finito, Γ0 |= F.
Rcordando infine che, sia in logica proposizionale che in logica predicativa, un insieme di enunciati
(o formule) Γ è insoddisfacibile se e solo se Γ |= ⊥, si ottiene la tesi.
Il Teorema di compattezza viene usato, fra l’altro, per dimostrare risultati limitativi sulla espressività del linguaggio al prim’ordine.
Definitione 1.1. Sia dato un linguaggio L, una classe C di strutture per L e una proprietà P
(vista come un sottoinsieme di C);
- la classe P si dice esprimibile al prim’ordine o elementare, se esiste un insieme di enunciati Γ
tale che, per ogni I ∈ C valga:
I |= Γ ⇔ I ∈ P;
- la classe P si dice elementare di base se esiste un enunciato φ tale che, per ogni I ∈ C, valga:
I |= φ ⇔ I ∈ P.
Vediamo un esempio di questo tipo di applicazione. Sia L un linguaggio al prim’ordine, contenente un simbolo predicativo binario r. Una struttura I di L si dice fondata se rI non ha catene
infinite, cioè se non esiste alcuna successione (di )i∈N di elementi del dominio tale che per ogni i
valga (di , di+1 ) ∈ rI .
Proposizione 1.2. Sia L un linguaggio al prim’ordine, contenente un simbolo predicativo binario
r. La proprietà di “fondatezza” non è esprimibile al prim’ordine, cioè, non esiste alcun insieme di
enunciati Γ tale che, per ogni struttura I di L valga:
I |= Γ ⇔ I è fondata.
1
2
Dimostrazione. Nota bene: a lezione abbiamo dimostrato questo risultato nel caso in cui Γ fosse
composto da un unico enunciato φ. Qui riportiamo la dimostrazione anche nel caso di un qualsiasi
insieme Γ, anche infinito, di enunciati. Supponiamo per assurdo che un tale insieme Γ esista.
Consideriamo un insieme numerabile C = {c0 , c1 , . . .} di nuove costanti (nel senso che non appaiono
già come costanti di L), ed il linguaggio L0 = L ∪ C. Sia Γ0 l’insieme degli enunciati di L0 definito
da:
Γ0 = Γ ∪ {r(ci , ci+1 ) : i ∈ N}.
È facile verificare che Γ0 è un insieme insoddisfacibile. Infatti, se per assurdo J fosse un modello
di Γ0 , consideriamo il modello I di L ottenuto dimenticando l’interpretazione dei simboli non in
L (come sopra) otteniamo una contraddizione: da una parte I |= Γ (perché J |= Γ!), quindi rI
è fondata, dall’altra gli elementi d0 = cJ0 , . . . , dn = cJn , . . . sono anche elementi del dominio di I e
formano una catena infinita in J, quindi anche in I (perché rI = rJ ). Questo è un assurdo, quindi
ne segue che Γ0 è insoddisfacibile.
Mostriamo che Γ0 è soddisfacibile: essendo questo palesemente in contraddizione con quanto
appena dimostrato, dovremo concludere che l’insieme Γ non esiste.
Per il Teorema di compattezza, è sufficiente dimostrare che ogni sottoinsieme finito ∆ di Γ0 è
soddisfacibile. Se ∆ è finito, esisterà un numero n ∈ N tale che
∆ ⊆ Γ ∪ {r(c0 , c1 ), r(c1 , c2 ), . . . , r(cn−1 , cn )}.
Sia J la struttura per L0 tale che DJ = {0, 1, . . . , n + 1}, cJi = i per 0 ≤ i ≤ n + 1, rJ =
{(0, 1), (1, 2), . . . , (n, n+1)}, e che interpreta gli altri simboli di L in maniera arbitraria (ad esempio:
ck = 0 per k > n + 1, e se L contiene un simbolo funzionale unario f , f J (d) = 0 per ogni d ∈ DJ ).
Dimostriamo che
J |= Γ ∪ {r(cn+1 , cn ), r(cn , cn−1 ), . . . , r(c1 , c0 )}.
Dalla definizione, J |= {r(c0 , c1 ), r(c1 , c2 ), . . . , r(cn−1 , cn )}. Per dimostrare che J |= Γ, sia I la
struttura di L che si ottiene da J dimenticando l’interpretazione dei simboli non in L, cioè: DI =
{0, 1, . . . , n + 1} e I e J coincidono sull’interpretazione dei simboli di L. Si ha I |= Γ perché rI è
fondata, quindi J |= Γ.
Poiché ∆ ⊆ Γ ∪ {r(c0 , c1 ), r(c1 , c2 ), . . . , r(cn−1 , cn )}, ne segue che ∆ è soddisfacibile.
Avendo dimostrato che ogni sottoinsieme finito di Γ0 è soddisfacibile, abbiamo che lo stesso Γ0 è
soddisfacibile per compattezza.
Ricapitolando: avendo dimostrato che Γ0 è sia soddisfacibile che insoddisfacibile, siamo giunti
ad una contraddizione. La contraddizione deriva dall’aver supposto l’esistenza di un insieme Γ di
enunciati al prim’ordine con la proprietà:
I |= Γ ⇔ I è fondata;
ne segue che un tale insieme non può esistere.
Il Teorema di Compattezza cessa di valere se ci restringiamo alla classe dei modell finiti, come
mostra il prossimo esempio. Questo spiega perché metodi come quello dei giochi di Ehrenfeucht,
che valgono su qualsiasi classe di modelli, siano molto apprezzati nelle applicazioni.
Esempio 1.1. L’insieme Γ = {ci 6= cj ) : i 6= j, i, j ∈ N}. è insoddisfacibile su modelli con dominio
finito, ma ogni suo sottoinsieme finito è soddisfacibile.
3
1.1. Esercizi.
(1) Una relazione binaria ρ ⊆ A × A si dice ciclica se esistono n elementi del dominio a1 , . . . , an
tali che
(a1 , a2 ) ∈ ρ, (a2 , a3 ) ∈ ρ, . . . , (an−1 , an ) ∈ ρ, (an , a1 ) ∈ ρ
(in questo caso, la sequenza a1 , . . . , an si dice un ciclo della relazione ρ).
Sia L un linguaggio predicativo contenente un simbolo predicativo binario r .
i) Per ogni n ≥ 1, scrivere una formula predicativa Fn tale che per ogni struttura I di L
valga:
I |= Fn ⇔ rI ha un ciclo di lunghezza n
ii) Dimostrare che non esiste alcun insieme di enunciati Γ di L tale che per ogni struttura
I di L valga:
I |= Γ ⇔ rI è ciclica.
(2) Si ricorda che la chiusura transitiva ρ∗ di una relazione binaria ρ su un insieme A è definita
da
[
ρn ,
ρ∗ =
n≥1
dove
ρ1 = ρ,
ρn+1 = ρn ∪ {(d, d0 ) ∈ A × A : ∃d00 (d, d00 ) ∈ ρn , (d00 , d0 ) ∈ ρ}.
Sia L un linguaggio predicativo contenente un simbolo predicativo binario r e due costanti
a, b.
i) Per ogni n ≥ 1, scrivere una formula predicativa Fn tale che per ogni struttura I di L
valga:
I |= Fn ⇔ (aI , bI ) ∈ (rI )n .
ii) Dimostrare che non esiste alcuna insieme di enunciati Γ di L tale che per ogni struttura
I di L valga:
I |= Γ ⇔ (aI , bI ) è nella chiusura transitiva (rI )∗ di rI .
Suggerimento: procedere per assurdo e considerare l’insieme Γ ∪ {¬Fn : n ≥ 1}.
(3) Sia L un linguaggio al prim’ordine, P una classe di interpretazioni per L e
P = {I : I struttura di L e I 6∈ P}
la classe complementare. Dimostrare che vale il seguente risultato:
P e P sono esprimibili al prim’ordine ⇔ P é elementare di base
(suggerimento per la freccia non banale: considerare l’insieme Γ ∪ Γ0 dove Γ descrive K e Γ0
descrive K , e utilizzare il teorema di compattezza sull’insieme Γ ∪ Γ0 ).