François G. Dorais

Research in Logic and Foundations of Mathematics


Subposets of small dimension

Behind the scenes at Boole’s Rings, there was some talk on asking more open questions related to our research. I have three related problems that I would like to share. They are strikingly similar in nature, but they properly belong in three different branches of mathematics: the first problem is about finite combinatorics, the second problem is about reverse mathematics, and the third problem is about infinite combinatorics. To me they are three faces of the same question and I currently don’t know how to answer any of them.

Three Problems. Let :

  1. Let denote the largest number such that every poset of size has a -dimensional subposet of size . What is the asymptotic growth of ?
  2. Every (countably) infinite poset has an infinite subposet of dimension at most . What is the logical strength of this statement over ?
  3. Is there an uncountable poset that has no uncountable -dimensional subposet?

In all three cases, dimension refers to the Dushnik–Miller dimension of the poset , which is the smallest number of linear orders on the set such that

for all . In other words, when thinking of each relation as a set of ordered pairs. Equivalently, for countable and finite posets, this is the smallest number such that is embeddable in with the coordinatewise ordering (which explains the name).

I asked the first question on MathOverflow (Dorais 2010). Observing that the dimension of a finite poset never exceeds its width, Goodwillie (2010) answered that for sufficiently large . This feels correct for , but it doesn’t feel optimal for . (No, I don’t have a concrete reason why I feel that way.) Goodwillie’s argument (for general ) runs as follows. Let be a poset of size and width . If then, by definition, has an antichain of size at least . Since antichains have dimension at most , we’re done. If then, by Dilworth’s Theorem, can be partitioned into chains of average size at least . If is large enough, the union of the largest chains in this partition forms a -dimensional subposet of with size at least . My main motivation for asking this question on MathOverflow was to get some inspiration to attack the other two questions. I was hoping that this question had already been answered in the finite combinatorics literature, perhaps in a different guise, but this does not appear to be the case.

The second question is a ramification of a problem from Denis Hirschfeldt and Richard Shore. In their paper (Hirschfeldt–Shore 2007), they studied the Chain-Antichain Principle (), which is the statement that every (countably) infinite poset either has an infinite chain or an infinite antichain. Since chains have dimension and antichains have dimension , this immediately implies that every infinite poset has an infinite subposet of dimension at most . Hirschfeldt and Shore also studied the Ascending-Descending Sequence Principle (), which they show is equivalent to the restriction of to -dimensional posets (Theorem 5.3). A straightforward induction shows that is equivalent to the restriction of to -dimensional posets for any standard integer . Although Hirschfeldt and Shore show that is strictly weaker than Ramsey’s Theorem for pairs and two colors (), it is still an open question whether is strictly weaker than . This is where the second problem comes in. If proves that every infinite poset has an infinite subposet of dimension at most then is equivalent to , if not then we have a separation of and .

The third question may be a little surprising. In the infinite case, the partition relation guarantees that every infinite poset has an infinite subposet of dimension at most . Since is false, it may seem unlikely that every uncountable poset has an uncountable -dimensional subposet. However, Sierpiński’s classical argument to prove that simply shows that there is an uncountable -dimensional poset that has no uncountable chains and no uncountable antichains, so this is of little help. Is there an uncountable poset that has no uncountable finite-dimensional subposet? I suspect that such monsters do exist, at least in some models of ZFC, but they are certainly very elusive!

There is a little side story to this last question. In (Moore 2006), Justin Moore showed that, assuming PFA, every uncountable linear ordering contains an isomorphic copy of one of the following five uncountable linear orders:

Sierpiński’s counterexample is the comparability graph of the two-dimensional poset obtained by combining and . Similar counterexamples can be made by combining and , or and , or all three , , and . Moore’s five element basis guarantees that every finite-dimensional poset contains a combination of this kind (assuming PFA). If every uncountable poset has an uncountable finite-dimensional subposet, then we obtain a nice basis for the class of uncountable posets!

References

  1. F. G. Dorais, 2010: Subposets of small Dushnik-Miller dimension, MathOverflow question 29169.

  2. T. Goodwillie, 2010: Subposets of small Dushnik-Miller dimension, MathOverflow answer 29570.

  3. D. R. Hirschfeldt, R. A. Shore, 2007: Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic 72, no. 1, 171–206.

  4. J. T. Moore, 2006: A five element basis for the uncountable linear orders, Ann. of Math. (2) 163, no. 2, 669–688.


CC0 Originally posted on by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.


Comments