# Non-isomorphic countable models of $\text{Th }(\mathbb{R},<, I)$

I want to show that the theory $$\text{Th } (\mathbb{R},<,I)$$ is not $$\aleph_0$$-categorical where $$I$$ is a unary relation which describes whether a variable is an integer or not.

Clearly we have that $$(\mathbb{Q},<,I)$$ is a model of the theory since $$(\mathbb{Q},<)\cong(\mathbb{R},<)$$ and $$\mathbb{Q}$$ contains all the same integers that $$\mathbb{R}$$ contains.

I wanted to axiomitize the theory using the typical unbounded DLO axioms plus, $$\neg \forall a\forall b (Ia\wedge Ib \wedge a Call this axiomitization $$\Sigma$$.

I was then thinking that I would create an extended language $$\mathcal{L}'$$ which includes countably infinite new constants $$c_1,c_2,c_3,\dots$$. In this extended language I would then consider the set of sentences $$\Sigma\cup \Phi$$ where $$\Phi=\{ \phi_n : n\in\mathbb{N}\}$$ and $$\phi_n \quad : \exists a \exists b (Ia \wedge Ib \wedge a Since for each $$n\in\mathbb{N}$$, we have a model of $$\Sigma\cup\phi_n$$, we conclude by compactness that $$\Sigma\cup\Phi$$ has a model.

By downward L.S., we have a countable model. Call this $$\mathfrak{D}'$$ When we restrict the $$\mathfrak{D}'$$ back to the original language, this should be a model of $$\text{Th }(\mathbb{R},<,I)$$. However, it is not isomorphic to $$(\mathbb{Q},<,I)$$ since those constants $$c_1,c_2,c_3,\dots \in |\mathfrak{D}|$$.

I believe that the satisfaction of $$\Sigma\cup\Phi$$ by $$\mathfrak{D}'$$ means that we have for some two integers, those two integers are separated by infinitely many other integers. Therefore, in the restriction of $$\mathfrak{D}'$$ back to the original language, $$\mathfrak{D}$$ still satisfies this property although we cannot pick out those constants $$c_1,c_2,c_3,\dots$$ explicitly any longer.

My questions are:

1. Is this the correct approach that I am taking to answer this problem?
2. Is $$\Sigma$$ the correct axiomitization of $$\text{Th }(\mathbb{R},<,I)$$? And is $$\Phi$$ the correct axiomitization to use the compactness theorem on?
3. How would I be able to express more rigorously that the satisfaction of $$\Sigma\cup\Phi$$ shows we have two integers infinitely far apart (if this is indeed what it's satisfaction demonstrates) (and hence have a model of the theory not isomorphic to $$(\mathbb{Q},<,I)$$?
• Maybe this works better: Let $\mathfrak{D}$ be a countable model of the theory$\text{Th }(\mathbb{R},<,Z)$. Extend the language by a single constant $c$. Then consider the following axioms: $\Phi = \{\phi_n : n\in\mathbb{N}\}$ where $\phi_n$ is $Ic \wedge Im_n \wedge m_n < c$. If we define $c=\max{m_1,m_2,\dots,m_n}$, then $(\mathfrak{D},c)$ is a model of each finite subset of $\Phi$. In turn, we have a model for the entire axiomitization by compactness. Then, for any variable $v\in|\mathfrak{D}|$, $v$ is $\infty$-far from $c$. Restricting back to the original language, this is still true. Commented May 30 at 2:15

Clearly we have that $$(\mathbb{Q},<,I)$$ is a model of the theory since $$(\mathbb{Q},<)\cong (\mathbb{R},<)$$ and $$\mathbb{Q}$$ contains all the same integers that $$\mathbb{R}$$ contains.

This argument is incorrect. For one thing, $$(\mathbb{Q},<)\not\cong (\mathbb{R},<)$$, since they have different cardinalities. But maybe you meant to write $$(\mathbb{Q},<)\equiv (\mathbb{R},<)$$. In this context, the symbol $$\cong$$ means "isomorphic" and the symbol $$\equiv$$ means "elementarily equivalent".

But in general, even if $$M\preceq N$$ (i.e., $$M$$ is an elementary substructure of $$N$$, which is stronger than $$M\subseteq N$$ and $$M\equiv N$$), and $$P$$ is a unary relation symbol such that $$P^N\cap M = P^M$$, this does not imply that $$(M,P)\equiv (N,P)$$.

For example, let $$Q$$ be a unary relation symbol interpreted as the set of rational numbers. Then $$(\mathbb{Q},<)\preceq (\mathbb{R},<)$$, and $$\mathbb{Q}$$ contains all the rational numbers that $$\mathbb{R}$$ contains, but $$(\mathbb{Q},<,Q)\not\equiv (\mathbb{R},<,Q)$$. They disagree about the truth of the sentence $$\forall x\, Q(x)$$.

In fact, it is true that $$(\mathbb{Q},<,I)$$ is an elementary substructure of $$(\mathbb{R},<,I)$$. This can be proved by the Tarski-Vaught test, or by EF games, or by eliminating quantifiers in a suitable expansion of the language.

But it turns out that we don't need to prove this to solve the problem!

I wanted to axiomatize the theory using the typical unbounded DLO axioms plus, $$\neg \forall a\forall b \left((Ia\wedge Ib \wedge a

This theory is not sufficient to axiomatize the complete theory of $$(\mathbb{R},<,I)$$. Your extra axiom merely asserts that $$I$$ is not densely ordered. For example, if $$I' = [0,1)\cup \{2,3\}\subseteq \mathbb{Q}$$, then $$(\mathbb{Q},<,I')$$ satisfies your axioms (since $$I'$$ is not densely ordered), but it is clearly not elementarily equivalent to $$(\mathbb{R},<,I)$$.

An axiomatization of the complete theory of $$(\mathbb{R},<,I)$$ is given by:

• $$<$$ is a dense linear order without endpoints
• The restriction of $$<$$ to $$I$$ is a discrete linear order without endpoints (meaning that every element has an immediate successor and an immediate predecessor)
• $$\forall x\, \exists y\,\exists z\, (I(y)\land I(z)\land y.

But it turns out that we don't need to find an axiomatization of this theory to solve the problem!

Let $$T = \mathrm{Th}(\mathbb{R},<,I)$$. The easiest way to show that $$T$$ is not $$\aleph_0$$-categorical is using the Ryll-Nardzewski characterization of $$\aleph_0$$-categorical theories (see Wikipedia).

Let $$\varphi_1(x,y)$$ be the formula $$I(x)\land I(y)\land x. This formula asserts that $$x$$ and $$y$$ are integers and $$y = x+1$$.

For each $$n>1$$, let $$\varphi_n(x,y)$$ be the formula $$\exists z_0,\dots,z_n\left(z_0 = x\land z_n = y\land \bigwedge_{i=0}^{n-1} \varphi_1(z_i,z_{i+1})\right)$$. This formula asserts that $$x$$ and $$y$$ are integers and $$y = x+n$$.

Now if $$T$$ were $$\aleph_0$$-categorical, then there would be only finitely many formulas in the $$2$$ free variables $$x$$ and $$y$$, up to equivalence in models of $$T$$. But the formulas $$\varphi_n$$ are pairwise non-equivalent (since they define different subsets of $$\mathbb{R}^2$$). So $$T$$ is not $$\aleph_0$$-categorical.

Here is another approach, following the compactness idea you suggested:

Let $$(M,<,I)\preceq (\mathbb{R},<,I)$$ be a countable elementary substructure (by Löwenheim-Skolem). Since $$I^M$$ is a subset of $$\mathbb{Z}$$, any two elements of $$I^M$$ are just finitely many steps apart. Now consider the partial type $$\{I(x),I(y),x. Here the formulas $$\varphi_n$$ are defined as above. This type is consistent by compactness, so it is realized in some countable model $$N\models T$$. But if the type is realized by $$a,b\in N$$, then $$a,b\in I^n$$ and $$a$$ and $$b$$ are not just finitely many steps apart. Thus $$N\not \cong M$$, and $$T$$ is not $$\aleph_0$$-categorical.

• So in your last example why do we know that $N\models T$? Wouldn't we need to add the axioms for $\text{Th }(\mathbb{R},<,Z)$ and then apply compactness to guarantee this result? Commented Jun 2 at 23:28
• And thank you for the detailed reply Commented Jun 2 at 23:34
• @Justanotherstudent Yes, when I wrote "consistent" I implicitly meant "consistent with $T$" (in order to get the type realized in a model of $T$). If $\Sigma(x,y)$ is the partial type, we can use compactness to show that $\Sigma(x,y)\cup T$ is consistent. Note that we don't need to know any explicit axiomatization for $T$ to make this argument work! Commented Jun 2 at 23:56

Here's another approach to prove it (which is more work but yields a useful lemma):

Suppose I have a pair of elementarily equivalent structures $$\mathcal{A}=(A;...),\mathcal{B}=(B;...)$$ in the same relational language $$\Sigma$$, and $$\mathcal{X}=(X;...)$$ is a structure in a relational language $$\Pi$$ disjoint from $$\Sigma$$. I can form two new structures $$\mathcal{X_A}$$ and $$\mathcal{X_B}$$ by "replacing each point in $$\mathcal{A}$$ and $$\mathcal{B}$$ respectively by a copy of $$\mathcal{X}$$." Formally, we do the following:

• The structures $$\mathcal{X}_-$$ are in the language $$\Sigma\sqcup\Pi$$.

• The underlying set of $$\mathcal{X_A}$$ is $$X\times A$$, and similarly for $$\mathcal{X_B}$$.

• Each $$n$$-ary relation symbol $$R\in\Sigma$$ gets interpreted as $$\{\langle(x_1,a_1), ..., (x_n,a_n)\rangle: \langle a_1,...,a_n\rangle\in R^\mathcal{A}\}$$ in $$\mathcal{X_A}$$ and as $$\{\langle(x_1,b_1), ..., (x_n,b_n)\rangle: \langle b_1,...,b_n\rangle\in R^\mathcal{B}\}$$ in $$\mathcal{X_B}$$.

• Each $$k$$-ary relation symbol $$S\in\Pi$$ gets interpreted as $$\bigcup_{a\in A}\{\langle (x_1, a), ...,(x_k,a)\rangle: \langle x_1,...,x_k\rangle\in S^\mathcal{X}\}$$ in $$\mathcal{X_A}$$ and as $$\bigcup_{b\in B}\{\langle (x_1, b), ...,(x_k,b)\rangle: \langle x_1,...,x_k\rangle\in S^\mathcal{X}\}$$ in $$\mathcal{X_B}$$.

The key point is the following:

Using Ehrenfeucht-Fraisse games, we can show that $$\mathcal{X_A}\equiv\mathcal{X_B}$$.

(In fact we can even generalize this further, but let's ignore that for now.) Now each countable structure elementarily equivalent to $$(\mathbb{R};<,\mathbb{Z})$$ is "more or less" just $$\mathcal{X_A}$$ for $$\mathcal{X}=(\mathbb{Q};<)$$ and $$\mathcal{A}$$ some countable model of the theory of discrete linear orders without endpoints (using a different symbol, say $$\triangleleft$$, for the linear order here). Any pair of non-isomorphic-but-elementarily-equivalent countable models of the latter theory (e.g. $$\mathbb{Z}$$ and $$\mathbb{Z}+\mathbb{Z}$$) yield examples of what you're searching for.

• Also, was there anything wrong with my original approach to this question? Was either candidate axiomitization to use for compactness (either in the question post or the comment) able to generate the desired model? I'm unfamiliar with E-F games, so ideally I'd like to adapt my original solution somehow Commented May 30 at 12:32