Let $\M$ be an o-minimal expansion of a dense linear order $(M,\lt)$, and let $S \subseteq M^2$.
Our goal is to show that if $S$ is definable and sparse, then $S$ satisfies uniform finitess.
For $z \in S$, we say that $\Pi_1\rest{S}$ is a homeomorphism at $z$ if there exists an open box $B \subseteq M^2$ containing $z$ and a continuous function $f:\Pi_1(B) \into M$ such that $B \cap S = \gr(f)$.
Lemma
Assume $S$ is definable and sparse.
- If $\ \Pi_1(S)$ is infinite, there is a definable, continuous $f:I \into M$, with $I$ an open interval, such that $\gr(f) \subseteq S$.
- If there exists a definable, continuous $f:I \into M$, with $I$ an open interval, such that $\gr(f) \subseteq S$, then there exists $x \in I$ such that $\Pi_1\rest{S}$ is a local homeomorphism at $(x,f(x))$.
Proof
1. Assume that $\Pi_1(S)$ is infinite; then it contains an open interval $J$. Since $S$ is sparse, after shrinking $J$ if necessary, we may assume that $S_x$ is finite for all $x \in J$. So we define $f:J \into M$ by $f(x):= \min S_x$; this $f$ is definable and, by the Monotonicity Theorem, contains an open interval $I$ such that $f \rest{I}$ is continuous.
2. Let $I$ be an open interval and $f:I \into M$ be definable and continuous such that $\gr(f) \subseteq S$. Again shrinking $I$ if necessary, we may assume that $S_x$ is finite for every $x \in I$. Define $g,h:I \into M \cup \{-\infty,+\infty\}$ by $$g(x) := \sup\set{y \in S_x:\ y \lt f(x)}$$ and $$h(x):= \inf\set{y \in S_x:\ y \gt f(x)}.$$ By the Monotonicity Theorem and because the sets $\{x \in I:\ g(x) = -\infty\}$ and $\{x \in I:\ h(x) = +\infty\}$ are definable, there exists an open interval $J \subseteq I$ such that both $g \rest{J}$ and $h\rest{J}$ are continuous. Since $g(x) \lt f(x) \lt h(x)$ for all $x \in I$, part 2 follows. $\qed$
Proposition
If $S$ is definable and sparse, there exists a finite set $F_2 = F_2(S) \subseteq M$ such that $\Pi_1\rest{S’}:S’ \into M$ is a local homeomorphism, where $S’:= S \setminus (F_2 \times M)$.
Proof. The set $$F_2:= \{x \in M:\ \exists y \in M \text{ such that } \Pi_1\rest{S} \text{ is not a homeomorphism at } (x,y)\}$$ is definable, and by the Lemma and o-minimality (details left as an exercise), it is finite. $\qed$
We let $\fr(S):= \cl(S) \setminus S$ be the frontier of $S$.
Exercise 3
Assume that $S$ is definable and sparse.
- The set $F_4 = F_4(S):= \Pi_1(\fr(S))$ is finite, and $S \setminus (F_4 \times M)$ is closed in $(M \setminus F_4) \times M$.
- There is a finite subset $F_3 = F_3(S) \subseteq M$ such that $S$ is locally bounded at every $x \in M \setminus F_3$.
Theorem (uniform finiteness)
Assume $S$ is definable and sparse. Then there exist $k \in \NN$ and $a_1, \dots, a_k \in M$ such that $$a_0:= -\infty \lt a_1 \lt \cdots \lt a_k \lt a_{k+1} := +\infty$$ and, for $j=0, \dots, k$, the cardinality $\left|S_x\right|$ is constant for $x \in (a_j,a_{j+1})$.
Proof. By the Corollary from this post and the Proposition and Exercise above, there exist $k \in \NN$ and $a_1, \dots, a_k \in M$ such that $$a_0:= -\infty \lt a_1 \lt \cdots \lt a_k \lt a_{k+1} := +\infty$$ and, for $j=0, \dots, k$, the set $S \cap ((a_j,a_{j+1}) \times M)$ satisfies the hypotheses of Exercise 1. $\qed$
Exercise
Assume $S$ is definable. Show that there exists $k \in \NN$ such that for every $x \in M$, if $S_x$ is finite, then $\left|S_x\right| \le k$.
[Hint: use the Exercise from this post.]
Here is an attempt of a proof for the two exercises:
1. The set $\{ x \vert fr(S_x)\neq (fr(S))_x \}$ is finite and $\{ x \vert fr(S_x)\neq \emptyset \} \subset \{ x \vert \rvert S_x \lvert = \infty \}$ which is finite because $S$ is sparse. Hence, the set $\{ x \vert (fr(S))_x \neq \emptyset \}$ is finite so $\Pi_i (fr(S))$ is finite.
Let $(x,y) \in fr(S\setminus (F_4 \times M)) $, then we can show that $x\in F_4$.
Indeed, since $S\setminus (F_4 \times M) \subset S$, we have:
$$fr(S\setminus (F_4 \times M)) \subset cl(S) \cap (S\setminus (F_4 \times M))^\complement$$
$$= fr(S) \cup (cl(S) \cap (F_4 \times M))$$ $$\subset fr(S) \cup (F_4 \times M)$$
Hence, $x\in \Pi_1(fr(S\setminus (F_4 \times M))) \subset \Pi_1( fr(S)) \cup \Pi_1((F_4 \times M)=F_4$.
Since $x\in F_4$, $(x,y)\not\in (M\setminus F_4) \times M$ i.e. $fr(S\setminus (F_4 \times M)) \cap
((M\setminus F_4) \times M) =\emptyset$ so $S\setminus F_4) \times M$ is closed in $(M\setminus F_4) \times M$.
2. Let $F$ be the finite set $\{ x \in \Pi_1(S) \vert \rvert S_x \lvert = \infty \}$. $\Pi_1(S)\setminus F$ is a finite union of points and intervals, say $\bigcup\limits_{i=1}^n \{ m_i \} \cup \bigcup\limits_{j=1}^m I_j$. For each interval $I_j$, define the two functions $f_j, g_j: I_j \rightarrow M$ with $f_j(x):= max\{ y \in S_x \}$ and $g_j(x):= min\{ y \in S_x \}$ (they are well-defined because $S_x$ is finite and non-empty for every $x\in I_j)$).
By the monotonicity theorem ($f_j,g_j$ are definable), there exists $k_j\in \mathbb{N}$ and $a_1, \dots, a_{k_j -1} \in M$ such that $a_0:= a < a_1 < \dots < a_{k_j}:=b$ (where $a,b$ are the endpoints of $I_j$) and $\left.f_j\right|_{]a_l, a_{l+1}[}$, $\left.g_j\right|_{]a_l, a_{l+1}[}$ are strictly monotone and continuous for all $l\in \{0, \dots, k_j-1 \}$.
Taking $F_3$ to be $F \cup \bigcup\limits_{i=1}^n \{ m_i \}$ together with the $a_l$’s for each interval $I_j$, we obtain a finite subset of $M$ such that $S$ is locally bounded at every $x\in M\setminus F_3$.
For the exercise at the end, since $S$ is definable, $bd(S)$ is sparse. Applying the uniform finiteness theorem, there exists $k\in \mathbb{N}$ and $a_1, \dots, a_{k -1} \in M$ such that $a_0:= -\infty < a_1 < \dots < a_{k_j}:= +\infty$ with $\vert (bd(S))_x\vert $is constant (denoted by
$M_i$) for all $x\in ]a_i, a_{i+1}[$ and $i \in \{0, \dots, k-1 \}$.
For $S_x$ finite, $S_x =bd(S_x) \subset (bd(S))_x$ so $M:= max\{M_j\}$ is an upper bound for all the cardinalities of the finite fibers of $S$.
Good!