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

Question

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)$?

Answer 1

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

Answer 2

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.

Answer 3

(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$