% A LaTeX2e file for a 9 page document,
% A short proof of a partition relation for triples, version 1, edition 49
% Copyright (C) 1999, 2000 Albin L. Jones
\documentclass[12pt]{article}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\topmargin 0pt
\advance \topmargin by -\headheight
%\advance \topmargin by -\headsep
\textheight 8.5in
\oddsidemargin 0in
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.1in
\newcommand{\ps}{\mathcal{P}}
\DeclareMathOperator{\cf}{cf}
\newcommand{\nto}{\nrightarrow}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\SET}[2]{\{#1\;|\;#2\}}
\newcommand{\AND}{\land}
\newcommand{\OR}{\lor}
\renewcommand{\setminus}{\smallsetminus}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem*{claim*}{Claim}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{question}{Question}
\begin{document}
\title{A short proof of a partition relation for triples}
\author{Albin L. Jones \\
Department of Mathematics \\
Kenyon College \\
Gambier, OH 43022, USA \\
\small{\texttt{jones@kenyon.edu}} \\
\small{\texttt{http://math.kenyon.edu/\symbol{126}jones/}}}
\date{Submitted: September 3, 1999; Accepted: March 11, 2000}
\maketitle
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000), \#R24\hfill}
\thispagestyle{empty}
\begin{abstract}
\noindent
We provide a much shorter proof of the following partition theorem
of P.~Erd\H{o}s and R.~Rado: If~$X$ is an uncountable linear order
into which neither~$\omega_1$ nor~$\omega_1^{*}$ embeds, then $X \to
(\alpha, 4)^{3}$ for every ordinal~$\alpha < \omega + \omega$. We
also provide two counterexamples to possible generalizations of this
theorem, one of which answers a question of E.~C.~Milner and
K.~Prikry.
\vspace{.5cm}
\noindent
MR Subject Classifications: 03E05, 04A20, 05A18, 05D10
\noindent
Keywords: partition relations, Ramsey theory, real orders,
transfinite ordinal numbers, triples
\end{abstract}
% \newpage
\section{A brief introduction}
In~\cite[Theorem~31, pp.~447--457]{MR18:458a}, P.~Erd\H{o}s and
R.~Rado proved the theorem cited in the abstract, namely that if~$X$
is an uncountable linear order into which neither~$\omega_1$
nor~$\omega_1^{*}$ embeds, then $X \to (\alpha, 4)^{3}$ for every
ordinal $\alpha < \omega + \omega$. The proof they provided was quite
complicated and difficult to follow. We thought it might be helpful
to exhibit a simpler, more elementary proof.
\section{Notation and definitions}
We use standard set-theoretic notation as used in, for example,
\cite{MR87g:04002}, \cite{X:3}, and~\cite{MR96k:03125}.
An \textit{order} is a set~$X$ together with an \textit{ordering}, a
binary relation~$<$ on~$X$ which is \textit{transitive} (if $x < y$
and $y < z$, then $x < z$) and \textit{irreflexive} (never is $x <
x$). If the ordering is \textit{trichotic} (if always either $x < y$,
$y < x$, or $x = y$), then the order is a \textit{linear order}. For
any order~$X$ (with ordering~$<$), the \textit{inversion} of~$X$ is
the order~$X^{*}$, with underlying set~$X$ and ordering $<^{*}$ which
is defined by putting $x <^{*} y$ if and only if $y < x$. For
example, $\mathbb{R}^{*} \cong \mathbb{R}$, while $\omega^{*}$ is
isomorphic to the negative integers with their usual ordering.
It is traditional when defining and describing orders to omit explicit
mention of their orderings whenever possible, leaving them to be
inferred from context or usage. We will continue this tradition, as
it greatly simplifies notation and seldom seems to leads to confusion.
For any two orders~$X$ and~$Y$, we let $[X]^{Y}$ be the collection of
all suborders of~$X$ (subsets of~$X$ together with the natural
restrictions of its ordering) which are order isomorphic to~$Y$. That
is,
\[
[X]^{Y} = \SET{Z \subseteq X}{Z \cong Y}.
\]
For example, $[\mathbb{R}]^{\omega}$ is the collection of all strictly
increasing infinite sequences of real numbers, while
$[\mathbb{R}]^{\mathbb{Q}}$ is the collection of all densely ordered
sets of real numbers with neither maximal nor minimal element. Most
importantly, for any order~$X$ and any natural number~$n$, we have
that~$[X]^{n}$ is the collection of all $n$-element chains of~$X$;
\[
[X]^{n} = \SET{\set{x_0, \dots, x_{n - 1}}}{x_0, \dots, x_{n - 1} \in
X \AND x_0 < \dots < x_{n - 1}}.
\]
And more generally, for two finite sequences of orders $X_0, \dots,
X_{m - 1}$ and $Y_0, \dots, Y_{m - 1}$, we define (after P.~Erd\H{o}s
and R.~Rado)
\[
[X_0, \dots, X_{m - 1}]^{Y_0, \dots, Y_{m - 1}} = \SET{Z_0 \cup \dots
\cup Z_{m - 1}}{Z_0 \in [X_0]^{Y_0} \AND \dots \AND Z_{m - 1} \in
[X_{m - 1}]^{Y_{m - 1}}},
\]
the most important consequence of which is the fact that $[X, Y]^{1,
2}$ is just the set of triples $\set{x_0, y_0, y_1}$ where $x_0 \in
X$ and $y_0, y_1 \in Y$ with $y_0 < y_1$.
We are interested in the combinatorics of orders, and most especially
in their \textit{Ramsey theory}, first described and investigated by
P.~Erd\H{o}s and R.~Rado in~\cite{MR18:458a}. In its most
straightforward form, Ramsey theory is the theory of the
\textit{ordinary partition relation}: Let~$X$ be an order,~$\mu$ be an
ordinal, and each~$Y_i$ for $i < \mu$ be an order. Then the
\textit{partition relation} $X \to (Y_i)_{i < \mu}^{n}$ holds if and
only if for every \textit{partition} $f : [X]^{n} \to \mu$ there are
an index $i < \mu$ and a suborder $Z \in [X]^{Y_i}$ such that
$f``[Z]^{n} = \set{i}$. (In general, if $f$ is a function and~$A$ is
a set, then by~$f``A$ we mean the \textit{image} of~$A$ under~$f$.
That is, $f``A = \SET{f(a)}{a \in A}$.) The failure of a partition
relation is indicated by replacing the ``$\to$'' with ``$\nto$''.
There are a few variations on this notation given in~\cite[Section~2,
pp.~428--431]{MR18:458a}, three of which we will need here. The first
variation is concerned with the possibility that all of the
orders~$Y_i$ for $i < \mu$ are identical: The partition relation $X
\to (Y)_{\mu}^{n}$ holds if for every partition $f : [X]^{n} \to \mu$
there are an index $i < \mu$ and a suborder $Z \in [X]^{Y}$ such that
$f``[Z]^{n} = \set{i}$. The second deals with the possibility that
the number of classes in the partition is finite: The partition
relation $X \to (Y_0, \dots, Y_{m - 1})^{n}$ holds if for every
partition $f : [X]^{n} \to \set{0, \dots, m - 1}$ there is an index $i
< m$ and a suborder $Z \in [X]^{Y_i}$ such that $f``[Z]^{n} =
\set{i}$. The third variation allows for the possibility that all but
one of the orders~$Y_i$ for $i < \mu$ are identical: The partition
relation $X \to ((Y)_{\mu}, Z)^{n}$ holds if for every partition $f :
[X]^{n} \to \mu + 1$ \textit{either} there are an index $i < \mu$ and
a suborder $U \in [X]^{Y}$ such that $f``[U]^{n} = \set{i}$
\textit{or} there is a suborder $V \in [X]^{Z}$ such that $f``[V]^{n}
= \set{\mu}$. Examples of each of these variations appear in the
results below.
An order is \textit{anti-well-founded} if it contains no strictly
increasing infinite sequences. That is,~$X$ is anti-well-founded if
and only if~$[X]^{\omega} = \emptyset$. The \textit{character} of an
order is the minimum cardinal number of anti-well-founded suborders
into which it can be decomposed. For example, the character of the
first uncountable ordinal~$\omega_1$ is~$\omega_1$ (as every
anti-well-founded suborder of~$\omega_1$ is finite), while the
character of the real line~$\mathbb{R}$ is~$2^{\omega}$ (as every
anti-well-founded suborder of~$\mathbb{R}$ is countable).
An order has \textit{countable character} if it can be decomposed into
countably many anti-well-founded suborders. Since every order can be
decomposed into some number of anti-well-founded suborders
(singletons, if need be), if an order does not have countable
character, then it must have \textit{uncountable
character}.\footnote{We feel obligated to note that the notions of
\textit{having countable character} and \textit{having uncountable
character} are both unique to this article; they are usually
rendered as \textit{being special} and \textit{being non-special},
respectively. We believe, however, that these latter phrases are
neither accurate nor illustrative, and hope that more useful
alternatives can be found, perhaps the ones we suggest here or
perhaps some others. With that said, we also wish to note that
there is currently no term in common use for the notion of
\textit{character} defined above.} We remark that an order~$X$ has
countable character if and only if the negative partition relation $X
\nto (\omega)_{\omega}^{1}$ holds. It follows that an order~$X$ has
uncountable character if and only if the positive partition relation
$X \to (\omega)_{\omega}^{1}$ holds. It is a triviality that all
countable orders and all anti-well-founded orders have countable
character.
A \textit{real order} is a linear order with uncountable character
into which~$\omega_1$ does not embed. It is not difficult to see that
the real line~$\mathbb{R}$ is a real order (which explains the
moniker ``real''), as is any other uncountable linear order into
which neither~$\omega_1$ nor~$\omega_1^{*}$ embeds. All real orders
do not, however, fall into this latter class, as J.~Baumgartner
demonstrated in~\cite[Corollary~3.6, p.~194]{MR54:4988}.
\section{A short proof}
The following theorem first appeared in~\cite[Theorem~31,
pp.~447--457]{MR18:458a}. (Actually, this is not quite true. The
theorem there was claimed only for uncountable orders into which
neither~$\omega_1$ nor~$\omega_1^{*}$ embeds, rather than for all real
orders; but the proof given there could be modified to yield this
slightly stronger result.) The proof given below first appeared
in~\cite[Section~5, pp.~32--34]{X:2}. (Actually, this is not quite
true, either. The proof given there was in spirit the one given
below, but the result was again claimed only for a restricted class of
real orders, namely those which cannot be decomposed into countably
many scattered suborders. An order is \textit{scattered} if it has no
densely ordered suborders.)
\begin{theorem}[P.~Erd\H{o}s--R.~Rado]
\label{theorem:main}
If~$X$ is a real order, then $X \to (\omega + m, 4)^{3}$ for every
natural number~$m$.
\end{theorem}
We will use the following ``well known'' facts in our proof of
Theorem~\ref{theorem:main}.
\begin{fact}[P.~Erd\H{o}s--R.~Rado]
\label{fact:real}
Every real order~$X$ contains suborders~$Y$ and~$W$ such that
\begin{enumerate}
\item $Y$ is also a real order,
\item $W$ is (order) isomorphic to the ordinal~$\omega^{2}$, and
\item $Y < W$ (\textit{i.e.}, $y < w$ for every $y \in Y$ and $w \in
W$).
\end{enumerate}
\end{fact}
\begin{fact}[F.~Ramsey, P.~Erd\H{o}s--G.~Szekeres]
\label{fact:ramsey}
For each natural number~$m$ there is a natural number~$n$ such that
$n \to (m, 4)^{3}$. Also, $\omega \to (\omega, 4)^{3}$.
\end{fact}
\begin{fact}[P.~Erd\H{o}s--R.~Rado, E.~Specker]
\label{fact:squared}
The relation $\omega^{2} \to (n, \omega + m)^{2}$ holds for any two
natural numbers $m$ and~$n$.
\end{fact}
\begin{fact}[J.~Baumgartner--A.~Hajnal]
\label{fact:pairs}
For any two natural numbers $m$ and~$n$, if~$Z$ is a real order,
then $Z \to ((\omega + m)_{n}, \omega)^{2}$.
\end{fact}
\noindent
In each case a much stronger statement is true; for details we refer
the interested reader to \cite[Lemma~1, pp.~446--447]{MR18:458a},
\cite[Theorem~1, p.~431]{MR18:458a}, \cite[Theorem~23,
pp.~439--440]{MR18:458a}, and \cite[Theorem~1,
pp.~194--195]{MR47:8310}, respectively. Evidently, all but the last
fact were known to Erd\H{o}s and Rado when they
wrote~\cite{MR18:458a}.
\begin{proof}[Proof of Theorem~\ref{theorem:main}]
Let~$X$ be a real order. Let a partition $f : [X]^{3} \to \set{0,
1}$ be given. Fix a natural number~$m$. We will show that either
\begin{itemize}
\item[(a)] there is $A \in [X]^{\omega + m}$ with $f``[A]^{3} =
\set{0}$, or
\item[(b)] there is $B \in [X]^{4}$ with $f``[B]^{3} = \set{1}$.
\end{itemize}
The claim below will be our most useful tool in this effort.
\begin{claim*}
\label{claim:main}
Suppose $x \in X$ and $A \in [X \setminus \set{x}]^{\omega + m}$
are such that $f``[\set{x}, A]^{1, 2} = \set{1}$. Then either (a)
or (b) holds.
\end{claim*}
\begin{proof}[Proof of Claim]
Clearly, if $f``[A]^{3} = \set{0}$, then (a) holds. But what if
$f``[A]^{3} \neq \set{0}$? Then there must be a triple $\set{a_0,
a_1, a_2} \in [A]^{3}$ such that $f\set{a_0, a_1, a_2} = 1$.
Let $B = \set{x, a_0, a_1, a_2}$. It is then easy to check that
$f``[B]^{3} = \set{1}$, and hence that (b) holds.
\end{proof}
Using Fact~\ref{fact:real}, find $Y, W \subseteq X$, such that~$Y$
is a real order, $W$ has order type~$\omega^{2}$, and $Y < W$. For
the remainder of the proof, we will focus our attention on the order
$Y \cup W$ and the partition $f \restriction [Y \cup W]^{3} : [Y
\cup W]^{3} \to \set{0, 1}$. It is important to keep in mind that
$[Y \cup W]^{3} = [Y]^{3} \cup [Y, W]^{2, 1} \cup [Y, W]^{1, 2} \cup
[W]^{3}$.
Using Fact~\ref{fact:ramsey}, find a natural number~$n$
such that $n \to (m, 4)^{3}$. For each $y \in Y$, define the
partition $f_y : [W]^{2} \to \set{0, 1}$ in the following way. For
each pair of distinct elements $w_0$ and~$w_1$ of~$W$, put
\[
f_y\set{w_0, w_1} = f\set{y, w_0, w_1}.
\]
For each $y \in Y$, by Fact~\ref{fact:squared}, either
\begin{itemize}
\item[(c)] there is $A_y \in [W]^{\omega + m}$ with $f_y``[A_y]^{2}
= \set{1}$, or
\item[(d)] there is $D_y \in [W]^{n}$ with $f_y``[D_y]^{2} =
\set{0}$.
\end{itemize}
If (c) holds for some $y \in Y$, then by the claim either (a) or (b)
holds, and we are done. We may therefore assume (without loss of
generality) that (d) holds for each $y \in Y$. That is, we may
assume that for each $y \in Y$ there is an $n$-element subset~$D_y$
of~$W$ such that $f``[\set{y}, D_y]^{1, 2} = \set{0}$. Because~$Y$
is a real order and $|[W]^{n}| = \omega$, there must be a real order
$Z \subseteq Y$ and a particular $n$-element set $D = \set{d_0,
\dots, d_{n - 1}} \subseteq W$ such that $D = D_y$ for every $y
\in Z$. In particular, we note that
\begin{itemize}
\item[(d')] $f``[Z, D]^{1, 2} = \set{0}$.
\end{itemize}
Define a partition $f_D : [Z]^{2} \to \set{0, \dots, n - 1, n}$ as
follows. For each pair of distinct elements $z_0$ and~$z_1$ of~$Z$,
put
\[
f_D\set{z_0, z_1} =
\begin{cases}
0 & \text{if $f\set{z_0, z_1, d_0} = 1$,} \\
\vdots & \quad \vdots \\
n - 1 & \text{if $f\set{z_0, z_1, d_{n - 1}} = 1$, or} \\
n & \text{if $f\set{z_0, z_1, d} = 0$ for each $d \in D$.}
\end{cases}
\]
By Fact~\ref{fact:pairs}, either
\begin{itemize}
\item[(e)] there are $i < n$ and $A \in [Z]^{\omega + m}$ such that
$f_D``[A]^{2} = \set{i}$ (and hence with $f``[A, \set{d_i}]^{2,1}
= \set{1}$), or
\item[(f)] there is $C \in [Z]^{\omega}$ such that $f_D``[C]^{2} =
\set{n}$ (and hence with $f``[C, D]^{2,1} = \set{0}$).
\end{itemize}
If (e) holds, then by the claim, either (a) or (b) holds, and we are
done. We may therefore assume (once again without loss of
generality) that (f) holds.
Consider the partition $f \restriction [C]^{3} : [C]^{3} \to \set{0,
1}$. Because $C \to (\omega, 4)^{3}$ (by Fact~\ref{fact:ramsey}),
either
\begin{itemize}
\item[(g)] there is $B \in [C]^{4}$ with $f``[B]^{3} = \set{1}$, or
\item[(h)] there is $E \in [C]^{\omega}$ with $f``[E]^{3} =
\set{0}$.
\end{itemize}
If (g) holds, then (b) follows, and we are done. We may therefore
assume that (h) holds. Similarly, because $D \to (m, 4)$ (by our
choice of~$n$), either
\begin{itemize}
\item[(i)] there is $B \in [D]^{4}$ with $f``[B]^{3} = \set{1}$, or
\item[(j)] there is $F \in [D]^{m}$ with $f``[F]^{3} =
\set{0}$.
\end{itemize}
As before, if (i) holds, then (b) follows, and we are done. We may
therefore assume that (j) holds.
Finally, let $A = E \cup F$. Note that $A \in [X]^{\omega + m}$,
since $E \in [X]^{\omega}$, $F \in [X]^{m}$, and $E < F$. Note also
that $f``[E, F]^{1, 2} = \set{0}$ by (d'); $f``[E, F]^{2, 1} =
\set{0}$ by (f); $f``[E]^{3} = \set{0}$ by (h); and $f``[F]^{3} =
\set{0}$ by (j). All of these together imply that $f``[A]^{3} =
\set{0}$. Thus (a) holds, and we are done.
\end{proof}
\section{In conclusion}
We wish to consider the possibilities for improvement on
Theorem~\ref{theorem:main}. We know of two negative results which
place direct limitations on such improvements,
Theorems~\ref{theorem:bad} and~\ref{theorem:ugly} below.
(Incidentally, Theorem~\ref{theorem:bad} provides an answer to a
question of E.~C.~Milner and K.~Prikry in~\cite[Section~1,
p.~489]{MR87f:04006}.)
\begin{theorem}
\label{theorem:bad}
Let~$X$ be an order and~$\kappa$ be an infinite cardinal. If~$X$ has
character no greater than~$2^{\kappa}$, that is, if~$X \nto
(\omega)_{2^\kappa}^{1}$, then $X \nto (\kappa + 2, \omega)^{3}$.
In particular, if~$X$ is an order with character no greater than the
cardinality of the continuum, that is, if $X \nto
(\omega)_{2^{\omega}}^{1}$, then $X \nto (\omega + 2, \omega)^{3}$.
\end{theorem}
\begin{proof}
Suppose $e : [X]^{1} \to {}^{\kappa}2$ witnesses that $X \nto
(\omega)_{2^{\kappa}}^{1}$. Thus for no set $B \in [X]^{\omega}$
is~$e$ constant on~$[B]^{1}$. Consequently, for any set $B \in
[X]^{\omega}$ there is a set $C \in [B]^{\omega}$ such that~$e$ is
one-to-one on~$[C]^{1}$.
Define a partition of pairs $f : [X]^{2} \to \kappa + 1$ as follows.
For each pair $x, y \in X$ with $x < y$, let
\[
f\set{x, y} = \delta(e\set{x}, e\set{y}),
\]
where $\delta (s, t) = \min \left( \SET{\xi < \kappa}{s(\xi) \neq
t(\xi)} \cup \set{\kappa} \right)$ for each pair of sequences
$s$ and~$t$ in~${}^{\kappa}2$. Next, define a partition of triples
$g : [X]^{3} \to \set{0, 1}$ as follows. For each triple $x, y, z
\in X$ with $x < y < z$, let
\[
g\set{x, y, z} =
\begin{cases}
0 & \text{if~$e$ is one-to-one on $[\set{x, y, z}]^{1}$ and
$f\set{x, y} < f\set{y, z}$,} \\
1 & \text{if~$e$ is not one-to-one on $[\set{x, y, z}]^{1}$ or
$f\set{x, y} \geq f\set{y, z}$.}
\end{cases}
\]
This partition does the trick:
\begin{claim*}
There is no set $A \in [X]^{\kappa + 2}$ with $g``[A]^{3} = \set{0}$.
\end{claim*}
Assume to the contrary that there is $A \in [X]^{\kappa + 2}$ with
$g``[A]^{3} = \set{0}$. Note that~$e$ is necessarily one-to-one
on~$[A]^{1}$, by the definition of~$g$. Enumerate~$A$ in increasing
order as
\[
A = \set{x_0, x_1, \dots, x_{\alpha}, \dots, x_{\kappa}, x_{\kappa + 1}}.
\]
Let $\xi = f\set{x_{\kappa}, x_{\kappa + 1}}$. Since
$e\set{x_{\kappa}} \neq e\set{x_{\kappa + 1}}$, it must be that $\xi
< \kappa$. Next, we note that for any triple $s, t, u \in
{}^{\kappa}2$, if $\delta(s, t) < \delta(t, u)$, then $\delta(s, u)
= \delta(s, t)$. Thus, for every pair $\alpha < \beta < \kappa$ we
have that $f\set{x_{\alpha}, x_{\kappa}} = f\set{x_{\alpha},
x_{\beta}} < f\set{x_{\beta}, x_{\kappa}}$. But also,
$f\set{x_{\alpha}, x_{\kappa}} < f\set{x_{\kappa}, x_{\kappa + 1}} =
\xi$ for each $\alpha < \kappa$. But this is absurd; if we define
$h : \kappa \to \kappa$ by letting $h(\alpha) = f\set{x_{\alpha},
x_{\kappa}}$ for each $\alpha < \kappa$, then the preceding
remarks tell us that~$h(\alpha) < h(\beta)$ for each pair $\alpha <
\beta < \kappa$ and yet $h``\kappa \subseteq \xi < \kappa$, which is
impossible. Thus no such set~$A \in [X]^{\kappa + 2}$ exists.
\begin{claim*}
There is no set $B \in [X]^{\omega}$ with $g``[B]^{3} = \set{1}$.
\end{claim*}
Assume to the contrary that there is $B \in [X]^{\omega}$ with
$g``[B]^{3} = \set{1}$. By the remarks at the beginning of the
proof, we may assume without loss of generality that~$e$ is
one-to-one on~$[B]^{1}$. Consider a new partition $h : [B]^{3} \to
\set{0, 1}$ defined as follows. For each triple $x, y, z \in B$
with $x < y < z$, let
\[
h\set{x, y, z} =
\begin{cases}
0 & \text{if $f\set{x, y} > f\set{y, z}$,} \\
1 & \text{if $f\set{x, y} = f\set{y, z}$.}
\end{cases}
\]
Since $g``[B]^{3} = \set{1}$, this partition is well-defined. But
also, since $\omega \to (\omega, 4)^{3}$, either
\begin{itemize}
\item[(a)] there is $C \in [B]^{\omega}$ such that $h``[C]^{3} =
\set{0}$, or
\item[(b)] there is $D \in [B]^{4}$ such that $h``[D]^{3} =
\set{1}$.
\end{itemize}
If (a) is true, then there would be an infinite descending sequence
of ordinals, which is absurd. If (b) is true, then there would be
three distinct sequences in~${}^{\kappa}2$, each pair of which first
differed at the same point, which is also absurd. Thus no such set
$B \in [X]^{\omega}$ exists.
\end{proof}
\begin{theorem}
\label{theorem:ugly}
Let~$X$ be an order and~$\kappa$ be an infinite cardinal. If $X
\nto (\cf \kappa)_{\kappa}^{1}$, then $X \nto (\kappa + 1, 4)^{3}$.
In particular, if~$X$ has countable character, then $X \nto (\omega
+ 1, 4)^{3}$.
\end{theorem}
\begin{proof}
Suppose the partition $e : [X]^{1} \to \kappa$ witnesses that $X
\nto (\cf \kappa)_{\kappa}^{1}$. Thus for no set $C \in [X]^{\cf
\kappa}$ is~$e$ constant on~$[C]^{1}$. Consequently, for any set
$A \in [X]^{\kappa}$ there is a set $B \in [A]^{\kappa}$ such
that~$e$ is one-to-one on~$[B]^{1}$. The next claim goes this one
step better.
\begin{claim*}
For any set $A \in [X]^{\kappa}$ there is a subset $B \in
[A]^{\kappa}$ such that~$e$ is strictly increasing on~$[B]^{1}$.
(That is, such that $e\set{x} < e\set{y}$ for any pair $x, y \in
B$ with $x < y$.)
\end{claim*}
\begin{proof}
It is a well-known theorem of B.~Dushnik, P.~Erd\H{o}s, and
E.~W.~Miller (see, for example,~\cite[Theorem~44,
pp.~475--476]{MR18:458a}) that $\kappa \to (\kappa, \omega)^{2}$
for any infinite cardinal~$\kappa$. If we define a partition $f :
[A]^{2} \to \set{0, 1}$ by letting
\[
f\set{x, y} =
\begin{cases}
0 & \text{if $e\set{x} \leq e\set{y}$,} \\
1 & \text{if $e\set{x} > e\set{y}$,}
\end{cases}
\]
for each pair $x, y \in A$ with $x < y$, then this tells us that
either
\begin{itemize}
\item[(c)] there is a set $C \in [A]^{\kappa}$ such that
$f``[C]^{2} = \set{0}$, or
\item[(d)] there is a set $D \in [B]^{\omega}$ such that
$f``[D]^{2} = \set{1}$.
\end{itemize}
If (d) is true, then $e``[D]^{1}$ would constitute an infinite
strictly decreasing sequence of ordinals, which is absurd. Thus
(c) must be true. As we mentioned above, there must be a set $B
\in [C]^{\kappa}$ with~$e$ one-to-one on~$[B]^{1}$. Clearly,~$e$
is strictly increasing on~$[B]^{1}$.
\end{proof}
Define a partition of triples $f : [X]^{3} \to \set{0, 1}$ as
follows. For a triple $x, y, z \in X$ with $x < y < z$, let
\[
f\set{x, y, z} =
\begin{cases}
0 & \text{if either $e\set{x} \geq e\set{y}$ or $e\set{y} \leq
e\set{z}$,} \\
1 & \text{if both $e\set{x} < e\set{y}$ and $e\set{y} >
e\set{z}$.}
\end{cases}
\]
We will show that neither
\begin{itemize}
\item[(a)] is there $A \in [X]^{\kappa + 1}$ such that $f``[A]^{3} =
\set{0}$, nor
\item[(b)] is there $B \in [X]^{4}$ such that $f``[B]^{3} =
\set{1}$.
\end{itemize}
For suppose there is $A \in [X]^{\kappa + 1}$ with $f``[A]^{3} =
\set{0}$. Enumerate~$A$ in ascending order as $A = \set{x_0, x_1,
\dots, x_{\alpha}, \dots, x_{\kappa}}$. By the claim, we may
assume that~$e$ is strictly increasing on~$[A \setminus
\set{x_{\kappa}}]^{1}$. Consider triples of the form
$\set{x_{\alpha}, x_{\beta}, x_{\kappa}}$ for $\alpha < \beta <
\kappa$; by the definition of~$g$, because $e\set{x_{\alpha}} <
e\set{x_{\beta}}$, it must be that $e\set{x_{\beta}} \leq
e\set{x_{\kappa}}$ for each $\beta < \kappa$. But this is absurd,
as~$e``[A \setminus \set{x_{\kappa}}]^{1}$ is cofinal in~$\kappa$
(because~$e$ is strictly increasing on~$[A]^{1}$). Thus no such set
$A \in [X]^{\kappa + 1}$ exists.
Suppose also that there is $B \in [X]^{4}$ with $f``[B]^{3} =
\set{1}$. Enumerate~$B$ in increasing order as $\set{y_0, y_1, y_2,
y_3}$. Because $g\set{y_0, y_1, y_2} = 1$, it must be that $y_1 >
y_2$. Because $g\set{y_1, y_2, y_3} = 1$, it must be that $y_1 <
y_2$. Clearly this is absurd; thus no such set $B \in [X]^{4}$
exists.
\end{proof}
In the light of Theorems~\ref{theorem:bad} and~\ref{theorem:ugly}, a
positive resolution of the following question would be the best
improvement of Theorem~\ref{theorem:main} possible.
\begin{question}
\label{question:main}
If~$X$ is an order with uncountable character, then does $X \to
(\alpha, n)^{3}$ for every countable ordinal~$\alpha$ and every
natural number~$n$?
\end{question}
Currently, the best results toward a resolution of this question are
due to E.~C.~Milner and K.~Prikry, who demonstrated
in~\cite[Section~3, pp.~185--190]{MR93i:03065} that $\omega_1 \to
(\omega + \omega + 1, 4)^{3}$; and to the author, who was able to show
in \cite[Sections~4 and~5, pp.~35--52]{X:2} that if~$X$ is an order
with uncountable character, then $X \to (\alpha, n)^{3}$ for any
ordinal $\alpha < \omega + \omega$ and any natural number $n <
\omega$. These two results make the final questions below the
simplest open cases of Question~\ref{question:main}.
\begin{question}
If~$X$ is an order with uncountable character (into which~$\omega_1$
does not embed), does then $X \to (\omega + \omega, 4)^{3}$? In
particular, does $\mathbb{R} \to (\omega + \omega, 4)^{3}$?
\end{question}
\begin{question}
Does $\omega_1 \to (\omega + \omega + 2, 4)^{3}$?
\end{question}
\begin{question}
Does $\omega_1 \to (\omega + \omega, 5)^{3}$?
\end{question}
\bibliographystyle{plain}
\bibliography{v7i1r24}
\end{document}