Un compendio d’insieme sui sistemi formali

4.1.2.1 Definizione

Sia S una segnatura composita e P un simbolo di relazione unario. La P -relativizzazione di una formula ψ ∈ LS _{è definita induttivamente come segue:}

ψP := ψ, nel caso ψ sia atomica; (_¬ψ)P :=_¬ψP_; (ψi∨ ψj)P := 5 ψ_iP ∨ ψP j 6 ; (_∃xψ)P :=_∃x!P x_{∧ ψ}P"_.

Vediamo adesso di riassumere le due ultime definizioni precisando cosa si intende quando vogliamo che un enunciato esprima il medesimo contenuto in una struttura e in una sottostruttura, passando per una P -relativizzazione.

Sia A una S ∪ {P }-struttura tale che PA_{⊂ A sia un insieme S-chiuso in A. Preso un} qualsiasi S-enunciato ψ si dà:

7

PA8A_{|= ψ sse A |= ψ}P_. 4.1.2.2 Definizione

Un sistema di logica astratta (da ora in avanti semplicemente sistema logico) L è una coppia ordinata (L, |=L) in cui L è una funzione che viene associata ad una qualsiasi segnatura S e produce l’insieme di tutti i possibili L-enunciati, che sono indicati come L (S). L’indice della funzione L risponde direttamente al sistema logico, pertanto per un sistema logico Li si scriverà Li(S) se vogliamo indicare l’insieme di tutti i possibili

6

Li-enunciati. Stessa cosa avviene per la relazione |=L che rappresenta la relazione di soddisfacibilità della logica che collega a un qualsiasi enunciato ϕ ∈ L (S) il modello A che lo verifica.

Un generico sistema logico L è definito attraverso le seguenti proprietà: 1. Se S0⊂ S1 allora L (S0)⊂ L (S1).

2. Se A |=L ϕallora A è una S-struttura e ϕ ∈ L (S), per S segnatura qualsiasi. 3. Se A ∼= B, allora A |=Lϕsse B |=Lϕ. (Isomorfismo)

4. Se S0⊂ S1, ϕ ∈ L (S0), e A è una S1-struttura, allora: A_|=Lϕsse A! S0 |=L ϕ. (Riduzione)

Alcune proprietà desiderabili per un sistema logico sono:

1. (Boole (L)) Un sistema logico L è detto chiuso sotto connettivi booleani sse: - per una segnatura S e un enunciato ϕ ∈ L (S), vale per A S-struttura qualsiasi: A_|=L¬ϕ sse non vale A |=Lϕ;

- per una segnatura S e due enunciati ϕ ∈ L (S), ψ ∈ L (S), vale per A S-struttura qualsiasi: A |=L(ϕ∨ ψ) sse A |=Lϕoppure A |=Lψ.

2. (Elim (L)) Data una segnatura composita S e una segnaura interamente

relazionale Sr_{, per un enunciato ϕ ∈ L (S) esiste un enunciato ψ∈L (S}r_{) tale che,} per A S-struttura qualsiasi:

A|=Lϕsse Ar |=Lψ.

3. (Rel (L)) Per una segnatura S, un enunciato ϕ ∈ L (S) e un simbolo unario U esiste un enunciato ψ ∈ L (S ∪ {U}) tale che:

!

A, UA"|=Lψ sse 7

UA8A|=Lϕ,

per tutte le S-strutture A e tutti i sottoinsiemi UA_{di A che siano S-chiusi.} 4. (L¨oSko (L)) Per un enunciato qualsiasi ϕ ∈ L (S), se ϕ ha un modello, allora ha

un modello al massimo numerabile.

5. (Comp (L)) Per un sistema logico L, sia T un insieme di enunciati tale che ogni sottoinsieme T0⊂ T , con T0 finito, sia soddisfacibile; allora T è soddisfacibile. Un sistema logico L che soddisfi le proprietà Boole (L), Elim (L) e Rel (L) è detto regolare.

4.1.2.3 Definizione Siano L e L"

due sistemi logici. Diciamo che L è potente almeno quanto L, e scriviamo

L_{≤ L}", sse per un qualsiasi S e un qualsiasi ϕ ∈ L (S) esiste un enuncitao ψ ∈ L"(S)

tale che

M odS

dove con ModS

L(ϕ)indichiamo la classe dei modelli di ϕ per una segnatura S. Due sistemi logici L"

e L si dicono allora equipotenti sse vale al contempo L"

≤ L e

L_{≤ L}"; in altre parole, la relazione ≤ trasferisce le proprietà dal sistema più debole al

più potente.

Per identificare due sistemi logici equipotenti scriviamo L"

∼ L. La definizione ModS

L(ϕ) :={A|A |=Lϕ} può essere considerata come la controparte, ma- tematicamente precisa, del concetto di definibilità di ϕ, e accenna a un aspetto di notevole importanza, ovvero la base modellistica per una valutazione della potenza espressiva di un sistema logico qualsiasi L per la relazione meta-semantica |=L.

4.1.2.4 Lemma

“Sia L un sistema logico regolare per il quale assumiamo che valga Comp (L). Per una segnatura qualsiasi S, una teoria T e un enunciato ϕ tale che T ∪ {ϕ} ⊂ L (S), valga T _|=Lϕ.

Esiste allora un sottoinsieme finito T0⊂ T tale che T0|=Lϕ.”

Dimostrazione. Per la proprietà Boole (L) prendiamo un enunciato ¬ϕ. Siccome tra le ipotesi abbiamo specificato T |=Lϕ, allora l’insieme T ∪ {¬ϕ} risulta non soddisfacibile. Adesso, utilizzando la proprietà Comp (L), possiamo trovare un sottoinsieme finito T0⊂ T in modo tale che l’insieme non soddisfacibile T ∪ {¬ϕ} diventi T0∪ {¬ϕ}, a sua volta non soddisfacibile; quindi concludiamo T0 |=Lϕ.

q.e.d. Questo significa che se L è compatto, allora la proprietà che lo determina vale sia per la soddisfacibilità che per la conseguenza logica. Come ulteriore proprietà della Compat- tezza, mostriamo che il significato di un L (S)-enunciato dipende unicamente dal numero finito di simboli di S. Da ora in avanti, con la notazione L1, sarà indicato il sistema logico elementare, ovvero la logica del prim’ordine.

4.1.2.5 Lemma

“Sia L un sistema logico regolare per il quale valgano le seguenti proprietà: Comp (L);

L1≤ L;

sia inoltre, per una qualsiasi segnatura relazionale S, ψ ∈ L (S);

allora, per un sottoinsieme finito S0⊂ S e per tutte le S-strutture A e B: A! S0 ∼= B! S0 =⇒ A |=Lψ sse B |=Lψ.”

Dimostrazione. Consideriamo una segnatura S e ad essa aggiungiamo tre nuovi simboli relazionali unari: {U, V, f}.

Attraverso la costruzione di una S ∪ {U, V, f}-teoria T , vogliamo esprimere che f è un isomorfismo che opera come raccordo tra la sottostruttura generata dal simbolo relazionale U e la sottostruttura generata dal simbolo relazionale V . T è una teoria del prim’ordine (L1) costituita dai seguenti enunciati:

1. ∃xUx; 2. ∃xV x;

3. ∀x (Ux → V fx);

4. ∀y (V y → ∃x (Ux ∧ fx = y));

5. ∀x∀y ((Ux ∧ V x ∧ fx = fy) → x = y);

6. ∀x1. . .∀xn((U x1∧ . . . ∧ Uxn)→ (Rx1. . . xn↔ Rfx1. . . f xn)).7

Vale la pena soffermarsi brevemente sul significato di queste espressioni. Inizialmente, con 1. e 2., si indica che l’insieme degli elementi segnati dalla relazione U non è vuoto, e similmente accade per V ; ai punti 3., 4. e 5. ci soffermiamo sul predicato f del quale diciamo che è una funzione biunivoca tra U e V ; per finire al punto 6. viene detto che f è un isomorfismo, avendo trasferito le sue proprietà funzionali ai simboli relazionali di S. In merito a quest’ultimo punto si tratta anche di notare che la dimensione o “cardinalità” di S trascina con sé la “cardinalità” della stessa teoria: è evidente infatti che se S dovesse essere infinitamente grande, anche T lo sarebbe. In più, T è una teoria composta unicamente da enunciati del prim’ordine, mentre il risultato che il teorema ci domanda riguarda esplicitamente un sistema logico L inteso come qualsiasi, a patto che valga L1 ≤ L; tuttavia, come stiamo per vedere, questo non è affatto un problema che attenti alla generalità della nostra dimostrazione. Per poter spiegare al meglio questo punto e per poter continuare con l’argomentazione del teorema, introduciamo la seguente definizione:

4.1.2.6 Definizione

Siano L1 e L due sistemi logici tali che L1 ≤ L; per un enunciato ϕ ∈ L1(S), definiamo un corrispettivo ϕ∗_{∈ L (S) nel seguente modo:}

M odS

L1(ϕ) = M od

S L(ϕ∗).

Nel caso si tratti di un insieme di formule T ⊂ L1(S), definiremo equivalentemente un insieme T∗ _{:= {ϕ}∗_{|ϕ ∈ T } ⊂ L (S), vale a dire che per ogni ϕ ∈ T in L1 esiste un} enunciato ϕ∗ _{∈ T}∗ _{in L e i modelli di ϕ e di ϕ}∗ _{sono gli stessi.}

Per il fatto che L è regolare, possiamo prendere due relativizzazioni di ψ, rispettiva- mente una U-relativizzazione e una V -relativizzazione, in modo da avere i due seguenti enunciati:

ψU ψV

Per entrambi sarà allora necessario provare la seguente asserzione: T∗_|=LψU ↔ ψV.

Se trattiamo l’espressione T∗_|=

LψU ↔ ψV dal punto di vista modellistico notiamo che, per come è stata costruita T , vale:

A_|=L1 T∗, che può essere letta anche come

!

A, UA_{, V}A_{, f}A"_|= L1 T;

ma !A, UA, VA_{, f}A" _|=

L1 T, proprio in forza della definizione 4.1.2.6, ovvero per

M odS_L1(ϕ) = M odS_L(ϕ∗), comporta direttamente: !

A, UA, VA, fA"|=L T∗. Se dunque vale !A, UA_{, V}A_{, f}A" _|=

L1 T allora, essendo T una teoria formulata esatta-

mente con gli enunciati 1.-6., UA _{e V}A _{sono sottoinsiemi non vuoti, e con l’espressione} fA! UAsi descrive l’isomorfismo il cui dominio è UAe che raccorda le due sottostrutture 7

UA8A e7VA8A.

Ma allora, per il fatto che per L vale la proprietà di isomorfismo, possiamo scrivere che 7

UA8A|=Lψ sse 7

VA8A|=Lψ,

dal momento che due strutture isomorfe soddisfano sempre le stesse formule. Appli- cando la proprietà Rel (L) adesso abbiamo:

A|=LψU sse B |=LψV, espressione che per Boole (L) diventa:

A_|=LψU ↔ ψV,

grazie alla capacità di trasformare l’oggetto metateorico “sse” in un oggetto del lin- guaggio come “↔”.

A questo punto possiamo cominciare la seconda parte del lemma, che sarà impegnata nella dimostrazione dell’enunciato:

T₀∗|=LψU ↔ ψV, dove T∗

0 è stato ottenuto dall’applicazione di Comp (L) su T . Questo passaggio, com- piuto inizialmente sulla teoria del prim’ordine, permette che con T0 si giunga a S0, cioè a un numero finito di simboli. Lo scopo di quest’ultima dimostrazione è proprio quello di garantire che per S0 le condizioni del lemma siano rispettate, e il metodo che affron- teremo prevederà per due S-strutture A e B la costruzione di una superstruttura C che

le includa, che sia a sua volta un modello per T0 e che permetta a A e a B di soddisfare i propri enunciati a livello di sottostruttura.

Per A e B si dia un isomorfismo, π : A ! S0 ∼= B ! S0, come in ipotesi, con l’aggiunta che i due domini siano disgiunti, ovvero A ∩ B = ∅.

Si costruisca adesso la struttura C = !C, γC" a cominciare dal dominio, che sia C := A_{∪ B, e dalla segnatura, che in quanto composta da S ∪ {U, V, f} recuperi la ragione di} fondo dei simboli che abbiamo utilizzato finora. Definiamo in seguito:

RC := RA∪ RB_{, per ogni R ∈ S;} UC := A;

VC _{:= B;}

fC per fC ! UC = π.

Allora, se A |=LT∗, da cui per Comp (L) arriviamo a A |=LT0∗, sarà vero anche C |=L T0∗, e più precisamente: ! C, UC, VC, fC"|=LT0∗, da cui, per T∗ 0 |=LψU ↔ ψV, ! C, UC, VC, fC"_|=LψU ↔ ψV. Utilizzando adesso Boole (L) troviamo che

C|=L ψU sse C |=LψV. Prendiamo con C"

il ridotto di C rispetto alla segnatura S, ovvero C"

=!C, γC ! S", e otteniamo: 5 C", UC"6_|= L ψU sse 5 C", VC"6_|= LψV. Si nota a questo punto che9UC":C

"

= Ae che9VC":C

"

= B; pertanto grazie all’utilizzo di Rel (L), da 5 C", UC"6_|= L ψU sse 5 C", VC"6_|= LψV, si conclude: A_|=Lψ sse B |=Lψ. q.e.d.

4.1.2.7 Lemma

“Sia L un sistema logico regolare per il quale valgano le seguenti proprietà: Comp (L);

L1 ≤ L.

Per due S-strutture qualsiasi,

A≡L1 B =⇒ A ≡LB

⇓

L1 ∼ L.”

Dimostrazione. Considerata la premessa L1 ≤ L, quello che abbiamo il compito di dimostrare è L ≤ L1. Per un enunciato ϕ ∈ L1(S), questo significa provare che l’insieme dei modelli di ϕ per L1 e l’insieme dei modelli di ψ per L sono due classi coincidenti; in altre parole:

M odL1(ϕ) = M odL(ψ).

Abbiamo bisogno inizialmente di dimostrare un passaggio intermedio che indichi come per un qualsiasi modello A tale che A |=L ψ vi sia un enunciato ϕA ∈ L1(S)8 tale che valgano:

A|=L1 ϕA e ϕ∗A|=Lψ.

Per come è impostato l’intero complesso di quest’ultima espressione possiamo già prevedere che sarà necessario ricorrere a un doppio utilizzo della proprietà Comp (L) che sfrutti la propria capacità di intervenire tanto al livello strutturale quanto al livello di conseguenza logica; non a caso la strategia adatta per giungere alla dimostrazione di “A |=L1 ϕA e ϕ∗A |= ψ” prevederà la costruzione di un enunciato del prim’ordine ϕ, definito come la congiunzione di un numero di enunciati che abbiamo individuato come ϕA.

Partiamo adesso dalla constatazione che per un modello A ∈ ModL(ψ)esiste una teoria T h (A)di cui l’enunciato ψ è una conseguenza logica: T h (A) |=Lψ; per le caratteristiche della funzione∗ _{diciamo allora che}

T h (A)∗ _|=L ψ,

non mancando di far notare come ancora ci stiamo muovendo all’interno di un sistema logico L e non in L1. A questo punto, per il fatto che vale A ≡L B, introduciamo una struttura B tale che B |=LT h (A)∗, che in L1 assume il seguente significato:

B_|=L1 T h (A). 8_{Sottolineando che ϕ}

Per k ∈ N numero finito, utilizziamo la proprietà Comp (L) per definire rispetto a T h (A)∗ un insieme di enunciati {ϕ1, . . . , ϕk}∗, ovvero {ϕ∗1, . . . , ϕ∗k}; siccome abbiamo già trovato T h (A)∗ _|=

L ψ, ci è permesso di sostituire l’espressione alla sinistra del simbolo di conseguenza logica e scrivere:

{ϕ∗

1, . . . , ϕ∗k} |=Lψ. A questo punto, grazie al fatto che gli enunciati ϕ∗

1, . . . , ϕ∗k in L sono segnati, ovvero presentano un corrispettivo in L1, indichiamo con ϕA := ϕ1 ∧ . . . ∧ ϕk la congiunzione degli enunciati per i quali vale:

A|=L1 ϕ1, . . . , ϕk.

Se a quest’ultimo fatto aggiungiamo, per ϕ∗

A:= ϕ∗1∧ . . . , ∧ϕk, anche ϕ∗_A|=Lψ,

allora l’intera espressione, “per ogni A ∈ ModL(ψ) esiste un enunciato ϕA ∈ L1(S) tale che A |=L1 ϕA e ϕ∗A|=Lψ”, è verificata.

Prendendo spunto da quanto appena raggiunto, e portando l’attenzione sul sistema logico L, troviamo che la generalizzazione

M odL(ψ) =%A∈ModL(ψ)M odL(ϕ

∗ A) esplicita la coestensività delle classi di modelli per ψ e ϕ∗

A, sottindendendo la tra- ducibilità di ψ in ϕ∗

Aper una data struttura A.

Adesso, ipotizziamo che ci siano n-strutture, per n ∈ N numero qualsiasi, tali che M odL(ψ) = M odL

!

ϕ∗_A1"_{∪ . . . ∪ Mod}L !

ϕ∗_An"; se questa espressione non fosse vera, ovvero ModL(ψ)$= ModL

!

ϕ∗_A1"_{∪. . .∪Mod}L !

ϕ∗_An", allora ogni sottoinsieme finito dell’insieme

Γ :={ψ} ∪ {¬ϕ∗

A|A ∈ ModA(ψ)}

sarebbe soddisfacibile; ma il sistema logico in cui stiamo operando è L, tra le cui assunzioni iniziali si trova Comp (L), e quindi non solo ogni sottoinsieme finito di Γ, ma l’intero Γ è soddisfacibile, in contraddizione con ModL(ψ) =%_A∈ModL(ψ)M odL(ϕ∗_A). Quanto alla conclusione del teorema, è possibile sfruttare la proprietà della funzione∗ _e indicare, in luogo degli enunciati ϕ∗

A1, . . . , ϕ

∗

An in L, una serie di n-enunciati in L1 per i

quali si può dire:

M odL(ψ) = M odL1(ϕA1)∪ . . . ∪ ModL1(ϕAn),

M odL(ψ) = M odL1(ϕA1 ∨ . . . ∨ ϕAn).

Infine, per un enunciato ϕ che sia definito come la disgiunzione dei vari ϕAi, cioè

ϕ := ϕA1 ∨ . . . ∨ ϕAn, otteniamo il risultato voluto:

M odL1(ϕ) = M odL(ψ).

q.e.d.

Nel documento Per una caratterizzazione della logica del prim'ordine: un'esposizione del Teorema di Lindström (pagine 71-79)