Skip to main content
Fixed some typos
Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

The question was first asked about uncountable sets of reals and $\omega_1$. Quickly, it was recognized to be a problem about what we knownow call specialnon-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 oneit contains a strictly increasing sequence. B-H proveBaumgartner and Hajnal proved that $L\to(\alpha)^2_n$ for any countable ordinal $\alpha$ and $n<\omega$.

(In human: If L is non-speacialspecial, 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.)

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 argument proceeds by three stages:

  1. To each $P$ we can associate a certain tree,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 versionsversion 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 forcingsforcing notions suffice.

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'shis theorem without using forcing.

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.)

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 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.

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.

The question was first asked about uncountable sets of reals and $\omega_1$. Quickly, it was recognized to be a problem about what we now call 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., it contains a strictly increasing sequence. Baumgartner and Hajnal proved that $L\to(\alpha)^2_n$ for any countable ordinal $\alpha$ and $n<\omega$.

(In human: If L is non-special, 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.)

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 beautiful 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 example, an appropriate version of Fodor's lemma holds.
  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 forcing notions suffice.

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 his theorem without using forcing.

deleted 3 characters in body
Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240
  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.
  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.
  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 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.
Post Made Community Wiki
Source Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

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.