Marker 4.5.36 - Showing elementary equivalence between two structures This is a question about part b) of the question. Below I'll show the major 'results' in my attempt at the solution, as well as where I got stuck:

1.

I defined a new $$\mathcal{L}$$-structure $$\mathcal{N}$$ defined as follows:

The universe is $$\mathbb{N}\times\mathbb{Q}$$ with $$\hat{U}_{i}^{\mathcal{N}}=\{i\} \times \mathbb{Q}$$ and $$s_{i}$$ defined in the usual way.

Intuitively, $$\mathcal{N}$$ acts the same as $$\mathcal{M}$$ and therefore one would expect $$\mathcal{M} \prec \mathcal{N}$$.

I have proved that to prove b), it suffices to show $$\mathcal{M} \prec \mathcal{N}$$.

2.

In my attempt to use the Tarski-Vaught test, I managed to prove a weaker result:

If $$\mathcal{N} \models \phi(a,\bar{b})$$ where $$\phi$$ is quantifier free, $$a\in N$$, and $$\bar{b}\in M$$ then there exists $$a'\in M$$ such that $$\mathcal{N} \models\phi(a',\bar{b})$$.

In part a), we are given that $$T$$, which is the full theory of $$\mathcal{M}$$ has quantifier elimination. Thus, if we can show that $$Th(\mathcal{N})$$ has quantifier elimination, as it should have, we can use the above result to complete the Tarski-Vaught argument and show that $$\mathcal{M} \prec \mathcal{N}$$.

The problem:

I am unable to show that $$Th(\mathcal{N})$$ has quantifier elimination, neither do I know how to show that $$T=Th(\mathcal{M})$$ has quantifier elimination either. I first tried to prove it by construction and failed. And then I used methods from 3.1 and found them inapplicable.

At this point, I have three options:

1. Find a way to show that $$Th(\mathcal{N})$$ has quantifier elimination

2. Find some other way to show that $$\mathcal{M} \prec \mathcal{N}$$

3. Scrap my previous ideas and try again to construct $$2^{\aleph_{0}}$$ non-isomorphic models of $$T$$.

Any hint or suggestion of where to go from here would also be greatly appreciated. Thanks for the read.

Just a bit of setup first, to make sure we are aiming for the same kind of proof here (I suspect you have something like this in mind when you say that $$\mathcal{M} \prec \mathcal{N}$$ suffices to prove (b)). For any subset $$J \subseteq \mathbb{N}$$ we define an $$\mathcal{L}$$-structure $$\mathcal{N}_J$$ with universe $$(J \times \mathbb{Q}) \cup ((\mathbb{N} - J) \times \mathbb{Z})$$. Then the interpretation of $$U_i$$ will be $$\{i\} \times \mathbb{Q}$$ if $$i \in J$$ and $$\{i\} \times \mathbb{Z}$$ otherwise. In particular, your structure $$\mathcal{N}$$ is then $$\mathcal{N}_\mathbb{N}$$, and $$\mathcal{M}$$ is just $$\mathcal{N}_\emptyset$$.

The goal will now be to prove that

1. for different $$J, J' \subseteq \mathbb{N}$$ the structures $$\mathcal{N}_J$$ and $$\mathcal{N}_{J'}$$ are not isomorphic,
2. $$Th(\mathcal{N}_J) = Th(\mathcal{M})$$ for all $$J \subseteq \mathbb{N}$$.

Point 1 should be easy to see since an isomorphism between $$\mathcal{N}_J$$ and $$\mathcal{N}_{J'}$$ restricts to an isomorphism between $$U_i^{\mathcal{N}_J}$$ and $$U_i^{\mathcal{N}_{J'}}$$ for all $$i \in \mathbb{N}$$.

Point 2 comes down to the problem you describe in your question. Probably the easiest way to solve this, is to work with Ehrenfeucht-Fraïssé games. The winning strategy should be roughly as follows: every element player 1 picks will be in some $$U_i$$, player 2 then always picks an element from the $$U_i$$ in the other structure. If player 1 picks an element that is not of integer distance to any previously element picked in $$U_i$$ (either because no elements in $$U_i$$ have been picked yet, or because player 1 picks an element in $$\{i\} \times \mathbb{Q}$$), player 2 can respond with any element (in the $$U_i$$ of the other structure). If player 1 does pick an element that has integer distance from a previously picked element, then this determines precisely which element player 2 has to pick in the other structure. This proves point 2.

Since there are continuum many subsets of $$\mathbb{N}$$ and they all give us a model (by point 2) of $$T$$, and all these models are pairwise non-isomorphic (by point 1), we have indeed that there are $$2^{\aleph_0}$$ many different countable models.

If you really want to work with elementary embeddings, then I think showing quantifier elimination for every $$\mathcal{N}_J$$ is the best way to go. That should be doable, but it can get tedious.