Let ${\cal M}$ be an o-minimal expansion of a dense linear order $(M,\lt)$, and let $I$ be an open interval.
Ordered Ramsey Theorem
(Peterzil and Starchenko)
Let $S_1, \dots, S_k \subseteq M^2$ be definable, and assume that $I^2 \subseteq S_1 \cup \cdots \cup S_k$. Then there exist $l \in
\{1, \dots, k\}$ and an open interval $J \subseteq I$ such that $\Delta(J) \subseteq S_l$.
The proof uses the following
Lemma
Let $g:I \longrightarrow M$ be definable, with $I$ an open interval, and assume that $g(x) \gt x$ for all $x \in I$. Then there exist an open interval $J \subseteq I$ and $c\gt J$ such that $g(x) \gt c$ for all $x \in J$.
Proof. Let $B:= \{y \in I:\ g(y) \ge g(x)$ for all $x \in (a,y)\}$; we distinguish two cases based on the lemma in this post:
- $(a,\epsilon) \subseteq B$ for some $\epsilon \gt a$; so $g$ is increasing on $(a,\epsilon)$. Choose $a \lt \alpha \lt \beta \lt \epsilon$ such that $\beta \lt g(\alpha)$ and put $J:= (\alpha,\beta)$, and choose $c \in (\beta, g(\alpha))$.
- $(a,\epsilon) \subseteq I \setminus B$ for some $\epsilon \gt a$. Choose $c \in (a,\epsilon)$; so there exists $x_1 \in (a,c)$ such that $g(x_1) \gt g(c)$. Iterating this, we find $x_1 \gt x_2 \gt \cdots \gt x_i \gt \cdots \gt a$, for $i \in {\mathbb N}$, such that $g(x_{i+1}) \gt g(x_i) \gt g(c)$ for all $i$. Therefore, the set of all $x \in (a,c)$ for which $g(x) \gt g(c)$ is infinite, so by o-minimality there exist $a \le \alpha \lt \beta \lt c$ such that $g(x) \gt g(c)$ for all $x \in (\alpha,\beta)$, so we take $J:= (\alpha,\beta)$ in this case. $\Box$
Proof of the ordered Ramsey theorem. For $i=1, \dots, k$ set
$$B_i:= \{x \in I:\ \exists \epsilon \gt x \text{ such that } (x,\epsilon) \subseteq (S_i)_x\}.$$
By the lemma in this post, there is an $i$ such that $B_i$ contains an interval $I’$. Now define $g:I’ \longrightarrow M$ by
$$g(x):= \sup\{\epsilon \in (x,b]:\ (x,\epsilon) \subseteq (S_i)_x\}.$$
Then $g$ is definable and $g(x) \gt x$ for all $x \in I’$. By the above lemma, there are an open interval $J \subseteq I’$ and $c\gt J$ such that $g(x) \gt c$ for all $x \in J$; in particular $\Delta(J) \subseteq S_l$. $\Box$
The Monotonicity Lemma follows from this “ordered Ramsey” theorem as outlined in this post, so this completes the proof of the Monotonicity Theorem.
Exercise 2
State and prove an ordered Ramsey theorem for subsets of $M^n$, for any $n \in \mathbb{N}$. Or, if this cannot be done, justify why not…
Here is an attempt at the exercise; my idea really amounts to iteratively applying the usual ordered Ramsey theorem to projections in $M^2$ of an $n$-cube $I^n$. (On the face of it, this seems a bit too simple to work the way it should…) Of course, throughout the proof I am assuming that my definitions are the “right” definitions.
Let $\mathcal{M}$ be an o-minimal expansion of a dense linear order $(M, <)$ and let $I = (a,b)$ be an interval in $M$. Define $\Delta_{n}(I) = \{ (x_{1}, \dots, x_{n}) \in I^n : x_{1} < \dots < x_{n} \}$ for $n \geq 2$.
Generalized Ordered Ramsey Theorem. Let $S_{1}, \dots, S_{k} \subseteq M^n$ be definable, and assume that $I^n \subseteq S_{1} \cup \dots \cup S_{k}$. Then there exist $l \in \{1, \dots, k\}$ and an open interval $J \subseteq I$ such that $\Delta_{n}(J) \subseteq S_{l}$.
For each $i \in \{1, \dots, k\}$, let $\Pi_{(j, j+1)}(S_{i})$ denote the projection of the set $S_{i}$ onto the $j^{\mathrm{th}}$ and $(j+1)^{\mathrm{th}}$ coordinates, for $j \in \{1, \dots, n-1\}$. Since $I^n \subseteq S_1 \cup \dots \cup S_k$, the inclusion $$\Pi_{(j, j+1)}(I^n) \subseteq \Pi_{(j, j+1)}(S_{1}) \cup \dots \cup \Pi_{(j, j+1)}(S_{k})$$ holds for all such $j$. Denote by $\Delta_{(j, j+1)}(I)$ the set of all pairs $(x_{j}, x_{j+1})$ in $I^2 = \Pi_{(j, j+1)}(I^n)$ such that $x_{j} < x_{j+1}$. Now apply the ordered Ramsey theorem to $$\Pi_{(1, 2)}(I^n) \subseteq \Pi_{(1, 2)}(S_{1}) \cup \dots \cup \Pi_{(1, 2)}(S_{k})$$ to obtain an open interval $J_1 \subseteq I$ such that $\Delta_{(1, 2)}(J_1) \subseteq \Pi_{(1, 2)}(S_{l_{1}})$ for some $l_{1} \in \{ 1, \dots, k \}$. Since $J_1 \subseteq I$, we have the inclusion $$J_{1}^{n} \subseteq I^n \subseteq S_1 \cup \dots \cup S_k.$$ Now project $J_{1}^{n}$ onto the $2^{\mathrm{nd}}$ and $3^{\mathrm{rd}}$ coordinates to get $$\Pi_{(2, 3)}(J_{1}^{n}) \subseteq \Pi_{(2, 3)}(S_{1}) \cup \dots \cup \Pi_{(2, 3)}(S_{k})$$ and apply the ordered Ramsey theorem to get an open interval $J_{2} \subseteq J_{1}$ such that $\Delta_{(2, 3)}(J_2) \subseteq \Pi_{(2,3)}(S_{l_2})$ for some $l_{2} \in \{1, \dots, k\}$.
Iteratively applying the ordered Ramsey theorem in this way, we obtain intervals $J_{j}$ for $j \in \{1, \dots, n – 1\}$ such that $$J_{n-1} \subseteq J_{n-2} \subseteq \dots \subseteq J_{1} \subseteq I$$ and such that $\Delta_{(j, j+1)}(J_{j}) \subseteq \Pi_{(j, j+1)}(S_{l_j})$ for each such $j$. In particular, $$\Delta_{(j, j+1)}(J_{n-1}) \subseteq \Pi_{(j, j+1)}(S_{l_j})$$ for all $j$ by the above inclusion of intervals. Since each diagonal $\Delta_{(j, j+1)}(J_{n-1})$ is contained in a projection of some $S_{l_{j}}$, $J_{n-1}$ intersects all such $S_{l_j}$ in $M^n$. Shrink $J_{n-1}$ if necessary so that $J_{n-1}^n$ is contained entirely in the intersection of the $S_{l_j}$, and fix any of these $l_{j} = l$; then for all $j \in \{1, \dots, n-1\}$ we have $\Delta_{(j, j+1)}(J_{n-1}) \subseteq \Pi_{(j, j+1)}(S_l)$. For each diagonal $\Delta_{(j, j+1)}(J_{n-1})$ take the appropriate Cartesian product with $n – 2$ copies of $J_{n-1}$ so that we can identify the diagonal with the set $$ \Delta'_{(j, j+1)}(J_{n-1}) = \{ (x_1, \dots, x_n) \in J_{n-1}^n : x_{j} < x_{j+1} \}$$ and note that this set is contained in $S_{l}$. To conclude, note that $$\Delta_{n}(J_{n-1}) = \bigcap_{j=1}^{n-1} \Delta'_{(j, j+1)} (J_{n-1}),$$ since $(x_1, \dots, x_n) \in \Delta_{n}(J_{n-1})$ if and only if $x_1 < \dots < x_n$ if and only if $x_1 < x_2 \wedge \dots \wedge x_{n-1} < x_n$. Since each $\Delta'_{(j, j+1)}(J_{n-1})$ belongs to $S_l$, the intersection belongs to $S_l$ and thus we can take $J = J_{n-1}$ to obtain the result. $\qed$
The statement certainly looks like what we want.
The proof works fine right up to the sentence beginning with “Since each diagonal … is contained in a projection of some …”: I don’t see why that implies that $J_{n-1}^n$ intersects all such $S_{l_j}$ in $M^n$. But even if it does, why would it mean that their intersection contains a box?
Rather than working with these projections, I would try to work with fibers, using induction on $n$.
I have a few more questions about the exercise: On Friday you suggested that we consider the function $g$ which maps a point $x \in I$ to the “corner” of the diagonal $\Delta_{n}(I)$ and then apply the monotonicity theorem to obtain a subinterval of $I$ on which $g$ is continuous. Now, I’ve been projecting $I^n$ down to the first $n – 1$ coordinates and applying the inductive hypothesis immediately to obtain an open interval $J \subseteq I$ such that $\Delta_{n-1}(J) \subseteq \Pi_{n-1}(S_l)$ for some $l$. Then, assuming I didn’t misinterpret your suggestion, I define a function $g : J \rightarrow M$ by $$g(y) = \sup \{ z \in J : z \in (S_l)_{(\bar{x}, y)}, \bar{x}_i < y, i \in \{1, \dots, n-2\} \}$$ where $\bar{x}$ is any tuple in $M^{n-2}$; in this sense $g$ maps each $y \in J$ to the maximal element over all fibers of $S_l$ above elements in $\Delta_{n-1}(J)$ with last coordinate $y$.
Now, we can apply the monotonicity theorem to this function to obtain a subinterval $J' \subseteq J$ on which $g$ is continuous, but I don't see how this gives us the conclusion we want. If we could somehow apply the above lemma to $g$ then I think that would be enough (since we should just be able to proceed as in the proof of the ordered Ramsey theorem), but in that case we wouldn't need to apply the monotonicity theorem to obtain continuity, hence my confusion. Any suggestions (from anyone)? I feel as though the proof shouldn't be this involved…
No, my suggestion is a bit more radical: instead of projecting on the first $n-1$ variables before you apply the inductive hypothesis, project on the first variable and apply the inductive hypothesis in each fiber. This gives a definable family $(J_x: x \in M)$ of intervals and a map $x \mapsto l(x) \in \{1, \dots, k\}$ such that $\Delta_{n-1}(J_x) \subseteq (S_{l(x)})_x$ for each $x$.
By o-minimality, may assume the $x$ range over an interval $U$ and $l(x)$ is constant. NOW consider the definable maps $f,g:U \into M$ defined by $f(x):= \inf J_x$ and $g(x):= \sup J_x$.
Ah, I see now, thanks! I had thought about projecting on the first variable and applying the inductive hypothesis in each fiber, but it never occurred to me to use o-minimality to obtain an interval $U$ on which $l(x)$ is constant. Here is the end of the proof, then, hopefully without any errors:
After defining $f$ and $g$ as above, we apply the monotonicity theorem to obtain an open interval $U’ \subseteq U$ such that $f$ and $g$ are continuous on $U’$; replace $U$ with this $U’$. Then we can find an open $V \subseteq U’$ such that the box $V \times V$ is contained in the interval $(f, g)$ (since $(f, g)$ lies entirely in $U’ \times U’$ and so the diagonal in $U’ \times U’$ must intersect $(f, g)$ in some set $I’$; choose a box $B = V \times V$ small enough so that the diagonal of $B$ is contained in $I’$). In particular, $V \subseteq J_x$ for all $x \in V$. Now let $(x_1, \dots, x_n) \in \Delta_{n}(V)$. Then $(x_2, \dots, x_{n}) \in \Delta_{n-1}(J_{x_1})$ since $V \subseteq J_{x_1}$ and so $(x_2, \dots, x_{n}) \in (S_l)_{x_1}$, i.e. $(x_1, \dots, x_n) \in S_l$, where $l$ is the constant value $l(x)$ for all $x \in U$. Thus $\Delta_{n}(V) \subseteq S_l$.
Hmm, I’m not quite following; I think you are a bit brief in the end here. May I suggest you write up the complete solution as a post to clear things up?
The following is a counterexample to the generalized ordered Ramsey theorem, found in a 1997 paper of Macpherson and Steinhorn entitled “Extending Partial Orders on o-Minimal Structures to Definable Total Orders”. They make use of the usual ordered Ramsey theorem, but later remark that the natural generalization of the ordered Ramsey theorem for subsets of $M^n$ does not hold in general, even in the case $n=3$. They briefly mention the following counterexample, which I’ve fleshed out a bit:
Let $\mathcal{M} = (\mathbb{Q}, \lt, +, 0)$. Take $I = \mathbb{Q}$ and partition $\mathbb{Q}^3$ into two sets $X_1$ and $X_2$ given by $$X_1 = \{(u,v,w) \in \mathbb{Q}^3 : w – v \gt v – u \}$$ and $$X_2 = \mathbb{Q}^3 \setminus X_1.$$ Then, given any non-empty open interval $J \subseteq \mathbb{Q}$, we have $\Delta_{3}(J) \cap X_1 \neq \varnothing$ and $\Delta_{3}(J) \cap X_2 \neq \varnothing$. Indeed, suppose $J = (a,b)$ and fix $0 \lt \epsilon \in \mathbb{Q}$ arbitarily small. Then $(a + \epsilon, a + 2 \epsilon, a + 4 \epsilon) \in \Delta_{3}(J)$ and $$ (a + 4\epsilon) – (a + 2\epsilon) = 2\epsilon \gt \epsilon = (a + 2\epsilon) – (a + \epsilon),$$ and so $(a + \epsilon, a + 2 \epsilon, a + 4 \epsilon) \in X_1$. Similarly, $(a + \epsilon, a + 2 \epsilon, a + 3 \epsilon) \in \Delta_{3}(J) \cap X_2$ since $$(a + 3 \epsilon) – (a + 2 \epsilon) \not \gt (a + 2 \epsilon) – (a + \epsilon).$$
So it seems that the generalized ordered Ramsey theorem fails even for subsets of $M^3$.