Gioco di Ehrenfeucht-Fraïssé

In teoria dei modelli, i giochi di Ehrenfeucht–Fraïssé sono un metodo matematico per trattare l'equivalenza elementare di due strutture.

Siano date due strutture ${\displaystyle {\mathfrak {A}}}$ e ${\displaystyle {\mathfrak {B}}}$, entrambe prive di simboli di funzione e aventi gli stessi simboli di relazione ^[1], e sia dato un numero naturale ${\displaystyle n}$. Il gioco di Ehrenfeucht-Fraïssé ${\displaystyle G_{n}({\mathfrak {A}},{\mathfrak {B}})}$ sarà giocato da due giocatori, un attaccante e un difensore. Scopo dell'attaccante è trovare una diversità tra le due strutture; il difensore deve fare il possibile per impedirglielo. Il gioco si gioca come segue:

1. L'attaccante sceglie un elemento ${\displaystyle a_{1}}$ di ${\displaystyle {\mathfrak {A}}}$ o un elemento ${\displaystyle b_{1}}$ di ${\displaystyle {\mathfrak {B}}}$.
2. Se l'attaccante ha scelto un elemento in ${\displaystyle {\mathfrak {A}}}$, il difensore sceglie un elemento ${\displaystyle b_{1}}$ di ${\displaystyle {\mathfrak {B}}}$; viceversa, se l'attaccante ha scelto un elemento in ${\displaystyle {\mathfrak {B}}}$, il difensore sceglie un elemento ${\displaystyle a_{1}}$ di ${\displaystyle {\mathfrak {A}}}$.
3. L'attaccante sceglie di nuovo un elemento ${\displaystyle a_{2}\neq a_{1}}$ di ${\displaystyle {\mathfrak {A}}}$ o un elemento ${\displaystyle b_{2}\neq b_{1}}$ di ${\displaystyle {\mathfrak {B}}}$.
4. Il difensore sceglie di nuovo un elemento nell'altra struttura.
5. Botta e risposta si ripetono in tutto ${\displaystyle n}$ volte.
6. Alla conclusione del gioco, sono stati selezionati ${\displaystyle n}$ elementi ${\displaystyle a_{1},\dots ,a_{n}}$ di ${\displaystyle {\mathfrak {A}}}$ e ${\displaystyle n}$ elementi ${\displaystyle b_{1},\dots ,b_{n}}$ di ${\displaystyle {\mathfrak {B}}}$. Possiamo vedere queste due collezioni come sottostrutture rispettivamente di ${\displaystyle {\mathfrak {A}}}$ e ${\displaystyle {\mathfrak {B}}}$, con le stesse relazioni.^[2]

Il difensore ha vinto se ${\displaystyle a_{i}\mapsto b_{i}}$ è un isomorfismo. Altrimenti, ha vinto l'attaccante.

Quello dato sopra è il modo più semplice per definire la vittoria in un gioco di Ehrenfeucht–Fraïssé.

Alternativamente, si può osservare che il difensore vince se, ad ogni sua mossa, l'elemento che sceglie verifica con gli elementi precedentemente scelti nella sua struttura tutte e sole le relazioni che l'elemento appena scelto dall'attaccante verifica con gli elementi precedentemente scelti nell'altra.

Sarà quindi questa seconda definizione di vittoria che considereremo nell'analizzare qualche esempio di gioco di Ehrenfeucht–Fraïssé.

Due strutture ${\displaystyle {\mathfrak {A}}}$ e ${\displaystyle {\mathfrak {B}}}$ si diranno ${\displaystyle m}$-equivalenti (questa relazione si indica con il simbolo ${\displaystyle {\underset {k}{\equiv }}}$) se il difensore ha una strategia vincente per il gioco ${\displaystyle G_{m}({\mathfrak {A}},{\mathfrak {B}})}$.

Si verifica facilmente che due strutture elementarmente equivalenti sono ${\displaystyle m}$-equivalenti per ogni numero naturale ${\displaystyle m}$ (purché i simboli di relazione sulle strutture siano in numero finito), e viceversa.

Se ${\displaystyle {\mathfrak {A}}}$ e ${\displaystyle {\mathfrak {B}}}$ sono due strutture finite di rispettivamente ${\displaystyle \alpha }$ e ${\displaystyle \beta }$ elementi, con ${\displaystyle \alpha >\beta }$ (se ${\displaystyle \beta >\alpha }$, il discorso è analogo), il difensore perde ogni gioco ${\displaystyle G_{n}({\mathfrak {A}},{\mathfrak {B}})}$ con ${\displaystyle n>\beta }$. Infatti sarà sufficiente che l'attaccante scelga un elemento alla volta da ${\displaystyle {\mathfrak {A}}}$: anche ammesso che il difensore riesca a resistere ${\displaystyle \beta }$ mosse, non riuscirà a trovare un elemento diverso dai precedenti in ${\displaystyle {\mathfrak {B}}}$ alla ${\displaystyle \beta +1}$-esima mossa.

Infatti due strutture finite con cardinalità diversa non sono mai elementarmente equivalenti.

Se invece ${\displaystyle \alpha =\beta }$, le due strutture sono elementarmente equivalenti se e solo se sono isomorfe, e in tal caso, dato ${\displaystyle \phi :{\mathfrak {A}}\rightarrow {\mathfrak {B}}}$ un isomorfismo, le mosse che deve effettuare il difensore sono semplici: ad ogni scelta di un elemento ${\displaystyle a_{i}\in {\mathfrak {A}}}$ da parte dell'attaccante, risponderà con ${\displaystyle \phi (a_{i})}$, ad ogni scelta di ${\displaystyle b_{i}}$ risponderà con ${\displaystyle \phi ^{-1}(b_{i})}$.

Consideriamo le strutture ${\displaystyle (\mathbb {Q} ,<)}$ e ${\displaystyle (\mathbb {R} ,<)}$, ovvero i numeri reali e i numeri razionali viste unicamente come insiemi linearmente ordinati densi. Queste due strutture sono elementarmente equivalenti: infatti, la completezza (che distingue il tipo d'ordine dell'una da quello dell'altra) è una proprietà del secondo ordine, nel senso che non può essere definita senza quantificare sugli insiemi ("per ogni insieme ${\displaystyle I\subset \mathbb {R} }$, esiste un elemento ${\displaystyle x}$ che ne è l'estremo superiore"). Questo significa che in un gioco di Ehrenfeucht–Fraïssé ${\displaystyle G_{n}({\mathfrak {A}},{\mathfrak {B}})}$, con un ${\displaystyle n}$ qualunque, il difensore ha sempre una strategia vincente.

Dopo ${\displaystyle k}$ mosse, infatti, saranno stati scelti gli elementi ${\displaystyle a_{1}\dots a_{k}}$ in una delle due strutture e ${\displaystyle b_{1}\dots b_{k}}$ nell'altra. Supponiamo che alla ${\displaystyle k+1}$-esima mossa, l'attaccante scelga un elemento ${\displaystyle a_{k+1}}$. Certamente ${\displaystyle a_{1}\dots a_{k+1}}$ è una catena, perché è un sottoinsieme di un insieme linearmente ordinato. Allora ${\displaystyle a_{k+1}}$ sarà:

• maggiore di ogni ${\displaystyle a_{i}}$ con ${\displaystyle i<k}$: in tal caso il difensore non ha che da prendere ${\displaystyle b_{k+1}}$ maggiore di ogni ${\displaystyle b_{i}}$ con ${\displaystyle i<k}$
• minore di ogni ${\displaystyle a_{i}}$ con ${\displaystyle i<k}$: il difensore non ha che da prendere ${\displaystyle b_{k+1}}$ minore di ogni ${\displaystyle b_{i}}$ con ${\displaystyle i<k}$
• compreso tra un ${\displaystyle a_{i}}$ e un ${\displaystyle a_{j}}$ (tali che tra ${\displaystyle a_{i}}$ e ${\displaystyle a_{j}}$ non ci siano altri elementi della collezione): in tal caso il difensore può prendere ${\displaystyle b_{k+1}={\frac {b_{i}+b_{j}}{2}}}$

La situazione è identica (basta sostituire ovunque le "a" con "b") se l'attaccante sceglie un elemento ${\displaystyle b_{k+1}}$.

Consideriamo ora ${\displaystyle (\mathbb {Q} ,<,0,+)}$ e ${\displaystyle (\mathbb {R} ,<,0,+)}$, ovvero i numeri razionali e i numeri reali visti come gruppi ordinati con l'operazione di somma. Queste due strutture non sono più elementarmente equivalenti, e anzi l'attaccante ha una strategia vincente per ogni gioco di almeno 3 mosse:

	Mossa dell'attaccante	Mossa del difensore	Motivazione
1	${\displaystyle a_{1}=0\in \mathbb {Q} }$	${\displaystyle b_{1}=0\in \mathbb {R} }$	Un isomorfismo di gruppi non può che mandare l'elemento neutro di un gruppo nell'elemento neutro dell'altro.
2	${\displaystyle b_{2}=1\in \mathbb {R} }$	${\displaystyle a_{2}={\frac {c}{d}}\in \mathbb {Q} {\text{, con }}{\frac {c}{d}}>0}$	${\displaystyle b_{2}>b_{1}}$, quindi deve essere ${\displaystyle a_{2}>a_{1}}$, per il resto, la scelta è libera.
3	${\displaystyle b_{3}=\pi \in \mathbb {R} }$	Il difensore ha perso	Se il difensore scegliesse un numero ${\displaystyle a_{3}={\frac {e}{f}}\in \mathbb {Q} }$, avremmo che: ${\displaystyle {\begin{matrix}\underbrace {a_{2}+a_{2}+\dots a_{2}} &={\frac {c}{d}}*d*e=c*e={\frac {e}{f}}*f*c=&\underbrace {a_{3}+a_{3}+\dots a_{3}} \\d*e{\text{ volte}}&&f*c{\text{ volte}}\end{matrix}}}$ ma: ${\displaystyle {\begin{matrix}\underbrace {b_{2}+b_{2}+\dots b_{2}} &=1*d*e=d*e\not =\pi f*c=&\underbrace {a_{3}+a_{3}+\dots a_{3}} \\d*e{\text{ volte}}&&f*c{\text{ volte}}\end{matrix}}}$ perché ${\displaystyle \pi }$ è irrazionale e quindi non può essere ${\displaystyle ={\frac {d*e}{f*c}}}$. Quindi avremmo una formula verificata in una sottostruttura ma non nell'altra, ovvero la mossa non sarebbe valida.

Consideriamo le strutture ${\displaystyle {\mathfrak {A}}=(\mathbb {N} ,<)}$ e ${\displaystyle {\mathfrak {B}}=(\mathbb {N} +\mathbb {Z} ,<')}$, dove con ${\displaystyle \mathbb {N} +\mathbb {Z} }$ si intende ${\displaystyle \mathbb {N} \times {0}\cup \mathbb {Z} \times 1}$ e ${\displaystyle <'}$ è l'ordine antilessicografico.

Le due strutture sono ${\displaystyle m}$-equivalenti per ogni numero naturale ${\displaystyle m}$; infatti la seguente è una strategia vincente per il difensore:

• se l'attaccante sceglie un elemento maggiore (o minore) di tutti quelli già scelti dalla stessa struttura (o comunque nella stessa "copia" di ${\displaystyle \mathbb {N} }$ o ${\displaystyle \mathbb {Z} }$), il difensore sceglie dall'altra struttura un elemento uguale all'elemento più grande (rispettivamente più piccolo) sommato (rispettivamente sottratto) ${\displaystyle 2^{k}}$, dove ${\displaystyle k}$ è il numero delle mosse mancanti alla fine del gioco
• altrimenti, se l'attaccante sceglie un elemento che è l'${\displaystyle n}$-esimo più grande tra quelli già scelti nella stessa struttura, il difensore sceglie dall'altra struttura la media aritmetica^[3] tra l'${\displaystyle n-1}$-esimo e l'${\displaystyle n}$-esimo più grandi elementi tra quelli già scelti

Si verifica facilmente per induzione che la media aritmetica di due elementi è sempre intera e che effettivamente quella data è una strategia vincente per il difensore.

Questo risultato implica che ${\displaystyle (\mathbb {N} ,<)}$ e ${\displaystyle (\mathbb {N} +\mathbb {Z} ,<')}$ (un modello non standard dei numeri naturali) sono elementarmente equivalenti. In effetti ciò è confermato dal fatto che per formulare il principio di induzione sui numeri naturali (che è valido in ${\displaystyle \mathbb {N} }$ ma non nel modello non standard dato), non è sufficiente una formula del primo ordine.

Il metodo "va e vieni" utilizzato nei giochi di Ehrenfeucht-Fraïssé per verificare l'equivalenza elementare è stato fornito da Roland Fraïssé nella sua tesi^[4],^[5]; fu riformulato sotto forma di gioco da Andrzej Ehrenfeucht.^[6] Nella letteratura anglofona, l'attaccante si chiama spesso Spoiler e il difensore Duplicator, per una consuetudine iniziata da Joel Spencer.^[7]

I giochi di Ehrenfeucht–Fraïssé, la terminologia di ${\displaystyle m}$-equivalenza e la notazione associata si possono generalizzare a numeri ordinali qualsiasi formalizzando la seguente intuizione:

• se ${\displaystyle \alpha =\beta +1}$, allora "il difensore ha una strategia vincente per ${\displaystyle G_{\alpha }({\mathfrak {A}},{\mathfrak {B}})}$" significa "il difensore ha una strategia vincente per ${\displaystyle G_{\beta }({\mathfrak {A}},{\mathfrak {B}})}$, al termine della quale è capace di resistere ancora una mossa";
• se ${\displaystyle \alpha =\sup\{\beta <\alpha \}}$, allora "il difensore ha una strategia vincente per ${\displaystyle G_{\alpha }({\mathfrak {A}},{\mathfrak {B}})}$" significa "il difensore ha una strategia vincente per ogni ${\displaystyle G_{\beta }({\mathfrak {A}},{\mathfrak {B}})}$ con ${\displaystyle \beta <\alpha }$".

Si noti che generalizzare in tale modo non significa introdurre giochi di Ehrenfeucht–Fraïssé "ad infinite mosse". Ad esempio:

• ${\displaystyle {\mathfrak {A}}{\underset {\omega }{\equiv }}{\mathfrak {B}}}$ vorrà dire semplicemente ${\displaystyle \forall m\in \mathbb {N} ,{\mathfrak {A}}{\underset {m}{\equiv }}{\mathfrak {B}}}$, ovvero "il difensore può vincere un gioco di ${\displaystyle m}$ mosse con ${\displaystyle m}$ numero naturale scelto arbitrariamente dall'attaccante.
• ${\displaystyle {\mathfrak {A}}{\underset {\omega +1}{\equiv }}{\mathfrak {B}}}$ vorrà dire "il difensore può vincere ${\displaystyle G_{\omega }({\mathfrak {A}},{\mathfrak {B}})}$ (che consiste in una partita ${\displaystyle G_{m}({\mathfrak {A}},{\mathfrak {B}})}$ con ${\displaystyle m\in \mathbb {N} }$ scelto dall'attaccante) e resistere un'ulteriore mossa
• ${\displaystyle A{\underset {\omega ^{2}}{\equiv }}B}$ vorrà dire "il difensore è in grado di resistere a ${\displaystyle n}$ (numero naturale scelto dall'attaccante) giochi consecutivi, ognuno di un numero finito di mosse scelto volta per volta arbitrariamente dall'attaccante.

Per questo motivo, si è aggiunta un'ulteriore notazione, ${\displaystyle {\mathfrak {A}}{\underset {\infty }{\equiv }}{\mathfrak {B}}}$, che significa "il difensore è in grado di resistere per un numero arbitrariamente grande e non fissato in partenza di mosse".

Il primo capitolo del testo di teoria dei modelli di Poizat^[8] contiene un'introduzione ai giochi di Ehrenfeucht-Fraïssé, così come i capitoli 6, 7 e 13 del libro di Rosenstein sugli ordini lineari.^[9]