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

Question

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<b) \rightarrow \exists x(Ix \wedge a<x \wedge x<b)$$ 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<b) \rightarrow (\bigwedge_{n}Ic_i \wedge a<x_1 \bigwedge_{1\leq i <n} x_i<x_{i+1} \wedge x_n<b)$$ 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)$?

Answer 1

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<b) \rightarrow \exists x(Ix \wedge a<x \wedge x<b)\right)$$

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<x<z)$.

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<y\land \lnot \exists z\, (I(z)\land x<z\land z<y)$. 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<y\}\cup \{\lnot \varphi_n(x,y)\mid n\geq 1\}$. 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.

Answer 2

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.