# A structure elementarily equivalent to $(\mathbb{N},0,\operatorname{S},<,+,\cdot)$

Given $\mathfrak{R} = (\mathbb{N},0,\operatorname{S},<,+,\cdot)$, Let $$\Sigma = \{ 0 < c, \operatorname{S}{0} < c, \operatorname{S}\operatorname{S}{0} < c, \ldots\}$$

By compactness theorem and Löwenheim–Skolem theorem, we claim that $\Sigma\cup \operatorname{Th}{\mathfrak{R}}$ has a countable model($\operatorname{Th}{\mathfrak{R}}$ means the set of all theorems of $\mathfrak{R}$),which is: $$\mathfrak{M} = (|\mathfrak{M}|,0^{\mathfrak{M}},S^{\mathfrak{M}},<^{\mathfrak{M}},+^{\mathfrak{M}},\cdot^{\mathfrak{M}},c^{\mathfrak{M}})$$

Let $\mathfrak{M}_0$ be the restriction of $\mathfrak{M}$to the original language:$$\mathfrak{M}_0 = (|\mathfrak{M}|,0^{\mathfrak{M}},S^{\mathfrak{M}},<^{\mathfrak{M}},+^{\mathfrak{M}},\cdot^{\mathfrak{M}})$$

I'm confused as to why they're elementarily equivalent. It seems to me there isn't a infinite number in $\mathfrak{R}$, but there's one in $\mathfrak{M}_0$. Isn't the case that $\nvDash_{\mathfrak{R}} \exists{x} \forall{y}(y <x \to\operatorname{S}{y} < x)$ But $\vDash_{\mathfrak{M}_0} \exists{x} \forall{y}(y <x \to\operatorname{S}{y} < x)$?

Suppose $\phi$ is a formula on the original language.

If $R \vDash \phi$, then $\phi \in Th \mathfrak R$, and since $\mathfrak M \vDash Th \mathfrak R$, $\mathfrak M \vDash \phi$, and in particular, $\mathfrak M_0 \vDash \phi$
If $R \nvDash \phi$, then $\neg \phi \in Th \mathfrak R$, and since $\mathfrak M \vDash Th \mathfrak R$, $\mathfrak M \vDash \neg \phi$, and in particular, $\mathfrak M_0 \nvDash \phi$

You cannot express "is an infinite number" with the original language (nor with the added constant). Your sentence is actually false in $\mathfrak R$ because $x$ can be $0$. And even with the sentence $\phi : \exists x, x \neq 0 \land \forall y, (y < x \implies S y < x)$, this doesn't say "the model contains an infinite number", it says "there is a nonzero number that has no predecessor", which is false again in $\mathfrak M_0$, even though $c^\mathfrak M$ is "infinite".

Even better, you actually know that $\forall x, \exists y, x = y+y \lor x = y+y+1$ which says that every number is even or odd, (and that you can divide even numbers by 2), so the sentence "c is even or odd" is true in $\mathfrak M_0$, even though you don't know in which case $c$ is.

• Congratulations on the 10K, welcome to the club! – Asaf Karagila Apr 26 '13 at 16:26
• Additionally, if you could express "is an infinite number", you could also express "there is no infinite number". Now assume you add that to $\textrm{Th}\, \mathfrak{R}$. Every finite subset of $\Sigma$ would still be consistent with that extended theory, yet the whole of $\Sigma$ would not. Which, due to compactness, is of course impossible. – fgp Apr 26 '13 at 16:32

InGoldstern and Judah's The Incompleteness Phenomenon there is a discussion of what countable models of your axioms look like. They show they are $\Bbb {N + Q \times Z}$: a standard copy of $\Bbb N$ followed by a dense order of copies of the integers. It is still true that every element except $0$ has a predecessor, in fact that contributes to showing the upper pieces are like $\Bbb Z$

• Thank you very much for your answer. Why $\mathbb{N}+\mathbb{Z}$ is not the model that satisfies the axioms in the question? – Metta World Peace Apr 27 '13 at 3:15
• @MettaWorldPeace: It isn't simple. They define an equivalence relation ~ as $a \sim b$ if $b-a$ or $a-b$ is a standard natural. They show the classes are ordered and the order on the classes respects the order on the model. Then they show that as any element except $0$ has a predecessor, the classes are $\Bbb Z$ Finally, and this is where $\Bbb{N + Z}$ fails, any pair of elements (or increasing one of them by $1$) in different equivalence classes have an arithmetic mean. No element of $\Bbb {N+Z}$ satisfies that if $a \in \Bbb N$ and $b \in \Bbb Z$ – Ross Millikan Apr 27 '13 at 4:00

Your new model $\frak{M}$ can't just say that there's one infinite element. It has to make sure that that new infinite element satisfies all the normal things from $\frak{R}$. Your construction only guaranteed that $\frak{M}$ would have a $c$ realizing $\Sigma$, not that it would be the only new element in $\frak{M}$. In particular, this new element in $\frak{M}$ must have successors and predecessors as well (since it's not the $0$ element). So while $\not\vDash_{\frak{R}} \exists x \forall y (y < x \rightarrow Sy < x)$, neither does $\frak{M}$ since $c$ must also have predecessors.

Note that ${\frak M}_0$ does not satisfy the property that you mention. Compactness argument gives us that there is some $c$ that is larger than all the standard integers. But this $c$ has a successor as well.

Being "truly finite" is not expressible in a first-order formula, it's a schema.