1.3 Il teorema di Beth (1953), Craig (1957)
2.1.2 Corrispondenze tra strutture
Valga per i teoremi che seguono la circoscrizione dell’ambiente tematico attorno a due strutture A e B, entrambe modellate su un linguaggio L del prim’ordine a segnatura relazionale. Seguono quasi immediatamente dalle definizioni di isomorfismo e di strutture parzialmente isomorfe e finitamente isomorfe tre proprietà:
" Se A ∼= B, allora I : A ∼=p B. " Se A ∼= B, allora A ∼=f B. " Se I : A ∼=pB, allora A ∼=f B.
Per giustificarle basta notare che, nel primo caso, se f : A ∼= B, allora I : A ∼=p B per I ={f}; nel terzo caso, se I : A ∼=p Ballora (In)α≤ω: A ∼=f Be ∀n : In= I. Il secondo caso segue ovviamente dagli altri due.
Si può anche notare come le precedenti affermazioni indichino un rapporto intuitiva- mente evidente: dall’isomorfismo “completo” all’isomorfismo cosiddetto finito vengono at- traversati tre gradi di restrizione decrescente, per cui due strutture isomorfe mostreranno
una somiglianza formale pervasiva, mentre i due isomorfismi “derivati” individueranno tra due strutture gradi di somiglianza formale sempre più limitati.
Più interessanti sono le relazioni che giocano con le cardinalità delle strutture e con il loro rapporto con l’equivalenza elementare; qui di seguito ne presentiamo alcune tra i più rilevanti:
2.1.2.1 Teorema
“Sia I : A ∼=pBcon A e B modelli al massimo numerabili, allora A ∼= B.”
Dimostrazione. Sia I : A ∼=p B e siano A = {a1, a2, . . .}, B = {b1, b2, . . .} due enumer- azioni senza ripetizioni degli elementi di A e di B, dove card (A) ∪ card (B) ≤ ℵ0. Prendiamo, per la definizione di isomorfismo parziale, una qualsiasi mappa pi ∈ I : pi(a1) = b1; siano poi pi+1, pi+2, . . . le estensioni di pi in I, organizzate in modo da produrre una distribuzione degli elementi di A e di B attraverso i successivi passaggi:
Passo 1. a1 ∈ dom (p1), posto convenzionalmente i = 0; Passo 2. b1 ∈ im (p2);
Passo 3. a2 ∈ dom (p3); Passo 4. b2 ∈ im (p4); ...
Si evince fin da subito come il procedimento possa essere generalizzabile a tutti gli elementi di A e di B e a tutte le funzioni in I:
" per n = 2m + 1, sia am∈ dom (pn); " per n = 2m + 2, sia bm ∈ im (pn).
Adesso, siccome ogni elemento a ∈ A si trova nel dominio della sequenza p0 ⊂ p1 ⊂ p2⊂ . . . e ogni elemento b ∈ B è nell’immagine di p0 ⊂ p1 ⊂ p2 ⊂ . . ., allora la relazione tra Ae B è un isomorfismo, per cui possiamo scrivere: A ∼= B.
q.e.d. Un altro modo per esporre la questione fondamentale del teorema è dire che, presi A e B domini dei modelli A e B, e presi Ai e Bi sottoinsiemi propri qualsiasi di A e B, si dà una sequenza di isomorfismi parziali pi : Ai +→ Bi in modo che p1 ⊆ p2 ⊆ . . . e tale che p, posta p := %
i∈N
pi come l’unione di tutti gli isomorfismi parziali pi, mantenga la relazione tra gli elementi dei due domini. Allora ogni pi è un isomorfismo parziale, e la sequenza è costruita in modo tale che l’unione di tutti gli Ai produca A, mentre l’unione di tutti i Bi produca B. Pertanto, con la definizione di p sarà ottenuta la corrispondenza biunivoca tra A e B.
Il teorema 2.1.2.1 è inoltre interpretabile come una versione semplificata del teorema di Cantor (1895), dal quale venga estratta la procedura dimostrativa. Il teorema di Cantor, vale la pena ricordare, rappresenta la prima applicazione del metodo back-and-forth e dimostra che la teoria dell’ordine lineare denso aperto (cioè senza massimo né minimo)
è categorica alla potenza ℵ0,7 e non vale se applicato al caso delle strutture più che numerabili: un esempio di ordini lineari densi aperti non isomorfi, della stessa cardinalità ℵα, per 1 ≤ α, può essere trovato prendendo un numero ℵα di copie dell’insieme dei razionali e ordinandole secondo l’ordine di ℵα.
Per concludere, è possibile trovare strutture non isomorfe ma parzialmente isomorfe con la stessa cardinalità (per esempio (R, ≤) e (R + Q, ≤)), ma le strutture parzialmente isomorfe e di cardinalità numerabile, come abbiamo visto, devono essere necessariamente anche isomorfe.
2.1.2.2 Teorema
“Se A ∼=f Be A contiene esattamente n elementi , allora A ∼= B.”
Dimostrazione. Sia (Iα)α≤ω : A ∼=f B, e supponiamo che il dominio di A sia finito, ponendo A = {a1, . . . , an}. Prendiamo un isomorfismo parziale p ∈ In+1 in modo tale che, applicando per n-volte la proprietà forth, troviamo un isomorfismo p1 ∈ I1 nel cui dominio sono contenuti tutti gli elementi a1, . . . , andi A, ovvero A stesso. Se l’immagine di p1 non combaciasse con B, e cioè tra A e B non fosse in alcun modo definibile una mappatura isomorfa, allora sarebbe individuabile un elemento b appartenente al dominio di B ma non all’immagine di p1, e quindi per la proprietà back (anch’essa inscritta nell’ipotesi A ∼=f B) esisterebbe un isomorfismo parziale p∗1 tale che p∗1 ⊃ p1, con b ∈ im (p∗
1). Ma dal momento che il dominio di p1 coincide con quello di A, non esisterà alcun elemento b ∈ B non già nell’immagine di p1, e dunque possiamo concludere che la funzione p1 definisce un isomorfismo tra A e B.
q.e.d. 2.1.2.3 Teorema
“Se A ≡ B e A è un modello finito, allora A ∼= B.”
Dimostrazione. Assumiamo che A ≡ B con A = {a1, . . . , an}.
Sia ψ = ∃!nx l’enunciato il cui contenuto esprime l’esistenza in una data struttura di un numero determinato di individui, precisamente n elementi. Ora, in A, essendo il suo dominio costituito proprio da n individui, l’enunciato ψ è verificato, e per l’ipotesi di equivalenza elementare possiamo affermare anche la validità della seguente espressione:
A|= ∃!nx sse B |= ∃!nx.
Essendo il riferimento dell’enunciato indirizzato verso elementi del dominio, si conclude che A e B hanno la stessa cardinalità, e scriviamo B = {b1, . . . , bn} per indicare il numero finito di elementi di B.
7Brevemente, un ordine lineare denso aperto (senza massimo né minimo) è ottenuto da un ordine lineare
con l’aggiunta di due assiomi:
1. ∀x∀y∃z ((x ≤ y ∧ x &= y) → (x ≤ z ∧ z &= x ∧ z ≤ y ∧ z &= y)); 2. ∃x∃y (y ≤ x ∧ x &= y).
Se dunque A e B contengono lo stesso numero di elementi, per trovare una funzione iso- morfa tra i due modelli dovremo considerare l’insieme delle funzioni biunivoche tracciabili tra A e B. Per ragioni combinatorie (l’elemento a1 può essere accoppiato con n elementi, l’elemento a2 con n − 1 elementi, etc.), vi sono n! possibili istanze di funzione biunivoca tra i domini delle due strutture; se procediamo per assurdo e ipotizziamo A % B, al- lora per ogni funzione biunivoca tra le n! possibili individuate, diciamo hi : A+→ B con 1 ≤ i ≤ n!, esisterà almeno una formula atomica (oppure, equivalentemente, una sua negazione) ϕhi tale che
A|= ϕhi(a1, . . . , an) ma B # ϕhi(hi(a1) , . . . , hi(an)).
Si costruisca quindi un enunciato che dichiari esplicitamente l’esistenza di n-elementi e in più asserisca la validità di ϕhi per ogni caso di i : 1 ≤ i ≤ n! attraverso la scrittura
∃x1. . .∃xn(x1$= x2∧ . . . ∧ x1$= xn∧ . . . ∧ xn−1 $= xn∧ ϕh1∧ . . . ∧ ϕhn!),
allora la porzione di enunciato che afferma la validità di ϕh1, . . . , ϕhn! è assicurata dalla
costruzione di A, mentre nel caso di B troviamo che B # (ϕh1∧ . . . ∧ ϕhn!); ma questo
fatto è in contraddizione con l’assunto iniziale A ≡ B, da cui allora possiamo dedurre A ∼= B.
q.e.d. 2.1.2.4 Lemma
“Due S-modelli qualsiasi A e B di una teoria T ⊂ LS
0 sono elementarmente equivalenti sse T è completa.”
Dimostrazione. Supponiamo prima che T sia completa, e siano A e B due modelli per T e ϕ ∈ LS0; segue da definizione che ϕ ∈ T oppure ¬ϕ ∈ T . Nel caso ϕ ∈ T , allora A|= ϕ e B |= ϕ oppure A # ϕ e B # ϕ. Avendo preso ϕ come un enunciato qualsiasi, si conclude che A ≡ B.
Siano adesso A e B due modelli elementarmente equivalenti di T e sia ϕ ∈ LS 0 un enunciato qualsiasi. Se A |= ϕ allora B |= ϕ per ogni B modello di T , e quindi T |= ϕ, cioè ϕ ∈ T . Se invece A # ϕ, allora A |= ¬ϕ e B |= ¬ϕ per ogni modello B di T , pertanto T |= ¬ϕ, da cui ¬ϕ ∈ T ; ovvero T è completa.
q.e.d.
2.2 Il teorema di Fraïssé (1953)
Il teorema di Fraïssé offre un metodo efficace per comparare due L-strutture prescindendo dal riferitmento diretto ai linguaggi del prim’ordine. La necessità di ricorrere a strumenti strutturali è innescata dalla intrinseca difficoltà di fornire esempi e di analizzare due
modelli di cui si vuole appurare la capacità di verificare le stesse formule. In effetti il problema di operare una verifica diretta sorge anche ad un livello basilare, per le strutture più semplici. Si prenda per esempio il caso della struttura Zan, ovvero la struttura per i numeri interi nel linguaggio degli anelli,8 e con T h (Zan)sia indicata la teoria dei numeri; è evidente che per approfondire T h (Zan) dovremmo essere in grado di conoscere tutti i teoremi della teoria dei numeri. Data l’impossibilità del compito, non saremmo nemmeno in grado di individuare, partendo da T h (Zan), una struttura A tale che: A ≡ Zan.
Un’applicazione positiva è rappresentata invece dal seguente risultato: siano (R, <) e (Q, <) due ordini lineari densi, allora per il teorema di Fraïssé essi sono elementarmente equivalenti, in quanto I : (R, <) ∼=p (Q, <) =⇒ (R, <) ∼=f (Q, <) per (Iα)α≤ω.
La dimostrazione che segue verrà scomposta in due sotto-teoremi distinti, il primo dei quali partirà dall’isomorfismo finito per arrivare all’equivalenza elementare, mentre il secondo compirà il percorso inverso.
2.2.0.5 Definizione
Date due L-strutture A e B e n ∈ N, scriviamo A ≡n B e diciamo che A e B sono n-equivalenti sse A e B verificano gli stessi enunciati ϕ con qr (ϕ) ≤ n.
Con la definizione 2.2.0.4, insieme alla definizione 2.1.0.3, possiamo impostare il teorema di Fraïssé mettendo in risalto le due seguenti asserzioni:
1. ∀n : A ∼=α Bsse A ≡nB. 2. A ∼=f Bsse A ≡ B.
Queste due espressioni sono equivalenti, con la seconda che segue direttamente dalla prima. La dimostrazione si occuperà di provare dapprima ∀n : A ∼=α B ⇒ A ≡n B e successivamente A ≡ B ⇒ A ∼=f B.
2.2.0.6 Teorema (Fraïssé)
“Sia dato ∀n : A ∼=α B, per A e B L-strutture; allora, per ogni enunciato ϕ ∈ FrS, se: qr (ϕ)≤ n;
p∈ In;
8Affermazione legittima, perché se è vero che la teoria dei numeri riguarda le proprietà generali dei nu-
meri interi, la si può altrettanto considerare come uno studio sulle estensioni strutturali che riguardano gli interi; in altre parole, una struttura algebrica della forma Z = (Z, a, b, #, $), dove a e b sono caratteri speciali che simulano il comportamento di 0 e di 1 nei confronti di due operazioni, #, $, generalmente intese come somma e moltiplicazione, è un anello (possibilmente commutativo) dei nu- meri interi che è in grado di esprimere l’intera teoria dei numeri. Detto in altri termini ancora, in Z è sempre possibile rispondere alla seguente domanda: dato un polinomio
f (x, y) = a0,0+ a1,0x + a0,1y + a2,0x2+ a1,1xy + a0,2y2+ . . .,
a1, . . . , ar∈ dom (p);
si avrà che le due strutture A e B sono n-equivalenti, ovvero:
A|= ϕ (a1, . . . , ar)sse B |= ϕ (p (a1) , . . . , p (ar)).”
Dimostrazione. La dimostrazione sarà compiuta per induzione sulla complessità di ϕ, tenendo conto che per il caso “base”, ovvero il caso che riguarda ϕ formula atomica, la prova è già stata affrontata nel lemma 2.1.0.10. Inoltre, verrà considerato un sistema di connettivi vero-funzionali che sia completo e che includa, oltre alla negazione {¬}, la disgiunzione {∨}.9
1) Se ϕ = ¬ψ, allora:
A|= ϕ (a1, . . . , ar) sse A # ψ (a1, . . . , ar), per definizione di soddisfacibilità.
A# ψ (a1, . . . , ar) sse B # ψ (p (a1) , . . . , p (ar)),
per ipotesi induttiva, grazie alla considerazione che ψ è meno complessa di ϕ. Ora, nuovamente per soddisfacibilità, come anche per l’ipotesi iniziale, avremo:
B# ψ (p (a1) , . . . , p (ar))sse B |= ϕ (p (a1) , . . . , p (ar)). 2) Se ϕ = (ψ ∨ χ), allora:
A|= ϕ (a1, . . . , ar) sse A |= ψ (a1, . . . , ar) oppure A |= χ (a1, . . . , ar), per soddisfacibilità. Per ipotesi induttiva, invece:
A|= ψ (a1, . . . , ar) oppure A |= χ (a1, . . . , ar) sse B |= ψ (p (a1) , . . . , p (ar))oppure B|= χ (p (a1) , . . . , p (ar)).
Da cui, ancora per soddisfacibilità:
B|= ψ (p (a1) , . . . , p (ar))oppure B |= χ (p (a1) , . . . , p (ar))sse B|= (ψ ∨ χ) (p (a1) , . . . , p (ar)),
cioè:
B|= ϕ (p (a1) , . . . , p (ar)).
3) Si consideri adesso il caso ϕ = ∃xψ (x). Dal momento che ϕ ∈ FS
r, dove vl (ϕ) ⊆ {x1, . . . , xr}, procediamo prendendo una vari- abile x /∈ vl (ϕ). Per effetto della presenza del quantificatore esistenziale, possiamo far ricadere la variabile x sotto il suo campo e, per distinguerla dalle altre variabili apparte- nenti all’insieme vl (ϕ), la indichiamo come xr+1. La scrittura corrispondente è data da: ∃xr+1ψ (xr+1), che troviamo ammissibile in quanto la variabile quantificata non compare libera all’interno della stessa formula. Vediamo allora che
A|= ϕ (a1, . . . , an) sse A |= ψ (a1, . . . , ar, ar+1).
La valutazione sulla complessità della formula ϕ = ∃xr+1ψ (xr+1) può essere condotta a partire dall’utilizzo del quantifier rank: se ne deduce che, se qr (∃xr+1ψ (xr+1))≤ n, allora -per la definizione stessa di quantifier rank- abbiamo che qr (ψ (xr+1)) < n. Raggiungiamo la conclusione della dimostrazione attraverso i due seguenti passaggi:
1. Utilizziamo il metodo forth e troviamo per l’elemento ar+1∈ A un’estensione q ⊃ p tale che p ∈ In; q ∈ In−1; con ar+1 ∈ dom (q), in modo che A |= ψ (a1, . . . , ar, ar+1); per ipotesi induttiva lo stesso procedimento è applicabile all’intera equivalenza elementare che vogliamo dimostrare, e quindi esisterà un elemento ar+1 ∈ A e un isomorfismo parziale q ∈ In−1 tale che q ⊃ p, ar+1 ∈ dom (q) e B |= ψ (p (a1) , . . . , p (ar) , q (ar+1)).
2. Utilizziamo il metodo back e troviamo per un elemento b ∈ B un’estensione q ⊃ p tale che p ∈ In; q ∈ In−1; e br+1 ∈ im (q), in modo che B |= ψ (p (a1) , . . . , p (ar) , br+1). Possiamo concludere, avendo posto l’equazione ϕ = ∃xr+1ψ (xr+1), che
B|= ϕ (p (a1) , . . . , p (ar)), e dunque il teorema è dimostrato.
q.e.d. Come conseguenza delle osservazioni culminate nello sviluppo dei contenuti del lemma 2.1.1.6 e del lemma 2.1.1.7, ci occupiamo della dimostrazione dell’implicazione inversa del teorema di Fraïssé.
2.2.0.7 Teorema (Fraïssé) “Date due L-strutture A e B;
se A ≡ B, allora A ∼=f B.”
Dimostrazione. Sia A ≡ B. Definiamo In come l’insieme degli isomorfismi parziali tali che p ∈ In sse p ∈ P art (A, B) e per r ∈ N, sia {a1, . . . , ar} ∈ A e il dominio di p coincida esattamente con {a1, . . . , ar}, in modo tale che per tutte le formule ϕ ∈ FrS con qr (ϕ) ≤ n valga che A |= ϕ (a1, . . . , ar) sse B |= ϕ (p (a1) , . . . , p (ar)). Si tratterà
di mostrare allora come l’insieme In sia estendibile attraverso la proprietà back-and- forth individuando opportunamente una catena (In)n≤α: A ∼=α B. Nel procedere con la dimostrazione ci occuperemo soltanto di verficare la validità della proprietà forth, giacché la dimostrazione della proprietà back ricalca i passaggi di quest’ultima.
(Forth property) Sia p ∈ In+1, ar+1 ∈ A e dom (p) = {a1, . . . , ar}. Come stabilito nel lemma 2.1.1.7 possiamo prendere formule in numero finito, diciamo ψ1, . . . , ψk ∈ Fr+1S con qr (ψi)≤ n, in modo che una qualsiasi formula presa da Fr+1S possa essere riscritta come una formula ψi. Da quanto detto deduciamo che, per ogni ψi∈ {ψ1, . . . , ψk}:
" Se A |= ψi(a1, . . . , ar, ar+1), scriviamo ϕi := ψi; " Se A |= ¬ψi(a1, . . . , ar, ar+1), scriviamo ϕi :=¬ψi.
In entrambi i casi, sia ϕi = (ψi∨ ¬ψi), e dunque A |= (ϕ1, . . . , ϕk) (a1, . . . , ar, ar+1). Procediamo allora come segue:
A|= (ϕ1∧ . . . ∧ ϕk) (a1, . . . , ar, ar+1) ↓ A|= ∃xr+1(ϕ1∧ . . . ∧ ϕk) (a1, . . . , ar). Siccome qr (∃xr+1(ϕ1, . . . , ϕk))≤ n + 1, e p ∈ In+1: B|= ∃xr+1(ϕ1∧ . . . ∧ ϕk) (p (a1) , . . . , p (ar)) ↓ B|= (ϕ1∧ . . . ∧ ϕk) (p (a1) , . . . , p (ar) , br+1),
in A e in B vengono cioè soddisfatte le stesse formule ϕi con qr (ϕi) ≤ n, rispettiva- mente da (a1, . . . , ar, ar+1)e da (p (a1) , . . . , p (ar) , br+1); allora, per ar+1∈ A e br+1 ∈ B, esiste un’estensione p%di p che è un isomorfismo parziale tale che ar+1 ∈ dom (p%)e p%∈ In. Infine, ci possiamo convincere che ogni Inpresenta almeno una mappa: dal momento che A≡ B, gli stessi enunciati con quantifier rank ≤ n valgono sia in A che in B e pertanto anche la mappa p = ∅ si trova in In.
q.e.d. 2.2.0.8 Osservazione
Certamente l’ausipicio di Alfred Tarski, che in una conferenza a Princeton del 1946 im- maginava che la nozione di equivalenza elementare si sarebbe finalmente mostrata più comprensibile una volta resa prossima ad una nozione strutturalmente profonda come quella di isomorfismo (Tarski, 1946), è stato raccolto ed esaudito da Fraïssé, il quale, come abbiamo visto, nella sua tesi di dottorato arrivò a dimostrare che una condizione necessaria e sufficiente che implichi l’esistenza di una qualsiasi equivalenza elementare è
in effetti individuabile. Dal punto di vista della teoria dei modelli, un tale risultato cor- risponde all’avvicinamento dei due metodi basilari utilizzati per analizzare e confrontare tra di loro le strutture, ovvero quello che vuole e deve passare attraverso il linguaggio della logica, e quello che invece ha come uniche risorse le strutture stesse e alcune op- erazioni matematiche. Questo fatto si ripercuote direttamente sulla valutazione delle distanze che intercorrono tra le due classi di strutture descritte rispettivamente dalle relazioni di isomorfismo e di equivalenza elementare:10 per ogni L-struttura A sappiamo che è sempre possibile scrivere {B|A ∼= B} ⊆ {B|A ≡ B}, e cioè che ogni isomorfismo, a prescindere dal tipo di struttura in oggetto, implica un’equivalenza elementare, con la precisazione che {B|A ∼= B} ⊂ {B|A ≡ B} nel caso in cui dom (A) sia infinito, e {B|A ∼= B} = {B|A ≡ B} nel caso in cui dom (A) sia finito.11 Ma una caratterizzazione che valesse in generale, fino al teorema di Fraïssé non era stata guadagnata: in un certo senso, questa nuova classe di equivalenza perfettamente ritagliata su quella generata dall’equivalenza elementare riesce a interpretare le qualità logiche di quest’ultima, come se ne esponesse gli ingranaggi di funzionamento; del resto, è certo che le motivazioni del matematico franco-algerino fossero puramente modellistiche, e questa incombenza del “metodo semantico” altro non fa che rafforzare una convinzione che pare aver guidato l’intero suo lavoro di logico, ovvero che lo sviluppo e la maturazione della logica siano percorribili unicamente attraverso un assorbimento progressivo del metodo sintattico da parte della teoria dei modelli.12
2.3 Giochi di Ehrenfeucht
Al teorema di Fraïssé manca la componente intuitiva e la facilità applicativa che invece è possibile considerare grazie ai giochi del logico polacco Ehrenfeucht. I giochi sono stati creati per garantire versatilità ed immediatezza all’artificio algebrico che caratterizza il metodo di comparazione tra due strutture, ovvero il metodo back-and-forth. Provved- eremo inizialmente a fornire una descrizione discorsiva del funzionamento dei giochi che risulti sostenibile per qualsiasi tipologia di struttura si voglia prendere in considerazione; in seguito andremo a dimostrare un teorema il cui contributo principale è di accertare l’equivalenza tra il metodo appena presentato e quello più strettamente algebrico ben delineato nel teorema di Fraïssé. Nella transizione tra queste due fasi incontreremo la nozione di strategia vincente, che sarà evidenziata nel modo più chiaro possibile esempli- ficando alcune ipotetiche partite condotte su grafi matematici senza perdita di generalità alcuna, in quanto il gioco vale per due qualsiasi strutture costruite a partire da un linguag- gio del prim’ordine con segnatura finita; quest’ultimo passaggio sarà poi l’occasione per collegarci ad una rapida considerazione sulla teoria dei modelli finiti, e alla valutazione critica di alcuni risultati che la distanziano dalla logica elementare classica.
10Sia ∼=che ≡ sono ovviamente relazioni di equivalenza sulla classe delle strutture. 11Cfr. 2.1.2.3.
12“...selon lui, l’avancement de la logique se traduit par une absorption croissante de la syntaxe par la
2.3.0.9 Definizione
Data un segnatura S = {E}, con E simbolo relazionale binario, un grafo è una E- struttura G =!G, EG" che soddisfa la simmetria ma non soddisfa la proprietà riflessiva:
1. Per ogni ai ∈ G, non vale EGaiai;
2. Per ogni ai ∈ G, e per ogni bj ∈ G, se EGaibj allora EGbjai.
L’insieme G è composto da elementi detti vertici oppure nodi, mentre le coppie di vertici che cadono sotto EG vengono chiamate spigoli (edges).
" Un grafo può essere orientato in caso non valga la proprietà simmetrica; allora, per distinguere la natura differente delle coppie ordinate, gli elementi di EG si dicono archi (arcs).
" Un sottoinsieme di G: X ⊂ G, è detto una clique se EGa, bper ogni a, b ∈ X con a$= b.
" Sia G un grafo orientato. Se n ≥ 1, per n ∈ N, e EGa1, a2, . . . , EGan−1an
allora l’intera serie di elementi da a1 fino an è considerata un percorso (path) di lunghezza n. Nel caso l’ultimo elemento del percorso, an, coincida con il primo, a1, si parla di grafo ciclico (cycle).
" Per un grafo G, con % è indicata la relazione di equivalenza su G, che vale tra due elementi a, b ∈ G sia nel caso in cui si dia a = b, che per un percorso (a, . . . , b). Potrebbero seguire numerose altre specificazioni, come quella di circuito Hamiltoniano o di radice, ma per i nostri scopi, sia immediati che venturi, le informazioni presentate su questa versatile struttura matematica sono più che sufficienti.
Precisiamo adesso che il gioco di Ehrenfeucht si svolge in un numero n di mosse; coinvolge evidentemente due strutture ed è disputato tra due giocatori, detti Spoiler e Duplica- tor:13 un gioco di Ehrenfeucht in n mosse giocato su due grafi viene abbreviato come Gn(G1, G2). L’obiettivo di fondo per Spoiler è dimostrare che le due strutture G1 e G2 sono differenti, viceversa l’obiettivo di Duplicator è di dimostrarne la somiglianza, o meglio ancora di far vedere che il gioco-linguaggio non è in grado di individuare differenze tra le due strutture G1 e G2. Per portare a termine uno dei due compiti, si danno una serie di regole fisse e di passaggi da rispettare che andiamo ad elencare con ordine:
13I soprannomi “Spoiler” e “Duplicator” sono dovuti a Spencer, e indicano rispettivamente il procedimento
adottato dall’operatore ∀ e da ∃. In letteratura è possibile trovare nomi più suggestivi e fantasiosi, come ad esempio ∀belard ed ∃loise. (cfr. Hodges W., Model Theory, Cambridge University Press, Cambridge, 1993, p.95)
" Spoiler è il primo a giocare e a decidere un numero k ≤ 1 ∈ N che stabilisce il numero complessivo delle mosse di cui sarà composto il gioco. Dopo aver deciso k, Spoiler sceglie un elemento da uno dei due domini delle strutture (dal momento che parliamo di grafi matematici, verrà scelto un vertice da G1 oppure da G2). " Duplicator sceglie un elemento del dominio del grafo da cui Spoiler non ha scelto. " Indichiamo con ai un elemento-vertice qualsiasi preso da G1, e con bi un
elemento-vertice qualsiasi preso da G2. In questo modo, dopo k-mosse saranno state scelte due serie di numeri:
a := (a1, . . . , ak); b := (b1, . . . , bk);
indipendentemente da chi tra i due giocatori ha compiuto le scelte sui singoli domini.
" Diciamo che Duplicator vince Gn(G1, G2) in un numero n di mosse sse dopo un numero n di mosse esiste una mappa p : p (ai) = bi che preserva le proprietà di adiacenza e uguaglianza. Nel caso particolare del gioco affrontato, Duplicator vince se aiaj sono due vertici adiacenti in G1 sse bibj sono due vertici adiacenti in G2;
ai = aj sse bi = bj;
la mappa p è allora un isomorfismo parziale tra G1 e G2.
" Il vincitore di Gn(G1, G2), sia dunque Spoiler o Duplicator, si dice dotato di una strategia vincente.
In teoria dei giochi, un sistema come quello appena descritto viene qualificato come un gioco a informazione perfetta, lo sono per esempio la dama, il backgammon e gli scacchi; questo significa che i dati di cui i giocatori dispongono (input, output, elaborazione e cornice) sono chiari e accessibili a partire dalla prima mossa della partita. Inoltre, il fatto che il contratto di gioco sia basato su una modalità a turni esclude il gioco di Ehrenfeucht dalla classe dei sistemi a informazione completa. Bisogna poi notare come per Spoiler non sia mai conveniente scegliere in due differenti turni le stesso elemento xi ∈ Gk, per quanto questo non sia strettamente proibito dal regolamento: Duplicator sarebbe a quel punto semplicemente invitato a ripetere la stessa scelta di accoppiamento in due turni distinti, accorciando così la durata del gioco e segnando un punto a suo favore.
Come è facile comprendere, se ha senso parlare di strategia vincente è grazie alla pun- tualità delle informazioni disponibili già dalla prima mossa di gioco; in particolar modo, l’informazione decisiva è rappresentata dalla pubblicità della funzione di isomorfismo. Per descrivere una stategia vincente forniamo, almeno per cominciare, un paio di esempi applicativi.
2.3.0.10 Esempio
Siano G1 e G2 due grafi semplici. Poniamo che G1 abbia almeno un vertice isolato (senza connessioni con altri vertici), mentre G2 non ne abbia alcuno. Allora Spoiler
vince Gk(G1, G2)per k ≥ 2.
Questa affermazione è verificabile nel seguente modo
" Spoiler sceglie il vertice isolato a1 ∈ G1 al primo turno; " Duplicator sceglie un vertice qualsiasi b2 ∈ G2;
" Spoiler sceglie l’elemento connesso con b2, mossa consentita dal momento che G2 non ha vertici isolati;
" Duplicator non può controbattere perché è impossibile trovare un elemento connesso