Assumption 3.7. D is a definable discrete set which is narrow and bounded below, and $\mathcal {R}$ is $\omega $ -saturated.

Proof. Suppose that no such l exists. Then by compactness we find $a \in X$ such that there are infinitely many $d \in D_a$ with $\gamma _{D_a}(d) \gg \delta $ . Let $\{d_i \, : \, i \in \omega \}$ list the first $\omega $ elements of D. By $\omega $ -saturation of $\mathcal {R}$ , there is an element $\varepsilon \in R$ such that

1. (1) for every $i \in \omega $ , $d_i < \varepsilon $ ; and

2. (2) there are infinitely many $d \in D_a$ such that $\gamma _{D_a}(d)> \varepsilon $ .

Let $F=\{x \in D_a : \gamma _{D_a}(x)\geq \varepsilon \}$ and notice that $F' \geq \varepsilon $ . Thus F and $D \cap [0, \varepsilon )$ are infinite discrete sets such that $D \cap [0,\varepsilon ]<F'$ , violating Theorem 2.14.

Proof. Suppose otherwise and let $C_i$ for $i \in \omega $ be distinct convex components of in . As $\mathcal {R}$ is assumed to be $\omega $ -saturated we may assume by compactness that $C_i<C_{i+1}$ for all $i \in \omega $ . We may find $a_i \in D \setminus E$ for $i \in \omega $ so that and so that $a_i \not \equiv e$ for any $e \in E$ .

Now let $b_i =\max \{e \in E : e<a_i\}$ for $i \in \omega $ . As and $\mathcal {R}$ is definably complete, $b_i$ exists; and as E is closed (by Fact 2.3), $b_i \in E$ . Note that $b_i$ is not maximal in E for any $i \in \omega $ as . We claim that $\gamma _E(b_i)>l \cdot \max {(D')}$ for all $i, l \in \omega $ . Suppose otherwise and that $\gamma _E(b_i) \leq l \cdot \max {(D)}$ for some $i,l \in \omega $ . But by choice of $b_i$ we must have that $S_E(b_i)>a_i$ . Hence $|a_i-b_i| \leq l \cdot \max {(D')}$ and so $a_i \equiv b_i$ but this violates our choice of $a_i$ . Thus for all $i, l \in \omega $ we have that $\gamma _E(b_i)>l \cdot \max {(D')}$ . But this violates Corollary 3.10.

Proof. First suppose that (1) fails. Let $N \in \omega $ . For $i \in \omega $ we may find $a_i \in D$ all lying on a single $\mathbb {Z}$ -chain so that

$$\begin{align*}\{S_D^{-N}(a_i), \dots, S^{-1}_D(a_i), a_i, S_D(a_i), \dots, S^N_D(a_i)\}\cap E = \emptyset\end{align*}$$

and $b_i \in E$ with $a_i<b_i<a_{i+1}$ for all $i \in \omega $ .

Then by compactness we find $a_i^* \in D$ for $i \in \omega $ so that $\{S^M_D(a_i^*) : M \in \mathbb {Z}\} \cap E = \emptyset $ and $b_i^* \in E$ so that $a_i^*<b_i^*<a_{i+1}^*$ . For each $i \in \omega $ we have that $|a_i^*-c|>l \cdot \min {(D')}$ for all $l \in \omega $ and any $c \in E$ . As D is narrow $a_i^* \not \equiv c$ for any $c \in E$ . Thus and furthermore but for all $i \in \omega $ . In particular each is in a distinct convex component of in violating Corollary 3.11

The proof of (2) is identical to that of (1) except that for each $N \in \omega $ we find $c_i \in E$ and $a_i \in D$ for $i \in \omega $ so that

$$\begin{align*}\{S_D^{-N}(a_i), \dots, S^{-1}_D(a_i), a_i, S_D(a_i), \dots, S^N_D(a_i)\}\cap E = \emptyset\end{align*}$$

with $a_i>c_i>a_{i+1}$ .

Now assume that (3) fails. As (1) and (2) hold, for each $N \in \omega $ we can find pairwise distinct $\mathbb {Z}$ -chains $Z_i$ of D and $ a_i \in Z_i$ for $i \in \omega $ so that

$$\begin{align*}\{S_D^{-N}(a_i), \dots, S^{-1}_D(a_i), a_i, S_D(a_i), \dots, S^N_D(a_i)\}\cap E = \emptyset\end{align*}$$

together with $b_i, c_i \in E \cap Z_i$ so that $c_i<a_i<b_i$ . We can assume that either the $Z_i$ are ordered so that $Z_i<Z_{i+1}$ for all $i \in \omega $ or that $Z_i>Z_{i+1}$ for all $i \in \omega $ . In the case that $Z_i<Z_{i+1}$ argue with $a_i, b_i$ exactly as in the proof of (1). In the case that $Z_i>Z_{i+1}$ argue with $a_i, c_i$ exactly as in the proof of (2).

Proof. For the purposes of this proof let us call a definable $E \subseteq D$ neat if we may find $M \in \mathbb {N}$ and $C_1, \dots , C_n$ closed intervals or rays satisfying conditions (1)–(8) of Proposition 3.8.

Notice that for clauses (6)–(8) in the statement of Proposition 3.8 the “moreover” portion will follow from the initial statements and Corollary 3.12. Hence to establish that a set is neat we need only produce the intervals or rays $C_1, \dots , C_n$ witnessing (1)–(8) in the definition of neat without the “moreover” clauses.

It is immediate that if $E=E_1 \cup \dots \cup E_l$ where the $E_i$ are definable, pairwise disjoint, and neat then E is neat.

Let $E \subseteq D$ be definable. By Corollary 3.11, has finitely many convex components. Let $H_j$ for $1 \leq j \leq k$ be the convex components of . We may pick $e_j,f_j \in D \cup \{\infty \}$ so that . Setting $E_j=[e_j,f_j) \cap E$ , to establish that E is neat it suffices to show that each $E_j$ is neat.

Thus fix $1 \leq j \leq k$ . If $E_j$ is finite then the result is immediate, hence we may assume that $E_j$ is infinite. Let $a =\min (E_j)$ , which exists as $E_j$ is bounded below. If $E_j$ is bounded above let $b=\max (E_j)$ . Let Z be any $\mathbb {Z}$ -chain so that $E_j \cap Z\not =\emptyset $ and $\mathcal {Z}(a)<Z<\mathcal {Z}(b)$ (if b exists). We claim that $E_j$ must be both cofinal and coinitial in Z. Suppose otherwise, then for any $N \in \omega $ we can find $c \in Z$ so that $\{S^{l}_D(c) : -N \leq l \leq N\} \cap E_j =\emptyset $ . By compactness we can then find another $\mathbb {Z}$ -chain $Z_0$ so that $\mathcal {Z}(a)<Z_0<\mathcal {Z}(b)$ (if b exists) and $Z_0 \cap E_j= \emptyset $ . But this violates the fact that is convex in . Hence $E_j$ is cofinal and coinitial in Z. Similarly we can conclude that $E_j$ is cofinal in $\mathcal {Z}(a)$ and coinitial in $\mathcal {Z}(b)$ (if b exists). Thus $C_1=[a,b]$ if b exists, or $C_1=[a, \infty )$ otherwise is a closed interval or ray witnessing that $E_j$ is neat.

Proof. Say $D' = \{\delta _1, \ldots , \delta _n\}$ where the $\delta _i$ are listed in increasing order. First we will give the proof of the existence of $m_0$ . By Lemma 3.9, there is some $l_0 \in \omega $ such that for any $a, b \in D$ , there are only finitely many $c \in P_{(a,b)}$ with $\gamma _{P_{(a,b)}}(c)\geq l_0 \cdot \delta _n$ . Since $\delta _1$ is Archimedean equivalent to $\delta _n$ , there is some $l \in \omega $ such that $l \cdot \delta _1 \geq l_0 \cdot \delta _n$ , and hence:

$(*)$ For any $a, b \in D$ , there are only finitely many $c \in P_{(a,b)}$ with $\gamma _{P_{(a,b)}}(c)\geq l \cdot \delta _1$ .

We claim that $m_0 = l$ works. Fix an $\omega $ -chain C and a natural number k and suppose that there are m distinct sequences ${\sigma }_1 \dots , {\sigma }_m$ of length k from $D'$ so that no $P_{{\sigma }_i}$ is bounded above in C. If there is a $\sigma _i$ such that the set

$$ \begin{align*}\{ a \in C \, : \, P_{{\sigma}_i} \cap \{a, S_D(a), \ldots, S_D^{l-1}(a)\} = \emptyset\}\end{align*} $$

is cofinal in C, then $P^{\prime }_{\sigma _i}$ contains infinitely many elements which are greater than or equal to $l \cdot \delta _1$ , contradicting statement $(*)$ above. Therefore for all sufficiently large $a \in C$ , each set $P_{{\sigma }_i}$ must intersect $\{a, S_D(a), \dots , S_D^{l-1}(a)\}$ . Since the sets $P_{\sigma _1}, \ldots , P_{\sigma _m}$ are pairwise disjoint, this implies that $m \leq l$ , as we wanted.

The same proof, mutatis mutandis, shows the existence of $m_1$ .

Proof. Suppose that $f_\tau (k) \leq M$ for every $k \in \omega $ . Note that since $D'$ is finite, it follows from the Pigeonhole Principle that every infinitely-recurring sequence of length k in $\tau $ can be extended to at least one infinitely-recurring sequence of length $k+1$ in $\tau $ . Hence

$$ \begin{align*}f_\tau(k) \leq f_{\tau}(k+1),\end{align*} $$

that is, the function $f_\tau $ is nondecreasing. By the hypothesis that values of $f_\tau $ are bounded above by some M, there is $k \in \omega $ for which $f_\tau (k) = f_\tau (k+1)$ .

Now fix some k as in the conclusion of the Claim above. Hence if $\sigma $ is any length-k subsequence of $\tau $ , it has a unique length- $(k+1)$ end extension $\sigma ^+$ which occurs as a subsequence of $\tau $ , and we define $\sigma '$ to be the sequence formed by the last k elements of $\sigma ^+$ . Let $\sigma $ be the first k elements of $\tau $ and form the sequence

$$ \begin{align*}\sigma, \sigma', \sigma", \ldots, \sigma^{(i)}, \ldots\end{align*} $$

by recursively applying this operation. By the Pigeonhole Principle, there must be $i < j$ such that $\sigma ^{(i)} = \sigma ^{(j)}$ , and we may pick j so that $j-i \leq f_\tau (k) \leq M$ . Thus $\tau $ is $(j-i)$ -periodic past the first instance of $\sigma ^{(i)}$ , and we are done.

Proof. We will show that there are finitely many finite sequences $\sigma _1, \ldots , \sigma _k$ such that any $\omega $ -chain of D is eventually $\sigma _i$ -periodic for some $i \in \{1, \ldots , k\}$ , and the same argument, with only notational changes, applies to $\omega ^*$ -chains of D, yielding the conclusion of Proposition 3.15.

So fix some $\omega $ -chain C of D. Pick $a\in C$ arbitrarily and let $\tau $ be the $\omega $ -chain $(\gamma _D(a), \gamma _D(S_D(a)) \dots \gamma _D(S_D^l(a)), \dots )$ . By Lemma 3.18, $f_\tau (n) \leq m_0$ for all $n \in \omega $ . Applying Lemma 3.19 we conclude that $\tau $ , and hence C, is eventually m-periodic for some $m \leq m_0$ . Since $D'$ is finite, there are only finitely many sequences of length at most $m_0$ from $D'$ , and the conclusion of Proposition 3.15 follows.

Proof. Suppose toward a contradiction that there are infinitely many non-periodic $\mathbb {Z}$ -chains in D. If there are sequences in $\{\sigma _1, \ldots , \sigma _k\}$ of different lengths, then if m is a common multiple of the lengths of all the $\sigma _i$ ’s, we may replace each $\sigma _i$ with a suitable number of concatenations with itself which has length m, and thus without loss of generality each $\sigma _i$ has the same length m. There is also no harm in assuming that the set $\{\sigma _1, \ldots , \sigma _k\}$ is closed under cyclic permutations.

Fix some $\mathbb {Z}$ -chain Z which is not periodic. Then there is some $a \in Z$ such that $\mathcal {Z}_{\geq }(a)$ is not periodic. By Proposition 3.15, $\mathcal {Z}_{\geq }(a)$ is eventually periodic. We may assume that a is maximal in the sense that if $a' \in Z$ and $a'> a$ , then $\mathcal {Z}_{\geq }(a')$ is periodic. Let $\tau $ be the $\omega $ -chain $\gamma _D(a), \gamma _D(S_D(a)), \gamma _D(S_D^2(a)), \ldots $ of successive elements of $D'$ beginning at $\gamma _D(a)$ . Then there is some $d_Z \in D'$ and some $i_Z \in \{1, \ldots , k\}$ such that $\tau = d_Z \sigma _{i_Z}^\omega $ (the concatenation of $d_Z$ followed by $\omega $ copies of $\sigma _{i_Z}$ ), since by our maximality assumption on a, the $\omega $ -chain of successive elements of $D'$ which begins at $\gamma _D(S_D(a))$ must be periodic.

By the assumption that there are infinitely many non-periodic $\mathbb {Z}$ -chains and the Pigeonhole Principle, there is a single $d \in D'$ and a single $i \in \{1, \ldots , k\}$ such that there are infinitely many non-periodic $\mathbb {Z}$ -chains Z such that $d_Z = d$ and $i_Z = i$ . Let $\sigma _i = \sigma _i^- e$ where $\sigma _i^-$ is the prefix consisting of the first $m-1$ elements of $\sigma _i$ and e is the final element of $\sigma _i$ . Then $e \neq d$ , since otherwise

$$ \begin{align*}d \sigma_i^\omega = d \sigma_i^- e \sigma_i^- e \ldots\end{align*} $$

would be an m-periodic sequence, contrary to our assumption.

Now let $\sigma = d \sigma _i$ . Since $d \neq e$ , the sequence $\sigma $ cannot be a subsequence of any m-periodic $\omega $ -chain. Thus there are infinitely many $a \in P_{\sigma }$ such that a is the last element of its $\mathbb {Z}$ -chain which intersects $P_{\sigma }$ . Therefore $P_{\sigma }$ is an infinite definable discrete subset of D and there are infinitely many elements $a \in P_{\sigma }$ such that $S_{P_\sigma }(a) - a \gg D'$ , but this contradicts Corollary 3.10.

Proof of Proposition 3.22.

By Proposition 3.15, for every narrow definable discrete set D which is bounded below, there is some $k \in \omega $ and finite sequences $\sigma _1, \dots , \sigma _k$ from $D'$ so that $\{\sigma _1, \dots , \sigma _k\}$ is a characteristic set for D. Let $k(D)$ be the minimum number such that there is a characteristic set $\{\sigma _1, \ldots , \sigma _{k(D)}\}$ for D. Without changing the number $k(D)$ of sequences in such a set, we may further assume that all the sequences $\sigma _i$ have the same length (arguing as in the first paragraph of the proof of Lemma 3.23). We also note that by minimality of $k(D)$ , no two sequences $\sigma _i$ and $\sigma _j$ for $1 \leq i < j \leq k(D)$ are cyclic permutations of one another. In case D is finite, we define $k(D) = 0$ , and whenever D is infinite, $k(D)> 0$ .

Our proof is by induction on $k(D)$ . We assume that the conclusion of Proposition 3.22 holds for all narrow discrete sets E which are bounded below and for which $k(E) < k(D)$ . We prove the conclusion of Proposition 3.22 for D. Note that the base case is when $k(D) = 0$ , which holds if and only if D is finite, in which case the conclusion of Proposition 3.22 is trivial.

Now suppose that $k(D)> 0$ . Fix a characteristic set $\{\sigma _1, \ldots , \sigma _{k(D)}\}$ for D with all $\sigma _i$ of the same length, none of which is a cyclic permutation of the other. We apply Proposition 3.8 to the subset of D defined by $P_{\sigma _1}$ to obtain a finite collection of closed, pairwise-disjoint intervals $\mathcal {C}_0 = \{C_1, \ldots , C_n\}$ such that $P_{\sigma _1} \subseteq \bigcup {1 \leq i \leq n} C_i$ and for each $i \in \{1, \ldots , n\}$ ,

1. (1) $P_{\sigma _1}$ is cofinal and coinitial in every $\mathbb{Z} $ -chain contained in $D \cap C_i$ ,

2. (2) $P_{\sigma _1}$ is cofinal in every $\omega $ -chain contained in $D \cap C_i$ , and

3. (3) $P_{\sigma _1}$ is coinitial in every $\omega ^*$ -chain contained in $D \cap C_i$ .

Since the $\mathbb{Z} $ -, $\omega $ -, and $\omega ^*$ -chains in (1)–(3) must be eventually $\sigma _i$ -periodic for some i, and by our assumptions that the $\sigma _i$ ’s are all of the same length and not cyclic permutations of one another, it follows that the chains in (1)–(3) are all eventually $\sigma _1$ -periodic.

The conclusion of Proposition 3.8 allows for some intervals $C_i$ which intersect $P_{\sigma _1}$ in only one point; by discarding such $C_i$ , we may further assume that every set $C_i \cap P_{\sigma _1}$ is infinite, and that

1. (4) $P_{\sigma _1} \setminus \bigcup _{C_i \in \mathcal {C}_0} C_i$ is finite.

The intervals in $\mathcal {C}_0$ may not be $\sigma _1$ -intervals for either one of two reasons. First, it may be the case that for some W, an eventually $\sigma _1$ -periodic but not $\sigma _1$ -periodic $\mathbb{Z} $ -chain of D, we have that $W \subseteq I$ for some $I \in \mathcal {C}_0$ . But by Lemma 3.23 there are only finitely many such chains. Thus we can rectify this problem by partitioning the elements of $\mathcal {C}_0$ into subintervals so that no such W is contained in any of the intervals. Secondly for some $J \in \mathcal {C}_0$ with $J=[a,b]$ or $J=[a, \infty )$ it may be the case that either $Z_{\geq }(a)$ or $Z_{\leq }(b)$ are only eventually $\sigma _1$ -periodic and not $\sigma _1$ -periodic. But this is easily fixed by replacing a by a suitably chosen $S^l(a)$ or replacing b by a suitably chosen $S^{-l}(b)$ . With these adjustments $\mathcal {C}_0$ is a finite collection of $\sigma _1$ -intervals.

Next let $D_1, \dots , D_r$ be the finitely many infinite D-convex components of $D \setminus \bigcup _{C_i \in \mathcal {C}_0} C_i$ (we may ignore any finite D-convex components). For each $i \in \{1, \ldots , r\}$ , any $\omega $ -chain of $D_i$ is also an $\omega $ -chain of D, and by construction it is not eventually $\sigma _1$ -periodic, hence it is $\sigma _j$ -periodic for some $j \in \{2, \ldots , k(D)\}$ , and likewise for $\omega ^*$ -chains; thus $\{\sigma _2, \dots , \sigma _{k(D)}\}$ is a characteristic set for each $D_i$ , and so $k(D_i) < k(D)$ . By the induction hypothesis we may find finite collections of intervals $\mathcal {C}_i$ for $1 \leq i \leq r$ so that each $I \in \mathcal {C}_i$ is a $\sigma _j$ -interval for some $2 \leq j \leq k(D)$ and so that $D_i \setminus \bigcup _{I \in \mathcal {C}_i}I$ is finite. Then setting $\mathcal {C}=\bigcup _{i =0}^r\mathcal {C}_i$ yields the desired collection of intervals.

Proof. Let D be definable, discrete, narrow, and bounded below. By Proposition 3.22, there are finitely many finite sequences $\sigma _1, \ldots , \sigma _k$ from $D'$ such that D is the union of a finite set F plus finitely many sets of the form $D \cap I$ where I is a $\sigma $ -interval for some $\sigma \in \{\sigma _1, \ldots , \sigma _k\}$ . Without loss of generality we may assume $D = D \cap I$ for some $\sigma $ -interval I.

Also without loss of generality, $\sigma $ is of minimal length—that is, for any finite sequence $\sigma '$ from $D'$ which is shorter than $\sigma $ , the interval I is not a $\sigma '$ -interval. Let k be the length of $\sigma $ , and for $i \in \{0, 1, \ldots , k-1\}$ , let

$$ \begin{align*}D_i = \{a \in D \, : \, S_D^i(a) \in P_\sigma\}.\end{align*} $$

Then $D = D_0 \cup \cdots \cup D_{k-1}$ , so it suffices to show that each set $D_i$ is pseudo-arithmetic.

By the Claim, if $\sigma = (d_1, \ldots , d_k)$ and $\eta = \sum _{i=1}^k d_i$ , then $D_i$ is $\eta $ -pseudo-arithmetic, as we wanted.

Assumption 3.25. $\mathcal {R}$ is $\omega $ -saturated.

Proof. Let D be an arbitrary definable discrete set. Let $D_0=D \cap R^{\geq 0}$ and let $D_1=D\setminus D_0$ . By Lemma 3.27(1) it suffices to show that $D_0$ and $D_1$ are piecewise pseudo-arithmetic. By Lemma 3.27(3) to show that $D_1$ is piecewise pseudo-arithmetic if suffices to show that ${-}D_1$ is piecewise pseudo-arithmetic. Thus we may assume that D is bounded below. By assumption D is a finite union of points and definable discrete sets $E_i$ for $1 \leq i \leq r$ each of which is narrow. By Lemma 3.27(1) it suffices to show that $E_i$ is piecewise pseudo-arithmetic for each $1 \leq i \leq r$ . Fix $1 \leq i \leq r$ . But Proposition 3.4 applies to $E_i$ and so $E_i$ is piecewise pseudo-arithmetic. Hence D is piecewise pseudo-arithmetic.

Assumption 3.29. D is bounded below.

Assumption 3.34. For each $\delta \in D'$ , there are infinitely many elements $a \in D$ with $\gamma _D(a) = \delta $ .

Proof. We induct on l. If $l=1$ the result is immediate. Thus suppose we have $\delta _1 < \dots <\delta _{l+1}$ . Let $\pi _{l+1} : \mathbb{N} ^{l+1} \to \mathbb{N} $ be the projection onto the last coordinate and first suppose that $\pi _{l+1}[Z]$ is finite. Let $\pi _{(1 \dots l)}: \mathbb{N} ^{l+1} \to \mathbb{N} ^l$ be the projection onto the first l coordinates. There is $m^* \in \pi _{l+1}[Z]$ whose pre-image is infinite. Let $Z_0:=\pi _{(1\dots l)}[\pi _{l+1}^{-1}(m^*)]$ . Then by induction

$$\begin{align*}\{ m_1 \delta _1 + \dots + m_l\delta_l+m^*\delta_{l+1} : (m_1 \dots m_l) \in Z_0\} \subseteq S\end{align*}$$

is infinite.

Therefore we may assume that $\pi _{l+1}[Z]$ is infinite. As $\delta _{l+1}$ is maximal among the $\delta _i$ ’s any sum of the form $m_1\delta _1 + \cdots + m_{l+1}\delta _{l+1}$ with $m_{l+1} \not = 0$ is Archimedean equivalent to $\delta _{l+1}$ (recall all the $\delta _i$ ’s are positive and $Z \subseteq \mathbb{N} ^{l+1}$ ). As $\pi _{l+1}[Z]$ is infinite, the set S must be cofinal in the Archimedean class $[\delta _{l+1}]$ of $\delta _{l+1}$ and thus infinite.

Proof. Suppose the lemma is false and take $\delta _1, \ldots , \delta _l$ so that D has arbitrarily large finite anti- $\{\delta _1, \ldots , \delta _l\}$ -components. Also let $D' = \{\delta _1, \ldots , \delta _n\}$ for $n \geq l$ (recalling that $D'$ must be finite). Let

$$\begin{align*}D_0=\{x \in D: \gamma_D(x) \in \{\delta_1, \ldots, \delta_l\} \}.\end{align*}$$

Let E be a finite anti- $\{\delta _{1} \dots \delta _{l}\}$ -component of D and further assume that $\min {(E)}>\min (D)$ . Let $M=|E|$ and let a be the minimal element of E. Now note that $\gamma _{D_0}(S^{-1}_D(a))=m_1\delta _1 + \cdots +m_n\delta _n$ where $m_1 + \cdots +m_n=M+1$ . As the size of finite anti- $\{\delta _{1} \dots \delta _{l}\}$ -components of D is unbounded there must be an infinite $Z \subseteq \mathbb{N} ^n$ so that if $(m_1 \dots m_n) \in Z$ then $m_1 \delta _1 + \dots + m_n\delta _n \in D_0'$ . By the previous lemma $D_0'$ is infinite, which is impossible since $D_0$ is a definable discrete set.

Proof. Suppose otherwise. By Lemma 3.26 we may without loss of generality assume that $D_i \subseteq R^{\geq 0}$ and $0 \in D_i$ for $i \in \{0,1\}$ . Set $D_0'=\{\eta _1, \dots , \eta _m\}$ . As ${D_0' \ll D_1'}$ and $0$ is the minimal element of $D_0$ it follows that if d is among the first $\omega $ many elements of $D_0$ then $d=l_1 \eta _1 + \cdots +l _m\eta _m$ for some $l_1 \dots l_m \in \mathbb {N}$ . In particular $d<D_1'$ . Hence by compactness find $\varepsilon \in R$ with $\varepsilon < D_1'$ so that $[0, \varepsilon ) \cap D_0$ is infinite. Then $(0, \varepsilon ) \cap D_0 < D_1'$ , violating Theorem 2.14.

Proof. We proceed by induction on $n=|D'|$ . If $n = 1$ then the result is trivial. Assume that $D'=\{\delta _1, \dots , \delta _{n+1}\}$ where the $\delta _i$ ’s are listed in increasing order, and suppose that we have established the lemma for all definable discrete sets which are bounded below and whose difference sets have size at most n.

We will do a sub-induction on $i \in \{1, \ldots , n+1\}$ , in reverse order (beginning with $i = n+1$ ), to show the following:

$(*)_i$ There is a definable finite convex partition of $D = D_0 \cup \cdots \cup D_m$ such that for every $1 \leq \ell \leq m$ and every $j \in \{i, i+1, \ldots , n+1\}$ , either $\delta _j \notin D^{\prime }_l$ , or else $D_l$ has no infinite anti- $\delta _j$ -component.

Notice that $(*)_1$ is our desired result.

First we will establish the base case, that is, $(*)_{n+1}$ . If there are only finitely many infinite anti- $\delta _{n+1}$ -components in D, then $(*)_{n+1}$ follows quickly: there is a definable finite convex partition $D = D_0 \cup \cdots \cup D_m$ such that for each $i,$ either (i) $D_i$ is an infinite anti- $\delta _{n+1}$ -component, or else (ii) $D_i$ has no infinite anti- $\delta _{n+1}$ -components.