9
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Asaf Karagila Jun 23 '14 at 17:47
  • $\begingroup$ (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.) $\endgroup$ – Asaf Karagila Jun 23 '14 at 18:01
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Asaf Karagila Jun 23 '14 at 17:41
  • $\begingroup$ Sure, my solution is probably overkill. $\endgroup$ – Clive Newstead Jun 23 '14 at 17:42
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jun 23 '14 at 17:44
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jun 24 '14 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.