Let $\mathcal{L}$ be a finite first-order language. When we say structure we mean $\mathcal{L}$-structure.

Question. Can someone lists different ways which we may use to show two given structures are elementarily equivalent?

For example:

1) doing induction on complexity of formulas,

2) using Ehrenfeucht-Fraisse games,

3) ....

  1. Finding a theory satisfied by both structures and then proving that this theory is complete, for example by Vaught's test.

  2. Building a forcing extension of the set-theoretic universe in which the structures become isomorphic. (This actually proves $L_{\infty,\omega}$-equivalence, and it tends to be similar to an argument about infinitely long Ehrenfeucht-Fraïssé games.)

  • 3
    $\begingroup$ This is a subset of 3. (and 1.), but can be useful: showing that the theory of each has elimination of quantifiers and that they satisfy the same quantifier-free sentences (possibly after expanding the language a bit). Another method is finding an elementary embedding or a common elementary extension (with which q.e. also helps). $\endgroup$ – tomasz May 16 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.