Teorema (Hájek, 1977)

“Esiste un enunciato del prim’ordine ϕ che definisce una proprietà P in modo implicito ma non in modo esplicito.”

Dimostrazione. Sia definito l’enunciato ϕ come la congiunzione dei seguenti enunciati: " < induce un ordinamento lineare sull’universo di riferimento;

" ∃x (Px ∧ ∀y (y = x ∨ x < y)); " ∀x∀y (xSy → (Py ↔ ¬Px)).

Allora ogni ordinamento lineare A ha una proprietà P che è unica ed è tale che A |= ϕ (P ). Ma come abbiamo appurato dall’esempio 1. in 3.0.3.2, se è vero che per un {<}- enunciato del prim’ordine ψ (x), P è definito esplicitamente, cioè ϕ |= P x ↔ ψ (x), con l’affermazione ψ (x) troviamo una contraddizione.

q.e.d. 3.0.3.4 Teorema (Hájek, 1977)

“Sia S = {<, c} una segnatura composta da una relazione d’ordine e una costante. Per due proprietà P e Q vi sono due enunciati: ϕ1 da S ∪ {P } e ϕ2 da {S ∪ Q}, tra i quali sussiste un rapporto di conseguenza logica. Allora non esiste un enunciato interpolante χ tale che

ϕ1|= χ e χ |= ϕ2.”

Dimostrazione. Recuperiamo l’enunciato ϕ come congiunzione di tre enunciati, esatta- mente come incontrato nel teorema 3.0.3.3, e rimpiazziamolo con un nuovo enunciato ϕ∗ ottenuto da ϕ sostituendo le occorrenze di P con la proprietà Q.

Siano adesso ϕ1:= (ϕ∧ P c) e ϕ2 := (ϕ∗ → Qc): ancora vale il rapporto di conseguenza logica ϕ1|= ϕ2.

Supponiamo per assurdo che un interpolante χ effettivamente esista, ovvero che ϕ1 |= χ e χ |= ϕ2; χ dovrà essere un S-enunciato, dal momento che in S risiede il linguaggio condiviso da ϕ1 e da ϕ2. Ma allora è vera ϕ |= P c ↔ χ, cioè ϕ definisce esplicitamente P, contro quanto dimostrato nel teorema 3.0.3.3.

Lindström

L’interesse per l’assiomatizzazione di classi di strutture, che tacitamente riconduceva al- l’intento originario di definire un modello “naturale” dell’aritmetica, a sua volta inserito nel progetto di unificazione della matematica allora in corso, era vigorosamente sostenuto alla fine del XIX secolo dalle convinzioni formaliste della scuola hilbertiana, mentre po- teva certamente dirsi osteggiato da una mente come quella di Frege, che pure non faceva mistero di non entrare in sintonia con lo spirito vetero-positivistico (logico) del periodo. Si trattava dello stesso lasso temporale in cui altri studiosi, come Peano e Huntington, si ponevano il problema di risucire a provare l’indipendenza assiomatica per taluni insiemi, argomento la cui radicale influenza risuonava a tal punto da scuotere l’intero edificio euclideo, come già abbiamo avuto modo di osservare menzionando Beltrami, e in ultima analisi lavorare a favore del progetto formalista.

Con lo sviluppo della teoria dei modelli durante la prima metà del Novecento, per quan- to battezzata come tale da Tarski tardivamente nel 1954, molte attenzioni si spostarono verso un modo di fare logica che privilegiasse l’interazione tra i linguaggi e le strutture, mantenendo una spiccata sensibilità nei confronti degli insiemi di enunciati validi, rite- nuti da buona parte dei teorici dei modelli portatori dei tratti distintivi di una relazione fondamentale come quella di conseguenza logica. Dal 1915, anno del primo teorema di Löwenheim per insiemi finiti di enunciati e modelli numerabili, poi esteso con validità generale da Skolem nel 1920 e nel 1922, si susseguirono una serie di risultati metateorici notabili, come la Completezza (Gödel, 1930) e la Compattezza, da tempo presente impli- citamente nelle dimostrazioni ma assolutizzata come procedura autonoma da Mal’tsev1 nel 1941,2 _{che ebbero il pregio non soltanto di definire i termini del discorso di questa} disciplina in ascesa, ma anche di dirottare l’attenzione dalla logica del second’ordine verso una logica più semplice, la logica elementare, grazie una metateoria che per come si presentava risultava essere più ricca, meglio definita e in grado di esibire un numero cospicuo di risultati postivi; involto in questa mutevole stagione del pensiero analitico, lo stesso teorema di Compattezza era riuscito a guadagnare in considerazione e importanza per via del suo imprescindibile ruolo strumentale nel costruire modelli all’interno di classi di strutture. Vista quindi la capacità della teoria dei modelli di puntualizzare le ragioni e i dettagli di interdipendenza tra i modelli e le componenti lessicali di un sistema logico, le domande su quelle che dovessero essere le proprietà degli enunciati veri di una classe di modelli, e viceversa su quelle che fossero le proprietà dei modelli per una data teoria,

1_{Gödel nel 1930 era arrivato a un esito equivalente.}

confluivano in un terreno comune di unità problematica proposta dalla caratterizzazione assiomatica.

4.1 Verso l’estensione della logica elementare

Entrando dunque nell’attualità della trattazione, miriamo a verificare alcune caratteristi- che dei modelli in accordo con le proprietà dei linguaggi che li generano, e a tal proposito mettiamo in evidenza preliminarmente due concetti e notazioni di cui in verità si è già fatto uso nelle pagine precedenti:

" Data una segnatura S e una S-teoria T, con Mod (T) si designa la classe di tutti i suoi modelli;

" Presa una classe di strutture W per una segnatura S, con Th (W) viene indicato l’insieme di tutti gli enunciati ϕ tali che A |= ϕ per ogni A ∈ W; se W = {A} scriviamo T h (A) con cui indichiamo la teoria completa di A.

Chiarite queste nozioni, siamo naturalmente portati a chiederci quali classi di strutture sia possibile caratterizzare utilizzando enunciati del prim’ordine; pertanto facciamo seguire una definizione che tende a puntualizzare quali classi di strutture possono essere definite usando un singolo enunciato (equivalentemente una congiunzione finita di enunciati) e quali invece usando un insieme (anche infinito) di enunciati:

4.1.0.5 Definizione

Se W è una classe di strutture per una determinata segnatura S.

" W è detta elementare oppure finitamente assiomatizzabile se esiste un S-enunciato ϕtale che W = ModS(ϕ);

" W è detta ∆-elementare oppure assiomatizzabile se esiste un insieme di S-enunciati T tale che W = ModS(T ).

Inoltre, per quanto riguarda il rapporto tra queste due definizioni, chiaramente ogni classe elementare è ∆-elementare, ma essendo

M od (T ) = * ϕ∈T

M od (ϕ),

ogni classe ∆-elementare è l’intersezione di classi elementari. Conseguentemente: T h (W) = *

A∈W

4.1.0.6 Osservazione

Si nota che presa una S-struttura A e la sua teoria completa T h (A), e presa una classe W di S-strutture, allora W sarà assiomatizzabile sse W = {A|A |= W}, cioè, definita Φ = T h (A), Φ è una teoria completa sse A ≡ B per ogni A, B ∈ W. Quindi, grazie al teorema di Fraïssé o equivalentemente al metodo di Ehrenfeucht possiamo trovare che due strutture sono parzialmente isomorfe sono anche finitamente isomorfe e quindi ele- mentarmente equivalenti, ovvero le loro teorie sono complete, e da questo, all’occasione, concludere che se le due teorie sono complete e ricorsivamente assiomatizzabili allora esse saranno anche ricorsivamente decidibili.3

4.1.0.7 Teorema

“Se A è una S-struttura di cardinalità infinita, allora {B|B ∼= A} non è una classe ∆- elementare.”

Dimostrazione. Ragioniamo per assurdo: sia T una teoria in S tale che ModS(T ) = {B|B ∼= A}, allora T ha un modello infinito, rappresentato da A. Per il teorema di Löwenheim-Skolem (verso l’alto), la cardinalità (del dominio) di B eccede quella di A; pertanto A e B non sono isomorfi, e arriviamo alla contraddizione voluta.

q.e.d. Il teorema 4.1.0.7 in fondo sostiene che nessuna struttura infinita può essere caratterizzata sotto isomorfismo da una teoria del prim’ordine; diversamente, e questo è un corollario che si appoggia sulla relazione già nota {B|B ∼= A} ⊂ {B|B ≡ A}, per ogni struttura infinita ne esiste una elementarmente equivalente e non isomorfa: una conclusione piuttosto ovvia se si osserva che, al contrario della classe {B|B ∼= A}, la famiglia di tutte le equivalenze elementari di una struttura infinita A, cioè {B|B ≡ A}, è invece assiomatizzabile al prim’ordine.

Ci stiamo così muovendo in direzione delle estensioni per i linguaggi del prim’ordine, avendo notato come il teorema di Löwenheim-Skolem intervenga a creare una sorta in- gestibile dispersione rispetto alle cardinalità infinite delle strutture, e indebolisca così il controllo che una teoria è in grado di operare sui propri modelli. Tuttavia, limitare le deficienze espressive della logica elementare alla incapacità di distinguere tra differenti insiemi infiniti di oggetti condurrebbe solo a una parziale valutazione dello stato di co- se, dal momento che anche la nozione matematica generale di finitezza non è in alcun modo definibile nello stesso linguaggio: un riflesso diretto di questo fatto è leggibile tra le conseguenze della Compattezza, per cui ogni teoria che presenti modelli di cardina- lità arbitrariamente grandi possiede necessariamente anche modelli infiniti. Il risvolto positivo di queste proprietà, che vedremo essere connaturate all’intero impianto logico del prim’ordine, è dato da un arricchimento dei metodi matematici abituali e dalla pos- sibilità di costruire modelli non-standard per determinate teorie: è il caso per esempio dell’aritmetica di Peano, che al prim’ordine può essere caratterizzata sotto equivalenza

3_{Per esempio la teoria degli ordinamenti densi (come T h (R, <)) e la teoria delle teorie con successore}

elementare ma non isomorfismo, così da consentire lo sviluppo dell’analisi non-standard come affrontata da Robinson intorno alla fine degli anni ’50, sulla base del recupero di infiniti e infinitesimi per mezzo del concetto di estensione elementare.

Sia adesso con le notazioni P A1_{e P A}2_{indicata la formalizzazione degli assiomi di Peano,} rispettivamente al prim’ordine e al second’ordine, allora:

4.1.0.8 Teorema

“La classe dei modelli per P A1 _{non è categorica.”}

Dimostrazione. L’idea che percorre la dimostrazione è di sfruttare un’estensione elemen- tare del modello standard per P A1 _{per alterare la composizione strutturale di quest’ul-} timo.

Sia dunque N |= P A1 _{il modello standard dell’aritmetica di Peano costruito per un} linguaggio S = {+, ·, σ, ∅}; prendiamo una nuova costante c tale che per S ∪{c} si dia una nuova teoria del prim’ordine T∗ _{generata dagli enunciati di T h (N) unitamente all’insieme} infinito dei seguenti enunciati:

{¬ (c ≡ ∅) ; ¬ (c ≡ σ (∅)) ; ¬ (c ≡ σ (σ (∅))) ; . . .},4

che, concedendo qualcosa alla legittimità formale dell’espressione, può essere chiarito dalla scrittura T h (N)∪    n−volte . /0 1 1 + 1 + 1 + . . . + 1 < c : n∈ N   .

Si vede subito che ogni sottoinsieme finito Tf ⊂ T∗ ha un modello: intuitivamente perché la nuova costante ha un ruolo strutturale differente sia da ∅ che da ogni successore, e da un punto di vista formale questo si giustifica considerando un’interpretazione n∗ _di c, appartenente al dominio della struttura per T∗, in modo tale che per ¬c ≡ σm_(∅) ∀m ≤ ω si indichi un oggetto non appartenente al sottoinsieme Tf.

Se allora ogni Tf ha un modello, sia N∗ = (N, n∗) l’estensione elementare di N, con n∗ rappresentante della costante c del dominio; e dunque

N∗_{|= T}f.

Adesso, applicando il teorema di Compattezza, anche la teoria T∗ _{avrà un modello.} Prendiamo il modello numerabile generico M e andiamo a vedere come il suo ridotto M0 = M ! S si comporta nei confronti del modello standard N, sapendo che M0 |= T h (N).

Bisogna a questo punto ricordare che per la definizione di sottostruttura/estensione elementare gli stessi enunciati sono soddisfatti in M come in M0 dagli stessi elementi; quindi pure avendo operato una riduzione su {+, ·, σ, ∅} con l’esclusione di c, la “traccia” del suo passaggio sulla modellizzazione di M e di M0 permane. Se dunque M0 fosse isomorfo a N si darebbe una funzione biunivoca h : N +→ M0 tale che h (nk) = cM, per nk∈ N; ma questo comportarebbe la verifica simultanea di queste formule chiuse:

M0 |= (¬x ≡ σnk(∅))!cM" e N |= (x ≡ σnk(∅)) (nk),

il che mostra come c non faccia parte dell’insieme degli oggetti intesi come numeri natu- rali e dunque vada a modificare la composizione strutturale di M0 rendendo impossibile l’isomorfismo.

q.e.d. Questo risultato può essere collegato a quanto Dedekind aveva dimostrato nel 1888, e cioè che un sistema di assiomi composto da due enunciati del prim’ordine:

∀x∀y (σ (x) ≡ σ (y) → x ≡ y) ∀x (¬σ (x) ≡ ∅)

aggiunti alla formulazione dell’assioma di induzione completa (ovvero al second’ordine): ∀P (P (∅) ∧ ∀x (P (x) → P (σ (x))) → ∀xP (x))

è un insieme con un modello unico, a meno di isomorfismo.

La proprietà induttiva dell’insieme dei naturali, che è riassumibile dicendo che, per un insieme X : X ⊆ N, X è induttivo se:

" 0 ∈ X;

" Se x ∈ X allora σ (x) ∈ X,

è risolta pienamente solo al second’ordine, dove la quantificazione su proprietà e sottoin- siemi dell’universo di riferimento è permessa. Quello che accade al prim’ordine invece è che in luogo di un assioma si ha uno schema di induzione, cioè un’infinita serie di assiomi, per cui dato un predicato P (x) e un insieme X = {x|P (x)}, X è un insieme induttivo tale che X = N. È in questo delicato passaggio che viene persa la categoricità della classe dei modelli - e la costante c del teorema appena dimostrato funziona come un elemento deittico in questa discrepanza - perché al prim’ordine la mancanza di un controllo quantificazionale sui predicati del linguaggio permette a molte proprietà non desiderate di entrare in gioco nella strutturazione del modello; un esempio che valga per tutti potrebbe essere costituito dall’espressione N (x) il cui significato è “x non è un numero naturale”.