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é

modifica

Siano date due strutture   e  , entrambe prive di simboli di funzione e aventi gli stessi simboli di relazione [1], e sia dato un numero naturale  . Il gioco di Ehrenfeucht-Fraïssé   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   di   o un elemento   di  .
  2. Se l'attaccante ha scelto un elemento in  , il difensore sceglie un elemento   di  ; viceversa, se l'attaccante ha scelto un elemento in  , il difensore sceglie un elemento   di  .
  3. L'attaccante sceglie di nuovo un elemento   di   o un elemento   di  .
  4. Il difensore sceglie di nuovo un elemento nell'altra struttura.
  5. Botta e risposta si ripetono in tutto   volte.
  6. Alla conclusione del gioco, sono stati selezionati   elementi   di   e   elementi   di  . Possiamo vedere queste due collezioni come sottostrutture rispettivamente di   e  , con le stesse relazioni.[2]

Il difensore ha vinto se   è un isomorfismo. Altrimenti, ha vinto l'attaccante.

Analisi passo-passo

modifica

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

Due strutture   e   si diranno  -equivalenti (questa relazione si indica con il simbolo  ) se il difensore ha una strategia vincente per il gioco  .

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

Strutture finite

modifica

Se   e   sono due strutture finite di rispettivamente   e   elementi, con   (se  , il discorso è analogo), il difensore perde ogni gioco   con  . Infatti sarà sufficiente che l'attaccante scelga un elemento alla volta da  : anche ammesso che il difensore riesca a resistere   mosse, non riuscirà a trovare un elemento diverso dai precedenti in   alla  -esima mossa.

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

Se invece  , le due strutture sono elementarmente equivalenti se e solo se sono isomorfe, e in tal caso, dato   un isomorfismo, le mosse che deve effettuare il difensore sono semplici: ad ogni scelta di un elemento   da parte dell'attaccante, risponderà con  , ad ogni scelta di   risponderà con  .

Numeri reali e numeri razionali

modifica

Consideriamo le strutture   e  , 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  , esiste un elemento   che ne è l'estremo superiore"). Questo significa che in un gioco di Ehrenfeucht–Fraïssé  , con un   qualunque, il difensore ha sempre una strategia vincente.

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

  • maggiore di ogni   con  : in tal caso il difensore non ha che da prendere   maggiore di ogni   con  
  • minore di ogni   con  : il difensore non ha che da prendere   minore di ogni   con  
  • compreso tra un   e un   (tali che tra   e   non ci siano altri elementi della collezione): in tal caso il difensore può prendere  

La situazione è identica (basta sostituire ovunque le "a" con "b") se l'attaccante sceglie un elemento  .

Consideriamo ora   e  , 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     Un isomorfismo di gruppi non può che mandare l'elemento neutro di un gruppo nell'elemento neutro dell'altro.
2      , quindi deve essere  , per il resto, la scelta è libera.
3   Il difensore ha perso Se il difensore scegliesse un numero  , avremmo che:
 
ma:
 
perché   è irrazionale e quindi non può essere  .
Quindi avremmo una formula verificata in una sottostruttura ma non nell'altra, ovvero la mossa non sarebbe valida.

Numeri relativi

modifica

Consideriamo le strutture   e  , dove con   si intende   e   è l'ordine antilessicografico.

Le due strutture sono  -equivalenti per ogni numero naturale  ; 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   o  ), il difensore sceglie dall'altra struttura un elemento uguale all'elemento più grande (rispettivamente più piccolo) sommato (rispettivamente sottratto)  , dove   è il numero delle mosse mancanti alla fine del gioco
  • altrimenti, se l'attaccante sceglie un elemento che è l' -esimo più grande tra quelli già scelti nella stessa struttura, il difensore sceglie dall'altra struttura la media aritmetica[3] tra l' -esimo e l' -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   e   (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   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]

Generalizzazione

modifica

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

  • se  , allora "il difensore ha una strategia vincente per  " significa "il difensore ha una strategia vincente per  , al termine della quale è capace di resistere ancora una mossa";
  • se  , allora "il difensore ha una strategia vincente per  " significa "il difensore ha una strategia vincente per ogni   con  ".

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

  •   vorrà dire semplicemente  , ovvero "il difensore può vincere un gioco di   mosse con   numero naturale scelto arbitrariamente dall'attaccante.
  •   vorrà dire "il difensore può vincere   (che consiste in una partita   con   scelto dall'attaccante) e resistere un'ulteriore mossa
  •   vorrà dire "il difensore è in grado di resistere a   (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,  , che significa "il difensore è in grado di resistere per un numero arbitrariamente grande e non fissato in partenza di mosse".

Letture consigliate

modifica

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]

  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  : la media di   e   sarà  
  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.