Does the rank (=height) of a well partial order bound its type (=length, =stature)?

Question

Terminology and context

(This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.)

A partially ordered set is called well-founded iff it has no infinite decreasing sequence. It is called well-partially-ordered (=wpo) iff it is well-founded and also has no infinite antichain; equivalently, every linearization (=total order extending the given order) is a well-order; equivalently, the lattice its downsets (=downwards-closed subset, =initial segments), partially ordered by inclusion, is well-founded.

The (well-founded) rank of a well-founded partially ordered set $P$ is the ordinal defined inductively by $\mathop{\mathrm{rk}}P = \sup\{\mathop{\mathrm{rk}}(x)+1 : x\in P\}$ where $\mathop{\mathrm{rk}}x = \sup\{\mathop{\mathrm{rk}}(y)+1 : y<x\}$. This is sometimes also called its “height”. (Obviously, for a well-order, this is just the order type.)

If $P$ is well-partially-ordered, then the sup of the order types of linearizations is attained (de Jongh and Parikh, “Well-Partial Orderings and Hierarchies”, Nederl. Akad. Wetensch. Proc. Ser. A 80 = Indag. Math. 39 (1977), 195–207, thm. 2.13). Furthermore, the sup in question is also the well-founded rank of the set of proper downsets, partially ordered by inclusion (a fact surprisingly difficult to find in the literature: see Blass & Gurevich, “Program Termination and Well Partial Orderings”, ACM Trans. Comput. Log. 9 (2008), art. 18, §4.1 and §7). Let this ordinal $o(P)$ be called the type or “length” or “stature” (comments about which term is best are welcome, incidentally).

Clearly, $\mathop{\mathrm{rk}} P \leq o(P)$ (with equality when $P$ is, in fact, totally ordered, i.e., well-ordered). Also note for example that if $P = \Sigma^*$ is the set of words on a finite alphabet $\Sigma$, partially ordered by the “subword” relation, then $o(\Sigma^*) = \omega^{\omega^{n-1}}$ where $n = \#\Sigma$ (see this other question), whereas $\mathop{\mathrm{rk}}(\Sigma^*) = \omega$.

Question

Is it possible to give a an upper bound on the type $o(P)$ of a wpo $P$ based solely on its rank $\mathop{\mathrm{rk}} P$?

And, of course, if the answer is “no”, I'd also like to know what is the smallest rank for which one can construct wpo's of arbitrarily large type, and how.

(Many papers related to the subject seem to tiptoe around this question without actually asking it, let alone answering it. I find this perplexing because it seems like an obvious thing to ask, and no matter if the answer is easy, well-known or an open problem, whether it is positive or negative, I think it would behoove to point it out. I seem to understand that the question might perhaps have been discussed in Diana Schmidt's Habilitationsschrift, but I don't have access to it.)

Answer 1

$\DeclareMathOperator{\rk}{rk}$If I’m not mistaken, there’s a rather easy crude bound: $o(P) < (\omega \cdot (\rk P))^+$, where $(-)^+$ is cardinal successor.

Since $o(P)$ is the order-type of some linearisation, it’s clear that $|o(P)| = |P|$, and so $o(P) < |P|^+$. So if we can bound the cardinality of $P$ based on its rank, then we get a bound on its type.

On the other hand, for each $\alpha < \rk P$, the elements of rank precisely $\alpha$ form an antichain. So there are only finitely many elements of each rank; so $|P| \leq \omega . |\rk P|$.

(Thanks to @Sylvain for pointing out an unnecessary overcomplication in my original answer.)

Answer 2

The height (aka rank) and maximal order type (aka type, aka length, aka stature) of a wpo are not functionally related.

Consider for instance the family of finite partial orders (thus wpos) $P_n=\{a_1,b_1,\dots,a_n,b_n\}$ where $a_i\geq b_i$ for all $i$ and all the other pairs of elements are incomparable. Then $h(P_n)=2$ for all $n$, but $o(P_n)=2n$, for instance $a_1>\cdots>a_n>b_1>\cdots>b_n$ is a linear extension of maximal order type.

Note that they are related if we add the width of the wpo (a measure of the rank of antichains) to the mix: $$o(P)\leq w(P)\otimes h(P)$$ by Theorem 4.13 in [Igor Kříž and Robin Thomas. Ordinal types in Ramsey theory and well-partial-ordering theory. In J. Nešetřil and V. Rödl, editors, Algorithms and Combinatorics vol. 5: Mathematics of Ramsey Theory, pages 57–95. Springer, 1990.]. In the previous example, $w(P_n)=n$. In the case of well-orders $w(P)=1$ hence $h(P)=o(P)$ as you mentioned.

Answer 3

By Peter's cardinality argument, we have $o(P)<|\text{rk}\,P|$.

We show that this is the best possible:

Given an ordinal $\alpha$ of cardinality $\aleph_i$, we construct an order of rank $\aleph_i$ with linearization of order type $\alpha$.

Take a bijection $f:\alpha\to\aleph_i$. We now order $\alpha$ with the order $x>_P y$ if $x>y$ as ordinals in $\alpha$, and $f(x)>f(y)$ as ordinals in the initial ordinal $\aleph_i=\omega_i$.

This is a subset of $\alpha\times\omega_i$, under the product order, and is hence a well-partial order. It also has the trivial linearisation to $\alpha$, by restoring the original order.

Finally, $f$ can be inductively proven to be an upper bound on the rank of each element. Via Peter's cardinality argument, one can see that $\aleph_i$ is also a lower bound; hence the height of $P$ is in fact $\aleph_i$.

Hence a well-partial order of rank $\aleph_i$ can have a linearisation of order type $\alpha$, which can be taken to be as large as desired.

Finally, it's worth noting that by extending the order by appending larger elements, this argument works for any rank not just $\aleph_i$.