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

Question

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.

Answer 1

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}$.