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

Esempi[modifica | modifica wikitesto]

Strutture finite[modifica | modifica wikitesto]

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

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

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.

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