I have been trying to solve to prove the following statement:

Let $\kappa$ be an uncountable cardinal. The following are equivalent:

  1. Every linear order of cardinality $\kappa$ has a suborder of order-type $\kappa$ or $\kappa^*$ ($\kappa$ inverted).
  2. $\kappa\longrightarrow (\kappa)_2^2$

The fact that (2) implies (1) is easy to show. For (1) implies (2), I have been trying to define a linear order based on an arbitrary coloring on $[\kappa]^2$, but so far my idea does not work.

Can anybody give me some suggestion?

  • $\begingroup$ This is an interesting problem! I couldn't do it directly, but I can show that (1) implies that $\kappa$ is inaccessible and has the tree property, which is equivalent to (2). I can write more about the proof, but here is a hint: look at lexicographic orders of trees. $\endgroup$ Aug 29, 2018 at 16:30
  • $\begingroup$ Yeah, I now know how to do the exercise using the equivalence between $\kappa\to(\kappa)_2^2$ and $\kappa$ inaccessible and with the tree property, although the details are still very involved. I am now wondering if there is any direct proof using an appropriate linear ordering of $\kappa$. $\endgroup$
    – Darío G
    Aug 30, 2018 at 20:32
  • $\begingroup$ You should write down your solution as an answer. I don't know of a more direct proof, but I think you can avoid talking about the tree property by starting with a colouring, looking at the tree of attempts to build a homogeneous set, and then applying (1) to the lex order of this particular tree. This effectively inlines the proof that the tree property implies the Ramsey property, but I don't know that it makes the solution more transparent. $\endgroup$ Aug 31, 2018 at 6:22
  • $\begingroup$ The sketch of the proof of this beautiful assertion can be found in the book "Set Theory: An Introduction To Large Cardinals" written by Frank Drake, in the pages 214 and 216, respectively. $\endgroup$ Feb 18, 2020 at 17:55

1 Answer 1


I am writing this answer so that the question is removed from the unanswered queue, but it is likely that there is a clever, more direct proof.$\newcommand{\funcs}[2]{{}^{#1}{#2}}$$\newcommand{\lelex}{<_{\mathrm{lex}}}$

I am going to show that (1) implies that $\kappa$ is inaccessible and has the tree property. It is a standard fact that these two properties are equivalent to (2) (see e.g. Theorem 7.8 in Kanamori's book).

First, $\kappa$ is regular. Otherwise, suppose that $\langle\kappa_\alpha;\alpha<\lambda\rangle$ for some $\lambda<\kappa$ is a cofinal sequence in $\kappa$. Consider the linear order $L=\sum_{\alpha<\lambda}[\kappa_\alpha,\kappa_{\alpha+1})^*$, that is, start with $\lambda$ and replace each $\alpha\in\lambda$ with the interval $[\kappa_\alpha,\kappa_{\alpha+1})$ ordered in reverse. Any increasing sequence in $L$ can have only finitely many elements in each block, and there are not enough blocks for an increasing sequence of length $\kappa$ to exist. On the other hand, any decreasing sequence in $L$ must eventually be contained in a single block, and none of the blocks are long enough for a decreasing sequence of length $\kappa$ to exist. But this contradicts (1).

Secondly, $\kappa$ is a strong limit. Otherwise, suppose that there is $\lambda<\kappa$ such that $2^\lambda\geq\kappa$. Consider the linear order $L=(\funcs{\lambda}{2},\lelex)$. Suppose that there is an increasing or decreasing sequence $\langle f_\alpha;\alpha<\kappa\rangle$ in $L$. In either case note that if $\alpha<\beta<\gamma$ then $f_\gamma$ splits away from $f_\alpha$ no later than $f_\beta$ splits away from $f_\alpha$. Now fix $f_0$. By the previous observation there are a node $t_0\in \funcs{<\lambda}{2}$ on the branch $f_0$ and an ordinal $\alpha_0<\kappa$ such that for every $\alpha\geq\alpha_0$ the branch $f_\alpha$ splits from $f_0$ at $t_0$. Now repeat this argument with $f_{\alpha_0}$ to get a new node $t_1\sqsupset t_0$ and a tail of the branches that split from $f_{\alpha_0}$ at $t_1$. Repeat this $\lambda$ many times and observe that the nodes $t_\alpha$ now form a branch $g\in \funcs{\lambda}{2}$. But $\kappa$ is regular, so the sequence of ordinals $\langle\alpha_\xi;\xi<\lambda\rangle$ is bounded by some $\alpha_\lambda<\kappa$. But from the way we constructed the branch $g$, it follows that all the branches after $f_{\alpha_\lambda}$ are equal to $g$, leading to a contradiction.

Thirdly, $\kappa$ has the tree property. Let $T$ be a $\kappa$-tree; we may assume that it is a subtree of $\funcs{<\kappa}{\kappa}$. Consider the linear order $L=(T,\lelex)$, where $s\lelex t$ if $s$ is an initial segment of $t$ or, when they split, $s$ splits to the left.

Suppose there is a lex-decreasing sequence of nodes $\langle t_\alpha;\alpha<\kappa\rangle$. As before, there is a node $s_0\sqsubset t_0$ such that a tail of the sequence splits from $t_0$ at $s_0$. Furthermore, there is an ordinal $\eta_0$ such that a (possibly smaller) tail of the sequence passes through $s_0^\frown \eta_0$. Now repeat this argument $\kappa$ many times as before to build a branch through $T$.

Now suppose that there is a lex-increasing sequence of nodes $\langle t_\alpha;\alpha<\kappa\rangle$. It may be the case that this sequence contains a branch, in which case we would be done. So assume there is no cofinal subsequence that would form a branch. Let $P_0$ be a maximal linearly ordered (in the tree order) subset of the $t_\alpha$ containing $t_0$. By our assumption a tail of the $t_\alpha$ is not contained in $P_0$, so each $t_\alpha$ in this tail must split away from $\bigcup P_0$. Since, again, later nodes in the sequence must split away no later than earlier nodes, a tail of them must split away from $\bigcup P_0$ at the same node $s_0$. But since $T$ is a $\kappa$-tree, there must be an ordinal $\eta_0$ such that a (possibly smaller) tail of the sequence passes through $s_0^\frown \eta_0$. Now repeat this argument $\kappa$ many times to build a branch through $T$ along the nodes $s_\alpha$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .