# Showing two infinite structures with one unary predicate are elementarily equivalent

Suppose M and N are two infinite structures in a language with one unary predicate symbol P. In each structure, let the predicate be satisfied on an infinite subet, and let the complement of that set in each structure be infinite as well. I would like to prove that M and N are elementarily equivalent.

I tried to prove it directly using the definition of elementary equivalence by induction on formulas, but I could not figure out the universal quantifier case.

I thought about using the Tarski-Vaught criterion, but I didn't think it would help since we don't even know one is a subset of the other to begin with. And showing one is an elementary substructure of another doesn't help to show that the two are elementarily equivalent?)

I think the key should be that first order language doesn't distinguish between different sizes of infinity, but I'm not too sure how to formalize this.

Things we have learned in class so far are isomorphisms between structures, elementary equivalence, elementary substructures, definability, the Tarski-Vaught criterion, and the Lowenheim-Skolem Theorem. I would like to be able to find an answer just using these concepts. Any help would be appreciated.

• Re "And showing one is an elementary substructure of another doesn't help to show that the two are elementarily equivalent?": That's incorrect! Being an elementary substructure is stronger than being elementarily equivalent. (It means they are elementarily equivalent not just over the original language but over the language with a constant symbol for each element of the submodel.) – Eric Wofsey Nov 7 '17 at 4:33
• Thank you for your comment and answer. Could you elaborate on what you mean by "they are elementarily equivalent not just over the original language but over the language with a constant symbol for each element of the submodel"? – user500144 Nov 7 '17 at 4:44
• If $M\preceq N$, that means that for any formula $\varphi(x_1,\dots,x_n)$ and any $a_1,\dots,a_n\in M$, $M\vDash \varphi(a_1,\dots,a_n)$ iff $N\vDash\varphi(a_1,\dots,a_n)$. But a formula $\varphi(a_1,\dots,a_n)$ with elements of $M$ plugged in for its free variables is the same thing as a sentence over the language where you've added a constant symbol for each element of $M$ (just replace each variable with the appropriate constant). So the condition is that $M\vDash\varphi$ iff $N\vDash\varphi$ for every sentence over this langauge, which just means $M\equiv N$ over this language. – Eric Wofsey Nov 7 '17 at 4:48
• See also the answers to math.stackexchange.com/questions/2139585/… – Eric Wofsey Nov 7 '17 at 4:50
• How about you play a game? Maybe an Ehrenfeucht–Fraïssé game? – Asaf Karagila Nov 7 '17 at 6:54

Hint: By Lowenheim-Skolem, there are countable elementary submodels $M_0\preceq M$ and $N_0\preceq N$. Can you show $M_0$ and $N_0$ are isomorphic?
• I am guessing that the idea is to show they are isomophic by mapping the elements in $M_0$ that satisfy the predicate to the elements in $N_0$ which satisfy the predicate. But how can you know that those sets have the same cardinality? Also, should I be able to construct an explicit map between them? – user500144 Nov 7 '17 at 5:54
• Well, given that $M_0$ and $N_0$ are countable, what cardinalities could those sets possibly have? – Eric Wofsey Nov 7 '17 at 6:10