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.

Organizzazione di un gioco di Ehrenfeucht–Fraïssé

Siano date due strutture ${\mathfrak {A}}$ e ${\mathfrak {B}}$ , entrambe prive di simboli di funzione e aventi gli stessi simboli di relazione ^[1], e sia dato un numero naturale $n$ . Il gioco di Ehrenfeucht-Fraïssé $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:

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

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

Analisi passo-passo

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é.

Interpretazione dei giochi

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

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

Esempi

Strutture finite

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

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

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

Numeri reali e numeri razionali

Consideriamo le strutture $(\mathbb {Q} ,<)$ e $(\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 $I\subset \mathbb {R}$ , esiste un elemento $x$ che ne è l'estremo superiore"). Questo significa che in un gioco di Ehrenfeucht–Fraïssé $G_{n}({\mathfrak {A}},{\mathfrak {B}})$ , con un $n$ qualunque, il difensore ha sempre una strategia vincente.

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

maggiore di ogni $a_{i}$ con $i<k$ : in tal caso il difensore non ha che da prendere $b_{k+1}$ maggiore di ogni $b_{i}$ con $i<k$
minore di ogni $a_{i}$ con $i<k$ : il difensore non ha che da prendere $b_{k+1}$ minore di ogni $b_{i}$ con $i<k$
compreso tra un $a_{i}$ e un $a_{j}$ (tali che tra $a_{i}$ e $a_{j}$ non ci siano altri elementi della collezione): in tal caso il difensore può prendere $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 $b_{k+1}$ .

Consideriamo ora $(\mathbb {Q} ,<,0,+)$ e $(\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

a_{1}=0\in \mathbb {Q}

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

b_{2}=1\in \mathbb {R}

a_{2}={\frac {c}{d}}\in \mathbb {Q} {\text{, con }}{\frac {c}{d}}>0

b_{2}>b_{1}

, quindi deve essere

a_{2}>a_{1}

, per il resto, la scelta è libera.

3

b_{3}=\pi \in \mathbb {R}

Il difensore ha perso

Se il difensore scegliesse un numero

a_{3}={\frac {e}{f}}\in \mathbb {Q}

, avremmo che:

{\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:

{\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é

\pi

è irrazionale e quindi non può essere

={\frac {d*e}{f*c}}

.

Quindi avremmo una formula verificata in una sottostruttura ma non nell'altra, ovvero la mossa non sarebbe valida.

Numeri relativi

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

Le due strutture sono $m$ -equivalenti per ogni numero naturale $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 $\mathbb {N}$ o $\mathbb {Z}$ ), il difensore sceglie dall'altra struttura un elemento uguale all'elemento più grande (rispettivamente più piccolo) sommato (rispettivamente sottratto) $2^{k}$ , dove $k$ è il numero delle mosse mancanti alla fine del gioco
altrimenti, se l'attaccante sceglie un elemento che è l' $n$ -esimo più grande tra quelli già scelti nella stessa struttura, il difensore sceglie dall'altra struttura la media aritmetica^[3] tra l' $n-1$ -esimo e l' $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 $(\mathbb {N} ,<)$ e $(\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 $\mathbb {N}$ ma non nel modello non standard dato), non è sufficiente una formula del primo ordine.

Storia

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]

Generalizzazione

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

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

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

${\mathfrak {A}}{\underset {\omega }{\equiv }}{\mathfrak {B}}$ vorrà dire semplicemente $\forall m\in \mathbb {N} ,{\mathfrak {A}}{\underset {m}{\equiv }}{\mathfrak {B}}$ , ovvero "il difensore può vincere un gioco di $m$ mosse con $m$ numero naturale scelto arbitrariamente dall'attaccante.
${\mathfrak {A}}{\underset {\omega +1}{\equiv }}{\mathfrak {B}}$ vorrà dire "il difensore può vincere $G_{\omega }({\mathfrak {A}},{\mathfrak {B}})$ (che consiste in una partita $G_{m}({\mathfrak {A}},{\mathfrak {B}})$ con $m\in \mathbb {N}$ scelto dall'attaccante) e resistere un'ulteriore mossa
$A{\underset {\omega ^{2}}{\equiv }}B$ vorrà dire "il difensore è in grado di resistere a $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, ${\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".

Letture consigliate

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]

Note

^ Si intende proprio che hanno gli stessi simboli, e che uno stesso simbolo ha la stessa arietà in entrambe le strutture; non significa che ci sia alcuna ulteriore somiglianza tra le relazioni che rappresentano (nonostante di solito ciò avvenga, perché in matematica ogni simbolo viene convenzionalmente utilizzato per indicare relazioni particolari e perché paragonare relazioni che non hanno nulla in comune è solitamente poco interessante).
^ O più precisamente con le restrizioni delle relazioni definite sulle rispettive strutture.
^ Il concetto di media aritmetica viene esteso in modo naturale a ${\mathfrak {B}}$ : la media di $(1,a)$ e $(1,b)$ sarà $\left(1,{\frac {a+b}{2}}\right)$
^ Sur une nouvelle classification des systèmes de relations, Roland Fraïssé, Comptes Rendus 230 (1950), 1022–1024.
^ Sur quelques classifications des systèmes de relations, Roland Fraïssé, thesis, Paris, 1953; published in Publications Scientifiques de l'Université d'Alger, series A 1 (1954), 35–182.
^ An application of games to the completeness problem for formalized theories, A. Ehrenfeucht, Fundamenta Mathematicae 49 (1961), 129–141.
^ (EN) Enciclopedia di Filosofia di Stanford, sezione su logica e giochi
^ A Course in Model Theory, Bruno Poizat, tr. Moses Klein, New York: Springer-Verlag, 2000.
^ Linear Orderings, Joseph G. Rosenstein, New York: Academic Press, 1982.

[1] Si intende proprio che hanno gli stessi simboli, e che uno stesso simbolo ha la stessa arietà in entrambe le strutture; non significa che ci sia alcuna ulteriore somiglianza tra le relazioni che rappresentano (nonostante di solito ciò avvenga, perché in matematica ogni simbolo viene convenzionalmente utilizzato per indicare relazioni particolari e perché paragonare relazioni che non hanno nulla in comune è solitamente poco interessante).

[2] O più precisamente con le restrizioni delle relazioni definite sulle rispettive strutture.

[3] Il concetto di media aritmetica viene esteso in modo naturale a ${\mathfrak {B}}$ : la media di $(1,a)$ e $(1,b)$ sarà $\left(1,{\frac {a+b}{2}}\right)$

[4] Sur une nouvelle classification des systèmes de relations, Roland Fraïssé, Comptes Rendus 230 (1950), 1022–1024.

[5] Sur quelques classifications des systèmes de relations, Roland Fraïssé, thesis, Paris, 1953; published in Publications Scientifiques de l'Université d'Alger, series A 1 (1954), 35–182.

[6] An application of games to the completeness problem for formalized theories, A. Ehrenfeucht, Fundamenta Mathematicae 49 (1961), 129–141.

[7] (EN) Enciclopedia di Filosofia di Stanford, sezione su logica e giochi

[8] A Course in Model Theory, Bruno Poizat, tr. Moses Klein, New York: Springer-Verlag, 2000.

[9] Linear Orderings, Joseph G. Rosenstein, New York: Academic Press, 1982.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]