# Can $(\Bbb N,\leq)$ have an $\aleph_0$-categorical theory (in a larger language)?

One of the nicer consequences of compactness is that there is no statement in first-order logic whose content "$\leq$ is a well-order". So we can show that there are countable structure $(M,\leq)$ which are elementarily equivalent to $\Bbb N$, but not isomorphic to it.

What about adding $S,+,\cdot$ and $0$? Well. Also not very good. The theory of the structure $(\Bbb N,0,S,+,\cdot,\leq)$ has $2^{\aleph_0}$ non-isomorphic countable models. This shows that none of these additions get us any closer to finding an $\aleph_0$-categorical theory for $\Bbb N$.

Question. Is there a finite (or countable if needed) first-order language which includes $\leq$, and an $\aleph_0$-categorical theory $T$ whose countable structure is order isomorphic to $(\Bbb N,\leq)$?

• For Super Bonus Points: Have $T$ decidable! – Asaf Karagila Jun 23 '14 at 17:33

Take countably many functions and relations on $\mathbb{N}$. Add a symbol for each, together with all sentences that are true in $\mathbb{N}$ under the natural interpretation. Let the resulting theory be $T$. In the usual way we can use the Compactness Theorem and Downward Loweheim-Skolem to find a countable model of $T$ that is not isomorphic to $\mathbb{N}$.

• Yeah, that's what I had in mind when I wrote the comment to Clive's answer. Add the entire diagram of the structure, and then use compactness to produce a non-isomorphic model. Thanks! – Asaf Karagila Jun 23 '14 at 17:47
• (In fact one can say even more, if $M$ is a countably infinite structure in which every element is definable, then there is no extension of the language in which $M$ has a categorical theory.) – Asaf Karagila Jun 23 '14 at 18:01

My model theory's a bit rusty, but I believe no such theory exists.

Since $T$ is countable, it is $\aleph_0$-categorical if and only if $|D_n(T)| < \aleph_0$ for all $n < \omega$, where $D_n(T)$ is the set of all complete $T$-types with $n$ free variables.

Let $\varphi_m(x) \equiv \exists^{=m} y(y \le x \wedge y \ne x)$ be the (first-order) formula asserting that $x$ has exactly $m$ predecessors. Since $T \cup \{\exists x\varphi_m(x) \}$ is consistent for each $m$ we can expand $\{\varphi_m(x)\}$ to a complete type $p_m(x) \in D_1(T)$. And moreover $p_m(x) \ne p_{m'}(x)$ whenever $m \ne m'$ since $\exists x[\varphi_m(x) \wedge \varphi_{m'}(x)]$ is clearly inconsistent.

So $\{ p_m(x) : m < \omega \} \subseteq D_1(T)$ and $|D_1(T)| \ge \aleph_0$. So $T$ cannot be $\aleph_0$-categorical.

• My model theory is apparently rustier than yours. And it seems that despite thinking about this for a few days, your post made me realize that one can make compactness/Lowenheim-Skolem arguments to show otherwise (which are similar to your answer, I think). – Asaf Karagila Jun 23 '14 at 17:41
• Sure, my solution is probably overkill. – Clive Newstead Jun 23 '14 at 17:42
• I'll give it some time. If no one posts the solution I had in mind, I'll post it later. Thanks! EDIT: Andre posted that. – Asaf Karagila Jun 23 '14 at 17:44

(After Clive answered, I realized that the answer is simple. I'm posting my own version, which is somewhat a generalized and expanded version of Andre's answer as I pointed in the comments thereof.)

Theorem. Suppose that $M$ is a countable structure for a countable language $\cal L$ that every element in $m$ is definable, then there is no extension $\cal L\subseteq L'$ such that the theory of $\operatorname{Th}_{\cal L'}(M)$ is $\aleph_0$-categorical.

Proof. Since every element of $M=\{m_n\mid n\in\Bbb N\}$ is definable, add to $\cal L$ countably many constant symbols $c_n$ and axioms which include $\varphi_n(c_n)$ (where $\varphi_n$ is the formula defining $m_n$), and the complete diagram of $M$ in $\cal L$.

Then $M$ is a model of the expanded language and the larger theory. Consider any $\cal L'$ which extends $\cal L$, with the added constant symbols and the axioms. By many theorems there exists an uncountable model of $T=\operatorname{Th}_{\cal L'}(M)$, pick $m$ in the uncountable model which is not any of the constant symbols, and consider the elementary submodel generated by $m$. Then this model satisfies the same theory as $M$, but is not isomorphic to it for obvious reasons.

Finally, forget about the additional constant symbols. $\qquad\square$

• This is quite annoying. It's the second time I had spent a good week or so thinking about something, and only after posting it and receiving a quick answer I realized that I knew the answer all along. At least this time there's a point in posting my own answer. – Asaf Karagila Jun 24 '14 at 3:22