Equivalenza elementare
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
In teoria dei modelli, due strutture nello stesso linguaggio si dicono elementarmente equivalenti se in una valgono tutte e sole le formule del primo ordine che valgono nell'altra.
In simboli, " è elementarmente equivalente a " si scrive .
Due strutture isomorfe sono sempre elementarmente equivalenti; tuttavia, non è vero il contrario. Ad esempio, l'insieme dei numeri razionali e quello dei numeri reali, visti entrambi come insiemi linearmente ordinati densi, sono elementarmente equivalenti pur non essendo isomorfi; , a differenza di , è completo, ma non è possibile esprimere la condizione di completezza con una formula del primo ordine.
Relazioni con i giochi di Ehrenfeucht-Fraïssé
I giochi di Ehrenfeucht-Fraïssé sono giochi astratti che permettono di verificare la elementare equivalenza.
Se indichiamo con l'affermazione "in un gioco di Ehrenfeucht-Fraïssé di mosse sulle strutture e , il difensore ha una strategia vincente", si osserva per induzione che:
- ,
ovvero il difensore ha una strategia vincente per mosse se e solo se non è possibile trovare formule con al più quantificatori innestati che siano vere in ma non in o viceversa.
Questa osservazione suggerisce che:
ovvero, tornando alla terminologia dei giochi, che due strutture sono elementarmente equivalenti se e solo se il difensore ha una strategia vincente per un gioco di Ehrenfeucht-Fraïssé di mosse con qualsiasi.
In questo senso, generalizzando la notazione dei giochi ad ordinale qualsiasi, si può scrivere:
Collegamenti esterni
- (EN) elementary equivalence, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)