5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Couldn't you bound directly by $o(P)<|P|^+$ in the second paragraph? $\endgroup$ – Sylvain Oct 11 '16 at 16:32
  • $\begingroup$ @Sylvain: oops, yes, of course! I don’t know what I was thinking, thanks :-) $\endgroup$ – Peter LeFanu Lumsdaine Oct 11 '16 at 16:38
  • $\begingroup$ Do I understand correctly that this yields $o(P)<\omega_1$ for all $0<\text{rk}\,P<\omega_1$? Couldn't one use the Dushnik-Miller Theorem to a similar end: $\kappa\longrightarrow(\kappa,\aleph_0)^2$ implies $o(P)<|\text{rk}\,P|^+$ for infinite $P$? $\endgroup$ – Sylvain Oct 12 '16 at 11:46
  • $\begingroup$ @Sylvain: absolutely — indeed, that doesn’t need Dushnik-Miller, just the fact that $| \omega . \alpha | = | \alpha |$ for infinite $\alpha$. $\endgroup$ – Peter LeFanu Lumsdaine Oct 12 '16 at 14:24
  • 3
    $\begingroup$ I have to say I can't remember whether I missed this easy bound or whether I forgot to mention I was mostly interested in countable wpos. You certainly answered the question as it was stated, but I have to admit I was hoping for an answer that would give a countable bound on the type for each countable bound on the rank. (It's probably not worth re-asking the question with this clarification, though, because if someone knew a better answer, they'd have given it by now.) $\endgroup$ – Gro-Tsen Oct 27 '16 at 13:44
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ These are nice facts/examples, but they don’t seem to answer the question. E.g. your first family of examples shows that wpo’s of height 2 can have unbounded finite length — but still, their length is bounded by $\omega$. $\endgroup$ – Peter LeFanu Lumsdaine Oct 11 '16 at 16:08
  • 1
    $\begingroup$ @PeterLeFanuLumsdaine true, I understood the question in a restrictive way, as asking whether there existed an ordinal-theoretic function $f$ such that $o(P)=f(h(P))$. $\endgroup$ – Sylvain Oct 11 '16 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.