I'm reading through Marker's Model Theory: An Introduction, and he defines two $\mathcal{L}$-structures $\mathcal{M}, \mathcal{N}$ to be isomorphic if there exists a bijection $\eta : M \to N$ which respects the interpretations of the various symbols of the language $\mathcal{L}$. He also defines two structures to be elementarily equivalent if they have the same full theory (i.e. set of true sentences). He shows that isomorphic structures are elementarily equivalent, but not vice versa. My intuition is that isomorphism is strictly stronger than elementary equivalence, and I have an idea of how to construct an example. If $\mathcal{L} = \emptyset$ is the empty language of pure sets, then the $\mathcal{L}$-structures are just sets and any bijection is an isomorphism between structures.
However, I suspect that any two infinite sets are elementarily equivalent. The atomic formulas in the language are exactly the formulas $v_i = v_j$ for variables $v_i, v_j$. My intuition is that any sentence is either (a) contradictory, i.e. is true for no $\mathcal{L}$-structures, (b) describes the existence of a subset of a cardinality of some finite cardinality, or (c) describes the nonexistence of a subset of some cardinality $n$. Statements of type (a) would never be true of an infinite set, statements of type (b) would be true of all infinite sets, and statements of type (c) would never be true of an infinite set. My reason for thinking these are the only statements is that a formula can only every describe some combination of equalities or inequalities between finitely many elements, since it only has finitely many variable symbols in it. But I have no idea how to turn this intuition into a fleshed out proof.
I've only finished the first chapter of the book, so I suppose it's possible that I'm asking a question that requires way more technology than I have so far. How can I turn my proof idea into an actual proof? Or am I off base altogether?
Thanks!
You have the exact right idea!
There are a few ways to make this precise. One way is to show that the theory of infinite sets is complete. This means that, up to elementary equivalence, there is only one model.
But one way to show completeness is to use the Łoś–Vaught Test, which says that a theory is complete whenever there is exactly one model of some infinite cardinality (and there's no finite models).
So for your example, it's clear that any two models of the same cardinality are isomorphic. And if you add axioms saying "I have infinitely many elements" then your theory satisfies the conditions for the Łoś–Vaught test.
Then the theory of infinite sets is complete, and any two models are elementary equivalent.
Another way to make your exact idea precise is with the notion of an Ehrenfeucht–Fraïssé Game. These say, basically, that if you can "finitely simulate" any formula from one model in another, then your two models are elementary equivalent.
The breakdown of possible formulas that you've outlined can quickly be converted into a formal Ehrenfeucht–Fraïssé proof. The reason I led with the completeness proof is because I encourage you to do the conversion yourself! I'm sure that now you know the name of this technique you'll be able to flesh out your idea!
Of course, you can always ask here again if you get stuck.
I hope this helps ^_^