Echivalența elementară

În teoria modelelor, se spune că două structuri în același limbaj sunt echivalente elementare dacă într-una toate și numai formulele de ordinul întâi care se mențin în cealaltă.

În simboluri, " $LA$ ${\ displaystyle A}$ $LA$ este practic echivalent cu $B.$ ${\ displaystyle B}$ $B.$ „ tu scrii $A\equiv B$ ${\ displaystyle A \ equiv B}$ ${\ displaystyle A \ equiv B}$ .

Două structuri izomorfe sunt întotdeauna echivalente elementare; cu toate acestea, inversul nu este adevărat. De exemplu, mulțimea numerelor raționale și cea a numerelor reale , ambele văzute ca mulțimi dense ordonate liniar , sunt elementar echivalente, chiar dacă nu sunt izomorfe; $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb R$ , Spre deosebire de $\mathbb {Q}$ ${\ displaystyle \ mathbb {Q}}$ ${\ mathbb Q}$ , este complet , dar nu este posibil să se exprime condiția completitudinii cu o formulă de ordinul întâi.

Relațiile cu jocurile Ehrenfeucht-Fraïssé

Jocurile Ehrenfeucht-Fraïssé sunt jocuri abstracte care permit verificarea echivalenței elementare.

Dacă indicăm cu $A{\underset {m}{\equiv }}B$ ${\ displaystyle A {\ underset {m} {\ equiv}} B}$ ${\ displaystyle A {\ underset {m} {\ equiv}} B}$ declarația „ într-o piesă de teatru a lui Ehrenfeucht-Fraïssé din $m$ ${\ displaystyle m}$ $m$ se deplasează pe structuri $LA$ ${\ displaystyle A}$ $LA$ Și $B.$ ${\ displaystyle B}$ $B.$ , apărătorul are o strategie câștigătoare ", se observă prin inducție că:

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

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

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

,

adică apărătorul are o strategie câștigătoare pentru $m$ ${\ displaystyle m}$ $m$ se mișcă dacă și numai dacă nu este posibil să găsești formule cu cel mult $m$ ${\ displaystyle m}$ $m$ cuantificatoarele grefei care sunt adevărate în $LA$ ${\ displaystyle A}$ $LA$ dar nu în $B.$ ${\ displaystyle B}$ $B.$ sau vice versa.

Această observație sugerează că:

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

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

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

adică, revenind la terminologia jocurilor, că două structuri sunt practic echivalente dacă și numai dacă apărătorul are o strategie câștigătoare pentru un joc de Ehrenfeucht-Fraïssé de $m$ ${\ displaystyle m}$ $m$ se mișcă cu $m\in \mathbb {N}$ ${\ displaystyle m \ in \ mathbb {N}}$ ${\ displaystyle m \ in \ mathbb {N}}$ orice.