3 Fixed some typos

The Baumgartner-Hajnal theorem, from "A proof (involving Martin’s Axiom) of a partition relation". Fund. Math., 78(3):193–203, 1973.

Actually, there is a very interesting mathematical story here, and several problems.

The question was first asked about uncountable sets of reals and $\omega_1$. Quickly, it was recognized to be a problem about what we know now call special non-special orders. $L$ is non-special iff $L\to(\omega)^1_\omega$, meaning that if $L$ is split into countably many pieces, at least one is not reverse-well-ordered, i.e., at least one it contains a strictly increasing sequence. B-H prove Baumgartner and Hajnal proved that $L\to(\alpha)^2_n$ for any countable ordinal $\alpha$ and $n<\omega$.

(In human: If L is non-speacialnon-special, and to each subset of L $L$ of size 2 we assign a color, there being only finitely many colors to begin with, then for any countable ordinals $\alpha$ there is a subset of $L$ order isomorphic to $\alpha$, all of whose 2-sized subsets are assigned the same color.)

Their original proof uses Martin's axiom, as it depends on a kind of diagonalization over certain functions $f:\omega\to\omega$ and one needs that if there are not "too many" of them, then there is one dominating all. This is to my mind the key use of MA in their paper, although there is another one. Then one argues that being special is preserved by ccc forcing and that the conclusion is absolute.

Galvin later found a very nice combinatorial argument that avoids forcing. Clinton Conley recently found a similar proof. It rests on a kind of abstract Fubini theorem, the point being that the special linear sub-orders of a non-special $L$ form a proper $\sigma$-complete ideal. Galvin noticed that the result should hold in a more general setting, and conjectured that that's the case.

The conjecture was later proved by Stevo Todorcevic. : $P\to(\alpha)^2_n$ holds if $P$ is non-special, but it suffices that $P$ is a partial order, rather than a linear order. Stevo's argument is beautiful , and argument proceeds by three stages:

1. To each $P$ we can associate a certain tree, ; if $P$ is non-special, so is the tree (in the usual sense of non-special, hence the name), and the result holds for $P$ iff it does for the tree. This is a direct combinatorial argument, but it is very general (not just for colorings of pairs). For example, it simplifies the proof that $P\to(\omega)^1_\omega$ implies $P\to(\alpha)^1_\omega$ for any $\alpha<\omega_1$. We get a nice combinatorial theory of non-special trees, for : For example, an appropriate versions version of Fodor's lemma holdholds.
2. The result holds for non-special trees of size less than the pseudo-intersection number ${\mathfrak p}$. (This is one of the cardinal invariants of the continuum.) Again, the proof does not use forcing.
3. Finally, a forcing argument shows that ${\mathfrak p}$ can be made as large as one wants while preserving being non-special, and by absoluteness we get the full theorem. The argument here shows in particular, that one does not need preservation of being non-special under ccc forcing, simpler particular classes of forcings forcing notions suffice.

Stevo's paper is "Partition relations for partially ordered sets". Acta Math., 155(1-2):1–25, 1985.

As far as I know, there is no forcing-free proof of 33., that the result holds for all non-special trees $T$, even if $|T|\ge{\mathfrak p}$. It cannot be a direct argument, as Stevo found examples of non-special trees all of whose subtrees of small size are special. Albin Jones indicated a while ago that he had an argument, but I never saw it and his webpage and contact information vanished since. In my mind, this remains open.

A few years ago, Rene Schipperus proved a "topological" version of Baumgartner-Hajnal, namely that if $L$ is an uncountable subset of ${\mathbb R}$, or $\omega_1$, then for any $\alpha<\omega_1$ and any coloring of the 2-sized subsets of $L$ with finitely many colors, we can find monochromatic sets of type $\alpha+1$ that, moreover, are closed in the natural topology of ${\mathbb R}$ or $\omega_1$. Rene uses an argument that builds on the original approach, and in particular uses MA. I don't know how to prove Rene's his theorem without using forcing.

Finally: The corresponding result in dimension 3 should be that if $P$ is a non-special partial order, then $P\to(\alpha,n)^3$, i.e., that if the 3-sized subsets of $P$ are colored with 2 colors, then either for the first color for each $\alpha<\omega_1$ there are homogeneous sets of type $\alpha$, or else for the second color there are linearly ordered homogeneous sets of any finite size. This is open, and several people have worked hard on it for years.

2 deleted 3 characters in body

The Baumgartner-Hajnal theorem, from "A proof (involving Martin’s Axiom) of a partition relation". Fund. Math., 78(3):193–203, 1973.

Actually, there is a very interesting mathematical story here, and several problems.

The question was first about uncountable sets of reals and $\omega_1$. Quickly, it was recognized to be a problem about what we know call special orders. $L$ is non-special iff $L\to(\omega)^1_\omega$, meaning that if $L$ is split into countably many pieces, at least one is not reverse-well-ordered, i.e., at least one contains a strictly increasing sequence. B-H prove that $L\to(\alpha)^2_n$ for any countable ordinal $\alpha$ and $n<\omega$.

(In human: If L is non-speacial, and to each subset of L of size 2 we assign a color, there being only finitely many colors to begin with, then for any countable ordinals $\alpha$ there is a subset of $L$ order isomorphic to $\alpha$, all of whose 2-sized subsets are assigned the same color.)

Their original proof uses Martin's axiom, as it depends on a kind of diagonalization over certain functions $f:\omega\to\omega$ and one needs that if there are not "too many" of them, then there is one dominating all. This is to my mind the key use of MA in their paper, although there is another one. Then one argues that being special is preserved by ccc forcing and that the conclusion is absolute.

Galvin later found a very nice combinatorial argument that avoids forcing. Clinton Conley recently found a similar proof. It rests on a kind of abstract Fubini theorem, the point being that the special linear sub-orders of a non-special $L$ form a proper $\sigma$-complete ideal. Galvin noticed that the result should hold in a more general setting, and conjectured that that's the case.

The conjecture was later proved by Stevo Todorcevic. $P\to(\alpha)^2_n$ holds if $P$ is non-special, but it suffices that $P$ is a partial order, rather than a linear order. Stevo's argument is beautiful, and proceeds by three stages:

1. To each $P$ we can associate a certain tree, if $P$ is non-special, so is the tree (in the usual sense of non-special, hence the name), and the result holds for $P$ iff it does for the tree. This is a direct combinatorial argument, but it is very general (not just for colorings of pairs). For example, it simplifies the proof that $P\to(\omega)^1_\omega$ implies $P\to(\alpha)^1_\omega$ for any $\alpha<\omega_1$. We get a nice combinatorial theory of non-special trees, for example, appropriate versions of Fodor's lemma hold.
2. The result holds for non-special trees of size less than the pseudo-intersection number ${\mathfrak p}$. (This is one of the cardinal invariants of the continuum.) Again, the proof is does not use forcing.
3. Finally, a forcing argument shows that ${\mathfrak p}$ can be made as large as one wants while preserving being non-special, and by absoluteness we get the full theorem. The argument here shows in particular, that one does not need preservation under ccc forcing, simpler particular classes of forcings suffice.

Stevo's paper is "Partition relations for partially ordered sets". Acta Math., 155(1-2):1–25, 1985.

As far as I know, there is no forcing-free proof of 3, that the result holds for all non-special trees $T$, even if $|T|\ge{\mathfrak p}$. It cannot be a direct argument, as Stevo found examples of non-special trees all of whose subtrees of small size are special. Albin Jones indicated a while ago that he had an argument, but I never saw it and his webpage and contact information vanished since. In my mind, this remains open.

A few years ago, Rene Schipperus proved a "topological" version of Baumgartner-Hajnal, namely that if $L$ is an uncountable subset of ${\mathbb R}$, or $\omega_1$, then for any $\alpha<\omega_1$ and any coloring of the 2-sized subsets of $L$ with finitely many colors, we can find monochromatic sets of type $\alpha+1$ that, moreover, are closed in the natural topology of ${\mathbb R}$ or $\omega_1$. Rene uses an argument that builds on the original approach, and in particular uses MA. I don't know how to prove Rene's theorem without using forcing.

Finally: The corresponding result in dimension 3 should be that if $P$ is a non-special partial order, then $P\to(\alpha,n)^3$, i.e., that if the 3-sized subsets of $P$ are colored with 2 colors, then either for the first color for each $\alpha<\omega_1$ there are homogeneous sets of type $\alpha$, or else for the second color there are linearly ordered homogeneous sets of any finite size. This is open, and several people have worked hard on it for years.

The Baumgartner-Hajnal theorem, from "A proof (involving Martin’s Axiom) of a partition relation". Fund. Math., 78(3):193–203, 1973.

Actually, there is a very interesting mathematical story here, and several problems.

The question was first about uncountable sets of reals and $\omega_1$. Quickly, it was recognized to be a problem about what we know call special orders. $L$ is non-special iff $L\to(\omega)^1_\omega$, meaning that if $L$ is split into countably many pieces, at least one is not reverse-well-ordered, i.e., at least one contains a strictly increasing sequence. B-H prove that $L\to(\alpha)^2_n$ for any countable ordinal $\alpha$ and $n<\omega$.

(In human: If L is non-speacial, and to each subset of L of size 2 we assign a color, there being only finitely many colors to begin with, then for any countable ordinals $\alpha$ there is a subset of $L$ order isomorphic to $\alpha$, all of whose 2-sized subsets are assigned the same color.)

Their original proof uses Martin's axiom, as it depends on a kind of diagonalization over certain functions $f:\omega\to\omega$ and one needs that if there are not "too many" of them, then there is one dominating all. This is to my mind the key use of MA in their paper, although there is another one. Then one argues that being special is preserved by ccc forcing and that the conclusion is absolute.

Galvin later found a very nice combinatorial argument that avoids forcing. Clinton Conley recently found a similar proof. It rests on a kind of abstract Fubini theorem, the point being that the special linear sub-orders of a non-special $L$ form a proper $\sigma$-complete ideal. Galvin noticed that the result should hold in a more general setting, and conjectured that that's the case.

The conjecture was later proved by Stevo Todorcevic. $P\to(\alpha)^2_n$ holds if $P$ is non-special, but it suffices that $P$ is a partial order, rather than a linear order. Stevo's argument is beautiful, and proceeds by three stages:

1. To each $P$ we can associate a certain tree, if $P$ is non-special, so is the tree (in the usual sense of non-special, hence the name), and the result holds for $P$ iff it does for the tree. This is a direct combinatorial argument, but it is very general (not just for colorings of pairs). For example, it simplifies the proof that $P\to(\omega)^1_\omega$ implies $P\to(\alpha)^1_\omega$ for any $\alpha<\omega_1$. We get a nice combinatorial theory of non-special trees, for example, appropriate versions of Fodor's lemma hold.
2. The result holds for non-special trees of size less than the pseudo-intersection number ${\mathfrak p}$. (This is one of the cardinal invariants of the continuum.) Again, the proof is does not use forcing.
3. Finally, a forcing argument shows that ${\mathfrak p}$ can be made as large as one wants while preserving being non-special, and by absoluteness we get the full theorem. The argument here shows in particular, that one does not need preservation under ccc forcing, simpler particular classes of forcings suffice.

Stevo's paper is "Partition relations for partially ordered sets". Acta Math., 155(1-2):1–25, 1985.

As far as I know, there is no forcing-free proof of 3, that the result holds for all non-special trees $T$, even if $|T|\ge{\mathfrak p}$. It cannot be a direct argument, as Stevo found examples of non-special trees all of whose subtrees of small size are special. Albin Jones indicated a while ago that he had an argument, but I never saw it and his webpage and contact information vanished since. In my mind, this remains open.

A few years ago, Rene Schipperus proved a "topological" version of Baumgartner-Hajnal, namely that if $L$ is an uncountable subset of ${\mathbb R}$, or $\omega_1$, then for any $\alpha<\omega_1$ and any coloring of the 2-sized subsets of $L$ with finitely many colors, we can find monochromatic sets of type $\alpha+1$ that, moreover, are closed in the natural topology of ${\mathbb R}$ or $\omega_1$. Rene uses an argument that builds on the original approach, and in particular uses MA. I don't know how to prove Rene's theorem without using forcing.

Finally: The corresponding result in dimension 3 should be that if $P$ is a non-special partial order, then $P\to(\alpha,n)^3$, i.e., that if the 3-sized subsets of $P$ are colored with 2 colors, then either for the first color for each $\alpha<\omega_1$ there are homogeneous sets of type $\alpha$, or else for the second color there are linearly ordered homogeneous sets of any finite size. This is open, and several people have worked hard on it for years.