2.1

Here are some facts to keep in mind.

• • The component of $y\in Y$ is the union of all connected sets containing y (and similarly for path components).

• • The quasicomponent of $y\in Y$ is the intersection of all clopen sets containing y.

• • If X is a component or a quasicomponent of Y, then X is closed.

• • If Y is locally connected, then its quasicomponents and its components are the same.

• • If Y is locally path connected, then its path components and its components are the same (which in turn are the same as its quasicomponents).

• • If Y has a countable basis at $y\in Y$ consisting of connected sets and $Y\setminus \{y\}$ is locally path connected, then Y is locally path connected.

Proof of Proposition 1.6 This is mostly just an exercise, so we give only an outline.

(1) $\Rightarrow $ (2). Let $\mathfrak R$ be locally o-minimal. Let $E\subseteq \mathbb R^n$ be bounded and definable. We contend that the expansion of $(\mathbb R,<)$ by all definable subsets of E is o-minimal. By the Bolzano–Weierstrass Theorem, every bounded subset of $\mathbb R$ definable in $\mathfrak R$ is a finite union of points and open intervals. Thus, there is an open interval $I\subseteq \mathbb R$ such that the expansion of $(I,<)$ by all subsets of E definable in $\mathfrak R$ is o-minimal. It is now routine to see that the expansion of $(\mathbb R,<)$ by all definable subsets of E is also o-minimal.

(2) $\Rightarrow $ (3). Recall the proof of Proposition 1.1.

(3) $\Rightarrow $ (4) is just topology, and (4) $\Rightarrow $ ((5) & (6)) is trivial.

(5) $\Rightarrow $ (7). If $E\subseteq \mathbb R$ has empty interior and a limit point c, then

$$ \begin{align*} (E\setminus\{c\}\times [0,1])\cup \{(c,1)\}\cup (\mathbb R\times \{0\}) \end{align*} $$

is connected, but not path connected.

(6) $\Rightarrow $ (7). If $E\subseteq \mathbb R$ has empty interior and a limit point c, then $\{(c,0),(c,1)\}$ is a quasicomponent of its union with $(E\setminus \{c\})\times [0,1]$ .

(7) $\Rightarrow $ (1). The boundary of every definable subset of $\mathbb R$ is closed and discrete.

Proof of Proposition 1.5 Suppose that $\mathfrak R$ defines $\mathbb N$ and is PCC, CC or QCC. We show that $\mathfrak R$ defines $\mid $ . For $d\in \mathbb N$ , put $d\mathbb N:=\{\, dn: n\in \mathbb N\,\}$ . As $a\mid b$ if and only if $b\mathbb N\subseteq a\mathbb N$ , it suffices to show that $\bigcup _{d\in \mathbb N}( \{d\}\times d\mathbb N)$ is definable.

First we show that each $d\mathbb N$ is definable. Let $\mathbb S_0$ be the intersection of the boundary of $(0,\infty )^3$ with the union of the boundaries of the boxes $(-n,n)^3$ , $0<n\in \mathbb N$ . Put $P=\{\, (x,0,z)\in \mathbb R^3: x,z>0\,\}$ . For $d\in \mathbb N$ , put

$$ \begin{align*} \mathbb{S}_d=\bigl(\mathbb S_0\setminus P\bigr) \cup \bigl((\mathbb S_0\cap P)+(d,0,0)\bigr) \cup \bigl([0,d]\times \{0\}\times \mathbb N^{>0}\bigr). \end{align*} $$

In words, $\mathbb {S}_d$ is the result of replacing $\mathbb S_0\cap P$ by shifting it d units in the positive x direction and then filling in the resulting gaps with the line segments $[0,d]\times \{0\}\times \{n\}$ , $n>0$ . (See Figure 1 for $d=2$ .) Observe that $\mathbb S_d$ is locally path connected, definable in $(\mathbb R,<,\mathbb N)$ and $(d,0,0)\in \mathbb S_d$ . Let $C_d$ be the component of $\mathbb S_d$ that contains $(d,0,0)$ ; then $C_d$ is also the path component and the quasicomponent that contains $(d,0,0)$ , and thus is definable. The intersection of $C_d$ with the positive x-axis is the set $\{\, (d(n+1),0,0):n\in \mathbb N\,\}$ . (See Figure 2 for $d=2$ .) As $C_d$ is definable, so is $d\mathbb N$ . Note that we could have obtained $d\mathbb N$ instead by first obtaining the set $\{\, dn+1: n\in \mathbb N\,\}$ , which is the intersection of the positive x-axis with the component of $\mathbb S_d$ that contains $(1,0,0)$ .

Figure 1

$\mathbb S_2$ near the origin.

Figure 2

$C_2$ near the origin.

Let $+{\restriction } \mathbb N^2$ denote addition on $\mathbb N$ , regarded as a subset of $\mathbb R^3$ . Examination of the construction of the sets $\mathbb S_d$ yields that $\bigcup _{d\in \mathbb N}( \{d\}\times \mathbb S_d)$ is locally path connected and definable in $(\mathbb R,<,+{\restriction }\mathbb N^2)$ (because shifting by d units along the positive x-axis is uniformly definable). Let C be the component of $ \{\, (t,1,0,0): t\in \mathbb R\,\}\cup \bigcup _{d\in \mathbb N}( \{d\}\times \mathbb S_d) $ that contains $(1,1,0,0)$ . Again, C is also the path component and the quasicomponent that contains $(1,1,0,0)$ , and thus is definable. Observe that $ C\cap \{\, (j,k,0,0): j,k\in \mathbb N\,\}=\bigcup _{d\in \mathbb N}\{\, (d,dn+1,0,0): n\in \mathbb N\,\}. $ Thus, $\bigcup _{d\in \mathbb N}(\{d\}\times \{\, dn+1: n\in \mathbb N\,\})$ is definable, yielding that $\bigcup _{d\in \mathbb N}( \{d\}\times d\mathbb N)$ is definable (as was to be shown). Hence, in order to finish the proof, it suffices to show that $\{\, (a,b,c)\in \mathbb N^3: a\leq b\And a+b=c\,\}$ is definable (as then $+{\restriction }\mathbb N^2$ is also definable).

Let $\chi $ denote the characteristic function of the set of odd natural numbers as a subset of $\mathbb R$ . For each $m,n\in \mathbb N$ with $m\leq n$ , let $\varGamma _{m,n}$ be the union of the images of the paths

$$ \begin{align*} t\mapsto (m,n,t,\chi(m)t,\chi(n)t)\colon& [0,1]\to\mathbb R^5, \\ t\mapsto (t,n,1,\chi(m),\chi(n))\colon& [m,m+1]\to \mathbb R^5, \\ t\mapsto (m+1,t,1,\chi(m),\chi(n))\colon& [n,n+1]\to\mathbb R^5, \\ t\mapsto (m+1,n+1,t,\chi(m)t,\chi(n)t)\colon& [0,1]\to\mathbb R^5. \end{align*} $$

Each path is definable in $(\mathbb R,<)$ , and $\varGamma _{m,n}$ is definable in $(\mathbb R,<)$ , connected and compact. If $j,k\in \mathbb N$ and $j\leq k$ , then $\varGamma _{j,k}\cap \varGamma _{m,n}$ is equal to one of the following:

$$ \begin{align*} \emptyset, \varGamma_{m,n}, \{(m,n,0,0,0,0)\}, \{(m+1,n+1,0,0,0,0)\}. \end{align*} $$

It is perhaps helpful to regard the pair $(\chi (m),\chi (n))\in \{0,1\}^2$ as a color assigned to the projection of $\varGamma _{m,n}$ on the first three coordinates, and then to regard projections having different colors as being disjoint except possibly at the endpoints in the $xy$ -plane (see Figure 3). Hence, for each $d\in \mathbb N$ , $ \{d\}\times \bigcup _{k\in \mathbb N}\varGamma _{k,d+k} $ is the component of $ \{d\}\times \bigcup _{m,n\in \mathbb N}\varGamma _{m,n} $ that contains $(d,0,d,0,0,0)$ . Let L be the line in $\mathbb R^6$ containing both the origin and $(1,0,1,0,0,0)$ . Put $ E=L\cup \bigl (\mathbb N\times \bigcup _{m\leq n\in \mathbb N}\varGamma _{m,n}\bigr ) $ and note that E is definable in $(\mathbb R,<,\mathbb N,2\mathbb N)$ . Let D be the component of E that contains the origin. As before, D is definable. It is routine to see that $ L\cup \bigcup _{d,k\in \mathbb N} \bigl (\{d\}\times \varGamma _{k,d+k}\bigr ) $ is closed, contained in D, and open in D; thus, $ D=L\cup \bigcup _{d,k\in \mathbb N} \bigl (\{d\}\times \varGamma _{k,d+k}\bigr ) $ . If $(a,b,c)\in \mathbb N^3$ , then $(a,b,c,0,0,0)\in D$ if and only if $a\leq b$ and $c=a+b$ . Hence, $\{\, (a,b,c)\in \mathbb N^3: a\leq b\And a+b=c\,\}$ is definable, as was to be shown.

Note

We did not need PCC, CC or QCC per se, only that certain rather special kinds of path-connected subsets of certain rather special definable sets are definable. We discuss this further at the end of the paper.

Figure 3

The projection of $\varGamma _{m,n}$ on the first three coordinates.

Proof of Theorem 1.4 Let $\emptyset \neq A\subseteq \mathbb R$ have empty interior and $f\colon A\to A$ be strictly increasing and strictly dominating the identity. We find a strictly increasing $\sigma \colon \mathbb N\to \mathbb R$ such that every expansion of $(\mathbb R,<,f)$ that is PCC, CC or QCC also defines $\{\, (\sigma (m),\sigma (n)): m \mid n\,\}$ . Note that A cannot have a maximal element and there exists $a_0\in A$ such that $A\cap [a_0,\infty )$ is infinite. By replacing A with $A\cap [a_0,\infty )$ and f with its restriction to $A\cap [a_0,\infty )$ we reduce to the case that $\min A$ exists; for ease of notation, say $\min A=0$ . We obtain a subset S of $\mathbb R^3$ by repeating the construction of $\mathbb S_1$ (as in the proof of 1.5), but with A instead of $\mathbb N$ , and f instead of the successor function on $\mathbb N$ . Note that S is definable in $(\mathbb R,<,f)$ . Let P be the path component of S that contains $f(0)$ . Note that P is a component and a quasicomponent of S, and the intersection of P with $[0,\infty )\times \{0\}\times \{0\}$ is the orbit of f on $f(0)$ . Thus, it suffices to assume that A is the image of a strictly increasing function $\mathbb N\to \mathbb R$ and f is the successor function on A; then $\bigl ((-\infty ,\sup A),<,A\bigr )$ is isomorphic to $(\mathbb R,<,\mathbb N)$ and we apply Proposition 1.5 to finish.

Proof of Theorem 1.2 Let $\mathfrak R$ be an expansion of $(\mathbb R,<,+)$ by Boolean combinations of open sets. Suppose that $\mathfrak R$ is PCC, CC or QCC, but is not o-minimal. We find a strictly increasing $\sigma \colon \mathbb N\to \mathbb R$ such that $\{\, (\sigma (m),\sigma (n)): m \mid n\,\}$ is definable. It suffices by the proof of Theorem 1.4 to show that $\mathfrak R$ defines the range of a strictly increasing sequence in $\mathbb R$ . By Dougherty and Miller [Reference Dougherty and Miller4] and Dolich et al. [Reference Dolich, Miller and Steinhorn3], $\mathfrak R$ defines an infinite discrete $A\subseteq \mathbb R$ . If A is closed, then at least one of $A\cap [0,\infty )$ or $-A\cap [0,\infty )$ is the range of a strictly increasing sequence. Suppose now that A is not closed. Put $F=\overline {A}\setminus A$ ; then F is nonempty, has no interior, and is closed (because A is locally closed).

Suppose that F has no isolated points; then there exists $N\in \mathbb N $ such that $F\cap [-N,N]$ is a Cantor set. The set of negatives of lengths of the maximal open intervals of $[-N,N]\setminus F$ is definable and the range of a strictly increasing sequence of real numbers.

Suppose that F has an isolated point c. Let $x,y\in \mathbb R$ be such that $F\cap (x,y)=\{c\}$ . As c is a limit point of A, at least one of $A\cap (x,c)$ or $A\cap (c,y)$ is infinite and discrete; assume the former (the latter is similar). By increasing x, we have that $A\cap (x,c)$ is the range of a strictly increasing sequence (because $A\cap (x,c)$ has no limit points in $(x,c)$ ).

Remark. The last paragraph of the proof does not require the group structure.

We now begin to work toward the proof of Proposition 1.8.

2.2

Let $\mathfrak R_0$ be an o-minimal expansion of $(\mathbb R,<,+)$ such that every bounded set definable in $\mathfrak R$ is definable in $\mathfrak R_0$ . Let $E\subseteq \mathbb R^n$ be connected and definable in $\mathfrak R$ . Let $x,y\in E$ . Then there is a path in E definable in $\mathfrak R_0$ joining x to y.

For the remainder of this section, our approach will be more model theoretic than our earlier material. In particular, we use both “expansion” and “reduct” in the traditional first-order syntactic sense, “quantifier-free definable” means “defined by a quantifier-free formula of the language under consideration,” and “QE” abbreviates “quantifier elimination.”

Let $T_{\mathbb Q}$ be the theory of ordered $\mathbb Q$ -vector spaces with a distinguished positive element, in the language $L_{\mathbb Q}:=\{\, <,+,0,1\,\}\cup \{\, \lambda _q: q\in \mathbb Q\,\}$ , where $0<1$ and $\lambda _q$ is intended to indicate left scalar multiplication by q. Let $\left \lfloor \phantom {x}\right \rfloor $ be a new unary function symbol and put $L_{\mathbb Q}'=L_{\mathbb Q}\cup \{\left \lfloor \phantom {x}\right \rfloor \}$ . Let $T_{\mathbb Q}'$ be the union of $T_{\mathbb Q}$ and the universal closures of the following:

• • $\left \lfloor \left \lfloor x\right \rfloor +y\right \rfloor =\left \lfloor x\right \rfloor +\left \lfloor y\right \rfloor $ ,

• • $0\leq x<1\rightarrow \left \lfloor x\right \rfloor =0$ ,

• • $\left \lfloor 1\right \rfloor =1$ ,

• • $\left \lfloor x\right \rfloor \leq x<\left \lfloor x\right \rfloor +1$ .

Observe that as $T_{\mathbb Q}$ is universally axiomatizable, so is $T_{\mathbb Q}'$ . By [Reference Miller12, Appendix], $T_{\mathbb Q}'$ has QE and is complete.Footnote ¹ It is easy to see that $(\mathbb R,<,+,\mathbb N)$ is $\emptyset $ -interdefinable with $ (\mathbb R,<,+,0,1, (q.x)_{q\in \mathbb Q},\left \lfloor \phantom {x}\right \rfloor ) $ , where $\left \lfloor \phantom {x}\right \rfloor $ denotes the usual “floor” function $t\mapsto \max (\mathbb Z\cap (-\infty ,t])$ for $t\in \mathbb R$ . Thus, $\operatorname {\mathrm {Th}}(\mathbb R,<,+,\mathbb N)$ is bi-interpretable with $T_{\mathbb Q}'$ . It is more convenient to prove Proposition 1.8 by working over $(\mathbb R,<,+,\mathbb Z)$ instead of $(\mathbb R,<,+,\mathbb N)$ .

Let $\mathfrak Z$ be a structure on $\mathbb Z$ in a language $L_{\mathfrak {Z}}$ such that:

• • $L_{\mathfrak {Z}}$ has no function or constant symbols;

• • there is a symbol $Z\in L_{\mathfrak Z}$ that is interpreted as $\mathbb Z$ in $\mathfrak Z$ ;

• • $\operatorname {\mathrm {Th}}(\mathfrak Z)$ has QE;

• • $\mathfrak Z$ defines $<$ and $\mid $ (hence also all arithmetic sets).

Put $L=L_{\mathbb Q}'\cup L_{\mathfrak Z}$ and $ T=T_{\mathbb Q}'\cup \{\forall x\,(Zx \leftrightarrow \left \lfloor x\right \rfloor =x)\}\cup \{\, \sigma ^Z: \sigma \in \operatorname {\mathrm {Th}}(\mathfrak Z)\,\} $ , where $\sigma ^Z$ denotes the relativization of $\sigma $ to Z (see, e.g., [Reference Chang and Keisler2] for a definition). We will show that T has QE. The proof is an extension of that of the corresponding result for $T_{\mathbb Q}'$ , but the added complication justifies outlining some details. We begin by disposing of a number of routine technical observations and lemmas (the proofs of which we leave mostly to the reader). Unless indicated otherwise, “term” means “L- term.”

Every term is a finite composition of $\left \lfloor \phantom {x}\right \rfloor $ and $L_{\mathbb Q}$ -terms. Every finite composition of $\lfloor \phantom {x}\rfloor $ is T- equivalent to $\left \lfloor \phantom {x}\right \rfloor $ . Every $L_{\mathbb Q}$ -term in variables $x_1,\dots ,x_n$ is $T_{\mathbb Q}$ -equivalent to one of the form $\sum _{i=1}^n\lambda _{q_i}x_i+\lambda _{q_0}1$ for some $n\in \mathbb N$ and $q_1,\dots ,q_n\in \mathbb Q$ ; we tend to write $ \sum _{i=1}^nq_ix_i+q_0 $ instead of $ \sum _{i=1}^n\lambda _{q_i}x_i+\lambda _{q_0}1 $ . If $\tau _1$ and $\tau _2$ are $L_{\mathbb Q}$ -terms in variables $x_1,\dots ,x_n$ , then there is an $L_{\mathbb Q}$ -term $\sigma $ in the same variables such that

$$ \begin{gather*} T_{\mathbb Q}\vdash \tau_1x_1\cdots x_n=\tau_2x_1\cdots x_n \leftrightarrow \sigma x_1\cdots x_n=0,\\ T_{\mathbb Q}\vdash \tau_1x_1\cdots x_n<\tau_2x_1\cdots x_n \leftrightarrow \sigma x_1\cdots x_n<0. \end{gather*} $$

In what follows, we tend to let $\mathfrak B$ (allowing subscripts) denote an arbitrary model of T, with underlying set B (allowing corresponding subscripts). Let $Z(\mathfrak B)$ denote the interpretation of the symbol Z in $\mathfrak B$ . Note that $Z(\mathfrak B)=\{\, b\in B: \left \lfloor b\right \rfloor =b\,\}$ . We recall a lemma used in the proof of QE of $T_{\mathbb Q}'$ , restated for our current purposes, followed by some routine consequences.

2.3

For all $b\in Z(\mathfrak {B})$ and positive integers m there exists a unique ${i\in \{0,\dots , m-1\}}$ such that $ \frac 1m(b+i) \in Z(\mathfrak {B}) $ .

2.4

Let $n\geq 1$ and $\tau (x_1,\dots ,x_n)$ be a term.

1. 1. There is a finite partition $\mathcal C$ of $Z(\mathfrak B)$ into sets $\emptyset $ -definable in the reduct of $\mathfrak B$ to $L_{\mathfrak {Z}}$ such that, for each $C\in \mathcal C$ , there exist $q\in \mathbb Q$ and a term $\sigma (x_1,\dots ,x_{n-1})$ with $\tau =\sigma +qx_n$ on $B^{n-1}\times C$ . (More precisely: The restriction to $B^{n-1}\times C$ of the interpretation of $\tau $ in $\mathfrak B$ is equal to the restriction to $B^{n-1}\times C$ of the interpretation of $\sigma +qx_n$ in $\mathfrak B$ .)

2. 2. There is a finite partition $\mathcal C$ of $Z(\mathfrak B)$ into sets $\emptyset $ -definable in the reduct of $\mathfrak B$ to $L_{\mathfrak Z}$ such that, for each $C\in \mathcal C$ , there exist $q,r\in \mathbb Q$ and a term $\sigma (x_1,\dots ,x_{n-1})$ such that for all $(b,c)\in B^{n-1}\times C$ , if $\tau (b,c)\in Z(\mathfrak B)$ , then $\tau (b,c)=\sigma (b)+qc+r$ and both $\sigma (b)$ and $qc+r$ lie in $Z(\mathfrak B)$ .

3. 3. Let $m\leq n$ , $b\in B^m$ and D be the definable closure of b in the reduct of $\mathfrak B$ to $L_{\mathbb Q}'$ . There is a finite partition $\mathcal C$ of $[0,1)^{n-m}$ into sets that are D-definable in the reduct of $\mathfrak B$ to $L_{\mathbb Q}$ such that, for each $C\in \mathcal C$ , there exist $q_1,\dots ,q_{n-m}\in \mathbb Q$ and $d,e\in D$ with $\tau {\restriction } (\{b\}\times C)=\sum _{i=m+1}^{n}q_ix_i+d$ and $\left \lfloor \tau \right \rfloor {\restriction } (\{b\}\times C)=e$ .

We omit proofs. (Generally, proceed via 2.3 and induction on terms, noting that the interesting cases tend to be when $\tau $ is of the form $\left \lfloor \phi \right \rfloor $ .)

2.5

Every subset of $Z(\mathfrak B)^n$ that is quantifier-free definable in $(\mathfrak B, (b)_{b\in B})$ is definable in $(Z(\mathfrak B), (R(\mathfrak B))_{R\in L_{\mathfrak Z}})$ , where $R(\mathfrak B)$ is the interpretation of R in $\mathfrak B$ .

2.6

Let $Y\subseteq B^{m+n}$ be quantifier-free definable in $\mathfrak B$ and $(u,z)\in B^m\times Z(\mathfrak B)^n$ . Let D be the definable closure of $(u,z)$ in the reduct of $\mathfrak B$ to $L_{\mathbb Q}'$ . Then

$$ \begin{align*} \{\, x\in B^n: (u,x)\in Y\,\}\cap \prod_{i=1}^n[z_i,z_i+1) \end{align*} $$

is D-definable in the reduct of $\mathfrak B$ to $L_{\mathbb Q}$ .

2.7 T is complete and has QE

Proof of Proposition 1.8 Suppose that $\mathfrak R$ is an expansion of $(\mathbb R,<,+,\mid )$ by subsets of various $\mathbb N^n$ . By passing to an extension by definitions, we assume that $ \mathfrak R=(\mathbb R,<,+,0,1,(qx)_{q\in \mathbb Q},\left \lfloor \phantom {x}\right \rfloor ,\mathfrak Z) $ where $\mathfrak Z$ is the expansion of $\mathbb Z$ by all subsets of each $\mathbb Z^n$ that are $\emptyset $ -definable in $\mathfrak R$ . (Remark: By 2.5, every definable subset of any $\mathbb Z^n$ is $\emptyset $ -definable, and so $\mathfrak Z$ is equal to the structure induced on $\mathbb Z$ in $\mathfrak R$ .) By 2.7, $\operatorname {\mathrm {Th}}(\mathfrak R)$ has QE and is axiomatized by T. By QE and 2.6, every bounded set definable in $\mathfrak R$ is definable in $(\mathbb R,<,+)$ , i.e., Proposition 1.8.1 holds; then Proposition 1.8.2 is immediate via 2.2. It remains to show that $\mathfrak R$ is CC.

Let $E\subseteq \mathbb R^n$ be definable in $\mathfrak R$ . We must show that each component of E is definable. Let $m\in \mathbb N$ , $c\in \mathbb R^m$ and $X\subseteq \mathbb R^{m+n}$ be $\emptyset $ - definable in $\mathfrak R$ such that $E=\{\, e\in \mathbb R^n: (c,e)\in X\,\}$ . Via QE, 2.5, 2.1 and model-theoretic compactness, there exist

• • $N\in \mathbb N$ ,

• • sets $Y_1,\dots ,Y_N\subseteq \mathbb R^{m+n}$ that are $\emptyset $ - definable in $(\mathbb R,<,+,1)$ ,

• • maps $F_1,\dots ,F_N\colon \mathbb R^{m+n}\to \mathbb R^m$ that are $\emptyset $ - definable in $\mathfrak R$ .

such that, for each $z\in \mathbb Z^n$ , there exists $J\subseteq \{1,\dots ,N\}$ such that the sets

$$ \begin{align*} \{\, x\in\mathbb R^n: (F_j(c,z),x)\in Y_j\,\},\quad j\in J \end{align*} $$

partition $ E\cap \prod _{k=1}^n[z_k, z_k+1) $ into cells of $(\mathbb R,<,+)$ . The set of all $z\in \mathbb Z^n$ such that $\prod _{k=1}^n[z_k, z_k+1)$ intersects E is definable in $\mathfrak R$ , and the possible descriptions of the cells in $E\cap \prod _{k=1}^n[z_k, z_k+1)$ can be coded uniformly in z by subsets of $\{0,1\}^d$ for some $d\in \mathbb N$ . Thus, there exist $m\in \mathbb N$ and definable $S\subseteq \mathbb Z^m\times \mathbb R^n$ such that, letting A be the projection of S on the first m coordinates, the fibers $S_a$ ( $=\{\, e\in \mathbb R^n: (a,e)\in S\,\}$ ) of S over A partition E into connected sets that are each definable in $(\mathbb R,<,+)$ . As any expansion of $(\mathbb Z,<,\{0\})$ has Definable Choice, we reduce to the case that $a\mapsto S_a$ is injective. Let G be the set of all pairs $(a,b)\in A^2$ such that $ (S_a\cap \overline {S_b})\cup (S_b\cap \overline {S_a})\neq \emptyset $ ; then G is definable in $\mathfrak R$ , hence also in $\mathfrak Z$ . As $\mathfrak Z$ defines all arithmetic sets, each graph component of $(A,G)$ is definable in $\mathfrak Z$ . (To put this another way: Since G is computable from A, each graph component of $(A,G)$ is computably enumerable from A, hence definable in $(\mathbb Z,+,\cdot , A)$ .) It is an exercise (cf. [Reference van den Dries5, Chapter 3, (2.19).5]) to see that C is a graph component of $(A,G)$ if and only if $\bigcup _{a\in C}S_a$ is a component of E.

3.1

Let $\mathfrak R$ be an expansion of $(\mathbb R,<,+,1,\mathbb Z)$ by subsets of various $\mathbb Z^n$ . Then $\operatorname {\mathrm {Th}}(\mathfrak R)$ is axiomatized over the union of $\operatorname {\mathrm {Th}}(\mathbb R,<,+,1)$ and the relativization to $\mathbb Z$ of the theory of the structure induced on $\mathbb Z$ in $\mathfrak R$ by expressing that $(\mathbb Z,+,1)$ is a substructure of $(\mathbb R,+,1)$ and, for every $r\in \mathbb R$ , there is a unique $k\in \mathbb Z$ such that $k\leq r<k+1$ .

3.2

If $\mathfrak R_0$ is a reduct in the sense of definability of $(\mathbb R,<,+)$ over $(\mathbb R,<)$ , and $\mathfrak R$ is an expansion of $(\mathfrak R_0,\mathbb N)$ by subsets of various $\mathbb N^n$ , then $\mathfrak R$ is PCC, CC or QCC if and only if it defines $\mid $ .

(For the QE, replace $\mathfrak R_0$ with the expansion in the syntactic sense of $(\mathbb R,<,0,1)$ by all $\{0,1\}$ -definable functions of $\mathfrak R_0$ . Every such function is $\emptyset $ -definable in $({\mathbb R,<,} +,1)$ .)

3.3

Let G be a divisible additive subgroup of $\mathbb R$ containing $1$ and $\mathfrak G$ be an expansion of $(G,<,+,\mathbb Z)$ by subsets of various $\mathbb Z^n$ . If $\mathfrak G$ defines $\mid $ , then for all $E\subseteq G^n$ definable in $\mathfrak G$ and $x\in E$ , $\mathfrak G$ defines the set of $y\in E$ for which there is a definable-in- $(G,<,+)$ continuous map $\gamma \colon [a,b]\to E$ such that $\gamma (a)=x$ and $\gamma (b)=y$ .

(The appropriate analogue of 2.2 follows from [Reference van den Dries5, p. 100].)

We now return to a question hinted at in the introduction: To what extent does Proposition 1.5 depend on working over $\mathbb R$ ?

The notion of PCC is problematic in more general settings. The usual definition of “path” includes the requirement that the domain of a path be a compact subinterval of $\mathbb R$ , and in practice, one typically uses that $-x$ is an order-reversing bijection of $\mathbb R$ and all infinite compact intervals are definably isomorphic in the vector space $(\mathbb R,+,(rx)_{r\in \mathbb R})$ . We can get around this in some special settings. Let $(M,<)$ be a linear order. If $X\subseteq M^n$ , then we say that a path in X, relative to $(M,<)$ , is a continuous map f from an interval $[a,b]$ into $M^n$ such that $f([a,b])\subseteq X$ , and declare a piecewise path in X (relative to $(M,<)$ ) to be a finite sequence

$$ \begin{align*} \gamma:=(\gamma_1\colon [a_1,b_1]\to M^n,\dots,\gamma_{p+1}\colon [a_{p+1},b_{p+1}]\to M^n) \end{align*} $$

of paths in X (for some $p\in \mathbb N$ ) such that $\gamma _k(b_k)=\gamma _{k+1}(a_{k+1})$ for $k=1,\dots ,p$ . We say that $\gamma $ is injective if each $\gamma _j$ is injective and the images $\gamma ([a_1,b_1))$ , …, $\gamma ([a_{p},b_{p}))$ , $\gamma ([a_{p+1},b_{p+1}])$ are pairwise disjoint. The image of $\gamma $ is the union of the images of the $\gamma _k$ . We abuse terminology somewhat and say that X is path connected relative to $(M,<)$ if for all $u,v\in X$ there is a piecewise path $\gamma $ in X such that u and v are contained in the image of $\gamma $ . If the piecewise paths can be taken to be injective, then we say that X is injectively path connected relative to $(M,<)$ . Now fix an expansion $\mathfrak {M}$ of $(M,<)$ and $A\subseteq M$ . We can specialize these definitions to the notion “A-definable in $\mathfrak {M}$ ” in a mostly obvious fashion. (Some authors might require that X be A-definable in order to call it A- definably path connected relative to $\mathfrak {M}$ , but we do not.) If $A=M$ , then we omit mention of A. (Thus, definably path connected relative to $(\mathbb R,<,+,\cdot ,\mathbb N)$ is the same as path connected in the usual sense.) An examination of the proof of Proposition 1.5 yields the following technical result, thus establishing that working over $\mathbb R$ is not necessary if one is willing to modify a few definitions.

3.4

Let D be a dense subset of $\mathbb R$ that contains $\mathbb N$ . Let $A\subseteq D$ and $\mathfrak {D}$ be an expansion of $(D,<,\mathbb N)$ such that for all $E\subseteq F\subseteq D^7$ , if F is $\emptyset $ -definable in $(D,<,\mathbb N)$ and E is maximally $\emptyset $ -definably injectively path connected relative to $(D,<,(n)_{n\in \mathbb N})$ , then E is A-definable in $\mathfrak {D}$ . Then $\mid $ is A-definable in $\mathfrak {D}$ .

(A priori, the hypothesis is weaker than PCC for expansions of $(\mathbb R,<)$ . We leave nonarchimedean settings to the interested reader.)

As an application, we obtain the converse of 3.3, hence also the following extension of Theorem 1.9.

3.5

Let G be a divisible subgroup of $\mathbb R$ containing $1$ and $\mathfrak G$ be an expansion of $(G,<,+,\mathbb Z)$ by subsets of various $\mathbb Z^n$ . Then $\mathfrak G$ defines $\mid $ if and only if for all E definable in $\mathfrak G$ and $x\in E$ , $\mathfrak G$ defines the set of all $y\in E$ for which there is a definable-in- $(G,<,+)$ continuous map $\gamma \colon [a,b]\to E$ such that $\gamma (a)=x$ and $\gamma (b)=y$ .

As we have defined it, the notion of CC is of little use in more general settings, even for o-minimal expansions of dense linear orders. To illustrate, every expansion of a totally disconnected linear order is trivially CC. However, there is a natural generalization of the notion of CC to first-order topological structures (as defined in [Reference Pillay19]): Every definable set A should be a union of definable sets C that are maximal with respect to the property of not being disconnected by any pair of definable open sets. In [Reference van den Dries5], such sets C are called definably connected components of A (and are definable by definition).

In o-minimal structures, all definable sets are unions of finitely many definably connected components [Reference van den Dries5, p. 57]. But by QE of $\operatorname {\mathrm {Th}}(\mathbb R,<)$ , there is no piecewise path definable in $(\mathbb R,<)$ joining any point in $(-\infty ,1)\times (-\infty ,2)$ to the point $(1,2)$ . Thus, in $(\mathbb R,<)$ , the set $(-\infty ,1)\times (-\infty ,2)\cup \{(1,2)\}$ is path connected and definably connected, but not definably path connected relative to $(\mathbb R,<)$ .

Let $\mathfrak {M}$ be as before. Under any reasonable definition, M should be regarded as $\emptyset $ -definably injectively path connected in $\mathfrak {M}$ —but M need not be definably connected in $\mathfrak {M}$ , even if $(M,<)$ is densely ordered (say, if $\mathfrak {M}$ is weakly o-minimal, but not o-minimal). This failure of the fundamental topological fact that path connectedness implies connectedness invalidates many of the techniques used in our arguments over $(\mathbb R,<)$ . However, it is known that if $(M,<)$ is densely ordered and M is definably connected in $\mathfrak {M}$ , then the implication is essentially restored for definable data. Hence, we have the following corollary of 3.4, the proof of which we leave as an exercise (familiarity with some results in [Reference Miller12] will be needed).

3.6

Let D be a dense subset of $\mathbb R$ that contains $\mathbb N$ . Let $\mathfrak {D}$ be an expansion of $(D,<,\mathbb N)$ such that D is definably connected in $\mathfrak {D}$ and every definable set is a union of definably connected components. Then $\mid $ is definable in $\mathfrak {D}$ .

In particular, if $\mathfrak R$ is an expansion of $(\mathbb R,<,\mathbb N)$ such that every definable set is a union of definably connected components (an a priori weaker condition than CC), then $\mid $ is definable.

We leave any potential generalizations of QCC to the interested reader.