4.2 La dimostrazione del teorema (1969)
4.2.0.8 Il Teorema di Lindström (1969)
“Sia L un sistema logico regolare che verifichi le condizioni: L1≤ L;
Comp (L); L¨oSko (L);
allora L è equivalente a un sistema logico che esprime la logica del prim’ordine, ovvero: L1 ∼ L.”
Dimostrazione. Prima di intraprendere la dimostrazione nelle sue parti più tecniche, è opportuno valutare il piano di svolgimento complessivo del teorema, in modo che le sezioni formali che lo promuovono siano ben organizzate all’interno di un’architettura che non solo ne sostenga i passaggi cruciali, ma anche scandisca e chiarifichi gli obbiettivi temporanei che andremo guadagnando avvicinandoci alla conclusione.
Presenteremo quindi un’articolazione schematica tripartita, preceduta a sua volta da un’introduzione con il compito principale di riassumere e tratteggiare gli argomenti che le tre successive sezioni si faranno carico di sviluppare. In ognuna di queste parti, a una premessa intuitivo-discorsiva di inquadramento generale delle tematiche di pertinenza, seguirà la dimostrazione dei passaggi più sottili o semplicemente impossibili da esprimere diversamente, al di fuori del lessico formale. Come è facile intendere, questo procedimento avrà validità per le tre sezioni incentrate sul corpo argomentativo, mentre per il brano introduttivo, che per natura e intento è il luogo destinato a risolvere pienamente la chiarificazione logica nella esibizione del quadro compiuto, si tratterà soltanto di esibire un’unica e autonoma esposizione schematica.
Introduzione
A partire dall’enunciato del teorema, si nota in primo luogo che, per via dell’ipotesi iniziale secondo la quale vale L1≤ L, per arrivare alla tesi L1 ∼ L possiamo opportuna- mente fissare l’attenzione sulla dimostrazione dell’espressione L ≤ L1.
Da adesso in poi sulla formula iniziale verranno operate una serie di riduzioni (o meglio: riformulazioni) con l’intento di alleggerire il carico logico-argomentativo dell’enunciato originale senza tuttavia concedere limitazioni alla sua validità generale. Può sicuramente risultare utile già da adesso pensare al teorema sotto l’ottica di una caratterizzazione meno restrittiva, in modo da rendere il lavoro con l’enunciato da dimostrare più facil- mente governabile: visto infatti che con i due lemmi di preparazione9al teorema abbiamo certificato alcune delle meta-proprietà nei riguardi di un sistema logico regolare utiliz- zando solamente Comp (L), per sfruttare direttamente ciò che questi due lemmi offrono in quanto a soluzioni, condurremo la dimostrazione come se Comp (L) fosse l’unica pro- prietà richiesta dal teorema di Lindström; seguendo questa impostazione, arriveremo fino alle soglie dell’ultima sezione, dove per la prima volta ci troveremo ad applicare anche la proprietà L¨oSko (L), finendo così per accordarci alle condizioni poste originariamente dal teorema.
Adesso, dato che il nostro obiettivo è stato fissato sulla dimostrazione di L ≤ L1, per quanto visto nel lemma 4.1.2.7 ci sarà sufficiente verificare la seguente affermazione:
“Per tutte le S-strutture A e B, se A ≡ B allora A ≡L B.”
Partendo da qui, possiamo guadagnare l’accesso a un’ulteriore riduzione grazie alla pos- sibilità che ci viene offerta di utilizzare segnature interamente relazionali.
Vediamo dunque che se un sistema logico regolare L gode delle proprietà: Comp (L);
L1≤ L;
allora queste due espressioni sono equivalenti:
“Per tutte le S-strutture A e B, se A ≡ B allora A ≡L B.” ;
“Per tutte le Sr-strutture relazionali Ar e Br, se Ar≡ Br, allora Ar≡ LBr.” Come già abbiamo visto (nel capitolo dedicato alle definizioni), sappiamo che se vale A ≡ Ballora per Ar e Br, vale Ar≡ Br. Si tratta piuttosto di capire se valga l’implicazione reciproca A ≡ B ⇐⇒ Ar ≡ Br, e in particolar modo se da Ar ≡ Br si possa inferire A≡L B. È una questione facilmente risolvibile, verificando che, per un enunciato ψ ∈ L (S), si può trovare:
A|=Lψ sse Ar|=Lψr, per la proprietà Elim (L);
Ar|=Lψr sse Br |=L ψr, grazie al fatto che vale Ar ≡ Br; Br|=Lψr sse B |=L ψ; da cui concludiamo
A≡LB.
Acquisita la legittimità dell’enunciato “Per tutte le Sr-strutture relazionali Ar e Br, se Ar ≡ Br, allora Ar ≡
L Br”, è il momento di rivolgere l’attenzione verso la strategia dimostrativa, che sarà affrontata con metodo indiretto o per contraddizione.
1. Inizialmente poniamo la questione: a) A ≡ B;
b) A |=Lψ;
c) B #L ψ, cioè B |=L ¬ψ; la proprietà Boole (L), per L regolare, garantisce il passaggio dalla negazione del modello rispetto a un enunciato, alla realiz- zazione della negazione dell’enunciato stesso.
2. Nel lemma 4.0.6 abbiamo dimostrato che il significato di ψ dipende da un numero finito di simboli relazionali. Presa quindi una segnatura finita S0 ⊂ S, e applicato il teorema di Fraïssé sull’equivalenza elementare delle due strutture A e B, per una catena (Iα)α≤ωtroviamo:
a) (Iα)α≤ω: A! S0 ∼=f B! S0; b) A |=Lψ;
c) B |=L ¬ψ;
Il passaggio adesso da compiere: i. Applicare Comp (L) e LoSko (L).
3. Si trovano due strutture numerabili A% e B% per le quali vale: a) A%! S0∼=p B% ! S0;
b) A%|= Lψ; c) B% |=
L¬ψ;
Per il fatto che i modelli A% e B% sono numerabili e che tra di essi sussiste un isomorfismo parziale, segue dal lemma 4.1.2.5 che
A%! S0∼= B% ! S0.
La prima parte della dimostrazione sarà dedicata ai passaggi 2.(a), (b), (c), di cui dovremo fornire una descrizione all’interno di L1 con un numero finito di enunciati. Le due strutture A e B dovranno a loro volta essere inserite all’interno di una sovrastruttura appositamente costruita.
La descrizione dell’isomorfismo nella struttura C
Inizialmente, invece di intraprendere la stesura dell’insieme finito di enunciati che rapp- resenteranno la relazione di isomorfismo finito tra le due strutture A e B, cominciamo considerando la costruzione della struttura che li verifica, in modo da chiarirne gli at- tributi generali. Ma prima ancora è il caso di soffermarci a riflettere che per quanto il nostro lavoro si muova all’interno del sistema logico L1, tanto che tutti gli enunciati imp- iegati da qui in avanti saranno del prim’ordine, la prospettiva di generalità riguardante un sistema logico L qualsiasi non sarà disattesa, e questo grazie alla condizione prelim- inare posta dal teorema per la quale L1 ≤ L; questo significa che ogni risultato raggiunto al prim’ordine vale a fortiori per un sistema logico qualsiasi, potente almeno quanto L. Intervenire sulle possibili divergenze espressive e ritagliare le caratteristiche di L in modo che vadano a coincidere con quella di L1 sarà compito delle sezioni successive; per ora basti intendere che la relazione tra L1 e L comporta per ogni enunciato ϕ ∈ L1(S) l’esistenza di un enunciato corrispettivo ϕ% ∈ L (S), entrambi con gli stessi modelli. Allora, per gli enunciati contenenti tutte le informazioni presenti nelle tre affermazioni
(Iα)α≤ω : A! S0 ∼=f B! S0; A|=Lψ;
B|=L¬ψ;
avremo una struttura C con le seguenti caratteristiche:
" C è una sovrastruttura tale da comprendere sia A che B. " Il dominio di C contiene A e B, posto A ∩ B = 0.10 " C contiene ω, la cui obbligatorietà è legata a In. " C contiene %
n∈N
In, cioè l’unione di n ∈ N isomorfismi parziali.
In più, perché la descrizione sia effettivamente realizzabile, abbiamo bisogno di introdurre nuovi simboli relazionali, in modo da coprire le sopraggiunte esigenze di linguaggio. In- troduciamo così, a partire da Sr
0, un’estensione Sr
+
0 :={U, V, P, <, I, G}, dove i simboli U,V ,P sono relazioni unarie; < e I binarie; G ternaria. Con questo potenziamento è possibile costruire finalmente la S+-struttura C nei particolari.
(a) C = A ∪ B ∪ N ∪ % n∈N
In.
Grazie al fatto che la segnatura è relazionale ed è posto A ∩ B = 0, è possibile tracciare un insieme in modo “intensionale” semplicemente marcando alcuni determinati elementi con un simbolo relazionale, ovvero attribuendo loro una proprietà: ecco il significato dell’introduzione dei due simboli unari U e V , ed ecco il loro ruolo nel generare due sottostrutture di C. Siccome sia A che B fanno riferimento a una segnatura non esposta all’arricchimento lessicale che abbiamo appena incontrato, i due enunciati (b) e (c) si dedicano a precisare il carattere di “ridotti” delle due strutture:
10Porre questa condizione non è necessario, ma semplifica lo svolgimento del teorema senza alterarne la
(b) UC = Ae7UC8C!S = A. (c) VC = Be 7VC8C!S = B.
(d) Le due espressioni <C e fC ! N indicano rispettivamente la relazione d’ordine e la funzione di predecessore, entrambe applicate all’insieme dei naturali.
I tre punti rimanenti hanno invece il compito di inscrivere nella struttura C le basi linguis- tiche per consentire la traduzione lessicale dell’isomorfismo finito tra le due sottostrutture Ae B: (e) PC = % n∈N In. (f) (n, p) ∈ IC sse n ∈ N e p ∈ I n. (g) (p, a, b) ∈ GC sse p ∈ PC e aC ∈ dom!pC" e!pC!aC"= bC". Con PC = % n∈N
In si intende qualificare P come il predicato impiegato per designare l’insieme degli isomorfismi parziali presenti in ogni estensione di I; in (f) si sostiene che pè il simbolo con cui si indica un singolo isomorfismo, accoppiato ad un numero naturale n: viene con tutta evidenza sottolineato che l’intero elemento del linguaggio (n, p) è un isomorfismo solo e soltanto se p (questa volta in quanto ente matematico e non linguis- tico) è un isomorfismo parziale in In; infine con (g) è esposto il grafico dell’isomorfismo, sottoforma di tripla ordinata, che indica come una mappa p ∈ In colleghi un elemento del dominio di A alla sua immagine in B.
Adesso, una volta mostrate le peculiarità di C, possiamo dedicarci alla stesura degli enunciati di descrizione che proprio in C trovano la loro realizzazione:
1. ∀p (P p → ∀x∀y (Gpxy → (Ux ∧ V y))).
2. ∀p (P p → ∀x∀x%∀y∀y%((Gpxy∧ Gpx%y%)→ (x = x% ↔ y = y%))).
3. ∀p (P p → ∀x1. . .∀xn∀y1. . .∀yn((Gpx1y1∧ . . . ∧ Gpxnyn)→ (Rx1. . . xn↔ Ry1. . . yn))).11 4. Gli assiomi della teoria dell’ordinamento parziale;12
∀x (∃y (x < y) → (fx < x ∧ ¬∃z (fx < z ∧ z < x))). 5. ∀x (∃y (x < y ∨ y < x) → ∃p (P p ∧ Ixp)).
6. ∀x∀p∀u ((fx < x ∧ Ixp ∧ Uu) → ∃q∃v (Ifxq ∧ Gquv ∧ ∀x%∀y%(Gpx%y% → Gqx%y%)))(Pro- prietà forth)
7. ∀x∀p∀v ((fx < x ∧ Ixp ∧ V v) → ∃q∃u (Ifxq ∧ Gqvu ∧ ∀x%∀y%(Gpx%y% → Gqx%y%)))(Pro- prietà back).
8. ∃xUx ∧ ∃yV y ∧ ψU∧ ¬ψV.
11Per ogni n ≤ ω e per ogni predicato n-ario R ∈ S 0. 12Cfr. Esempio 1.2.2.2.
I primi tre enunciati sono abbastanza autoesplicativi, comunicano che se p è un isomor- fismo parziale (è quanto in effetti segue da(e)) allora gli elementi segnati con U e V fanno parte della mappatura isomorfa, che a sua volta è rappresentata nella sua completezza dalla relazione G, il cui insieme generato va così a sovrapporsi allo stesso insieme coperto da p. In particolare, il punto 2. si sofferma sul carattere iniettivo della mappatura,13 mentre il punto 3. afferma che l’isomorfismo parziale può lavorare anche all’interno di una segnatura relazionale finita, come quella che noi abbiamo preso in considerazione. In 4., con la presenza degli assiomi dell’ordinamento parziale, si pongono le condizioni per la generazione di un ordinamento non-riflessivo K = (field <, <), il cui dominio f ield < è appunto un campo,14 e a cui, in forza dell’estensione assiomatica provvisoria, con l’inserimento dell’enunciato
∀x (∃y (x < y) → (fx < x ∧ ¬∃z (fx < z ∧ z < x))) viene aggiunta la funzione-predecessore f.
Proseguendo, un modo differente di rendere l’asserzione 5. è il seguente: “se x è nel campo di <, allora Ix = {p|P p ∧ Ixp} $= 0”. In questo modo l’enunciato stabilisce una basilare interdipendenza tra gli elementi dell’ordinamento e gli elementi racchiusi sotto I, che ovviamente sono isomorfismi parziali: come già nel punto (f) sopraelencato, ogni elemento x del campo con predecessore (la premessa ∃y (x < y ∨ y < x) precisa volutamente la condizione d’ordine) concorre ad estendere gli isomorfismi parziali p per Ix.
Sia il punto 6. che il punto 7. offrono una formalizzazione della proprietà back-and-forth, che abbiamo visto rivestire un ruolo prominente nell’individuzione di isomorfismi finiti; in questo caso specifico l’impiego di questi due “assiomi” è necessario per caratterizzare la catena (Iα)α≤ω per i due ridotti di C.
Per ultimo troviamo l’enunciato ∃xUx∧∃yV y∧ψU∧¬ψV. Se fino al punto 7. gli enunciati si sono occupati di descrivere l’isomorfismo finito, in modo tale che l’espressione
(Iα)α≤ω: A! Sr
+
0 ∼=f B! Sr
+
0
assumesse significato all’interno di una struttura portante C per tramite di una de- costruzione nella sintassi logica, con 8. è possibile anche formalizzare la contraddizione rappresentata dalla simultaneità delle due affermazioni
A|=Lψ e B |=L¬ψ.
Creando infine una congiunzione χ di tutti gli enunciati trattati dal numero 1. al numero 8.troviamo:
χ := 1.∧ 2. ∧ 3. ∧ 4. ∧ 5. ∧ 6. ∧ 7. ∧ 8.
13Letteralmente: preso un isomorfismo parziale p e presi quattro elementi qualsiasi nel dominio della
struttura, se la stessa funzione-mappa collega prima una coppie e poi un’altra, allora i due elementi presi dal dominio della mappa sono identici, così come identici sono i due elementi presi dall’insieme- immagine.
14Per “campo” è necessario intendere non la struttura algebrica ma quel particolare insieme per cui ogni
e dunque
C|=Lχ. Il rovesciamento
Prendiamo la serie (Iα)α≤ω : A ! S0 ∼=f B ! S0 come è stata descritta nella sezione precedente. Per la definizione di isomorfismo finito, ogni insieme Ik contiene isomorfismi parziali estendibili k-volte, ovvero da Ik−1 fino a I0. Dalle affermazioni presenti in χ, gli elementi numerici del dominio sono disposti secondo la relazione d’ordine <C, che per comodità e senza rischio di confusione può essere scritta semplicemente come <: quindi per In+1, In, . . . , I0 non abbiamo indici disposti secondo il seguente ordinamento infinito:
0 < 1 < 2 < . . . < n + 1 < . . .
Il lavoro di rovesciamento deve quindi essere realizzato su N, tenendo conto che f è stato introdotto nel linguaggio con lo specifico intento di esprimere la funzione di predecessore f ! N. Facendo agire questa funzione in rapporto all’ordinamento stabilito, possiamo riqualificare il medesimo ordinamento attraverso una nuova espressione, con la differenza che le k-indicizzazioni faranno riferimento, per uno stesso k ≤ ω, a un predecessore in luogo di un successore.
Il passaggio da compiere, per chiarire questo procedimento, comporta innanzitutto un ulteriore intervento sulla segnatura Sr+
0 , che dopo essere stata ridotta a componenti relazionali, validata come insieme finito per mezzo dell’applicazione del lemma 4.1.2.5 e arricchita con 7 nuovi simboli, si estende nuovamente attraverso l’introduzione di un simbolo relazionale unario d, il cui compito linguistico è quello di ricoprire il ruolo di costante non logica;15allora diciamo:
S0r++ := S0r+ ∪ {d}.
La costante appena introdotta rappresenta il perno attorno al quale la serie ordinata vira il suo corso, inteso come verso di progressione. Adesso è possibile costruire una successione infinita di termini:
f0d, f1d, f2d, . . .16 e impostare la serie, evidentemente infinita,
. . . fn+1d < fnd < . . . < f2d < f1d < f0d.
Dal momento che il nostro obiettivo è di giungere a concentrare il contenuto dell’asserzione in un singolo enunciato, siamo in grado di aggirare l’ostacolo dell’infinità andando a definire il seguente insieme:
15Deve essere letto come una relazione che simula i modi di una funzione di arietà 0. 16Dove f0d = d; f1d = f d;f2d = f f d; e così via.
O :=#fn+1d < fnd|n ≤ ω$.
Volgiamoci adesso verso il contesto strutturale e integriamo questo insieme di enunciati alla realizzazione modellistica avviata con la costruzione di C, subordinando l’insieme O ad un nuovo insieme che contenga anche l’enunciato congiunto χ:
Υ :={χ} ∪ O = {χ} ∪#fn+1d < fnd|n ≤ ω$.
Successivamente, se notiamo che ogni sottoinsieme finito di O propone e mantiene la relazione d’ordine tra due elementi, ne deduciamo che ogni sottoinsieme di O è soddis- facibile, e che il ruolo che in questo ambito è ricoperto da d è quello di indicare nel do- minio il numero più alto collegabile a (Iα)α≤ω di un qualsiasi sottoinsieme finito estratto da #fn+1d < fnd|n ≤ ω$. Siccome dunque ogni sottoinsieme di O è soddisfacibile, per mezzo dell’applicazione della proprietà Comp (L) giungiamo a dichiarare la soddisfaci- bilità dell’intero insieme #fn+1d < fnd|n ≤ ω$, e conseguentemente la soddisfacibilità di Υ. A questo punto siamo in grado di presentare un’appropriata estensione di C, che chiamiamo D, in modo tale che sia modello dell’insieme Υ. Questo modello sarà fatto in un modo molto semplice, dal momento che l’unico elemento di differenza tra le due strutture è costituito dall’estraneità della costante d alla segnatura di riferimento per C: il suo assorbimento nei piani della nuova struttura è un’operazione che può risolversi semplicemente associando all’elemento linguistico d quell’elemento di N17 indicato con dC, attraverso la funzione di designazione di C. Nella struttura D cambia unicamente la funzione di designazione, che però restituisce lo stesso risultato, ovvero dC = dD. Partendo dunque da dD, in D si trova la seguente catena, ordinata secondo la funzione di predecesore:
. . . (fnd)D <!fn−1d"D. . . <!f1d"D < dD. Il modello numerabile E
Ciò di cui adesso abbiamo bisogno è una struttura che sia modello di Υ e al contempo sia numerabile. Siamo portati a interpellare quasi automaticamente la proprietà L¨oSko (L), che finalmente può essere introdotta ed utilizzata, andando così a completare il quadro prospettico iniziale del teorema, con tutte le premesse finalmente operative.
Giunti però alle soglie di quest’ultimo passo, sorge il problema della valutazione delle condizioni di applivabilità di L¨oSko (L) in base a quanto raggiunto finora: sebbene i movimenti di riduzione e le architetture strutturali non ci abbiano condotto al di fuori del sistema logico oggetto di trattazione, ci troviamo adesso al cospetto di un modello per un insieme infinito di enunciati, ovvero
. . . (fnd)D <!fn−1d"D. . . <!f1d"D < dD,
mentre L¨oSko (L) è applicabile unicamente su enunciati presi singolarmente. È perciò evidente che dobbiamo ricercare il metodo per convertire l’intero contenuto di Υ, ma in particolare di#fn+1d < fnd|n ≤ ω$, in un singolo enunciato.
Ampliamo dunque la segnatura Sr++
0 con l’aggiunta di un nuovo simbolo relazionale unario Q per ottenere
S0r+++ := S0r++∪ {Q}.
Sfruttando poi Boole (L), andiamo a formulare l’enunciato in L: χ1:= Qd∧ ∀x (fx < x ∧ Qfx).
Questo nuovo enunciato ci dice che Q, in quanto individua un insieme, contiene l’elemento segnato da d, e così pure la serie di tutti gli elementi ordinati per mezzo della funzione- predecessore f. Adesso, opportunamente riutilizzando Boole (L), possiamo scrivere:
ϑ := χ∧ χ1, che replica esattamente il contenuto di Υ.
Come già accaduto nella sezione precedente, in merito alla reinterpretazione a partire da C di un nuovo elemento aggiunto alla segnatura, anche adesso la presenza attiva del simbolo relazionale Q domanda chiaramente una modifica strutturale a partire questa volta da D. Si introduce pertanto con D% una nuova struttura tale che dom (D) = dom (D%)e tale che la sua funzione di interpretazione riservi per Q il seguente significato:
QD" :=&(fnd)D"
|n ∈ N'.
Per ricordare a questo punto come è composta D%, la scriviamo esplicitandone il con- tenuto:
D%=5C, dD, QD"6.
Si può ben rimarcare come si è giunti a D% partendo da C e dal suo dominio rimasto inal- terato, e andando poi ad aggiungere per i simboli d e Q due interpretazioni adeguatamente selezionate. Osservare la struttura D% in forma chiara ed estesa ci persuade del fatto che ci troviamo di fronte a un modello di ϑ:
D% |=Lχ∧ χ1,
e che, per un secondo utilizzo di L¨oSko (L), troviamo un modello numerabile, denominato E, tale che:
E|=Lχ∧ χ1.
∃xUx ∧ ∃yV y ∧ ψU∧ ¬ψV,
che garantisce la presenza di almeno un elemento nei due sottoinsiemi UE e VE.18 Da questi due sottoinsiemi siamo allora in grado di riproporre le due sottostrutture A% e B%, definite rispetto alla segnatura iniziale come tali:
A%:=7UE8E!S
B% :=7VE8E!S
Vediamo allora di verificare che in effetti valga quanto dichiarato al punto 3. (a) della sezione introduttiva, ovvero: I : A% ! S0 ∼=pB% ! S0.
Recuperiamo da χ i seguenti enunciati: 1. ∀p (P p → ∀x∀y (Gpxy → (Ux ∧ V y))).
2. ∀p (P p → ∀x∀x%∀y∀y%((Gpxy∧ Gpx%y%)→ (x = x% ↔ y = y%))).
3. ∀p (P p → ∀x1. . .∀xn∀y1. . .∀yn((Gpx1y1∧ . . . ∧ Gpxnyn)→ (Rx1. . . xn↔ Ry1. . . yn))).19 4. ∀x (∃y (x < y ∨ y < x) → ∃p (P p ∧ Ixp)).
5. ∀x∀p∀u ((fx < x ∧ Ixp ∧ Uu) → ∃q∃v (Ifxq ∧ Gquv ∧ ∀x%∀y%(Gpx%y% → Gqx%y%))). 6. ∀x∀p∀v ((fx < x ∧ Ixp ∧ V v) → ∃q∃u (Ifxq ∧ Gqvu ∧ ∀x%∀y%(Gpx%y% → Gqx%y%))). Per quanto concerne gli enunciati 1. − 3., e dato p ∈ PE un isomorfismo parziale da A% ! S0 a B% ! S0, definiamo l’elemento en come (fnd)E.20 Dal momento che vale !
C, cE, QE" |=L χ1, per dE = dD e QE = QD", allora en∈ QE per ogni n ≤ ω, e con en viene indicata una catena in ordine discendente:
. . . < en< en−1< . . . < e2< e1 < e0,
dove anche la relazione <, che più propriamente dovrebbe presentare la scrittura <E, rimane un ordinamento per E.
Definiamo adesso l’insieme∧IE: ∧
IE :=#pE|∃n ≤ ω : (en, p)∈ IE$.
18UE e VE vengono evidentemente mutuati da UC e VC, senza discontinuità. 19Per ogni n ∈ N e per ogni predicato n-ario R ∈ S
0.
20Ricordiamo che la funzione di designazione per una struttura, che in questo caso è E, è definita
propriamente solo per costanti non logiche, ed è estendibile all’insieme dei termini nel modo canonico: (fnd)E= (f )E#!fn−1d"E$
La condizione dell’insieme ∧IE, stabilisce un nesso, relativamente a E, con il punto (f) incontrato durante la caratterizzazione di C. Pertanto, facendo valere gli enunciati 4., 5., 6.dell’elenco, abbiamo la certezza che l’insieme ∧IE non sia vuoto e che per esso valga la proprietà back-and-forth, che potrebbe essere verificato così:
" (Forth) Se (en, p)∈ IE e a ∈ dom (A%) = A% = UE, allora esiste (en+1, q)∈ IE tale che q estende p e a ∈ dom (q).
" (Back) Se (en, p)∈ IE e b ∈ rg (B%) = B% = VE, allora esiste (en+1, q)∈ IE tale che q estende p e b ∈ rg (q).
Per completare, scriviamo: ∧
IE : A%! S0∼=p B% ! S0; ma per l’equivalenza di∧IE con IC:
I : A% ! S0 ∼=pB% ! S0, che è l’isomorfismo parziale che stavamo cercando.
Dobbiamo ancora mostrare come le due sottostrutture A% e B% entrino in contraddizione sull’enunciato ψ. Prendiamo quindi il modello E e scriviamo:
E|=LψU E|=L¬ψV
Queste due affermazioni, grazie alla proprietà Rel (L), che si appella alla natura re- lazionale della segnatura, diventano:
A%|=Lψ B% |=L¬ψ
Adesso l’intero punto 3. presentato nell’introduzione è stato dimostrato; dalla contrad- dizione ricavata possiamo effettiamente dichiarare che
per tutte le Sr-strutture relazionali Ar e Br, se Ar≡ Br, allora Ar≡ LBr, da cui:
L1∼ L.
[1] Barwise J. (a cura di), Handbook of Mathematical Logic, North Holland, 1982. [2] Barwise J. e Feferman S. (a cura di), Model-Theoretic Logics, Springer-Verlag, New
York 1985.
[3] Boolos G. S., Burgess J. P. e Jeffrey R. C., Computabiliy and Logic, Cambridge University Press, Cambridge 2010.
[4] Chang C. C., Keisler H., Model Theory, Dover Publications, 2012.
[5] Della Chiara Scabia M. L., Logica, Enciclopedia Filosofica ISEDI, Milano 1974. [6] Di Martino P., Algebra, Edizioni PLUS - Università di Pisa, Pisa 2003.
[7] Ebbinghaus H.-D., Flum J., Finite Model Theory, Springer-Verlag, New York 1999. [8] Ebbinghaus H.-D., Flum J. e Thomas W., Mathematical Logic, Springer-Verlag, New
York 1984.
[9] Fraïssé R., Cours de Logique Mathématique, Paris, Gauthier-Villars Éditeur, 3 vol., 1971-1975.
[10] Gabbay D., Günthner F. (a cura di), Handbook of Philosophical Logic, 1 vol., El- ements of Classical Logic, Kluwer Academic Bublishes Dordrecht, Boston, London 1994.
[11] Herstein I. N., Algebra, Editori Riuniti, Roma 2003.
[12] Hodges W., Model Theory, Cambridge University Press, 1993.
[13] Hodges W., «Model Theory». http://wilfridhodges.co.uk/history07.pdf
[14] Hunter G., Metalogic: An Introduction to the Metatheory of Standard First Order Logic, Univeristy of California Press, Berkeley 1996.
[15] Libkin L., Elements of Finite Model Theory, Springer-Verlag, Berlin 2004.
[16] Lindström P., First Order Logic, Philosophical Communication Web Series 36 Göte- borg, Sweden, 2006. http://www.phil.gu.se/posters/first-order-logic.pdf
[18] Mariani M., Marletti C. e Moriconi E., Argomenti di Logica, Edizioni PLUS - Pisa University Press, Pisa 2009.
[19] Otto M., «Finite Model Theory». http://www.karlin.mff.cuni.cz/~krajicek/otto.pdf
[20] Rossberg M., «First-Order Logic, Second-Order Logic
and Completeness», University of St. Andrews.
http://homepages.uconn.edu/~mar08022/papers/RossbergCompleteness.pdf [21] Simpson S. G., Mathematical Logic, Pennsylvania State University Press, 2013.
http://www.math.psu.edu/simpson/courses/math557/logic.pdf
[22] Stegmüller W., Varga M. (col contributo di), Strukturtypen der Logik, 3 vol., Springer-Verlag, Berlin 1984.
[23] Väänänen J., «A Short Course on Finite Model The-
ory», Department of Mathematics, University of Helsinki.
http://www.math.helsinki.fi/logic/people/jouko.vaananen/shortcourse.pdf