Equivalenza elementare

Da Wikipedia, l'enciclopedia libera.

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é[modifica | modifica sorgente]

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
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica