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:
Using a very similar approach we can prove something more general that might actually be conceptually easier.
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}$.