Equivalenza elementare

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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, "${\displaystyle A}$ è elementarmente equivalente a ${\displaystyle B}$" si scrive ${\displaystyle A\equiv B}$.

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; ${\displaystyle \mathbb {R} }$, a differenza di ${\displaystyle \mathbb {Q} }$, è completo, ma non è possibile esprimere la condizione di completezza con una formula del primo ordine.

I giochi di Ehrenfeucht-Fraïssé sono giochi astratti che permettono di verificare la elementare equivalenza.

Se indichiamo con ${\displaystyle A{\underset {m}{\equiv }}B}$ l'affermazione "in un gioco di Ehrenfeucht-Fraïssé di ${\displaystyle m}$ mosse sulle strutture ${\displaystyle A}$ e ${\displaystyle B}$, il difensore ha una strategia vincente", si osserva per induzione che:

${\displaystyle A{\underset {m}{\equiv }}B\iff (A\vDash \varphi \leftrightarrow B\vDash \varphi )\;\;\forall \varphi :rk(\varphi )\leq m}$,

ovvero il difensore ha una strategia vincente per ${\displaystyle m}$ mosse se e solo se non è possibile trovare formule con al più ${\displaystyle m}$ quantificatori innestati che siano vere in ${\displaystyle A}$ ma non in ${\displaystyle B}$ o viceversa.

Questa osservazione suggerisce che:

${\displaystyle A\equiv B\iff \forall m\in \mathbb {N} (A{\underset {m}{\equiv }}B)}$

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 ${\displaystyle m}$ mosse con ${\displaystyle m\in \mathbb {N} }$ qualsiasi.

In questo senso, generalizzando la notazione dei giochi ad ${\displaystyle m}$ ordinale qualsiasi, si può scrivere:

${\displaystyle A\equiv B\iff A{\underset {\omega }{\equiv }}B}$

• (EN) elementary equivalence, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica