Equivalenza elementare

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, "$A$ è elementarmente equivalente a $B$" si scrive $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; $\mathbb {R}$, a differenza di $\mathbb {Q}$, è 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 $A{\underset {m}{\equiv }}B$ l'affermazione "in un gioco di Ehrenfeucht-Fraïssé di $m$ mosse sulle strutture $A$ e $B$, il difensore ha una strategia vincente", si osserva per induzione che:

$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 $m$ mosse se e solo se non è possibile trovare formule con al più $m$ quantificatori innestati che siano vere in $A$ ma non in $B$ o viceversa.

Questa osservazione suggerisce che:

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

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

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

Collegamenti esterni

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