2
$\begingroup$

enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.