1 Interpolazione e Definibilità 6
1.1 La dimostrazione del lemma di Craig e del teorema di Robinson . . . 6
1.1.0.1 Definizione . . . 6 1.1.0.2 Definizione . . . 7 1.1.0.3 Definizione . . . 8 1.1.0.4 Definizione . . . 8 1.1.0.5 Definizione . . . 9 1.1.0.6 Lemma . . . 9
1.1.0.7 Teorema (lemma di Interpolazione o lemma di Craig) . . 9
1.1.0.8 Osservazione . . . 13
1.1.1 Il teorema di Robinson . . . 14
1.1.1.1 Teorema (Joint Consistency o teorema di Robinson) . . . 14
1.1.1.2 Esempio . . . 16
1.1.1.3 Teorema . . . 16
1.2 Definibilità in una teoria . . . 18
1.2.0.4 Teorema . . . 18
1.2.1 Definizione implicita . . . 20
1.2.1.1 Definizione . . . 20
1.2.2 Definizione esplicita . . . 21
1.2.2.1 Definizione . . . 21
1.2.2.2 Esempio (simboli relazionali) . . . 22
1.2.2.3 Esempio (simboli di funzione) . . . 22
1.2.2.4 Esempio (simboli di costante) . . . 23
1.2.2.5 Osservazione . . . 23
1.3 Il teorema di Beth (1953), Craig (1957) . . . 24
1.3.0.6 Lemma . . . 24
1.3.0.7 Teorema (Beth) . . . 25
1.3.0.8 Osservazione . . . 27
2 Il teorema di Fraïssé e i giochi di Ehrenfeucht 29 2.1 Isomorfismi, relazioni e forme equivalenti . . . 29
2.1.0.9 Definizione . . . 29
2.1.0.10 Lemma . . . 30
2.1.0.11 Definizione . . . 33
2.1.1 Forme standard . . . 34 2.1.1.1 Definizione . . . 35 2.1.1.2 Definizione . . . 36 2.1.1.3 Definizione . . . 36 2.1.1.4 Osservazione . . . 36 2.1.1.5 Lemma . . . 37 2.1.1.6 Lemma . . . 38 2.1.1.7 Lemma . . . 39
2.1.2 Corrispondenze tra strutture . . . 40
2.1.2.1 Teorema . . . 41 2.1.2.2 Teorema . . . 42 2.1.2.3 Teorema . . . 42 2.1.2.4 Lemma . . . 43 2.2 Il teorema di Fraïssé (1953) . . . 43 2.2.0.5 Definizione . . . 44 2.2.0.6 Teorema (Fraïssé) . . . 44 2.2.0.7 Teorema (Fraïssé) . . . 46 2.2.0.8 Osservazione . . . 47 2.3 Giochi di Ehrenfeucht . . . 48 2.3.0.9 Definizione . . . 49 2.3.0.10 Esempio . . . 50 2.3.0.11 Esempio . . . 51 2.3.0.12 Definizione . . . 52 2.3.0.13 Teorema . . . 53 2.3.0.14 Osservazione . . . 54
3 Alcuni risultati negativi per i modelli finiti 55 3.0.1 Insiemi enumerabili e insiemi decidibili . . . 56
3.0.1.1 Definizione . . . 56
3.0.1.2 Definizione . . . 56
3.0.1.3 Definizione . . . 57
3.0.1.4 Definizione . . . 57
3.0.1.5 Teorema . . . 58
3.0.2 Il fallimento dei teoremi di Completezza, di Compattezza e di Löwenheim-Skolem . . . 58
3.0.2.1 Definizione . . . 58
3.0.2.2 Lemma . . . 59
3.0.2.3 Lemma . . . 59
3.0.2.4 Teorema (indecidibilità della logica del prim’ordine) . . . 60
3.0.2.5 Teorema di Trakhtenbrot (1950) . . . 60
3.0.2.6 Lemma . . . 61
3.0.2.7 Osservazione . . . 61
3.0.3 Il fallimento del teorema di Beth e del lemma di Craig . . . 61
3.0.3.2 Esempio . . . 62
3.0.3.3 Teorema (Hájek, 1977) . . . 63
3.0.3.4 Teorema (Hájek, 1977) . . . 63
4 Un’esposizione del teorema di Lindström 65 4.1 Verso l’estensione della logica elementare . . . 66
4.1.0.5 Definizione . . . 66
4.1.0.6 Osservazione . . . 67
4.1.0.7 Teorema . . . 67
4.1.0.8 Teorema . . . 68
4.1.1 Il fallimento della Compattezza per Lω1,ω e per la logica del se-cond’ordine . . . 69
4.1.2 Un compendio d’insieme sui sistemi formali . . . 71
4.1.2.1 Definizione . . . 71 4.1.2.2 Definizione . . . 71 4.1.2.3 Definizione . . . 72 4.1.2.4 Lemma . . . 73 4.1.2.5 Lemma . . . 73 4.1.2.6 Definizione . . . 74 4.1.2.7 Lemma . . . 77
4.2 La dimostrazione del teorema (1969) . . . 79
La teoria dei modelli, oltre ad alcuni importanti risultati come ad esempio il teorema di Morley (1965) o la dimostrazione del teorema di Compattezza attraverso l’impiego di ultraprodotti, intorno agli anni ’50 e ’60 aveva visto fiorire nuove logiche infinitarie che seguendo l’esempio del second’ordine puntavano ad una maggiore potenza dal punto di vista espressivo pur desiderando mantenersi sufficientemente semplici e maneggevoli, dal momento che potevano contare sulla logica elementare come base simbolica e lessicale. Non sorprende, quindi, che in un contesto che sembrava spingere con insistenza verso una maggiore sofisticazione linguistica vi fosse stato un ritorno di interesse nei confronti della stessa logica del second’ordine, rimasta in disparte per circa l’intera prima metà del secolo, e che da tempo non era più vista come uno strumento privilegiato di indagine logica e meta-matematica. Il teorema di Lindström (1969) giunse allora a suggello del dibattito sulle capacità espressive inaugurando un metodo di analisi modellistica deno-mintato teoria dei modelli astratta che, concentrandosi sulle estensioni della logica del prim’ordine, aveva lo specifico intento di considerarne le proprietà generali rispetto al sostrato elementare. In questo senso il teorema del ’69, sostenendo che nessuna logica in grado di estendersi oltre il prim’ordine può mantenere tra le sue meta-proprietà i teo-remi di Compattezza e di Löwenheim-Skolem (verso il basso), mostrava come per ogni estensione, per quanto desiderabile, il costo da pagare fosse valutabile nei termini dell’al-terazione del precario e difficile equilibrio tra il potenziamento della ricchezza linguistica e il controllo ottenibile sulle classi dei propri modelli (Barwise, 1974). Si può dire che questo nuovo settore di indagine abbia ampliato i confini tradizionali del contesto di trat-tazione andando al contempo a definirne di nuovi: grazie alla precisione garantita dalla formalizzazione, ogni evento di ordine intra-logico diventava in modo del tutto naturale trasferibile o traducibile in una lettura inclusiva che tenesse nota delle modificazioni e delle implicazioni a livello sistemico.
Il capitolo 4 del presente studio si occupa precisamente di fornire gli strumenti definitori e concettuali adatti per chiarire questo aspetto e i precedenti accennati, e successivamente si impegna nella dimostrazione estesa e dettagliata del teorema principale, che in que-sto caso è essenzialmente ottenibile grazie all’applicazione degli strumenti algebrici di comparazione tra strutture messi a punto da Fraïssé e da Ehrenfeucht, ai quali è dedi-cato espressamente il secondo capitolo e a cui fa seguito una disamina sulle condizioni di applicabilità delle proprietà metateoriche fondamentali relativamente alle logiche infi-nitarie più utilizzate così come per i modelli finiti. A partire da questi ultimi risultati, nel capitolo 3 vengono affrontate le condizioni di sussistenza delle proprietà metateori-che caratteristimetateori-che dei linguaggi elementari nella loro transizione verso una cornice di riferimento più restrittiva, come quella della teoria dei modelli finiti. Per quanto si pos-sa imputare a questa sezione una certa sommarietà nella trattazione, bisogna ricordare
che l’ambito di studio che con queste pagine viene aperto costituisce un’intera branca a sé stante della ricerca logica, grossomodo riconducibile ala teoria della computabilità (quando non alle tematiche autonome della teoria dei modelli finiti) e sovente culminante con la dimostrazione dei teoremi di Incompletezza di Gödel; si capisce allora come un campo di ricerca siffatto sia comprensivo di una tale ricchezza e varietà di problemi da rendere ogni ipotesi di completezza sull’argomento del tutto impraticabile, soprattutto se rapportata al tipo di lavoro che abbiamo deciso di portare avanti. Infine il capitolo 1, con il quale si apre la nostra discussione, si sofferma ad analizzare due proprietà de-terminanti come l’Interpolazione e la Definibilità, che insieme contribuiscono a delineare quasi una completezza dello scambio e del contenuto informativo per le teorie dei sistemi logici elementari.
Come si noterà, rimane fuori dalla trattazione un qualsiasi approfondimento relati-vo ai teoremi di Compattezza e di Löwenheim-Skolem, di cui non vengono presentate le dimostrazioni ma soltanto le diverse applicazioni mirate a scopi specifici; questa è una scelta che è stata compiuta per non appesantire il passo argomentativo, ma anche perché, insieme con il teorema di Completezza (Gödel, 1930) e l’equivalente teorema del-l’Esistenza del Modello, questi risultati fanno parte di un corpo di conoscenze indubbia-mente fondazionale, e possono pertanto considerarsi dei prerequisiti all’intero contenuto dell’esposizione.
1.1 La dimostrazione del lemma di Craig e del teorema di
Robinson
Il contenuto del lemma di Interpolazione verte sulla relazione o intreccio (entanglement) tra due linguaggi del prim’ordine. Più precisamente, grazie ad esso viene esplicitata la rilevanza dell’informazione che una teoria è in grado di trasmettere a un’altra. Sia infatti ϕ→ ψ una formula valida, esisterà allora una formula χ tale che ϕ |= χ e χ |= ψ la cui caratteristica è di incarnare restrizioni linguistiche: al suo interno dovrà avere soltanto simboli di funzione, costante e predicato presenti sia in ϕ sia in ψ.
Pare evidente come questa restrizione caratterizzi le teorie del prim’ordine secondo una capacità di pregnanza linguistica che in un certo modo formalizza il principio economico noto come rasoio di Ockham. Alternativamente, possiamo esprimere il medesimo pensiero considerando l’interpolante χ come fosse “un’astrazione dell’essenza di ϕ” (Feferman, 2007), nella relazione ϕ |= ψ.
Vedremo come queste considerazioni guadagneranno in profondità non appena ci rivol-geremo a quel caso particolare costituito dall’identità, e ad altri casi limite, in cui l’interpolazione sussiste, ma è fondata su circostanze superficiali.
Prima di enunciare - e successivamente dimostrare - il lemma di Interpolazione, abbiamo bisogno di premettere la definizione della fondamentale nozione di inseparabilità di due teorie, nonché il risultato di un lemma, la cui acquisizione sarà di aiuto nella prima parte della dimostrazione. Aggiungiamo inoltre alcune definizioni che si renderanno necessarie tanto per la dimostrazione del primo teorema di questa sezione, come nelle sezioni e nei capitoli successivi.
1.1.0.1 Definizione
Siano A e B due strutture in L, dove con L si intende un linguaggio qualsiasi appartenente al prim’ordine. A è detta una sottostruttura di B, e scriviamo A ⊆ B, se
1. ∅ $= A ⊆ B;
2. Per ogni predicato di arietà n, P ∈ L e PA=!PB∩ An";
3. Per ogni lettera funzionale di arietà n, f ∈ L, fA= fB! An; cioè fAè la restrizione di fBrispetto a An;
Di conseguenza, nella relazione A ⊆ B la struttura B è detta un’estensione di A. Da un punto di vista algebrico non tutte le sottostrutture logiche individuano sotto-strutture specifiche del campo di ricerca. Per esempio, un sottogruppo H di un gruppo G, scritto H < G, è un sottoinsieme di G chiuso sotto l’operazione di gruppo, iden-tità ed elemento inverso. È facile vedere per esempio che (N, +, 0) ⊆ (Z, +, 0) ma (N, +, 0) ≮ (Z, +, 0), e questo perché in N manca ovviamente la possibilità di defini-re l’elemento inverso, ovvero (N, +, 0) non è un gruppo. Se ne deduce così che la nozione di sottostruttura dipende in modo prominente dalla scelta della segnatura, ed è così che spesso, se vogliamo studiare le proprietà di specifiche strutture algebriche, nella segnatu-ra evidenziata vogliamo mettere in evidenza la funzione f (x) = x−1 con cui si definisce l’inverso. Del resto, proprio per quanto detto, per una segnatura Lan = {±, ·, 0, 1} ogni sottostruttura di un anello è un sottoanello, come ad esempio (Z, ±, ·, 0, 1) pere (Q, ±, ·, 0, 1), e infatti si può dire che (Z, ±, ·, 0, 1) è un sottoanello di (Q, ±, ·, 0, 1) se vale (Z, ±, 0) < (Q, ±, 0), e se (Z, ±, 0) è chiuso sotto l’operazione di moltiplicazione (che in questo caso sappiamo essere associativa).
1.1.0.2 Definizione
Sia S una segnatura composita per un linguaggio L, e siano A e B due S-strutture; sia inoltre A una sottostruttura di B. Il sottoinsieme A, per A ⊆ B e nel caso in cui A contenesse almeno un elemento, è detto S-chiuso in B sse:
1. a1, . . . , an∈ A implica fB(a1, . . . , an)∈ B, per f ∈ S. 2. cB∈ A, per c ∈ S.
Se il rapporto viene letto al contrario, ogni sottoinsieme ∅ $= X ⊂ B, per X S-chiuso, gen-era una sottostruttura di B. La sottostruttura gengen-erata dal dominio X viene scritta come [X]Bo alternativamente come B|X. Nel caso di una S-struttura A, con S una segnatura interamente relazionale, ogni sottoinsieme ∅ $= X ⊂ A determina una sottostruttura di A, e di conseguenza ogni elemento di A induce una sottostruttura su A.
La sottostruttura del campo (R, ±, ·, 0, 1)1 generata dalle sue costanti, cioè 1 e 0, e chiusa sotto le operazioni di somma e moltiplicazione è l’anello (Z, ±, ·, 0, 1) degli interi; a riprova dell’importanza della scelta della segnatura, se oltre all’insieme {±, ·, 0, 1} aves-simo considerato il simbolo per 1
x, allora la sottostruttura generata dal campo (R, ±, ·, 0, 1) sarebbe stato il campo dei razionali.
1Un campo è definibile attraverso la formalizzazione delle seguenti proprietà:
1. ∀x∀y∀z (x + (y + z) ≡ (x + y) + z); ∀x∀y∀z (x ◦ (y ◦ z) ≡ (x ◦ y) ◦ z), proprietà associativa della somma e del prodotto;
2. ∀x∀y (x + y ≡ y + x); ∀x∀y (x ◦ y ≡ y ◦ x), proprietà commutativa della somma e del prodotto; 3. ∀x∀y∀z (x ◦ (y + z) ≡ x ◦ y + x ◦ z), proprietà distributiva;
4. ∀x ((x + ∅) ≡ x); ∀x ((x ◦ 1) ≡ x), esistenza dell’elemento neutro per la somma e per il prodotto; 5. ∀x∃y ((x + y) ≡ ∅); ∀x∃y ((x ◦ y) ≡ 1), posto x &= ∅, esistenza dell’opposto e del reciproco.
1.1.0.3 Definizione
Prese due strutture A e B per un linguaggio L, si dice che A è una sottostruttura elementare di B se:
1. ∅ $= A ⊆ B;
2. ogni L-formula ϕ è soddisfatta in A e in B dagli stessi n-elementi: A |= ϕ (a1, . . . , an) sse B |= ϕ (a1, . . . , an).2
Se A è una sottostruttura elementare di B scriviamo A ( B e B è detta conseguente-mente un’estensione elementare di A.
La nozione di sottostruttura elementare è estremamente restrittiva: se si prendono infatti due ordinamenti totali (N, <) e (N+, <) si vede non solo che tra le due strutture vale la relazione (N+, <) ⊆ (N, <), ma anche (N+, <) ∼= (N, <). Nonostante le strutture siano dunque isomorfe, l’elemento 1 in (N+, <) indica il più piccolo numero dell’ordinamento, ma lo stesso non può dirsi per (N, <); pertanto (N+, <)" (N, <) .
1.1.0.4 Definizione
Siano L e L∗ due linguaggi, di cui L∗ è ottenuto aggiungendo all’insieme dei simboli non logici di L una quantità al massimo numerabile di simboli relazionali, simboli di fuzione e simboli di costante (L ⊆ L∗). Siano adesso A e A∗ due strutture per L e L∗, rispettivamente. Se dom (A) = dom (A∗) e se le due strutture denotano allo stesso modo gli elementi non logici di L, allora l’unica differenza tra A e A∗ è apprezzabile nell’interpretazione che viene data ai simboli di L∗ non presenti in L, e così A∗ è detta un’espansione di A relativamente a L e, viceversa, A indica il ridotto di A∗ rispetto a L. Questa relazione è esprimibile scrivendo: A = A∗ ! L.
Un esempio, tra i molti possibili, è dato dalla relazione del campo dei reali K = (R, +, ·, 0, 1) con il campo dei reali con ordinamento3 K≤ = (R, ≤, +, ·, 0, 1), in quanto K = K≤! L
ar e i simboli del linguaggio comune sono appunto Lar = {+, ·, ∅, 1}. Infatti, in termini
2In quest’ultima precisazione si trova la vera differenza con la nozione appena definita di sottostruttura. 3I campi ordinati sono campi su cui è definita una relazione d’ordine totale (≤):
1. ∀x (x ≤ x), riflessività;
2. ∀x∀y∀z ((x ≤ y ∧ y ≤ z) → x ≤ z), transitività; 3. ∀x∀y ((x ≤ y ∧ y ≤ x) → x ≡ y), asimmetria; 4. ∀x∀y (x ≤ y ∨ y ≤ x), linearità.
Inoltre, la relazione d’ordine in un campo deve essere compatibile con le operazioni di somma e prodotto:
1. ∀x∀y∀z (x ≤ y → x + z ≤ y + z), compatibilità della relazione d’ordine con la somma;
generali, per due modelli A∗ e A per L ⊆ L∗, se A∗ ! L = A allora, per ϕ ∈ L n e a1, . . . , an∈ A,
A|= ϕ (a1, . . . , an) sse A∗|= ϕ (a1, . . . , an),
dove evidentemente gli elementi a1, . . . , an sono gli stessi per entrambi i modelli. Per vedere che questo avviene scegliamo una funzione β : {vn: n∈ N} +→ A tale che β (vi) = aiper i < n, e applichiamo successivamente il lemma di coincidenza per formule, in modo da trovare che le due interpretazioni I1 = (A, β)e I2= (A∗, β)coincidono sia sui simboli che sulle variabili libere di ϕ.
1.1.0.5 Definizione
Siano L1 e L2 due linguaggi del prim’ordine, e sia T una teoria in L1 e S una teoria in L2. Diciamo che un enunciato ψ ∈ (L1∩ L2) separa le due teorie sse T |= χ e S |= ¬χ. Due teorie si dicono inseparabili se non esiste alcun enunciato χ che le separa.
1.1.0.6 Lemma
“Sia L un linguaggio del prim’ordine, e T una teoria in L. Sia dunque ϕ una formula in T e C = {c1, . . . , cn} un insieme di costanti tale che C ∩ L = ∅.
Allora:
T |= ϕ (c1, . . . , cn)⇒ T |= ∀x1. . .∀xnϕ (x1, . . . , xn)”.
Dimostrazione. Supponiamo che T # ∀x1. . .∀xnϕ (x1, . . . , xn), esiste allora una struttura Acon un insieme di elementi {a1, . . . , an} ⊂ A tale che
A|= ¬ϕ (a1, . . . , an).
La L ∪ {c1, . . . , cn}-struttura A∗ = (A, a1, . . . , an), con dom (A∗) = dom (A), che mette in evidenza l’interpretazione delle nuove costanti del linguaggio {c1, . . . , cn} con elementi del dominio {a1, . . . , an} ⊂ A è un’espansione di A che appunto interpreta c1, . . . , cn con a1, . . . , an. A∗ è allora un modello di T ∪{¬ϕ (c1, . . . , cn)}, generando una contraddizione con la premessa T |= ϕ (c1, . . . , cn).
q.e.d. 1.1.0.7 Teorema (lemma di Interpolazione o lemma di Craig)
“Siano ϕ e ψ due enunciati tali che ϕ |= ψ. Esiste allora un enunciato χ tale che: 1. ϕ |= χ e χ |= ψ;
2. Ogni simbolo di funzione, costante e predicato che occorre in χ (escluso il simbolo per l’identità: ≡), occorre sia in ϕ sia in ψ .
Un enunciato di questo tipo si chiama interpolante per ϕ e χ.”
Il secondo punto specifica che l’interpolante può presentare nel suo vocabolario il sim-bolo ≡, anche se questo non è presente negli enunciati ϕ e ψ; questa precisazione si rende necessaria per far sì che la generalità dell’enunciato non venga meno nel contesto della considerazione di casi particolari che esemplificheremo brevemente alla fine della dimostrazione.
Dimostrazione. Procediamo per assurdo e mostriamo che se non esiste un interpolante χ, allora ϕ # ψ. La dimostrazione sarà compiuta quando avremo costruito un modello J per ϕ ∧ ¬ψ.
Sia dunque L1il linguaggio contenente tutti i simboli di ϕ e L2il linguaggio contenente tutti i simboli di ψ. Poniamo:
L0 =L1∩ L2; L = L1∪ L2.
Sia ora C = {c1, c2, . . .} un insieme numerabile di nuove costanti tale che C ∩ L1 =∅ e C∩ L2 =∅. Troveremo le seguenti equazioni:
L∗ 1 =L1∪ C; L∗ 2 =L2∪ C; L∗ 0 =L0∪ C; L∗ =L ∪ C.
(a) Per costruire un modello che verifichi sia ϕ che ¬ψ facciamo vedere che le teorie costruite a partire da {ϕ} in L1 e {¬ψ} in L2 sono inseparabili. Se esistesse un enunciato χ ∈ L∗
1∩ L∗2 che separa {ϕ} e {¬ψ} avremmo: {ϕ} |= χ (c1, . . . , cn) e {¬ψ} |= ¬χ (c1, . . . , cn), cioè χ (c1, . . . , cn) |= {ψ}. Questo significa che prese x1, . . . , xnvariabili che non occorrono già in χ (c1, . . . , cn), l’enunciato ∀x1. . .∀xnχ (x1, . . . , xn)sarebbe un interpolante per ϕ e ψ, contro
quanto assunto.
Applicando il lemma 1.0.1.4 arriviamo alla conclusione desiderata, ovvero che {ϕ} e {¬ψ} sono inseparabili tanto in L1∩ L2 quanto in L∗1∪ L∗2. (b) Siano ϕ0, ϕ1, . . . , ϕn e ψ0, ψ1, . . . , ψn enumerazioni di tutti gli enunciati di
L∗1 e L∗2, rispettivamente. Costruiamo due successioni crescenti di teorie: {ϕ} = T0⊂ T1 ⊂ T2⊂ . . . in L∗1e {¬ψ} = S0 ⊂ S1 ⊂ S2 ⊂ . . . in L∗2, tali che: a) Tm e Sm sono insiemi finiti e inseparabili di enunciati; b) Se Tm ∪ {ϕm} e Sm sono inseparabili, allora ϕm ∈ Tm+1; c) Se Sm ∪ {ψm} e Tm+1 sono inseparabili, allora ψm ∈ Sm+1; d) Se ϕm := ∃xϕ (x) e ϕm ∈ Tm+1, allora esiste una costante c ∈ C per cui ϕ!x
c "
Parimenti vale per Sm.
In (b).d le costanti vengono scelte in modo che non compaiano in Tm, Sm, ϕm o ψm. Si tratta a questo punto di mostrare che l’inseparabilità delle teorie è preservata:
" Per il caso T0, S0 la dimostrazione è già stata affrontata, si trova in 1.
" Se invece ϕm:=∃xϕ (x) e ϕm ∈ Tm+1, ipotizziamo che Tm∪ {∃xϕ (x)} e Sm siano inseparabili, lo saranno anche Tm ∪
# ∃xϕ (x) , ϕ!xc "$ e Sm, e quindi # ϕ!xc"$ ∈ Tm+1.
Supponiamo che χ separi Tm∪ #
∃xϕ (x) , ϕ!xc "$
e Sm, allora avremo: Tm∪#∃xϕ (x) , ϕ!xc"$|= χ e Sm|= ¬χ; per il teorema semantico di Deduzione:
Tm∪ {∃ϕ (x)} |= ϕ !x
c "
→ χ.
Siccome nessuna nuova costante si trova in Tm∪{∃xϕ (x)}, cosa evidente per costruzione, allora con un metodo che non va a disturbare le parti linguistiche di Tm e ∃xϕ (x) andiamo a sostituire liberamente la costante in ϕ!x
c "
con una variabile nuova, diciamo y, e provvediamo alla chiusura, con un procedimento non dissimile da quanto già visto al punto (a). ϕ!xc"→ χ ⇓ ϕ (y)→ χ ⇓ ∀y (ϕ (y) → χ) ⇓ ¬∀y¬ϕ (y) → χ cioè: ∃yϕ (y) → χ.
Applichiamo il teorema semantico di Deduzione una seconda volta: Tm∪ {∃xϕ (x) , ∃yϕ (y)} |= χ.
Ma le due variabili, x e y, sono entrambe variabili qualsiasi, quindi ∃xϕ (x) e ∃yϕ (y) sono la stessa formula. Da questo si deduce che χ separa Tm∪ {∃ϕ (x)} e Sm, contro l’ipotesi induttiva.
Le serie crescenti di teorie T0 ⊂ T1 ⊂ T2 ⊂ . . . in L∗1, e S0 ⊂ S1 ⊂ S2 ⊂ . . . in L∗2 sono inseparabili; questo significa che non c’è un singolo enunciato nel loro linguaggio comune tale che Ti|= χ e Si|= ¬χ.
(c) Chiamiamo Tω = %m∈NTm e Sω = %m∈NSm.
Poiché Tω e Sω sono inseparabili, sono anche coerenti. Per poter costruire il modello di {ϕ}∧{¬ψ} dobbiamo passare per la dimostrazione della coerenza
di Tω ∪ Sω.
Mostriamo innanzitutto che Tω è massimale consistente in L∗1 e Sω è mas-simale consistente in L∗
2. Partendo da Tω procediamo per assurdo e ipo-tizziamo esista un enunciato φm tale che φm ∈ T/ ω e ¬φm ∈ T/ ω. Ma al-lora la teoria Tm ∪ {φm} sarebbe separabile da Sω, perché altrimenti φm si troverebbe in Tm+1 e quindi in Tω; quindi abbiamo sia Tω ∪ {φm} |= χ che Sω |= ¬χ, per qualche χ. Supponiamo adesso che esista un enunciato ¬φm tale che Tm∪ {¬φm} è separabile da Sω. Portando in fondo lo stesso procedimento appena adottato si troverà che Tω ∪ {¬φm} |= χ∗ e Sω |= ¬χ∗.Da questi due fatti, entrambi con lo stesso valore ipotetico, troviamo che l’enunciato (χ ∨ χ∗)separa T
ωe Sω, ovvero Tω|= (χ ∨ χ∗)e Sω|= ¬ (χ ∨ χ∗). Adesso facciamo vedere che la teoria Tω∩ Sω è massimale consistente nel lin-guaggio condiviso L∗
0. Prendiamo dal risultato appena raggiunto, cioè la massimalità di Tω in L∗1 e di Sω in L∗2, e consideriamo un enunciato qualsi-asi, diciamo ϕ, dal linguaggio condiviso L∗
0. Dal momento che Tω e Sω sono inseparabili avremo solamente due opzioni possibili: ϕ ∈ Tω e ϕ ∈ Sω oppure ¬ϕ ∈ Tω e ¬ϕ ∈ Sω, ovvero ϕ ∈ Tω∩ Sω oppure ¬ϕ ∈ Tω∩ Sω.
(d) Costruiamo il modello per Tω∪ Sω.
Per la coerenza di Tω, con B∗1={B1, b1, b2, . . .} definiamo un modello per Tω in L∗
1. B∗1 ha una parte strutturale e un dominio in cui vengono interpretate le costanti di C utilizzate. Esplicitiamo questo rapporto di interpretazione e scriviamo B∗
1= (B1, b1, b2, . . .), dove B1 è un modello per Tω in L1 e la sua parte strutturale è stata espansa attraverso le denotazioni (b1, b2, . . .)per le nuove costanti introdotte in L∗
1. Per il fatto che le costanti {c1, . . . , cn} ⊂ C in Tωsono dei testimoni, come mostrato in (b).d, il sottomodello di B∗1, che sarà formato da un dominio composto dalle denotazioni per {c1, c2. . .} e da una parte strutturale dovuta all’adeguamento delle restrizioni delle interpretazioni dei simboli relazionali e dei funtori, è modello di Tω e lo indichiamo come A∗1. A∗1 può essere scritto come A∗1 = (A1, b1, b2, . . .), dove A1 rappresenta la parte strutturale, e il dominio A∗
1 di A∗1 è proprio costituito dagli elementi {b1, b2, . . .}.
" Mostriamo adesso che A∗
1 è un modello di Tω in L∗1:
(Base) Sia P c un enunciato atomico di Tω; allora A1 |= P c. Per la definizione di sottomodello vale ovviamente A∗
1|= P c.
(Passo induttivo) Sia ora ϕm:=∃xϕ (x) ∈ Tω e si assuma che valga A1 |= ϕm. Sap-piamo che in Tω c’è anche ϕ
!x c "
, per una costante c ∈ C; dunque A1 |= ϕ !x c " . Per ipotesi vale A∗ 1 |= ϕ !x c " e pertanto A∗
1 |= ∃ϕ (x). Per la dimostrazione dei casi
enun-ciativi basterà seguire l’ipotesi induttiva.
Rivolgendoci verso Sω possiamo proporre un argomento del tutto simmetrico a quello appena compiuto, introducendo un modello B∗
2 per Sω in L∗2e un sottomod-ello A∗
2 = (A2, d1, d2, . . .)il cui dominio A∗2 è dato dagli elementi {d1, d2, . . .}. " Prendiamo adesso i due ridotti A∗°
1 := A∗1 ! L∗0 e A∗°2 := A∗2 ! L∗0 e vediamo che, siccome in entrambi i casi i domini A∗°
1 e A∗°2 sono composti dalle denotazioni dell’in-sieme di costanti {c1, c2. . .}, i due insiemi possono essere messi in corrispondenza biunivoca, individuando una funzione, diciamo h, che associ a ogni bi ∈ {b1, b2. . .} un di ∈ {d1, d2. . .}. 4 Questa funzione stabilisce inoltre che A∗°1 e A∗°2 sono iso-morfi, cosa che possiamo mostrare ragionando per assurdo e supponendo che esista un enunciato atomico P t ∈ L∗
0 tale che P t ∈ Tω e P t /∈ Sω; ma allora Tω |= P t mentre, per il fatto che Sω è consistente massimale, Sω |= ¬P t. Sappiamo però che P t ∈ L∗
0 e che anche la teoria Tω∩ Sω è consistente massimale, da cui l’assurdo cercato.
" Siamo nelle condizioni per poter considerare la funzione h precedentemente intro-dotta come la funzione identità e fare in modo tale che valga bn = dn per ogni n ∈ N. Così facendo le due strutture A1 e A2, che sono caratterizzate dal fatto di avere le interpretazioni di {c1, c2. . .} nel dominio e non nella struttura espansa, cioè modelli rispettivamente di Tω e Sω in L1 e in L2 e non in L∗1 e in L∗2, hanno lo stesso ridotto in L0. Sia a questo punto J il modello per L tale che A1:= J! L1 e A2:= J! L2. J : (A1, A2), per J = A1∪ A2, sia cioè una struttura costruita come composizione di A1 e di A2, che siamo certi non presenti contraddizioni perché il modello di Tω∩ Sω in L0 è lo stesso sia per A1 che per A2. Adesso, dal momento che ϕ ∈ Tω e A1 |= Tω, abbiamo A1 |= ϕ, e similmente, in ragione di ¬ψ ∈ Sω e A2|= Sω, troviamo che A2 |= ¬ψ.
Per la composizione del modello precedentemente descritta, troviamo che J |= ϕ ∧ ¬ψ, che contiene la contraddizione cercata.
q.e.d. 1.1.0.8 Osservazione
Consideriamo il caso in cui l’identità si renda necessaria nella costruzione dell’interpolante in mancanza di simboli condivisi.
Prendiamo tre coppie di formule come esempio:
4Da notare, in particolare, che per quanto detto si dà dom!A∗° 1 " = dom (A∗1)e dom ! A∗°2 " = dom (A∗2).
1. ϕ := ∃x (P (x) ∧ ¬P (x)), ψ :=∃xQ (x); 2. ϕ := ∃xQ (x), ψ :=∃x (P (x) ∨ ¬P (x)); 3. ϕ := ∀x∀y (x ≡ y), ψ :=∀x∀y (P (x) ↔ P (y)).
I tre interpolanti per le tre coppie di formule saranno, rispettivamente: χ1 :=∃x (x $= x);
χ2 :=∃x (x ≡ x); χ3 :=∀x∀y (x ≡ y).
Questo ci porta a concludere, in particolare nei casi 1. e 2., che un interpolante con identità si rende ammissibile ogniqualvolta valga |= ¬ϕ oppure |= ψ, e tra le due formule non vi siano simboli condivisi, esemplificando così il rapporto debole di conseguenza logica che sussiste tra ϕ e ψ. D’altra parte, se l’identità non fosse del tutto ammessa, nessuna delle tre coppie di formule presenterebbe un interpolante. Vale la pena allora di ricollegare questo risultato con quanto detto in sede di introduzione al teorema, nello specifico alle considerazioni in merito ad Ockham.
Lo studio dell’implicazione - o consequentia - ockhamiana, costruita a partire dal modello stoico, distingueva le consequentiae materiales dalle consequentiae formales. Solo queste ultime tuttavia avevano carattere informativo (meglio ancora: logico), ovvero stabilivano ciò che faceva di un nesso consequenziale un’implicazione necessaria (formales). Significa-tivamente, alle cosiddette consequentiae materiales si guardava come fossero sinonimo di paradossi, in quanto prive di un qualsiasi contenuto logico cogente, che in ultima analisi le rendeva valide e applicabili solamente per motivi eteronomi e insoddisfacenti: esat-tamente il caso in cui l’antecedente mostrava una contraddizione e il conseguente una tautologia, oppure entrambe le cose insieme.
Risulta così ancora più precisa l’affermazione di Feferman: l’interpolante rappresenta il concentrato informativo, che proviene dall’antecedente, di cui il conseguente può dis-porre affinché il nesso argomentale risulti investito dal maggiore tasso di rilevanza logica, andando a determinare quella che in termini medievali sarebbe stata detta appunto con-sequentia formalis.
1.1.1 Il teorema di Robinson
1.1.1.1 Teorema (Joint Consistency o teorema di Robinson)
“Siano L∗ e L° due linguaggi del prim’ordine tali che L = L∗ ∩ L°; T sia una teoria sintatticamente completa in L e T∗ e T° siano due estensioni coerenti di T , in L∗ e in L°, rispettivamente. Allora, l’unione delle due teorie T∗ ∪ T° è una teoria coerente in L∗∪ L°.”
Dimostrazione. Partiamo dall’assunzione dell’incoerenza di T∗∪ T°, cioè T∗∪ T° 5⊥, per arrivare infine a dimostrare che la teoria T in L non è sintatticamente completa.
Siccome T∗∪ T° è una teoria incoerente, allora esistono, e sono finiti, due sottoinsiemi Σ∗⊂ T∗ e Σ°⊂ T° tali che la loro unione Σ∗∪ Σ° è incoerente. Siano
ϕ∗:= ϕΣ1∗∧ ϕΣ∗ 2 ∧ . . . ∧ ϕΣ ∗ n e ϕ°:= ϕΣ° 1 ∧ ϕΣ ° 2 ∧ . . . ∧ ϕΣ ° n
le congiunzioni, ovviamente finite, di tutti gli enunciati presenti nei due sottoinsiemi Σ∗ e Σ°. Così facendo siamo passati dal concetto insiemistico di unione a quello logico-linguistico di congiunzione; pertanto possiamo affermare che se Σ∗∪ Σ° 5⊥, allora anche ϕ∗∧ ϕ°5⊥.
A partire da questo risultato possiamo innescare la seguente catena di inferenze: |= ¬!ϕ∗∧ ϕ°" ⇓ |= ¬ϕ∗∨ ¬ϕ° ⇓ |= ϕ∗→ ¬ϕ° ⇓ ϕ∗ |= ¬ϕ°
Per il lemma di Craig, possiamo affermare l’esistenza di un interpolante χ ∈ T tale che ϕ∗ |= χ e χ |= ¬ϕ°. Dall’espressione ϕ∗ |= χ si deduce che χ è una conseguenza logica di T∗, mentre dalla coerenza di quest’ultima possiamo concludere che T # ¬χ. Per T° invece avremo: T° |= ¬χ, e infine T # χ.
Ma allora, per il fatto che T # ¬χ e T # χ, la teoria T non sarebbe sintatticamente completa in L, in contraddizione con l’ipotesi iniziale.
q.e.d. Portiamo all’attenzione un esempio, il cui contributo istruttivo è di sottolineare l’importanza della assunzioni che vengono fatte su T e sul linguaggio in cui T è espressa; si tratta ovvi-amente della proprietà di consistenza massimale, che T è sostanzialmente obbligata ad esibire, e, per quanto concerne L, di essere il linguaggio condiviso da L∗ e L°.
1.1.1.2 Esempio
Siano L∗ e L° due linguaggi tali che L∗ ={P, Q} e L° = {P, Q}, dove con P e con Q sono indicati due predicati monadici. Di conseguenza:
L =!L∗∩ L°"=L∗ =L° ={P, Q}.
Sia ora T∗ una teoria in L∗ avente come assiomi ∀xP x e ∀xQx; e T° invece una teoria i cui assiomi sono ∀xP x e ∀x¬Qx.
Sia adesso T una teoria in L il cui unico assioma è dato da ∀xP x. Si osserva che T∗∪ T° non è soddisfacibile, nonostante sia T∗ che T° siano individualmente estensioni soddisfacibili di T . Questo avviene, e può avvenire, unicamente per il fatto che T non è una teoria consistente massimale.
Allo stesso modo, se prendessimo L = {P }, andremmo nuovamente incontro all’impossibilità di dimostrare il teorema, ma L $= L∗∩ L°.
Dopo avere dimostrato sia il lemma di Craig che il teorema di Robinson (utilizzando per quest’ultimo proprio il lemma di Interpolazione), è possibile fornire un ulteriore risultato di interesse: assunto il teorema di Robinson, grazie ad esso si giunge a dimostrare il lemma di Craig, mostrando così l’equivalenza di fondo dei due enunciati. Da un punto di vista dimostrativo, il seguente teorema utilizza quello che è stato definito il double compactness argument5, che come suggerisce il termine stesso riguarda una doppia applicazione, sequenziale, del teorema di compattezza.
1.1.1.3 Teorema
“Siano L∗ e L° due linguaggi del prim’ordine tali che L = L∗ ∩ L°; T sia una teoria sintatticamente completa in L e T∗ e T° siano due estensioni coerenti di T , in L∗ e in L°, rispettivamente. Allora, l’unione delle due teorie T∗ ∪ T° è una teoria coerente in L∗∪ L°.”
⇓
“Siano ϕ e ψ due enunciati tali che ϕ |= ψ. Esiste allora un enunciato χ tale che: 1. ϕ |= χ e χ |= ψ;
2. Ogni simbolo di funzione, costante e predicato che occorre in χ, occorre sia in ϕ sia in ψ.”
Dimostrazione. Consideriamo ϕ |= ψ e ϕ ∈ L∗, ψ ∈ L°. Sia anche L = L∗∩L°. Dobbiamo trovare un interpolante χ ∈ L per ϕ e ψ.
Sia ∆ l’insieme degli enunciati ρ di L tali che ϕ |= ρ. Cioè: ∆ = Cn (ϕ)∩ L.
5Boolos G. S., Burgess J. P. e Jeffrey R. C., Computabiliy and Logic, Cambridge University Press,
Per trovare χ, mostriamo che l’insieme ∆ ∪ {¬ψ} è incoerente. Per cominciare, supponi-amo per assurdo che la teoria ∆ ∪ {¬ψ} sia coerente e che pertanto abbia un modello, diciamo A |= ∆ ∪ {¬ψ}. Definiamo adesso in L l’insieme
Π ={θ ∈ L|A |= θ} = T h (A),
dove A è appunto il modello introdotto per ∆∪{¬ψ} e T h (A) è, per ipotesi del teorema, consistente massimale, a cui aggiungiamo la definizione dei seguenti insiemi di enunciati per L∗ e L°:
Π∗={θ ∈ L∗|Π ∪ {ϕ} |= θ} = Cn (T h (A) ∪ ϕ) ∩ L∗. Π°=#θ∈ L°|Π ∪ {¬ψ} |= θ$= Cn (T h (A)∪ ¬ψ) ∩ L°.
Π° è a tutti gli effetti un’estensione coerente di Π: A è infatti un modello per ∆ ∪ {¬ψ}; A|= Π°; da cui la coerenza di Π°.
L’insieme Π∗ ∪ Π° invece non è coerente. Se infatti esistesse un modello B |= Π∗∪ Π°, dovrebbe allo stesso tempo valere B |= ϕ ∧ ¬ψ, quando invece per ipotesi sappiamo che vale ϕ |= ψ.6 Allora, per il teorema di Robinson, Π∗ non è una estensione coerente di Π; quindi l’insieme Π ∪ {ϕ} non è coerente, e pertanto non ha modelli.
Introduciamo a questo punto il procedimento double compactness.
1. Per Compattezza, sia Σ ⊂ Π (Σ è un insieme finito) tale che Σ ∪ {ϕ} |=⊥.
Sia µ la congiunzione di tutte le formule in Σ. Allora ϕ |= ¬µ, con ¬µ ∈ L. Ma allora ¬µ ∈ Cn (ϕ) ∩ L, cioè ¬µ ∈ ∆ e, per come è stato impostato il modello:
A|= µ.
Quest’ultimo risultato confligge con il dato che tutti i congiunti impegnati nella formazione di µ sono presenti in Π, e siccome Π = T h (A) sono tali che
A|= µ.
Raggiunta questa contraddizione possiamo rifiutare l’assunzione per assurdo e con-cludere che ∆ ∪ {¬ψ} è incoerente.
2. Per Compattezza, sia T tale che T ⊂ ∆. Sia poi ϑ la congiunzione degli elementi di T che determinano la contraddizione: ϑ ∧ ¬ψ |=⊥, ovvero ϑ |= ψ.
Ognuno dei congiunti che appartengono a ϑ si trova in L, e quindi ϑ ∈ L. Per definizione di ∆, ognuno dei congiunti è una conseguenza logica di ϕ:
ϕ|= ϑ.
Ecco l’interpolante cercato.
q.e.d.
1.2 Definibilità in una teoria
Durante quel periodo che fu apocalittico per le scienze esatte, e che idealmente coincide con il corso a noi prossimo della fondazione della moderna logica matematica, si assistet-te allo sforzo di isolare quelle proprietà delle assistet-teorie che poassistet-tessero supportare il processo di assiomatizzazione. Ciò su cui si dibatteva era, tra le molte altre cose, la legittimità naturale della disciplina, il genus, che Frege considerava acquisito una volta stabilite le stipulazioni corrispondenti all’assetto assiomatico: un percorso sotto questo aspetto affine al fondamento scientifico già presente in Euclide, che intese gli assiomi come entità auto-nome e dotate di una intrinseca evidenza di significato. In ottica formalista questo non risultava più semplicemente applicabile, dal momento che le teorie cominciavano a essere studiate come collezioni di formule il cui significato variava armonicamente con il varia-re dei modelli ammissibili. Affinché dunque uno specifico significato fosse non soltanto preservato dalle oscillazioni semantiche ma posto persino in evidenza, ci si aspettava che le teorie formali, oltre che non-contraddittorie, fossero categoriche, ovvero che la varietà molteplice dei loro modelli potesse essere composta all’interno di una relazione isomorfa, così da rilevare e intendere un unico modello naturale (modello standard) che permettesse di sorvolare sulle differenze inessenziali garantite dalla riproduzione con varianze dello stesso.7
L’idea era quella di giungere a caratterizzare la categoricità passando per la completezza sintattica (Entscheidungsdefinitsheit, seguendo la terminologia di Hilbert) e avere così la possibilità, avendo a che fare con una teoria che fosse massimale, di rivendicare si-multaneamente tanto la completezza - da pensarsi come esaustione deduttiva fondata sulle nozioni assiomatiche di base - come l’integrità semantica e la non degenerazione del senso logico. Qualcosa tuttavia dovette essere concesso o messo da parte, e questo perché si giunse a capire che le interpretazioni o modelli possibili non potevano essere così facilmente dominabili: è oggi noto che tra le proprietà di categoricità e di massimalità l’equivalenza non sussiste; equivalenza che invece si rende rintracciabile tra la comple-tezza sintattica e la relazione di equivalenza elementare, e può essere caratterizzata con precisione dal seguente teorema, il cui contributo aggiuntivo è quello di chiarire alcu-ni equilibri simmetrici tra le relazioalcu-ni che investono le strutture, e il loro riflesso sulle proprietà delle teorie:
1.2.0.4 Teorema
“Sia T una teoria del prim’ordine. Vale che:
T è sintatticamente completa sse due modelli qualsiasi di T sono elementarmente equivalenti.”
Dimostrazione. (Si dimostra prima l’implicazione forte del teorema) Siano dati A e B due modelli qualsiasi per T . Sappiamo dunque che, per un qualsiasi enunciato ϕ, dal
7Un corpus ben più nutrito di conoscenze in merito sarebbe stato raggiunto negli anni a venire con la
momento che T è sintatticamente completa, avremo che T 5 ϕ oppure T 5 ¬ϕ. Da qui, per il teorema di Correttezza, la possibilità di trasferire la proprietà inferenziale alla sfera semantica: nel caso del primo modello A |= ϕ oppure A |= ¬ϕ; B |= ϕ oppure B |= ¬ϕ, nel caso del secondo. Entrambi i modelli allora si trovano in accordo su ϕ (oppure su ¬ϕ, rispettivamente), dal momento che entrambi sono modelli di T . Questo prova che A e B dimostrano le stesse formule chiuse, ovvero che sono elementarmente equivalenti. Procediamo adesso considerando un enunciato ϕ tale che T $ ϕ; se ne deduce per comple-tezza semantica T # ϕ, come anche l’esistenza di un modello A di T ∪{¬ϕ}: quest’ultimo passaggio è garantito dal fatto che ϕ è un enunciato, ovvero una formula chiusa il cui destino semantico deve poter essere deciso secondo l’alternativa restrittiva A |= ϕ oppure A |= ¬ϕ. Sia con ModS(T ) indicata la classe dei modelli di T per la segnatura S in cui T è espressa, e con A∗ un modello qualsiasi tale che A∗ ∈ Mod
S(T ). Per quan-to sostiene l’ipotesi di quesquan-to versante della dimostrazione, presi arbitrariamente due modelli A, A∗ ∈ Mod
S(T ) sappiamo che vale A ≡ A∗; allora possiamo affermare che A∗|= T ∪ {¬ϕ}, e per il teorema di Completezza concludere T 5 ¬ϕ.
q.e.d. Quanto appena visto presenta un risvolto immediato:
" Per dimostrare l’incompletezza di una teoria si esibiscono due modelli non equiva-lenti.
Se si considera invece che nel caso della categoricità il tipo di relazione tra i modelli è un isomorfismo, concludiamo che:
" Per dimostrare la non categoricità di una teoria si esibiscono due modelli non isomorfi.
Con la realizzazione di un modello di geometria iperbolica (ancorché con validità locale circoscritta), Beltrami si era inserito nel clima di fermento critico sorto intorno al quinto postulato euclideo: si cercava di farlo derivare dalle conoscenze inequivocabilmente evi-denti, immaginando una dimostrazione; oppure di corroborarne lo statuto fondazionale provando a costruire sistemi geometrici che risultassero essere contraddittori in seguito alla sua negazione. In continuità con le considerazioni appena affrontate, il metodo uti-lizzato da Beltrami per provare l’indipendenza di un dato assioma ϕ da un insieme di assiomi ψ1, . . . , ψn può essere opportunamente sintetizzato come segue: se esistono due modelli A e B tali che un dato assioma ϕ è sia verificabile nel modello A, che a sua volta verifica gli assiomi ψ1, . . . , ψn, sia falsificabile nel modello B, che vogliamo verifichi ψ1, . . . , ψn (garantendo in ogni caso la coerenza del corpo teorico), allora l’assioma ϕ non è derivabile a partire da alcun enunciato nella serie ψ1, . . . , ψn. È da questo sche-ma a validità generale fornito dalla procedura di Beltrami che Padoa derivò il metodo per dimostrare l’indipendenza di un concetto da altri concetti, all’interno di una teoria formale.
1.2.1 Definizione implicita
Il concetto di definizione implicita risente, per la portata teorica dei suoi connotati e per lo schema che lo informa, di una duplice discendenza: alla paternità prospettata dal metodo di Padoa si anticipa in ambito esclusivamente matematico la nozione di funzione implicita, comparsa per la prima volta con Eulero in Introductio Analysin Infinitorum (1784), poi ripensata da Gergonne con specifici intenti definizionali intorno al 1830, e definitivamente precisata da Dini nella pubblicazione delle sue lezioni del 1907, le quali riprendevano i corsi tenuti quasi trent’anni addietro. Ciò che caratterizza una funzione implicita è l’analisi del comportamento di una funzione a livello locale. In termini geo-metrici, un’equazione del tipo x = y2+ 1 non rappresenta il grafico di una funzione, dal momento che è possibile tracciare almeno una retta x = k (k ≥ 2) che intersechi il grafico in due punti distinti. Se tuttavia l’attenzione viene rivolta ad una porzione specifica dello spazio cartesiano allora è possibile isolare un’area (ovvero: un intorno) in cui l’equazione assuma i valori di una funzione. Ad esempio, continuando con l’equazione appena intro-dotta, questo vale in R2 per un intorno definibile su (2, 2). Più precisamente: presi due sottoinsiemi di R, A e B, sia definita una funzione f su A × B +→ R. Sia C un intervallo aperto, sottoinsieme di A, e infine f∗ : C +→ R una funzione definita in C. Allora si dice che l’equazione f (x, y) = 0 definisce implicitamente la funzione f∗ : C +→ R se e soltanto se per ogni x nell’insieme aperto vale f (x, f∗(x)) = 0. Il teorema di Dini sulle funzioni implicite interviene a sancire le condizioni sotto le quali da un’equazione come quella appena vista di forma f (x, y) = 0 sia possibile isolare il luogo geometrico (o algebrico) delle radici, ovvero definire una funzione che sia unica. Questo procedimento, in ultima analisi, risulta scarsamente dominabile, e molto spesso la complessa operazione attraverso la quale certe condizioni vengono ricercate non è in grado di raggiungere l’esito sperato.
A differenza di quanto avviene all’interno del contesto analitico, il definiendum in un ambiente logico è individuato sempre univocamente, dal punto di vista linguistico formale, per mezzo di una definizione implicita che utilizzi metodi modellistici e la nozione di conseguenza logica.
1.2.1.1 Definizione
Sia data T una teoria, e con LT sia indicato il linguaggio in cui la teoria è espressa. Un simbolo Rn si dice definito implcitamente e determinato univocamente in T per mezzo di simboli non-logici Q1, . . . , Qn ∈ LT se due modelli qualsiasi di T , diciamo A e B, con A = B, concordando sull’interpretazione da attribuire a Q1, . . . , Qn coincidono sull’interpretazione di Rn.
Si può opportunamente sottolineare come per una logica - come quella circoscritta nei termini del prim’ordine - per cui valga il teorema di Compattezza, la definibilità implicita comporta che se una data proprietà (espressa da un simbolo linguistico) R è determinata univocamente in una teoria T , allora esiste un sottoinsieme finito T% ⊂ T all’interno del quale la proprietà R è opportunamente, cioè implicitamente, definita. A margine di
quanto scritto specifichiamo infine che è possibile estendere il risultato definitorio dalle logiche semplici a logiche di ordine superiore, come per esempio dimostrato da Tarski nel caso della logica del secondo ordine (Tarski, 1935).8
1.2.2 Definizione esplicita
La definizione esplicita offre una facilità di comprensione pressoché immediata, dal mo-mento che le teorie oggetto di studio altro non fanno che confermare, con il rigore del-la sintassi formale, il metodo di precisazione terminologica già familiare al linguaggio naturale. L’idea che sostiene la nozione di definizione esplicita è che
“...a theory defines a concept in terms of others when a definition of that concept in terms of the others is a consequence of the theory.”9
Ovvero, “una teoria definisce un concetto in termini di altri concetti” quando è deducibile in una teoria una formula che affermi la sostituibilità del simbolo da definire con il contenuto concettuale che ne informi il significato.
1.2.2.1 Definizione
Sia T una teoria, e con LT sia indicato il linguaggio in cui la teoria è espressa. a) Una simbolo relazionale Rn∈ L/
T di arietà n è definibile esplicitamente in T tramite una LT-formula ϕ se
T |= ∀x1. . .∀xn(R (x1, . . . , xn)↔ ϕ (Q1, . . . , Qn, x1, . . . , xn)),
dove con (Q1, . . . , Qn) sono indicati tutti i simboli non logici di ϕ, e le (eventuali) variabili libere di Rn e di ϕ si trovano tutte nell’insieme {x
1, . . . , xn}.10 b) Un simbolo di funzione fn ∈ L/
T di arietà n è definibile esplicitamente in T tramite una LT-formula ϕ se
T |= ∀x1. . .∀xn∃!xn+1(f (x1. . . xn)≡ xn+1↔ ϕ (x1, . . . , xn, xn+1)),
dove le variabili dell’insieme {x1, . . . , xn, xn+1} possono comparire libere, e l’elemento individuato dalla variabile legata xn+1 esiste ed è unico.
c) Un simbolo di costante c /∈ LT è definibile esplicitamente in T tramite una LT-formula ϕse
T |= ∃!x1(c≡ x1 ↔ ϕ (x1)).
Il caso della costante è riconducibile ad un caso particolare della definizione di un funtore, propriamente a un simbolo funzionale con arietà 0.
8Con il metodo di Padoa si opera semplicemente per contrapposizione.
9Boolos G. S., Burgess J. P. e Jeffrey R. C., Computabiliy and Logic, Cambridge University Press,
Cambridge 2010, p. 266.
10La non-circolarità della definizione è garantita indipendentemente dalle condizioni imponibili al
rapporto definiens-definiendum, per via del fatto che Rn è un simbolo estraneo al linguaggio di
1.2.2.2 Esempio (simboli relazionali)
Sia Tpord la teoria dell’ordinamento parziale.11 Allora ∀x(R(x) ↔ ∃y(x < y ∨ y < x))
è una definizione esplicita di R in Tpord attraverso la quale l’enunciato
∀x∀y((∃p(x < p ∨ p < x) ∧ ∃m(y < m ∨ m < y)) → (x < y ∨ x ≡ y ∨ y < x)) può essere riscritto in modo più semplice e chiaro come
∀x∀y((R(x) ∧ R(y)) → (x < y ∨ x ≡ y ∨ y < x)).
1.2.2.3 Esempio (simboli di funzione) Sia con Tgr indicata la teoria dei gruppi.12
Siccome in un qualsiasi modello di Tgr è verificata l’espressione ∀x∃!y (x ◦ y ≡ e),
allora è possibile definire un simbolo di funzione f che rappresenti l’operazione inversa scrivendo:
∀x∀y (f (x) ≡ y ↔ x ◦ y = e).
11Sia X un insieme, una relazione binaria ≤ su X è detta una relazione d’ordine parziale (e X è detto
un insieme parzialmente ordinato) se sono verificati gli assiomi che esprimono la proprietà riflessiva, transitiva, antisimmetrica:
1. ∀x (x ≤ x);
2. ∀x∀y∀z ((x ≤ y ∧ y ≤ z) → x ≤ z); 3. ∀x∀y ((x ≤ y ∧ y ≤ x) → x ≡ y).
Dove per x ≤ y bisogna leggere (x < y ∨ x ≡ y).
Quindi, una relazione d’ordine è parziale quando nel suo campo cadono coppie di elementi (in questo caso appartenenti a X) che non sono confrontabili; difatti un ordine totale (oppure ordine lineare) si ottiene a partire da un ordine parziale garantendo in aggiunta che la relazione in questione sia connessa:
1. ∀x∀y (x ≤ y ∨ y ≤ x).
12Per teoria dei gruppi intendiamo la teoria della classe di tutti i gruppi, che è formulabile
equiva-lentemente, grazie al teorema di Completezza, come la chiusura deduttiva del seguente insieme di assiomi:
1. ∀x∀y∀z((x ◦ y) ◦ z ≡ x ◦ (y ◦ z)); 2. ∀x((x ◦ e) ≡ x);
3. ∀x∃y ((x ◦ y) ≡ e).
1.2.2.4 Esempio (simboli di costante)
Sia TZF C il sistema Zermelo-Fraenkel (comprensivo dell’assioma di scelta) per la teoria degli insiemi.13
In TZF C il simbolo di costante ∅ è definito inserendo nel sistema la definizione: ∃!x (∅ ≡ x ↔ ∀y (¬y ∈ x)),
dal momento che
TZF C |= ∃!x∀y (¬y ∈ x).
Alternativamente, nella struttura (Z, +, ·) possiamo definire l’esistenza dell’elemento neutro per la somma introducendo la seguente definizione:
∃!x (∅ ≡ x ↔ ∀y (x + y ≡ y)).
1.2.2.5 Osservazione
Per una qualsiasi segnatura S che sia composita è sempre possibile e, come vedremo, spesso desiderabile14 ridurre tutti gli elementi di S ai soli simboli relazionali. Ciò no-nostante si è preferito, principalmente per esaustività espositiva, dettagliare le varietà definitorie per ogni classe di simboli non-logici; tuttavia, da qui in avanti, verrà indi-cato sistematicamente il lessico relazionale come unico rappresentante per l’insieme dei simboli di S, questo a meno di casi particolari o in cui la segnatura stessa sia oggetto tematico del discorso. Irrilevante ai fini del contenuto teorico è anche la considerazione della arietà di un dato simbolo relazionale, che quindi è trascurabile nel rispetto delle valutazioni di ordine generale.
La forma comprensiva della definizione esplicita sarà allora rappresentata dalla seguente scrittura:
13Un’esposizone classica del sistema Zermelo-Fraenkel è la seguente:
1. ∀x∀y∀z ((z ∈ x ↔ z ∈ y) → x ≡ y), o assioma di estensionalità; 2. ∀x∀y∃z (x ∈ z ↔ (x ∈ y ∧ ϕ (x))), o assioma di separazione;
3. ∀x (∃y (y ∈ x) → ∃y (y ∈ x ∧ ¬∃z (z ∈ x ∧ z ∈ y))), o assioma di fondazione; 4. ∃x∀y¬ (y ∈ x), o assioma dell’insieme vuoto;
5. ∀x∀y∃z∀u (u ∈ z ↔ (u ≡ z ∨ u ≡ y)), o assioma della coppia; 6. ∀x∃y∀z (z ∈ y ↔ ∃u (u ∈ x ∧ z ∈ u)), o assioma dell’unione;
7. ∀x∃y∀z (z ∈ y ↔ ∀u (u ∈ z → u ∈ x)), o assioma dell’insieme potenza;
8. ∃x (∃y (∀u¬ (u ∈ y) ∧ y ∈ x) ∧ ∀y (y ∈ x → ∃z (∀u (u ∈ z ↔ (u ∈ y ∨ u ≡ y)) ∧ z ∈ x))), o assioma dell’infinito;
9. ∀u∀v∀w (ϕ (u, v) ∧ ϕ (u, w) → u ≡ w) → ∀x∃y∀z (z ∈ y ↔ ∃u (u ∈ x ∧ ϕ (u, z))), o assioma di rimpiazzamento;
10. ∀x (∀u∀v ((u ∈ x ∧ v ∈ x ∧ u &= v) → ¬∃z (z ∈ u ∧ z ∈ v)) → ∃y∀u (u ∈ x → ∃w∀z ((z ∈ u ∧ z ∈ y) ↔ z ≡ w))), o assioma di scelta.
∀x1. . .∀xn(R (x1, . . . , xn)↔ ϕ (Q1, . . . , Qn, x1, . . . , xn)).
1.3 Il teorema di Beth (1953), Craig (1957)
Quando al Terzo Congresso Internazionale di Parigi, tenuto nel 1900, Padoa espose i dettagli del procedimento utile per stabilire se e sotto quali condizioni un termine fosse definibile per mezzo di altri in un sistema deduttivo, non fornì una prova della sua correttezza, considerandola del tutto evidente. Sulla scia di Tarski, Beth si occupò di revisionare il contenuto della conferenza del 1900 e, grazie soprattutto al fatto che la logica nel frattempo si era arricchita di nuovi strumenti deduttivi, nel 1953 dimostrò il teorema che porta il suo nome, stabilendo pertanto che il metodo organizzato da Padoa è completo per la logica del prim’ordine. In seguito il teorema di Beth fu recuperato, rivisitato ed esteso ad altre logiche (per esempio da Schütte (1962) alla logica intuizionista), ma per quanto ci riguarda è importante soprattutto notare, come scrive van Heijenoort, che
“Using his previously proved interpolation lemma (1957), Craig gave a sim-pler proof of Beth’s result. A. Robinson (1955) had obtained a theorem that is equivalent to the interpolation lemma and had derived Beth’s result from it.”15
Prima di intraprendere la dimostrazione del teorema, procediamo a precisare ulterior-mente la nozione di definizione implicita, come rimasto in sospeso dalla definizione 2.0.3.1.
Sia LT il linguaggio nel quale è espressa la teoria T che definisce implicitamente il simbolo R, e sia L∗T∗ un nuovo linguaggio ottenuto dalla sostituzione in LT di tutti i simboli non-logici, tranne Q1, . . . , Qn, con altrettanti aventi la stessa arietà. Si individuano due procedimenti generativi simmetrici, uno ascendente e uno discendente:
1. A e B siano due modelli di T tali che A = B e QA
i = QBi . Sia C il modello ottenuto a partire da A e B tale che A = B = C e QA
i = QBi = QCi. Per un qualsiasi altro simbolo non-logico η ∈ LT la procedura di interpretazione sia strutturata in modo tale che i simboli η ∈ LT vengano interpretati da C come ηA e i simboli η∗ ∈ L∗T∗
siano interpretati da C come ηB. Da questo segue che C |= T ∪ T∗; 2. Sia invece C |= T ∪ T∗. Allora A = C ! L
T e B = C ! L∗T∗ sono modelli
rispettivamente di T e di T∗, stante il fatto che A = B = C e QA
i = QBi = QCi. 1.3.0.6 Lemma
“R è definibile implicitamente tramite Q1, . . . , Qn in T sse
T ∪ T∗ |= ∀x1. . .∀xn(R (x1, . . . , xn)↔ R∗(x1, . . . , xn)).”
Dimostrazione. (Prima il verso “solo se”) Supponiamo che R sia definibile implicitamente tramite Q1, . . . , Qn e che esista un modello qualsiasi C tale che C |= T ∪ T∗. Siano A e Bi modelli ottenibili da C come descritto nel punto 2.. Essendo per ipotesi R definibile tramite Q1, . . . , Qn in T , sappiamo che RA = RB. Se dunque A e B convergono sulla stessa interpretazione di R, per il punto 2., C offre la stessa interpretazione di R e di R∗, ovvero
C|= ∀x1. . .∀xn(R (x1, . . . , xn)↔ R∗(x1, . . . , xn)). Ma C |= T ∪ T∗, pertanto
T∪ T∗|= ∀x1. . .∀xn(R (x1, . . . , xn)↔ R∗(x1, . . . , xn)). Al contrario, supponiamo che
T∪ T∗|= ∀x1. . .∀xn(R (x1, . . . , xn)↔ R∗(x1, . . . , xn)).
Siano A e B due modelli per T con le stesse caratteristiche descritte precedentemente al punto 1.. Conseguentemente C è un modello tale che C |= T ∪ T∗ e in accordo con l’ipotesi dimostrativa
C|= ∀x1. . .∀xn(R (x1, . . . , xn)↔ R∗(x1, . . . , xn)).
Segue che C assegna la stessa interpretazione a R e R∗ e, per la costruzione dei modelli descritta al punto 1., RA= RB.
Questo significa che R è definito implicitamente tramite Q1, . . . , Qn in T .
q.e.d. 1.3.0.7 Teorema (Beth)
“I metodi di definizione implicita e di definizione esplicita sono equivalenti.”
Dimostrazione. Avendo già provveduto alla dimostrazione del verso “se” con il lemma precedente, la dimostrazione che seguirà si occuperà di provare che “se R è definibi-le implicitamente tramite Q1, . . . , Qn in T , allora R è definibile esplicitamente tramite Q1, . . . , Qn in T ”.
Per il lemma 2.1.0.6 avremo allora: T ∪ T∗ |= ∀x
1. . .∀xn(R↔ R∗).
Per il teorema di Compattezza esistono due sottoinsiemi finiti Σ ⊂ T e Σ∗ ⊂ T∗ tali che Σ∪Σ∗ |= ∀x1. . .∀xn(R↔ R∗). Siano ora ϕ := ϕΣ1 ∧ϕΣ2 ∧. . . ϕΣn e ϕ∗ := ϕΣ ∗ 1 ∧ϕΣ ∗ 2 ∧. . .∧ ϕΣ∗
n le congiunzioni di tutti gli enunciati in Σ e Σ∗tali che ϕ∧ϕ∗|= ∀x1. . .∀xn(R↔ R∗). Preso C = {c1, . . . , cn} come un insieme di nuove costanti da aggiungere al linguaggio di T, e sostituendo ogni variabile con il suo nuovo “nome” nel linguaggio, abbiamo ϕ ∧ϕ∗|= R (c1, . . . , cn)↔ R∗(c1, . . . , cn).
Partendo adesso da una formula come quella appena scritta, si interviene con una se-rie di passaggi logici al fine di riorganizzare la formalizzazione del contenuto logico dell’enunciato:16
ϕ∧ ϕ∗|= R (c1, . . . , cn)↔ R∗(c1, . . . , cn) ↓ ϕ∧ ϕ∗, R (c1, . . . , cn)|= R∗(c1, . . . , cn) ↓ ϕ, ϕ∗, R (c1, . . . , cn)|= R∗(c1, . . . , cn) ↓ ϕ∧ R (c1, . . . , cn)|= ϕ∗→ R∗(c1, . . . , cn) .
In questo modo i simboli appartenenti alle due teorie vengono disposti simmetricamente ai due lati della relazione di conseguenza logica. Con questa nuova disposizione è possibile utilizzare il lemma di Craig e trovare un enunciato interpolante χ (c1, . . . , cn) ∈ L ∪ C tale che
ϕ∧ R (c1, . . . , cn)|= χ (c1, . . . , cn) e χ (c1, . . . , cn)|= ϕ∗→ R∗(c1, . . . , cn), da cui, per logica,
ϕ|= R (c1, . . . , cn)→ χ (c1, . . . , cn)e ϕ∗|= χ (c1, . . . , cn)→ R∗(c1, . . . , cn). A questo punto si può legittimamente notare che né il predicato R né il predicato R∗ compaiono tra i simboli dell’interpolante, e in ϕ∗ |= χ (c
1, . . . , cn) → R∗(c1, . . . , cn) è possibile rimpiazzare tutte le occorrenze di R∗ con R ed ottenere
ϕ|= χ (c1, . . . , cn)→ R (c1, . . . , cn) e ϕ |= R (c1, . . . , cn)→ χ (c1, . . . , cn). Da questo fatto troviamo direttamente che
ϕ|= R (c1, . . . , cn)↔ χ (c1, . . . , cn).
Ricordando che ϕ è una congiunzione di formule, possiamo riscrivere la precedente formula come segue:
Σ|= R (c1, . . . , cn)↔ χ (c1, . . . , cn).
α∧ β |= x ↔ z,
da cui si possono seguire due versanti di ragionamento mettendo in evidenza uno dei due termini della doppia implicazione:
1. α ∧ β, x |= z; 2. α ∧ β, z |= x.
Dal momento che nessuna costante individuale c1, . . . , cncompare in T , possiamo pren-dere y1, . . . , yknuove variabili da sostituire per c1, . . . , cn, e quantificando universalmente troviamo:
Σ|= ∀y1. . .∀yk(R (y1, . . . , yk)↔ χ (y1, . . . , yk)).
Siccome i simboli non logici tramite i quali definire R si trovano in χ (e non ve ne sono altri) e siccome Σ ⊆ T , allora con
T |= ∀y1. . .∀yk(R (y1, . . . , yk)↔ χ (Q1, . . . , Qn, y1, . . . , yn)) abbiamo una definizione esplicita di R tramite Q1, . . . , Qn in T .
q.e.d. Se è vero che il versante della dimostrazione che dalla definizione esplicita conclude la de-finizione implicita non introduce passaggi di particolare spessore argomentativo, e anche speculativamente è oggi possibile ritenerlo un esito del tutto scontato, più interessante è osservare il percorso inverso, al quale non a caso si rende utile l’applicazione del lemma di Craig. Da un punto di vista intuitivo generale, le definizioni esplicite offrono una lettura del nesso definizionale prettamente sintattica, mentre il procedimento implicito accede al medesimo contenuto per via semantica. Questo fatto, unito alla natura della riformulazione in termini modellistici ed equivalenti del lemma di Craig da parte di Ro-binson (Joint Consistency theorem), ci introduce ad una sostanziale unità tematica dello schema che informa il pensiero del teorema appena nominato e al procedimento implicito di definizione di un termine R attraverso Q1, . . . , Qnin una teoria. Vediamo infatti che i due linguaggi L∗ e L° si rispecchiano inalterati nelle teorie T e T∗, mentre in Robinson, dall’assunzione iniziale che il linguaggio L = L∗∩ L° sia massimale, si giunge a inferire la coerenza di T∗∪ T°; nel sistema definitorio si muove proprio dalla coerenza di T ∪ T∗ (che ha un modello qualsiasi, C) per individuare un insieme di predicati (Q1, . . . , Qn), coerenza che è garantita ancora una volta dalla presenza di un modello, e la completezza sintattica è ottenibile in modo naturale attraverso la considerazione dal carattere finito dell’insieme. Quest’ultimo quindi è un insieme, si potrebbe dire, “a contenuto disponibi-le”, e per questo è possibile farvi riferimento per l’individuzione di un unico predicato da definire. Il collegamento diretto con il lemma di Craig ci dice infine che è il linguaggio condiviso da due teorie a permettere la comprensione, l’ascolto, di tutti quei possibi-li circuiti di scambio possibi-linguistico in grado di permettere la traduzione di un significato implicito in un’affermazione sintatticamente (ovvero linguisticamente) verificabile. 1.3.0.8 Osservazione
L’estensione del campo di validità relativo ai procedimenti definizionali merita una con-siderazione a sé stante. Dal momento che si tratta di individuare le leggi di formazione di particolari capacità espressive, le caratteristiche linguistiche delle logiche in ogget-to diventano condizionanti la validità del procedimenogget-to. Se dunque per la logica del
prim’ordine si dà un naturale assorbimento sia in termini sintattici che modellistici della procedura definitoria, altrettanto non può essere garantito da logiche che non presentano lo stesso grado di bilanciamento tra semantica e sintassi. Dunque il teorema di Beth fallisce nel proprio intento di completezza per quelle logiche estese da un quantificatore con numero cardinale (del tipo: “esiste un numero x di y tale che...”), nel caso il numero cardinale non risultasse essere numerabile; fallisce per logiche che siano sufficientemente potenti da descrivere la propria sintassi e la propria semantica: è quanto afferma il con-tenuto del teorema di Indefinibilità (Tarski,17 1936);18 infine fallisce anche per la logica (debole) del second’ordine e per la logica del prim’ordine, quest’ultima nel caso in cui presentasse una semantica ristretta alle strutture finite.
Vedremo in seguito più in dettaglio i casi di nostro interesse, quelli per cui il metodo di definibilità qui appena esposto risulti non applicabile (Gurevich 1984), (Hájek 1977).19
17Ma già Gödel (1930).
18Boolos G. S., Burgess J. P. e Jeffrey R. C., Computabiliy and Logic, Cambridge University Press,
Cambridge 2010, p. 222.
Ehrenfeucht
Il presente capitolo concentra l’attenzione attorno alla dimostrazione del teorema di Fraïssé, fissandone la rilevanza attraverso una serie di argomenti che proprio nel risultato del matematico francese trovano naturale assorbimento e risoluzione. Ciò che pone il teorema in un quadro di preminenza complessiva, al cospetto di molte altre conquiste appartenenti alla teoria dei modelli, è dovuto principalmente alla sua qualità “sintetica”, esprimibile diversamente come la capacità di caratterizzare in termini puramente alge-brici (e quindi strutturali, non-linguistici) una proprietà così importante e al contempo così sfuggente per le misure degli strumenti logici come quella di equivalenza elementare. Alla dimostrazione del teorema di Fraïssé si affiancherà una formulazione ludico-teoretica nota come “giochi di Eherenfeucht” assolutamente equivalente all’enunciato originale. L’esposizione da ora in avanti seguirà un ordine di sviluppo tripartito, in cui dapprima verranno presentati gli strumenti necessari all’enunciazione del teorema, e in seguito si darà spazio proprio alla dimostrazione delle due forme equivalenti dello stesso: ne emerg-erà un’impressione della vicinanza nel metodo e negli strumenti della teoria dei modelli alle proprietà dell’algebra astratta (proprietà che diverranno ancora più evidenti e fonda-tive nel prossimo capitolo dedicato ai sistemi logici), e una serie di applicazioni che, nel breve percorso che da ultimo sarà aperto sulla teoria dei modelli finiti, riqualificheranno alcuni dei risultati notevoli mostrati nei precedenti capitoli sotto l’ottica particolare che il presente contesto teorico permette di adottare.
2.1 Isomorfismi, relazioni e forme equivalenti
2.1.0.9 Definizione
Siano A e B due strutture per L linguaggio del prim’ordine con segnatura S, che può essere considerata relazionale senza perdita di generalità. Per isomorfismo parziale tra A e B si intende una mappa p tale che sia un omomorfismo iniettivo tra un sottoin-sieme di A e un appropriato sottoinsottoin-sieme di B. Ovvero, per elencare completamente le caratteristiche:
1. p è una funzione iniettiva;
2. il dominio di p è un sottoinsieme di A, indicato dalla notazione dom (p) ⊂ A; 3. l’immagine di p è un sottoinsieme di B, indicato dalla notazione im (p) ⊂ B; 4. per ogni Rn
RA
i (a1, . . . , an) sse RBi (p (a1) , . . . , p (an)).
In caso di strutture costruite con segnature interamente relazionali, un isomorfismo parziale non è altro che un isomorfismo h : A|A" ∼= B|B" definito tra le sottostrutture
indotte di A e B attraverso i sottoinsiemi propri A% ⊂ A e B% ⊂ B, in cui dom (h) = A% e im (h) = B%.
Con P art (A, B) si denota infine l’insieme degli isomorfismi parziali da A a B. 2.1.0.10 Lemma
“Sia S una segnatura relazionale, a cui appartiene anche una specifica relazione binaria ≡ per l’identità. Allora, date due strutture A e B, per S, a1, . . . , ar ∈ A e b1, . . . , br∈ B vale la seguente equivalenza:1
p (ai) = bi definisce un ismorfismo parziale tra le due strutture A e B ;
Per ogni formula atomica ϕ ∈ FS
r , si ha che A|= ϕ (a1, . . . , ar) sse B |= ϕ (b1, . . . , br).”2
Dimostrazione. La seguente sarà una dimostrazione compiuta sulle formule atomiche di FS
r . Come si vedrà, questo sarà sufficiente per circoscrivere e mettere a fuoco il problema, ovvero capire secondo quali circostanze un isomorfismo parziale possa dirsi definito. Con lo specifico riferimento alle formule atomiche, inoltre, introduciamo il primo passo di una più completa dimostrazione (svolta ovviamente sulla complessità della formula stessa) che avrà l’obiettivo di verificare la validità della proposizione anche per i rimanenti casi rimasti qui senza studio.
Si pongano preliminarmente alcune osservazioni: una riguardante l’interpretazione della relazione di identità tra due elementi del dominio; l’altra che concerne la n-arietà di un simbolo relazionale R, che si mostra naturalmente legata al numero r di elementi presi da Ae da B. Dati allora i, j ≤ r ∈ N+ per i casi 1. e 2.; e Rn∈ LS con i
1, . . . , ir≤ r ∈ N+, per i casi 3., 4.: 1. ai = aj sse A |= vi≡ vj(ai, . . . , ar); 2. bi= bj sse B |= vi ≡ vj(bi, . . . , br); 3. RA(a i1. . . ain)sse A |= Rvi1. . . vin(a1, . . . , ar);3 1Con l’ulteriore precisazione che dom (p) = {a
1, . . . , an}, im (p) = {b1, . . . , bn}, e!i, j≤ n ∈ N+". 2Con la notazione FS
r si intende indicare l’insieme delle formule per una data segnatura S e con un
numero r ∈ N massimo di variabili.
3Per un qualsiasi simbolo relazionale R con arietà n, a
i può anche essere la stessa, ma si presenta
pur sempre ripetuta entro le n ≤ r volte. Questo dipende dal fatto che, nel linguaggio, stiamo considerando ψ ∈ Ls
4. RB(b
i1. . . bin) sse B |= Rvi1. . . vin(b1, . . . , bn).
Iniziamo dimostrando che, per ogni formula atomica ϕ ∈ FS
r, se vale: A|= ϕ (a1, . . . , ar)sse B |= ϕ (b1, . . . , br),
allora una funzione p (ai) = bi definisce un isomorfismo parziale tra le due strutture A e B. Per 1. e 2., e per l’assunzione preliminare del caso che stiamo trattando, abbiamo:
A|= vi≡ vj(a1, . . . , ar)sse B |= vi ≡ vj(b1, . . . , br); e anche:
ai = aj sse bi = bj.
Si può notare immediatamente come sia possibile trovare una mappa p tale che p (ai) = bi, e come questa funzione a elementi distinti di {a1, . . . , ar} ∈ A assegni elementi distinti in {b1, . . . , br} ∈ B; ovvero: p è iniettiva.
Ora, siccome per 3. e 4. è vero anche che
A|= Rvi1. . . vin(a1, . . . , ar)sse B |= Rvi1. . . vin(b1, . . . , br),
dove, per l’equivalenza in rilievo, RA(a
i1. . . ain) sse RB(bi1. . . bin),
la mappa p che abbiamo appena definito e visto essere iniettiva restituirà di con-seguenza la seguente relazione:
A|= Rvi1. . . vin(a1, . . . , ar) sse B |= Rvi1. . . vin(p (a1) , . . . , p (ar)).
Ma allora p : p (ai) = bi, come definita nella tesi da dimostrare, è anche omomorfa. Dimostriamo adesso la conversa.
Sia p (ai) = bi (i≤ r) un isomorfismo parziale tra le due strutture A e B; allora per ogni formula atomica ψ ∈ FS
r A|= ψ (a1, . . . , ar) sse B |= ψ (b1, . . . , br). Per 1. e 2. e per la definizione di p:
ai= aj e, al posto di bi = bj,
p (ai) = p (aj).
Dal momento che p è iniettiva, allora la formula vi ≡ vj è vera in A per una definita coppia di elementi (ai, aj), così come in B è valida per una coppia (p (ai) , p (aj)). Questo significa che le due strutture verificano la stessa formula:
