Gioco di Ehrenfeucht-Fraïssé

Per capire cosa sia il gioco di Ehrenfeucht–Fraïssé serve anzitutto un crash-course di algebra universale (e un pizzico di teoria dei modelli).

Algebra Universale

In estrema sintesi si tratta della disciplina che studia la nozione di struttura algebrica "avulsa dalle sue incarnazioni concrete": invece della singola struttura di gruppo, anello o campo si studiano le proprieta` generali (date mediante assiomi) delle operazioni che definiscono la struttura. L'idea basale e' quella di arieta` di una operazione, l'arieta` essendo il numero di argomenti che l'operazione deve incamerare per funzionare.

Anche se non e` stato usato alcun termine tecnico credo che il concetto non sia chiaro: spero che un esempio sia risolutore.

Un gruppo e` un insieme <m>G</m> dotato di una operazione binaria <m>G\times G\to G</m> (potete tutti pensarla come la moltiplicazione) che sia associativa (<m>a,b,c\in G\Rightarrow a\cdot (b\cdot c)=(a\cdot b)\cdot c</m>), dotata di un elemento neutro (esiste <m>1\in G</m> tale che <m>1\cdot g=g\cdot 1=g</m> per ogni altro elemento <m>g\in G</m>), e tale che ogni elemento possieda un inverso <m>\bar g</m> tale che <m>\bar g\cdot g=g\cdot \bar g=1</m>, scritto evocativamente come <m>g^{-1}</m>.

Una prima osservazione: strutture come queste sono onnipresenti nella Matematica e nei modelli del mondo che la matematica offre; l'insieme delle simmetrie (rotazioni, riflessioni, traslazioni, etc.) di un cristallo regolare e` un gruppo, dove l'operazione e` data dalla composizione di funzioni (ruotare e poi riflettere, e infine traslare, o viceversa traslare, riflettere e infine ruotare).

Una osservazione bis: esattamente l'esempio precedente mostra che non c'e` alcuna ragione per cui l'operazione di <m>G</m> sia commutativa (tale che <m>a\cdot b=b\cdot a</m>).

Una seconda osservazione: questa impostazione e` soddisfacente per usi pratici e intuitivi, ma non lo e` affatto in teoria dei modelli, dove l'unico espediente per distinguere gli enti in studio e` confrontare le operazioni che abbiamo posto su di essi e vedere se sono uguali (in questa intercapedine si inserisce il gioco di Ehrenfeucht, quindi non trovare inutile questo cappello introduttivo). Dobbiamo quindi "far diventare delle operazioni" le proprieta' di avere un elemento neutro e di avere un inverso; per farlo e` necessaria qualche definizione precisa.

Definizione. Sia <m>n</m> un numero intero non negativo. Una operazione n-aria su un insieme <m>X</m> consta di una funzione dal prodotto cartesiano <m>X\times\dots\times X</m> fatto n volte all'insieme X. Il numero n si dice arieta` dell'operazione.

Esempi: Un gruppo e` come gia` detto un insieme che ha una operazione binaria associativa etc etc. Ma non finisce qui: per ragioni nascoste in seno all'insiemistica, il prodotto cartesiano di <m>X</m> fatto zero volte consiste di un insieme con un singolo elemento, diciamolo <m>1</m>. Una operazione 0-aria consiste allora di una qualche funzione <m>1\to X</m>. Di funzioni di questo tipo ce ne sono tante quante gli elementi di <m>X</m>, dato che piuttosto ovviamente una tale funzione e` totalmente determinata dall'immagine dell'unico elemento nel dominio (e` consigliabile farsi un esempio disegnando le patate care alle maestre delle elementari, notando che per esempio esistono esattamente tre funzioni dall'insieme {a} all'insieme {x,y,z}; quella che manda a in x, quella che manda a in y, e quella che manda a in z). Una operazione 0-aria su X e` dunque determinata dalla scelta di un elemento di X. In un gruppo, l'elemento neutro e` una operazione 0-aria.

Una operazione 1-aria consta di una funzione <m>a\colon X\to X</m>; in un gruppo, la mappa che manda un elemento nel suo inverso e` una operazione 1-aria.

L'operazione di moltiplicazione cui eravamo abituati fin dall'inizio e` una operazione binaria (2-aria), associativa e dotata di tutte le proprieta` di compatibilita` con le altre operazioni di neutro e di inversione.

In ultima analisi si puo` affermare senza tema di smentita che un gruppo e` un insieme con tre operazioni, una 0-aria (detta <m>1</m>), una 1-aria (detta <m>(-)^{-1}</m>) e una 2-aria (detta moltiplicazione, e scritta <m>\cdot</m>). Questa osservazione si riscrive compattamente come

<m>\mathbf{G}=\{G,\cdot,1,(-)^{-1}\}</m>

indicando con questo che la struttura <m>\mathbf G</m> e` determinata dall'insieme G e dalle operazioni suddette.

Il gioco di Ehrenfeucht–Fraïssé

(Copio spudoratamente la struttura del gioco dalla relativa pagina di Wikipedia). Decidere se due strutture algebriche sono uguali e` un problema difficile, intendendo cio` come "manca un criterio preciso e computazionalmente semplice per stabilire se due strutture su uno stesso insieme sono la stessa". L'idea e` allora quella di controllare a mano, campionando a caso le due strutture in "punti" determinati, nella speranza di trovare ad un certo punto una diversita` tra una sottostruttura della prima e una sottostruttura della seconda, testimoniata dalla mancanza di un isomorfismo tra le due. Questa situazione viene immaginata come quella in cui due giocatori, <m>\alpha</m> e <m>\beta</m>, "pescano a caso elementi" dalle due strutture in studio, e dopo averne pescati un numero prescritto si fermano e controllano se le sottostrutture <m>\{a_1,\dots, a_n\}</m> e <m>\{b_1,\dots, b_n\}</m> che hanno ottenuto sono isomorfe (=confondibili a meno di chiamare "a" ogni "b", intendendo con cio` che l'azione delle operazioni sugli elementi non cambia, cambiano solo i nomi degli elementi).

Il gioco

Siano date due strutture <m>\mfrak{A}</m> e <m>\mfrak{B}</m> [...], e sia dato un numero naturale <m>n</m>. Il gioco di Ehrenfeucht-Fraïssé <m>G_n(\mfrak{A},\mfrak{B})</m> 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 <m>a_1</m> di <m>\mfrak{A}</m> o un elemento <m>b_1</m> di <m>\mfrak{B}</m>.
2. Se l'attaccante ha scelto un elemento in <m>\mfrak{A}</m>, il difensore sceglie un elemento <m>b_1</m> di <m>\mfrak{B}</m>; viceversa, se l'attaccante ha scelto un elemento in <m>\mfrak{B}</m>, il difensore sceglie un elemento <m>a_1</m> di <m>\mfrak{A}</m>.
3. L'attaccante sceglie di nuovo un elemento <m>a_2 \ne a_1</m> di <m>\mfrak{A}</m> o un elemento <m>b_2 \ne b_1</m> di <m>\mfrak{B}</m>.
4. Il difensore sceglie di nuovo un elemento nell'altra struttura.
5. Botta e risposta si ripetono in tutto <m>n</m> volte.
6. Alla conclusione del gioco, sono stati selezionati <m>n</m> elementi <m>a_1, \dots, a_n</m> di <m>\mfrak{A}</m> e <m>n</m> elementi <m>b_1, \dots, b_n</m> di <m>\mfrak{B}</m>. Possiamo vedere queste due collezioni come sottostrutture rispettivamente di <m>\mfrak{A}</m> e <m>\mfrak{B}</m>, con le stesse relazioni.

Il difensore ha vinto se <m>a_i \mapsto b_i</m> è un isomorfismo. Altrimenti, ha vinto l'attaccante.