Countable proper elementary extension of $(\mathbb{N}, \leq, \cdot, +, 0, 1)$

model-theory

How can I show that there exist countable proper elementary extension of structure $(\mathbb{N}, \leq, \cdot, +, 0, 1)$? I'm self-studying model theory and I would appreciate some help in this exercise.

My approach for the proof is as follows:

I will denote the structure $(\mathbb{N}, \leq, \cdot, +, 0, 1)$ as $\mathcal{N}$ with universe $\mathbb{N}$ and language $\mathcal{L} = \{ \leq, \cdot, +, 0, 1 \}$.

Let $\mathcal{L}^* = \mathcal{L} \cup \mathcal{L}_{\mathbb{N}} \cup \{c\}$ where $c$ is a new constant symbol and let
$$ T = \mathrm{Diag}_{\mathrm{el}}(\mathcal{N}) \cup \left\{ \underbrace{1 + 1 + \cdots + 1}_{n\text{-times}} < c : \text{for }n = 1, 2, \ldots \right\} $$
If $T_0$ is a finite subset of $T$, then $\mathcal{N} \models T_0$ if we interpret $c$ as large enough natural number. Thus $T$ is finitely satisfable and using Godel's compactness theorem, $T$ is satisfable, so there exist $\mathcal{M} \models T$, so $\mathcal{M} \models \mathrm{Th}(\mathcal{N})$ and $\mathcal{N} \equiv \mathcal{M}$. If $a \in M$ is interpretation of $c$, then $a$ is greater than every natural number, therefore $a \notin \mathbb{N}$, so $\mathbb{N} \subsetneq M$. Using downward Lowenheim–Skolem theorem, there exist elementary substructure $\mathcal{S} \preceq \mathcal{M}$, such that $\mathbb{N} \subsetneq S$ and
$$ |\mathcal{N}| \leq |S| + |\mathcal{L}| + \aleph_0 = \aleph_0 + 5 + \aleph_0 = \aleph_0 $$
so $\mathcal{M}$ is countable proper elementary extension of $\mathcal{S}$. Since $\mathcal{S} \models \mathrm{Diag}_{\mathrm{el}}(\mathcal{N})$, then there exist elementary embedding of $\mathcal{N}$ into $\mathcal{S}$, so $\mathcal{N} \preceq \mathcal{S}$, so $\mathcal{M}$ is countable proper elementary extension of $\mathcal{N}$.

However I'm not sure if my proof is correct. I'd be glad of getting any help.

Best Answer

There is already an extensive discussion in the comments raising some good points about your proof. I will summarise them here and also propose a proof that similar but more general (and perhaps easier).

As for your proof, it is generally good and definitely the right idea. Here are some points that could be improved:

  • You should explicitly state that $a \in S$, otherwise we are just picking some countable elementary substructure of $M$ which might as well be $\mathcal{N}$ (this point was raised by spaceisdarkgreen).
  • There is something off in the last few sentences. You say "$\mathcal{M}$ is a countable proper elementary extension ..." twice, but $\mathcal{M}$ could have any (infinite) cardinality. The point of using Löwenheim-Skolem to produce $\mathcal{S}$ is to have $\mathcal{S}$ be countable. So this is probably a typo or so, but it should really say something about $\mathcal{S}$ being countable.
  • You use Löwenheim-Skolem to produce an elementary substructure $\mathcal{S}$ of $\mathcal{M}$, and then you argue that this means that $\mathcal{S} \models \operatorname{Diag_{el}}(\mathcal{N})$. However, in your cardinal inequalities you only mention the language $\mathcal{L}$, so this should really be $\mathcal{L} \cup \mathcal{L}_\mathbb{N}$. This is luckily still countable, so everything still works. Alternatively you could argue that this is not necessary by noting that every element in $\mathbb{N}$ is definable, but you would have to make that point and I think this is making things unnecessarily complicated (this point was also raised by spaceisdarkgreen).

Using a very similar approach we can prove something more general that might actually be conceptually easier.

Let $\mathcal{A}$ be an $\mathcal{L}$-structure, where $\mathcal{L}$ is a countable language. Then there is a countable proper elementary extension $\mathcal{A} \preceq \mathcal{B}$.

Proof. Define the language $\mathcal{L}^* = \mathcal{L} \cup \mathcal{L}_A \cup \{c\}$, where $\mathcal{L}_A$ contains a constant for each element in the domain $A$ of $\mathcal{A}$ and $c$ is a new constant symbol. Then $\mathcal{L}^*$ is still countable. Now consider the $\mathcal{L}^*$-theory $$ T = \operatorname{Diag_{el}}(\mathcal{A}) \cup \{c \neq a : a \text{ is a constant in } \mathcal{L}_A \}. $$ By compactness $T$ is satisfiable, so there is a model $\mathcal{C} \models T$. By downward Löwenheim-Skolem we find an $\mathcal{L}^*$-elementary substructure $\mathcal{B}$ of $\mathcal{C}$ with cardinality $|\mathcal{L}^*|$. That is, $\mathcal{B}$ is countable. Furthermore, we do have $\mathcal{C} \models \operatorname{Diag_{el}}(\mathcal{A})$ and as $\mathcal{B}$ is an $\mathcal{L}^*$-elementary substructure we thus also get $\mathcal{B} \models \operatorname{Diag_{el}}(\mathcal{A})$, and so $\mathcal{A} \preceq \mathcal{B}$ as $\mathcal{L}$-structures. Finally, the constant $c$ yields some element in $\mathcal{B}$, which we will also call $c$, that is not equal to any of the elements in $\mathcal{A}$. So we do indeed have that $\mathcal{B}$ is a countable proper elementary extension of $\mathcal{A}$.

Related Question