Decomposing definable subsets of the plane

First some terminology: Let $X$ be a set and $Y_1, \dots, Y_l \subseteq X$, and put $\Y:= \{Y_1, \dots, Y_l\}$. We say that the $\Y$ partitions $X$ if $X = Y_1 \cup \cdots \cup Y_l$ and the $Y_j$-s are pairwise disjoint.
Given $Z \subseteq X$, we say that $\Y$ is compatible with $Z$ if, for every $j$, either $Y_j \subseteq Z$ or $Y_j \cap Z = \emptyset$.

Exercise
Let $Z_1, \dots, Z_k \subseteq X$, and let $\bo$ be the finite boolean algebra of subsets of $X$ generated by $Z_1, \dots, Z_k$. Prove that $\Y$ is compatible with each $Z_i$ if and only if $\Y$ is compatible with each atom of $\bo$.

We now return to our setting: let $\M$ be an o-minimal expansion of a dense linear order $(M,\lt)$.

For an open interval $I$ and continuous functions $f,g:I \into M \cup \{-\infty,\infty\}$ satisfying $f(x) \lt g(x)$ for all $x \in I$, we set $$(f,g)_I := \set{(x,y) \in M^2:\ f(x) \lt y \lt g(x)}.$$

Theorem (Cell decomposition in $M^2$)
Let $S_1, \dots, S_k \subseteq M^2$ be definable. Then there exist $a_0 = -\infty \lt a_1 \lt \cdots \lt a_l \lt a_{l+1} = +\infty$ and, for each $j=0, \dots, l$, there are definable continuous functions $f_{j,1}, \dots, f_{j,p(j)}:\left(a_j,a_{j+1}\right) \into M$ such that, with $$f_{j,0}:= -\infty\rest{\left(a_j,a_{j+1}\right)}$$ and $$f_{j,p(j)+1}:= +\infty \rest{\left(a_j,a_{j+1}\right)},$$ we have:

  1. $f_{j,1}(x) \lt \cdots \lt f_{j,p(j)}(x)$ for each $j$ and all $x \in \left(a_j,a_{j+1}\right)$;
  2. the collection of all sets $\gr\left(f_{j,q}\right)$ and $\left(f_{j,q},f_{j,q+1}\right)$ is compatible with each $S_i$.

Proof. It suffices to prove the theorem with the $\bd_1(S_i)$-s in place of the $S_i$-s, that is, we may assume that each $S_i$ is sparse. By the Exercise above, we may also assume that the $S_i$ are pairwise disjoint. Now choose $a_j$-s such that the ones obtained from the Theorem in this post, with each $S_i$ in place of $S$, are all listed among the $a_j$-s. Hence, for each $i$ and each $j$, there are definable functions $$f_{i,j,1}, \dots, f_{i,j,p(i,j)}:\left(a_j, a_{j+1}\right) \into M$$ such that $$S_i \cap \left(\left(a_j,a_{j+1}\right) \times M\right) = \bigcup_{l=1}^{p(i,j)} \gr\left(f_{i,j,p(i,j)}\right)$$ and their graphs are pairwise disjoint. Moreover, since the $S_i$-s are pairwise disjoint, it follows that the graphs of all $f_{i,j,q}$ are pairwise disjoint. So, for each $j$, we set $p(j):= \sum_{i=1}^k p(i,j)$, and we list all $f_{i,j,q}$ for this fixed $j$ in a list $f_{j,1}, \dots, f_{j,p(j)}$. Finally, by the Montonicity Theorem, after refining our collection of $a_j$-s if necessary, we may assume that each $f_{j,q}$ is continuous, so we are done by the Intermediate Value Theorem. $\qed$

Exercise
In the situation of the above Theorem, what can you say about the sets $S_i \cap \left(\{a_j\} \times M\right)$?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Close