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](http://www.sciencedirect.com/science/article/pii/1385725877900671)”, *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](http://dl.acm.org/citation.cfm?id=1352586)”, *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](https://mathoverflow.net/questions/237188/computing-the-ordinal-of-a-rational-language-well-partially-ordered-by-the-subwo)), 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.)



Does the rank (=height) of a well partial order bound its type (=length, =stature)?
$\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.)


