MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(I am assuming choice.)

Suppose that ${\mathbb P}=(P,{\lt})$ is a partially ordered set (a poset), and that $\kappa\le\lambda$ are ordinals. The notation $$ {\mathbb P}\to(\kappa)^1_\lambda $$ means that whenever $f:P\to\lambda$, we can find some $i\in\lambda$ and some subset $H$ of $P$ such that $(H,{\lt})$ is order-isomorphic to $\kappa$ and $f(a)=i$ for all $a\in H$.

Theorem. Suppose that $P$ is a poset and $P\to(\kappa)^1_\kappa$, where $\kappa$ is an infinite cardinal. Then $P\to(\alpha)^1_\kappa$ for all $\alpha\lt\kappa^+$.

This is due to Galvin (unpublished). A nice combinatorial argument is presented in Stevo Todorcevic, "Partition relations for partially ordered sets", Acta Math. 155 (1985), no. 1-2, 1-25.

In fact, Galvin result is that:

For any poset $P$, $$ P\to(\kappa)^1_\lambda $$ implies $$ P\to(\alpha)^1_\lambda $$ whenever $\kappa\le\lambda$ are infinite cardinals and $\alpha\lt\kappa^+$.

This can be proved by collapsing $\lambda$ to $\kappa$ with a $\kappa$-closed forcing, noting that in the extension $P\to(\kappa)^1_\kappa$, so (by the theorem) $P\to(\alpha)^1_\kappa$, and using the closure of the forcing to find such a homogeneous set of type $\alpha$ in the ground model.

My question:

How can we prove Galvin's result without appealing to a forcing argument?

Very briefly, Stevo's proof of the theorem proceeds as follows: Given a poset $P$, let $\sigma'P$ be the collection of injective sequences $\tau$ whose domain is a successor ordinal and whose range is strictly increasing in the ordering of $P$. This is a poset under the "initial segment" ordering of sequences. Stevo proves two results:

  1. If $P\to(\kappa)^1_\kappa$ holds, then $\sigma' P\to(\kappa)^1_\kappa$ holds.
  2. If $\sigma' P\to(\alpha)^1_\gamma$ holds, then $P\to(\alpha)^1_\gamma$ holds.

Item 2 is straightforward, and a more general result holds. Item 1 uses a delicate argument and I do not know of a more general statement. The general version of 2 says that many partition relations that hold for $\sigma' P$ must hold for $P$ as well.

The combination of 1 and 2 is very powerful: It says that to prove partition results for posets $P$ satisfying $P\to(\kappa)^1_\kappa$ it suffices to prove the result for trees, for which the combinatorics tends to be much better understood than for arbitrary posets.

For example, for trees $T$ it is essentially obvious that if $T\to(\kappa)^1_\kappa$, then $T\to(\alpha)^1_\kappa$ for all $\alpha\lt\kappa^+$, and the theorem follows.

share|cite|improve this question
Hi Andres. This sounds interesting. But can you elaborate on how you use the ${<}\kappa$-closure of the forcing $Coll(\kappa, \lambda)$ to get a homogeneous set of order type $\alpha$ in the ground model for arbitrary $\alpha < \kappa^+$? I can see how we can use it to recover a well order of order-type $\kappa$ by defining a descending sequence of conditions $\langle p_{\alpha}| \alpha < \kappa\rangle$ where $p_{\alpha}$ decides element # $\alpha$ in the order, but no more. Also, are you assuming $\kappa$ is regular since you're using that $Coll(\kappa, \lambda)$ is ${<}\kappa$-closed? – Jason Dec 8 '10 at 7:37
@Jason : One can assume $\kappa$ regular (though you are right, I didn't comment on it). Then, given a homogeneous set of type $\alpha\in[\kappa,\kappa^+)$, fix a bijection $\varphi$ between $\kappa$ and $\alpha$, and let $p_\beta$ ($\beta<\kappa$) decide the $\varphi(\beta)$-th element of the set. – Andrés E. Caicedo Dec 8 '10 at 17:40
@Andres: Oh yeah, of course. Thanks. – Jason Dec 8 '10 at 18:00
up vote 7 down vote accepted

Assume that $P\rightarrow(\kappa)^1_\lambda$, yet for some $\alpha<\kappa^+$, $P\not\rightarrow(\alpha)^1_\lambda$. Accordingly, there is a decomposition $P=\bigcup_{\xi<\lambda}P_\xi$ such that no $(P_\xi,<)$ does contain a chain of type $\alpha$. For some $\xi<\lambda$ we must have $P_\xi\rightarrow (\kappa)^1_\lambda$ as otherwise all of them would be the union of $\lambda$ subsets, each missing a chain of type $\kappa$, and then, takigk union, the same would hold for $P$. Applying Galvin's original theorem, $P_\xi$ contains a chain of type $\alpha$, contradiction.

share|cite|improve this answer
Hi Peter. Thanks! This turned out easier than expected. – Andrés E. Caicedo Dec 8 '10 at 17:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.