1.3 Il teorema di Beth (1953), Craig (1957)
2.1.1 Forme standard
Prima di proseguire con l’approfondimento di alcune proprietà metateoriche fondamentali della logica elementare, ci soffermiamo brevemente ad analizzare quel piano di rilettura formale o standardizzazione del contenuto linguistico di una formula (come del resto anche di un insieme di formule) che costituisce il terreno di incontro delle forme ridotte e delle occorrenze dei connettivi cosiddette “normali”.
In generale, diciamo che si trovano in forma ridotta quelle formule complesse le cui sottoformule sono articolate attraverso un insieme adeguato di connettivi, che sia cioè adatto ad esprimere ogni valore di verità possibile; sono insiemi di questo tipo {¬, →} e {¬, ∧, ∨}. Ne consegue che ogni formula ϕ, costruita a partire da un linguaggio del prim’ordine con data segnatura, è logicamente equivalente ad una formula in forma ri- dotta ϕ°, così che ϕ e ϕ° presentino le stesse caratteristiche di soddisfacibilità: vengono introdotte a questo proposito le occorrenze “normali” dei connettivi, ovvero un criterio di posizionamento dell’intera griglia vero-funzionale che preveda, nel caso di una formula complessa, la sola presenza dei connettivi ¬, ∧, ∨ tale che la negazione compaia unica- mente davanti a una formula atomica. Una formula è allora detta in forma normale disgiuntiva se i suoi connettivi sono ristretti all’insieme {¬, ∧, ∨}, se la negazione si pre- senta esclusivamente davanti alle formule atomiche e se, in generale, assume la forma
4La relazione ∼=
f può essere considerata un’approssimazione finita dell’isomorfismo. 5La relazione ∼=
(ϕ1∨ . . . ∨ ϕk), dove ogni disgiunto ϕi è a sua volta fomato da un insieme di congiunti (ψ1∧ . . . ∧ ψn), e ogni ψi è una formula atomica oppure una negazione di una formula atomica. È opportuno a questo punto notare che anche per il caso particolare k = 1 e n = 1 la definizione risulta corretta e applicabile; si conclude allora che è sufficiente la presenza di un’unica formula ψ1per trovarsi al cospetto di una formula disposta in forma normale disgiuntiva.
È prevista anche un’occorrenza “normale” per le formule che includono al loro interno dei quantificatori, è il caso delle formule in forma normale prenessa, le cui caratteristiche vengono fissate attraverso la seguente definizione:
2.1.1.1 Definizione
Una formula ϕ è detta in forma normale prenessa se: 1. In ϕ non sono presenti quantificatori; oppure
2. ϕ := ∃xiψ (xi), dove ψ è in forma normale prenessa e la variabile xi non occorre legata in ψ; oppure
3. ϕ := ∀xiψ (xi), dove dove ψ è in forma normale prenessa e la variabile xi non occorre legata in ψ.
Segue che se ϕ è una formula in forma normale prenessa nessuna variabile presente in ϕoccorre sia libera che legata e, tra quelle legate, nessuna ricade all’interno del campo di più di un quantificatore. Si può inoltre dimostrare a partire da quanto scritto il teorema della forma normale prenessa (tanto per la logica proposizionale come per la logica dei predicati), che in perfetta continuità con qualsiasi teorema legato alle forme normali stabilisce che ogni formula ϕ appartenente a un linguaggio del prim’ordine è logicamente equivalente ad una formula disposta in forma normale prenessa.
Le ragioni e i vantaggi di una standardizzazione delle occorrenze dei connettivi sono da ricercare principalmente in una migliore maneggevolezza delle formule più complesse, che automaticamente concentrano a livello sintattico proprietà fondamentali e assumono una forma che propone uno stampo di facile riconoscimento e conseguente utilizzabilità. Nel caso della logica proposizionale, per esempio, una qualsiasi formula ϕ in forma normale disgiuntiva offre un’immagine istantanea e dettagliata delle istanze di interpretazioni vere di ϕ; mentre, nel caso di una formula in forma normale prenessa, le ragioni del suo utilizzo variano dalla deduzione automatica (automated theorem proving, per l’informatica) alla facilitazione sintattica nella transizione verso la forma skolemizzata, a sua volta strumento indispensabile per una dimostrazione alternativa dei teoremi di Löwenheim-Skolem. In questa prospettiva di precisazione sintattica introduciamo un parametro nuovo, il quantifier rank, il cui obiettivo è di determinare il grado di complessità di una formula tenendo in considerazione come unica variabile il quantificatore esistenziale. In effetti, essendo proprio quest’ultimo l’ente logico direttamente coinvolto nelle possibilità per un isomorfismo di risultare estendibile, il quantifier rank di una formula diviene qualificabile
come il punto di equilibrio e indice esplicativo attorno al quale misurare le capacità di una funzione isomorfa di individuare, per due modelli qualsiasi, somiglianze strutturali. 2.1.1.2 Definizione
Il quantifier rank di una qualsiasi formula ϕ corrisponde al numero massimo di quantifi- catori annidati che ϕ contiene al suo interno. Viene abbreviato attraverso la scrittura notazionale qr (ϕ) ed è definito ricorsivamente dalle seguenti condizioni:
se ϕ è una formula atomica , allora qr (ϕ) = 0; se ϕ = ¬ψ, allora qr (ϕ) = qr (¬ψ);
se ϕ = (ψ1∨ ψ2), allora qr (ϕ) = max {qr (ψ1) , qr (ψ2)}; se ϕ = (∃xψ (x)), allora qr (ϕ) = qr (ψ) + 1.
È importante sottolineare come nel caso di una formula ϕ disposta in forma normale prenessa il quantifier rank corrisponda esattamente al numero di quantificatori presenti in ϕ. Possono infatti darsi formulazioni equivalenti di ϕ con un valore di rango differente. Un esempio in questo senso è il seguente:
Sia ϕ l’enunciato ∃x (∃yR (x, y) ∧ ∃zQ (x, z)), allora qr (ϕ) = 2. Se riformuliamo ϕ se- condo i criteri dettati dalla disposizione in forma normale prenessa e supponiamo che il nostro linguaggio abbia solo i due simboli relazionali utilizzati, otteniamo l’enunciato ϕ∗ =∃x∃y∃z (R (x, y) ∧ Q (x, z)), il cui rango ha valore 3, e non è possibile trovare al- cuna formulazione equivalente a ϕ che, una volta espressa in forma normale prenessa, abbia un quantifier rank pari a 2.
Diversamente, la misura della complessità di una formula in forma normale prenessa è data un indice numerico, un rango, che restituisce il numero di volte in cui i quantifi- catori presenti nella formula sono alternati; una formula di matematica elementare come ∀x∀y!2xy≤ x2+ y2" ha dunque rango pari a 0.
2.1.1.3 Definizione
Sia L un linguaggio del prim’ordine con segnatura S. Si consideri l’insieme T ⊂ FS r, per r ∈ N, e da esso si derivi un insieme < T > in modo tale che sia il più piccolo sottoinsieme di FS
r contenente T e chiuso sotto le operazioni di negazione e disgiunzione: questo significa che per ogni formula ϕ ∈ T si ha ϕ, ¬ϕ ∈< T >, mentre per due formule qualsiasi ϕ, ψ ∈ T si ha (ϕ ∨ ψ) ∈< T >.
2.1.1.4 Osservazione
Consideriamo ϕ una formula qualsiasi appartenente all’insieme T ⊂ FS
r appena definito. Date due L-strutture A e B con a1, . . . , ar∈ A e b1, . . . , br∈ B, se
A|= ϕ (a1, . . . , ar)sse B |= ϕ (b1, . . . , br), allora
dove ϕ%è una formula qualsiasi appartenente a < T >. Questo significa che la proprietà di equivalenza elementare tra due strutture che interpretano uno stesso insieme di formule viene mantenuta con l’estensione a un insieme che preveda l’introduzione dell’insieme di connettivi {¬, ∨}. Lo si può verificare, nel caso della negazione, pensando che se le due strutture sono in accordo nel verificare una data formula ϕ, concorderanno anche sulla realizzazione di ϕ% := ¬ϕ (quindi A |= ϕ (a
1, . . . , ar) e B |= ϕ (b1, . . . , br) sse A # ¬ϕ (a1, . . . , ar) e B # ¬ϕ (b1, . . . , br), e viceversa); nel caso della disgiunzione il ragionamento segue in modo simile.
Con quanto appena visto, risalta immediatamente un’altra proprietà: considerato l’insieme T1 ={ϕ1, . . . , ϕn} ⊂ FrS, sia T2 l’insieme formato dalle formule logicamente equivalenti a qualche ϕ ∈ T1, in modo che ϕi ≡ ϕ%i per ϕ%i ∈ T2; allora, se con < T1 > e con < T2>indichiamo i due insiemi derivati da T1 e da T2 secondo le modalità spiegate nella definizione 2.1.1.3, a ogni formula ϕi∈< T1 >è associabile una formula ϕ%i ∈< T2 >che sia ad essa logicamente equivalente.
Nel lemma che segue faremo utilizzo unicamente del quantificatore esistenziale, ponendo la condizione che, in generale, ∃xR (x) = ¬∀x¬R (x).
2.1.1.5 Lemma “Sia ϕ ∈ FS
r e qr (ϕ) ≤ n + 1, allora ϕ ∈< T >:
< T >=#ψ∈ FrS|qr (ψ) ≤ n$∪#∃xψ (x) ∈ FrS|qr (ψ) ≤ n$.” Dimostrazione. Procediamo sulla complessità di ϕ:
se ϕ è atomica allora qr (ϕ) = 0 e ϕ ∈#ψ∈ FS
r|qr (ψ) ≤ n $
⊂< T >; se ϕ = ¬ψ il caso è identico al precedente;
se ϕ = (ψ1∨ ψ2) allora qr (ϕ) = max {qr (ψ1) , qr (ψ2)}, dove ψ1, ψ2 ∈#ψ∈ FrS|qr (ψ) ≤ n $ ⊂< T >; se ϕ = ∃xψ (x) allora ∃xψ (x) ∈#∃xψ (x) ∈ FS r |qr (ψ) ≤ n $
; nel caso ψ fosse atomica, avremmo qr (ϕ) = 1.
q.e.d. Il seguente lemma riguarda formule soddisfacibili in cui non compaiono quantificatori; queste formule sono dette quantifier-free e rappresentano un caso banale di formule in forma normale prenessa. Per esse vale un teorema di portata generale noto come teorema della forma normale disgiuntiva la cui formulazione risulta equivalente al risultato che andiamo ad esporre:
2.1.1.6 Lemma
“Sia T = {ϕ1, . . . , ϕn} un insieme di n-formule. Allora ogni formula ϕi ∈< T >, se è soddisfacibile, è equivalente a una formula espressa in forma normale disgiuntiva, ovvero della forma:
((ψ1,1∧ . . . ∧ ψ1,n)∨ . . . ∨ (ψk,1∧ . . . ∧ ψk,n)), dove k < 2n e ψ
i,j = ϕoppure ψi,j =¬ϕ, per il fatto che {ϕ1, . . . , ϕn,¬ϕ1, . . . ,¬ϕn} ⊂< T >.”
Dimostrazione. Consideriamo prima di tutto l’insieme T = {ϕ1, . . . , ϕn} ⊂ FrS, per r∈ N numero finito. Per una L-struttura A e una r-pla ar:= (a1, . . . , ar)∈ Ar tale che l’espressione
ψ∧(A,ar):= ψ1∧ . . . ∧ ψn rappresenti l’insieme dei congiunti,6 dove: ψ
i = ϕi se A |= ϕi(a1, . . . , ar), e ψi =¬ϕi se A |= ¬ϕi(a1, . . . , ar). Allora ogni ψi è una realizzazione in A, e pertanto possiamo scrivere:
A|= ψ∧(a1, . . . , ar). Presa adesso una L-struttura B e una r-pla br := (b
1, . . . , br) ∈ Br, scriviamo in ragione delle considerazioni affrontate nella osservazione 2.0.1.7 che
B|= ψ∧(b1, . . . , br) ⇔ A |= ϕ (a1, . . . , ar) sse B |= ϕ (b1, . . . , br)
per ogni ϕ ∈< T >, dal momento che l’equivalenza elementare tra le due strutture è mantenuta con il passaggio dall’insieme T a < T >. Da notare a questo punto che se A |= ψ∧(a
1, . . . , ar) (oppure, indifferentemente, B |= ψ∧(b1, . . . , br)) individua una singola realizzazione, scrivendo:
&
ψ(A,a∧ r)|A |= ψ∧(a1, . . . , ar) , ar∈ Ar '
vengono individuate tutte le possibili realizzazioni, per differenti r-ple, il cui numero finito per semplici ragioni combinatorie assomma a 2n.
Ciò che a questo punto rimane da dimostrare è l’equivalenza tra una qualsiasi formula ϕi ∈< T > e una formula disposta in forma normale disgiuntiva. Sia dunque con χ∨ indicata la disgiunzione di congiunti in modo che, per una stessa L-struttura A, si definisca come segue:
6ψ 1:= ϕ1 oppure ψ1:=¬ϕ1; ψ2:= ϕ2 oppure ψ2:=¬ϕ2; .. . ψn:= ϕn oppure ψn:=¬ϕn.
χ∨ :=( &ψ∧(A,ar)|A |= ϕ (a1, . . . , ar) , ar∈ Ar '
.
" Assumiamo prima la formula soddisfacibile ϕ ∈< T > e prendiamo A come suo modello. Abbiamo visto che vale A |= ϕ (a1, . . . , ar) sse A |= ψ∧(a1, . . . , ar), e per come è stato definito χ∨ troviamo la formula ψ∧
(A,ar) appartenente all’insieme
( &
ψ∧(A,ar)|A |= ϕ (a1, . . . , ar) , ar∈ Ar '
; dunque possiamo affermare che A|= χ∨(a1, . . . , ar)
dal momento che almeno un disgiunto è realizzato dalla struttura A. " Assunta per una L-struttura B e br ∈ Brla realizzazione B |= χ∨(b
1, . . . , br), dalla definizione di χ∨ segue che esiste una L-struttura A tale che A |= ϕ (a
1, . . . , ar)con ar ∈ Ar. Essendo la formula ψ∧ (B,br) un membro di ( & ψ∧(B,ar)|B |= ϕ (b1, . . . , br) , br∈ Br ' , sappiamo che vale B |= ψ∧(b
1, . . . , br); ma allora, da quanto visto in precedenza, ovvero che B |= ψ∧(b
1, . . . , br) ⇔ A |= ϕ (a1, . . . , ar)sse B |= ϕ (b1, . . . , br), possi- amo concludere sia A |= ϕ (a1, . . . , ar) che B |= ϕ (b1, . . . , br).
q.e.d. Ecco che infine possiamo dimostrare un lemma che riunisce i passaggi argomentativi legati alle forme equivalenti, e li collega alla nozione di quantifier rank:
2.1.1.7 Lemma
“Sia n ∈ N. Allora per ogni r ∈ N ci sono, a meno di equivalenza logica, formule in numero finito ϕ ∈ FS
r tali che qr (ϕ) ≤ n.”
Dimostrazione. La dimostrazione sarà compiuta per induzione su n.
Sia posto inizialmente n = 0. Questo rappresenta il caso base ed è di semplice risoluzione. Le formule atomiche in FS
r sono costruite con una segnatura relazionale (finita) e con un insieme di varibili anch’esso finito: quindi esse sono in numero finito anche a meno di equivalenza logica, come verificato nel lemma 2.1.1.6.
Passo induttivo. Per ipotesi induttiva esistono due insiemi di formule: 1. ψ1, . . . , ψk∈ FrS e qr (ψi)≤ n;
2. χ1, . . . , χh∈ Fr+1S e qr (χi)≤ n; tali che, rispettivamente:
" Per ogni ϕj ∈ FrS esiste una formula ψi ∈ FrS 1≤ i ≤ k, tale che ϕj ↔ ψi; " Per ogni φj ∈ Fr+1S esiste una formula χi ∈ Fr+1S 1≤ i ≤ h, tale che φj ↔ χi. Siano adesso dati due insiemi di formule:
T1 =#ψ∈ FrS|qr (ψ) ≤ n $ ∪#∃xψ (x) ∈ FS r |qr (ψ) ≤ n $ , e T2 ={ψ1, . . . , ψk} ∪ {∃xr+1χ1, . . . ,∃xr+1χh};
allora ogni formula ϕi ∈ T1 sarà logicamente equivalente ad una formula ϕ%i∈ T2. Per dimostrare quanto appena affermato si consideri prima l’evidente equivalenza tra le formule dei due insiemi #ψ∈ FS
r |qr (ψ) ≤ n $
⊂ T1 e {ψ1, . . . , ψk} ⊂ T2, per cui ogni ϕ = ψ tale che ψ ∈ FrS sarà logicamente equivalente a una qualche ψi ∈ {ψ1, . . . , ψk}. Consideriamo adesso il caso in cui ϕ = ∃xψ (x). La formula in questione allora apparterrà all’insieme #∃xψ (x) ∈ FS
r |qr (ψ) ≤ n $
e sarà logicamente equivalente a una formula del tipo ∃xr+1ψ (xr+1/x), tale che ∃xr+1ψ (xr+1/x) ∈ Fr+1S e, con l’esclusione valutativa del quantificatore esistenziale, qr (ψ (xr+1)) ≤ n. Ma così facendo la formula ψ (xr+1) sarà logicamente equivalente ad una qualsiasi χi ∈ {∃xr+1χ1, . . . ,∃xr+1χh}; pertanto possiamo concludere:
|= ∃xψ (x) ↔ ∃xr+1χi(xr+1).
A questo punto, per quanto abbiamo appurato con la dimostrazione del breve lemma 2.1.1.5, nell’insieme < T1>generato a partire da T1 si trovano tutte le formule ϕ% ∈ FrS tali che qr (ϕ%) ≤ n + 1, e quindi - per il passo induttivo e la considerazioni affrontate nella osservazione 2.1.1.4 - ognuna di esse sarà logicamente equivalente ad una formula ϕ%%∈< T2>. L’insieme < T2 >, come abbiamo visto nel lemma 2.1.1.6, contiene membri in numero finito a meno di equivalenza logica.
q.e.d.