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.
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?