Gioco di Ehrenfeucht-Fraïssé

Da Wikipedia, l'enciclopedia libera.

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é[modifica | modifica wikitesto]

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:

  1. L'attaccante sceglie un elemento a_1 di \mathfrak{A} o un elemento b_1 di \mathfrak{B}.
  2. 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}.
  3. L'attaccante sceglie di nuovo un elemento a_2 \ne a_1 di \mathfrak{A} o un elemento b_2 \ne b_1 di \mathfrak{B}.
  4. Il difensore sceglie di nuovo un elemento nell'altra struttura.
  5. Botta e risposta si ripetono in tutto n volte.
  6. 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Strutture finite[modifica | modifica wikitesto]

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>\alpha. 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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 nonstandard 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 nonstandard dato), non è sufficiente una formula del primo ordine.

Storia[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  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.