{"id":4209,"date":"2021-10-23T15:20:37","date_gmt":"2021-10-23T13:20:37","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=4209"},"modified":"2022-11-19T14:57:06","modified_gmt":"2022-11-19T13:57:06","slug":"statures-of-noetherian-spaces-i-maximal-order-types-of-wpos","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=4209","title":{"rendered":"Statures of Noetherian spaces I: maximal order types of wpos"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Quite some time ago, I posted a list of open problems under the heading of &#8220;<a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1134\">ordinal heights of Noetherian spaces<\/a>&#8220;.  I am happy to say that a masters student of mine, Bastien Laboureix, made quite some forays in the field.  It is therefore time that I spoke about the notions involved.  Unfortunately, I will not be able to say anything about what Bastien did, since I will have plenty of other things to say before.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">By the way, I will change some of the notions of the aforementioned page of open problems\u2014because they are not really suitable.  The main theme of Bastien&#8217;s work is about a generalization of the theory of <em>maximal order types<\/em> of well-quasi-orders to the setting of Noetherian spaces.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Well-quasi-orders<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">A well-quasi-order is a preordered set (<em>P<\/em>,\u2264), or simply <em>P<\/em>, that is well-founded (there is no strictly descending sequence <em>p<\/em><sub>0<\/sub> &gt; <em>p<\/em><sub>1<\/sub> &gt; &#8230; &gt; <em>p<sub>n<\/sub><\/em> &gt; &#8230;) and has no infinite antichain (an antichain is a set of pairwise incomparable elements).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">There is an amazing collection of equivalent characterizations of well-quasi-orders (for short, wqos).  Some of them are given in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>, see Proposition 9.7.17:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A wqo is a preordered set <em>P<\/em> that is Noetherian in its Alexandroff topology.  This is probably the weirdest possible characterization of wqos.  Explicitly, that means that every ascending sequence <em>U<\/em><sub>0<\/sub> \u2286 <em>U<\/em><sub>1<\/sub> \u2286 &#8230; \u2286 <em>U<\/em><sub><em>n<\/em><\/sub> \u2286 &#8230; of upwards-closed subsets of <em>P<\/em> (=of open subsets in its Alexandroff topology) is <em>stationary<\/em>: after some rank <em>n<\/em><sub>0<\/sub>, all the sets <em>U<\/em><sub><em>n<\/em><\/sub> must be equal.  Equivalently, by taking complements, every descending sequence <em>C<\/em><sub>0<\/sub> \u2287 <em>C<\/em><sub>1<\/sub> \u2287 &#8230; \u2287 <em>C<\/em><sub><em>n<\/em><\/sub> \u2287 &#8230; of downwards-closed subsets (=closed sets in the Alexandroff topology) is stationary.<\/li>\n\n\n\n<li>A wqo is a preordered set <em>P<\/em> in which every (countably infinite) sequence <em>p<\/em><sub>0<\/sub>, <em>p<\/em><sub>1<\/sub>, &#8230;, <em>p<sub>n<\/sub><\/em>, &#8230; of points is <em>good<\/em>: there must be two points <em>p<sub>m<\/sub><\/em> and <em>p<sub>n<\/sub><\/em>, with <em>m<\/em>&lt;<em>n<\/em> and <em>p<sub>m<\/sub><\/em>\u2264<em>p<sub>n<\/sub><\/em>.  In other words, imagine your task is to emit an infinite sequence of points; whatever you do, at some point you will be forced to play a point <em>p<sub>n<\/sub><\/em> that is above some point <em>p<sub>m<\/sub><\/em> that you have played earlier.<\/li>\n\n\n\n<li>A wqo is a preordered set <em>P<\/em> in which every (countably infinite) sequence <em>p<\/em><sub>0<\/sub>, <em>p<\/em><sub>1<\/sub>, &#8230;, <em>p<sub>n<\/sub><\/em>, &#8230; of points is <em>perfect<\/em>: there must be an (infinite) subsequence that is monotonic.<\/li>\n\n\n\n<li>A wqo is a preordered set <em>P<\/em> in which every upwards-closed subset is finitary, namely of the form \u2191<em>A<\/em> with <em>A<\/em> finite.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">I have been teaching a <a href=\"https:\/\/wikimpri.dptinfo.ens-paris-saclay.fr\/doku.php?id=cours:c-2-9-1\">masters 2 course<\/a> on the topic for a few years.  If you are curious, maybe the easiest introduction is to browse through the slides (<a href=\"https:\/\/wikimpri.dptinfo.ens-paris-saclay.fr\/lib\/exe\/fetch.php?media=cours:upload:slides-2-9-1-cours1.pdf\">part 1<\/a>, <a href=\"https:\/\/wikimpri.dptinfo.ens-paris-saclay.fr\/lib\/exe\/fetch.php?media=cours:upload:slides-2-9-1-cours2.pdf\">part 2<\/a>, <a href=\"https:\/\/wikimpri.dptinfo.ens-paris-saclay.fr\/lib\/exe\/fetch.php?media=cours:upload:slides-2-9-1-cours3.pdf\">part 3<\/a>, and <a href=\"https:\/\/wikimpri.dptinfo.ens-paris-saclay.fr\/lib\/exe\/fetch.php?media=cours:upload:slides-2-9-1-cours4.pdf\">part 4<\/a>).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">That course is geared towards computer scientists, so each concept is illustrated with an application in computer science.  Some of them are quite fascinating, notably the decidability of the coverability question for effective WSTS, which is incredibly easy once you have the proper tools, but totally out of reach if you don&#8217;t; or what I call &#8220;magic algorithms&#8221;\u2014efficient algorithms that provably exist, but which nobody can implement, since nobody knows what they are.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I am only teaching the mathematical basis of wqo theory, and <a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~phs\/\">Philippe Schnoebelen<\/a> then takes on, studying the complexity of certain wqo-based algorithms.  That complexity is usually completely crazy.  For example, the time complexity of the reachability question for lossy channel systems\u2014a question that can be solved with a very simple, 3-line algorithm\u2014is provably (much) higher than the Ackermann function (which is already growing insanely fast towards infinity).  Those complexity results are based on so-called finite minimizations of results on so-called <em>maximal order types<\/em> of wqos&#8230; and here we come to the topic of the current post.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I am interested in generalizing this notion to Noetherian spaces, and I will claim that the correct generalization of maximal order types to the setting of Noetherian spaces is something that I will call the <em>stature<\/em> of the Noetherian space, generalizing only slightly from a notion introduced by Blass and Gurevich [4].  I will require some basic knowledge of ordinals.  Anyway, I will only give proofs of only the easiest results.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Wolk&#8217;s theorem<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Before we come to statures, I will have to explain some of the basics of the theory of maximal order types of wqos.  The following will apply to <em>well<\/em> <em>partial orders<\/em>, namely to wqos whose preordering is an ordering (i.e., is antisymmetric).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Every well-partial-order (<em>wpo<\/em>, for short) is well-founded, and Szpilrajn&#8217;s theorem [1] states that every well-founded partial ordering \u2264 on a set <em>P<\/em> has at least one well-founded linearization \u2291; a <em>linearization<\/em> is a total extension of \u2264, namely a total ordering \u2291 such that for all <em>p<\/em>, <em>q<\/em> in <em>P<\/em> such that <em>p<\/em>\u2264<em>q<\/em>, we have <em>p<\/em>\u2291<em>q<\/em>.  I have already mentioned this theorem in the post on <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2702\">chains and nested spaces<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In 1967, Wolk showed the following.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Theorem (Wolk [2]).<\/strong>  A partial ordering \u2264 on a set <em>P<\/em> is a wpo if and only if <em>all<\/em> its linearizations are well-founded.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Every partial ordering \u2264 has at least one linearization, by Zorn&#8217;s Lemma: Szpilrajn&#8217;s theorem states that if \u2264 is well-founded, at least one of them is well-founded, while Wolk&#8217;s theorem states that \u2264 is wpo if and only if all those linearizations are well-founded.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>Proof.<\/em><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In one direction, we assume that \u2264 is wpo on <em>P<\/em>, and that \u2291 is a linearization of \u2264.  We consider an infinite (strictly) descending sequence <em>p<\/em><sub>0<\/sub> \u2290 <em>p<\/em><sub>1<\/sub> \u2290 &#8230; \u2290 <em>p<sub>n<\/sub><\/em> \u2290 &#8230; with respect to \u2291.  Since \u2264 is wpo, we can find two indices <em>m<\/em>&lt;<em>n<\/em> such that <em>p<sub>m<\/sub><\/em>\u2264<em>p<sub>n<\/sub><\/em>, and therefore <em>p<sub>m<\/sub><\/em>\u2291<em>p<sub>n<\/sub><\/em>, which is impossible since <em>p<sub>m<\/sub><\/em>\u2290<em>p<sub>n<\/sub><\/em>.<\/li>\n\n\n\n<li>In the other direction, we show that if \u2264 is not wpo on <em>P<\/em>, then it has a linearization that is not well-founded.  Since \u2264 is assumed not to be wpo, there is a sequence <em>p<\/em><sub>0<\/sub>, <em>p<\/em><sub>1<\/sub>, &#8230;, <em>p<sub>n<\/sub><\/em>, &#8230; that is <em>bad<\/em> (i.e., not good): for no pair of indices <em>m<\/em>&lt;<em>n<\/em> does <em>p<sub>m<\/sub><\/em>\u2264<em>p<sub>n<\/sub><\/em> hold.  We define a new relation \u2264&#8217; on <em>P<\/em> by <em>p<\/em>\u2264&#8217;<em>q<\/em> if and only if <em>p<\/em>\u2264<em>q<\/em> (case 1) or there are two indices <em>m<\/em>&lt;<em>n<\/em> such that <em>p<\/em>\u2264<em>p<sub>n<\/sub><\/em> and <em>p<sub>m<\/sub><\/em>\u2264<em>q<\/em> (case 2).  The following picture may help one understand case 2:<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/wolk.png\"><img loading=\"lazy\" decoding=\"async\" width=\"354\" height=\"242\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/wolk.png\" alt=\"\" class=\"wp-image-4275\"\/><\/a><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>We verify the following:<ul><li>\u2264&#8217; is transitive.  We assume that <em>p<\/em>\u2264&#8217;<em>q<\/em>\u2264&#8217;<em>r<\/em> and we wish to show that <em>p<\/em>\u2264&#8217;<em>r<\/em>.  There are four cases to consider, depending on whether <em>p<\/em>\u2264&#8217;<em>q<\/em> was obtained in case 1 or in case 2, and similarly for <em>q<\/em>\u2264&#8217;<em>r<\/em>.  Only of those cases is interesting, and this is the case 2\/case 2 situation: then there are indices <em>m<\/em>&lt;<em>n<\/em> and <em>i<\/em>&lt;<em>j<\/em> such that <em>p<\/em>\u2264<em>p<sub>n<\/sub><\/em> and <em>p<sub>m<\/sub><\/em>\u2264<em>q<\/em>, and <em>q<\/em>\u2264<em>p<sub>j<\/sub><\/em> and <em>p<sub>i<\/sub><\/em>\u2264<em>r<\/em>. In particular, <em>p<sub>m<\/sub><\/em>\u2264<em>p<sub>j<\/sub><\/em>, and that cannot happen if <em>m<\/em>&lt;<em>j<\/em>, so <em>m<\/em>\u2265<em>j<\/em>. In that case, we have <em>i<\/em>&lt;<em>n<\/em> (since <em>i<\/em>&lt;<em>j<\/em>\u2264<em>m<\/em>&lt;<em>n<\/em>), and also <em>p<\/em>\u2264<em>p<sub>n<\/sub><\/em> and <em>p<sub>i<\/sub><\/em>\u2264<em>r<\/em>, so that <em>p<\/em>\u2264<em>r<\/em>.<\/li><\/ul>\n<ul class=\"wp-block-list\">\n<li>\u2264&#8217; is antisymmetric: we again have four cases to consider.  We start with <em>p<\/em>\u2264&#8217;<em>q<\/em>\u2264&#8217;<em>r<\/em> as above, where now <em>r<\/em>=<em>p<\/em>.  In the case 2\/case 2 situation (profiting from the fact that the situation is still fresh in your memory!), we have <em>p<\/em>\u2264<em>p<sub>n<\/sub><\/em> and <em>p<sub>i<\/sub><\/em>\u2264<em>r<\/em>, where now <em>r<\/em>=<em>p<\/em>; this implies <em>p<sub>i<\/sub><\/em>\u2264<em>p<sub>n<\/sub><\/em>, which is impossible since <em>i<\/em>&lt;<em>n<\/em>.  The case 1\/case 2 situation and the case 2\/case 1 situation lead to similar contradictions, and in the case 1\/case 1 situation, we have <em>p<\/em>\u2264<em>q<\/em>\u2264<em>r<\/em>=<em>p<\/em>, so <em>p<\/em>=<em>q<\/em>, since \u2264 is a partial ordering.<\/li>\n\n\n\n<li>The sequence <em>p<\/em><sub>0<\/sub>, <em>p<\/em><sub>1<\/sub>, &#8230;, <em>p<sub>n<\/sub><\/em>, &#8230; is an infinite sequence that is strictly decreasing with respect to \u2264&#8217;: it suffices to show that for every natural number <em>n<\/em>, <em>p<sub>n<\/sub><\/em>\u2265&#8217;<em>p<sub>n<\/sub><\/em><sub>+1<\/sub> (a typical case 2 situation) and <em>p<sub>n<\/sub><\/em>\u2270&#8217;<em>p<sub>n<\/sub><\/em><sub>+1<\/sub>.  We claim that the latter cannot happen, and for that, we assume that <em>p<sub>n<\/sub><\/em>\u2264&#8217;<em>p<sub>n<\/sub><\/em><sub>+1<\/sub>, aiming (again) for a contradiction.  Since we started with a bad sequence, <em>p<sub>n<\/sub><\/em>\u2264&#8217;<em>p<sub>n<\/sub><\/em><sub>+1<\/sub> cannot have been obtained from a case 1 situation (since <em>p<sub>n<\/sub><\/em>\u2270<em>p<sub>n<\/sub><\/em><sub>+1<\/sub>); therefore there are two indices <em>i<\/em>&lt;<em>j<\/em> such that <em>p<sub>n<\/sub><\/em>\u2264<em>p<sub>j<\/sub><\/em> and <em>p<sub>i<\/sub><\/em>\u2264<em>p<sub>n<\/sub><\/em><sub>+1<\/sub>.  Again since the original sequence is bad, and <em>p<sub>n<\/sub><\/em>\u2264<em>p<sub>j<\/sub><\/em>, we cannot have <em>n<\/em>&lt;<em>j<\/em>, so <em>n<\/em>\u2265<em>j<\/em>; similarly, <em>i<\/em>\u2265<em>n<\/em>+1.  It follows that <em>i<\/em>&gt;<em>j<\/em>, which is absurd since <em>i<\/em>&lt;<em>j<\/em>.<\/li>\n\n\n\n<li>We now consider any linear extension \u2291 of \u2264&#8217;.  I have already said that every partial ordering has at least one linear extension.  Since <em>p<\/em><sub>0<\/sub> &gt;&#8217; <em>p<\/em><sub>1<\/sub> &gt;&#8217; &#8230; &gt;&#8217; <em>p<sub>n<\/sub><\/em> &gt;&#8217; &#8230;, we also have <em>p<\/em><sub>0<\/sub> \u2290 <em>p<\/em><sub>1<\/sub> \u2290 &#8230; \u2290 <em>p<sub>n<\/sub><\/em> \u2290 &#8230;  We have therefore reached our goal of proving that \u2264 has a linear extension (\u2291) that is not well-founded.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Maximal order types of wpos<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">So let (<em>P<\/em>, \u2264) be a wpo.  By Wolk&#8217;s theorem, all the linear extensions \u2291 of \u2264 are well-founded.  Every total well-founded ordering \u2291 is isomorphic to a unique ordinal \u03b1, which is fancy way to say that you can enumerate the elements of <em>P<\/em> as (<em>p<\/em><sub>\u03b2<\/sub>)<sub>\u03b2&lt;\u03b1<\/sub> in such a way that <em>p<\/em><sub>\u03b2<\/sub>\u2291<em>p<\/em><sub>\u03b3<\/sub> if and only if \u03b2\u2264\u03b3, for all \u03b2,\u03b3&lt;\u03b1; in other words, <em>p<\/em><sub>0<\/sub> \u228f <em>p<\/em><sub>1<\/sub> \u228f &#8230;  \u228f <em>p<\/em><sub>\u03c9<\/sub> \u228f <em>p<\/em><sub>\u03c9+1<\/sub> \u228f &#8230; \u228f <em>p<\/em><sub>\u03c9.2<\/sub> \u228f <em>p<\/em><sub>\u03c9.2+1<\/sub> \u228f &#8230; (and so on and so forth).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Such ordinals are called the <em>order types<\/em> of (linear extensions of) \u2264.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">What kinds of ordinals \u03b1 can you obtain this way?  In other words, what do the order types of (linear extensions of) \u2264 look like?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">When <em>P<\/em> is finite, say of cardinality <em>n<\/em>, any enumeration of <em>P<\/em> will be of the form <em>p<\/em><sub>0<\/sub> \u228f <em>p<\/em><sub>1<\/sub> \u228f &#8230; \u228f <em>p<\/em><sub><em>n<\/em>\u20131<\/sub>, and the only possible order type you will ever get is <em>n<\/em> (= the ordinal {0, 1, &#8230;, <em>n<\/em>\u20131}).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">When \u2264 is a total well-founded ordering (in particular, a wpo, as one can check\u2014even when <em>P<\/em> is infinite), then (<em>P<\/em>, \u2264) is itself isomorphic to a unique ordinal \u03b1, which is its unique order type.  For example, the order type of <strong>N<\/strong> with its usual ordering is \u03c9, the first infinite ordinal; the order type of <strong>N<\/strong><sup>2<\/sup>, with the lexicographic ordering, is \u03c9<sup>2<\/sup> (the first ordinal strictly larger than every ordinal \u03c9.<em>i<\/em>+<em>j<\/em> with <em>i<\/em>,<em>j<\/em> \u2208 <strong>N<\/strong>; the isomorphism maps the pair (<em>i<\/em>,<em>j<\/em>) to \u03c9.<em>i<\/em>+<em>j<\/em>); the order type of <strong>N<\/strong><sup>3<\/sup>, with the lexicographic ordering, is \u03c9<sup>3<\/sup>; &#8230; and so on.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The situation gets more interesting with infinite, partially ordered wpos.  Let me illustrate this with the example of <strong>N<\/strong>+<strong>N<\/strong>, the coproduct of two copies of <strong>N<\/strong>, each one with its usual ordering.  The elements of <strong>N<\/strong>+<strong>N<\/strong> are pairs (0,<em>m<\/em>) and (1,<em>n<\/em>), where <em>m<\/em>,<em>n<\/em> \u2208 <strong>N<\/strong>; 0 means &#8220;coming from the left copy&#8221;, 1 means &#8220;coming from the right copy&#8221;.  We order them by: (<em>i<\/em>,<em>m<\/em>) \u2264 (<em>i<\/em>,<em>n<\/em>) if and only if <em>m<\/em>\u2264<em>n<\/em> in <strong>N<\/strong> (whether <em>i<\/em> is 0 or 1), and (0,<em>m<\/em>) and (1,<em>n<\/em>) are always incomparable.  The left part of the following figure should help you picture this.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/ordertypes.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/ordertypes.png\" alt=\"\" class=\"wp-image-4233\" width=\"607\" height=\"172\"\/><\/a><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">The ordering we have just defined is a wpo.  One can see this directly: any infinite sequence in <strong>N<\/strong>+<strong>N<\/strong> must contain an infinite subsequence that lies entirely in the left copy, or entirely in the right copy, by the pigeonhole principle, and then it is easy to see that this subsequence must be good.  We produce the following two linearizations:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We can enumerate the elements of <strong>N<\/strong>+<strong>N<\/strong> by taking one from the left side, and one from the right side in alternation.  Namely, we enumerate them as (0,0) \u228f (1,0) \u228f (0,1) \u228f (1,1) \u228f (0,2) \u228f (1,2) \u228f &#8230; \u228f (0,<em>m<\/em>) \u228f (1,<em>m<\/em>) \u228f (0,<em>m<\/em>+1) \u228f (1,<em>m<\/em>+1) \u228f &#8230;  This has order type \u03c9.  I have shown this in blue above (the middle part).<\/li>\n\n\n\n<li>We can also enumerate them by listing all the elements of the first copy, followed by all the elements of the second copy: (0,0) \u228f (0,1) \u228f &#8230; \u228f (0,<em>m<\/em>) \u228f &#8230; (infinitely many elements here) \u228f (1,0) \u228f (1,1) \u228f &#8230; \u228f (1,<em>n<\/em>) \u228f &#8230; (infinitely many elements again).  The order type of this enumeration is \u03c9.2, the first ordinal larger than all the ordinals \u03c9+<em>n<\/em>, <em>n<\/em> \u2208 <strong>N<\/strong>.  Explicitly, the elements of the form (0,<em>m<\/em>) receive number <em>m<\/em> in that enumeration, while the elements of the form (1,<em>n<\/em>) receive number \u03c9+<em>n<\/em>.  This is shown on the right part of the above figure, in red.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">A remarkable result in the theory of well-partial-orders is the following theorem, due to de Jongh and Parikh:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Theorem [3, Theorem 2.13].<\/strong>  Given any wpo (<em>P<\/em>,<em>\u2264<\/em>), there is a linearization \u2264 whose order type is the largest among all order types of linearizations of \u2264.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The corresponding order type is called the <em>maximal order type<\/em> of \u2264 on <em>P<\/em>, and is written as <em>o<\/em>(<em>P<\/em>).  In the example of <strong>N<\/strong>+<strong>N<\/strong>, that maximal order type is <em>o<\/em>(<strong>N<\/strong>+<strong>N<\/strong>)=\u03c9.2.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The proof by de Jongh and Parikh is relatively long, and consists of twelve intermediate results before their main theorem.  The proof of the main theorem itself proceeds through several subcases.  This is long, but not too hard to understand.  In any case, I hope you will forgive me for not giving it here.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Blass and Gurevich [4] give another proof of the same result.  They claim that it is simpler, but their proof is at least as long, and uses a non-elementary Ramsey-type result due to Dushnik and Miller, so I doubt that there is any real gain in simplicity there.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">However, what Blass and Gurevich show is a more general result pertaining to the so-called <em>stature<\/em> of wpos.  (See Theorem 10 of [4].  We slowly come to the topic of the post!)  The same result had already been claimed by K\u0159\u00ed\u017e [5, Proposition 2.2, last two equalities], as an easy consequence of the de Jongh and Parikh theorem.  I must have missed something: I do not see any easy way of proving this, even using de Jongh and Parikh&#8217;s theorem.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">One possible definition of the stature of a wpo is as the ordinal rank of its poset of proper downwards-closed subsets under inclusion.  Oh, then, I need to explain what an ordinal rank is!  and I will do this right away.  We will return to statures once this is done.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Measuring the height of well-founded sets<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">There are at least two ways one can measure the height of a well-founded poset.  We start with the easy one\u2014which happens not to be the right one, but at least it is probably easier to understand.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">A <em>chain<\/em> in a poset <em>Z<\/em> is a total well-founded subset.  It is equivalent to say that this is a family (<em>z<\/em><sub>\u03b2<\/sub>)<sub>\u03b2&lt;\u03b1<\/sub>, indexed by the ordinals smaller than some ordinal \u03b1, such that for all \u03b2,\u03b3&lt;\u03b1, \u03b2&lt;\u03b3 implies <em>z<\/em><sub>\u03b2<\/sub>&lt;<em>z<\/em><sub>\u03b3<\/sub>.  The ordinal \u03b1 is the <em>length<\/em> of the family.  Let me call the <em>chain length<\/em> of <em>Z<\/em> the supremum of the lengths of all the chains included in <em>Z<\/em>, and let me write it as <em>l<\/em>(<em>Z<\/em>).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">That may sound similar to the maximal order type of <em>Z<\/em>, but that is very different.  Looking at <strong>N<\/strong>+<strong>N<\/strong> again should reveal the main difference.  The picture below is the same as the previous picture, except that I have shown the two maximal chains in <strong>N<\/strong>+<strong>N<\/strong> on the left, in green.  Each one has length \u03c9, and therefore <em>l<\/em>(<strong>N<\/strong>+<strong>N<\/strong>)=\u03c9.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/maxchains.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/maxchains.png\" alt=\"\" class=\"wp-image-4238\" width=\"607\" height=\"172\"\/><\/a><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">As you see, the green arrows are required to connect comparable elements; roughly, all the green arrows are drawn next to <em>some<\/em> black line.  This is very different from the blue and red arrows (extensions), which may connect incomparable elements.  With extensions, what you require is that <em>every<\/em> black line is colored blue or red.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let me proceed with the second measure of the height of a well-founded poset <em>Z<\/em>, which I will call its <em>rank<\/em>, and is sometimes called its <em>height<\/em> as well.  That has two equivalent definitions.  Let me start with the more abstract one: the rank rk <em>Z<\/em> of <em>Z<\/em> is the smallest ordinal \u03b1 such that one can number each element <em>z<\/em> of <em>Z<\/em> with an ordinal \u03c6(<em>z<\/em>)&lt;\u03b1, in such a way that <em>z<\/em>&lt;<em>z&#8217;<\/em> implies \u03c6(<em>z<\/em>)&lt;\u03c6(<em>z<\/em>&#8216;).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In other words, rk <em>Z<\/em> is the smallest ordinal \u03b1 such that there is a strictly monotonic map from <em>Z<\/em> to \u03b1.  (For that, you have to know that an ordinal is equal to the set of all ordinals strictly less than itself.)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">That smallest ordinal exists by the following argument.  First, there is an ordinal \u03b1 at all such that there is a strictly monotonic map from <em>Z<\/em> to \u03b1: we use Szpilrajn&#8217;s theorem to find a well-founded linearization of <em>Z<\/em>, and the order type of that linearization is such an ordinal.  Second, there is a <em>least<\/em> such ordinal because the class of ordinals is well-founded.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Note again the different between rank, chain length, and maximal order type:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The <strong>rank<\/strong> rk(<em>Z<\/em>) is the <em>least<\/em> ordinal \u03b1 such that there is a strictly monotonic map \u03c6 : <em>Z<\/em> \u2192 \u03b1.<\/li>\n\n\n\n<li>The <strong>chain length<\/strong> <em>l<\/em>(<em>Z<\/em>) is the <em>supremum<\/em> of all the ordinals \u03b1 such that there is a strictly monotonic map \u03c6 : \u03b1 \u2192 <em>Z<\/em>.  (Note that \u03b1 and <em>Z<\/em> have switched sides.)<\/li>\n\n\n\n<li>The <strong>maximal order type<\/strong> <em>o<\/em>(<em>P<\/em>) (of a wpo <em>P<\/em>) is the <em>largest<\/em> ordinal \u03b1 such that there is there is a bijective, strictly monotonic map \u03c6 : <em>Z<\/em> \u2192 \u03b1.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Here is the other definition or rank.  That one is a lot more concrete, and more operational.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">For each element <em>z<\/em> of <em>Z<\/em>, we define its rank rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>) (relative to <em>Z<\/em>) by well-founded induction (namely, knowing that we already know the rank of all strictly lower elements) by: rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>) is the smallest ordinal strictly larger than rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>&#8216;), for all elements <em>z<\/em>&#8216;&lt;<em>z<\/em>.  In other words:<\/p>\n\n\n\n<p class=\"has-text-align-center wp-block-paragraph\">rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>) = sup<sub><em>z<\/em>&#8216;&lt;<em>z<\/em><\/sub> (rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>&#8216;)+1).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Oh, please, do not write this as (sup<sub><em>z<\/em>&#8216;&lt;<em>z<\/em><\/sub> rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>&#8216;))+1.  Although that would give the same value in most cases, those two values differ when <em>z<\/em> is minimal; the latter would be equal to 1, whereas the rank of a minimal element is really equal to 0.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let us show that the two definitions are equivalent.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Lemma.<\/strong>  For every well-founded poset <em>Z<\/em>, rk <em>Z<\/em> = sup<sub><em>z\u2208Z<\/em><\/sub> (rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>)+1).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>Proof sketch.<\/em>  The map rk<em><sub>Z<\/sub><\/em> is a strictly monotonic map from <em>Z<\/em> to \u03b1\u225dsup<sub><em>z\u2208Z<\/em><\/sub> (rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>)+1).  Therefore rk <em>Z<\/em>\u2264\u03b1.  In the reverse direction, let \u03c6 be any strictly monotonic map from <em>Z<\/em> to some ordinal \u03b1&#8217;.  By well-founded induction on <em>z<\/em> in <em>Z<\/em>, it is easy to see that rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>) \u2264 \u03c6(<em>z<\/em>).  Therefore rk<em><sub>Z<\/sub><\/em>(<em>z<\/em>)+1 \u2264 \u03b1&#8217; for every <em>z<\/em> in <em>Z<\/em>, and by taking suprema, we obtain that \u03b1\u2264\u03b1&#8217;.  \u2610<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This leads to a useful trick.  Given a poset <em>Z<\/em>, let <em>Z<\/em><sup>\u22a4<\/sup> be <em>Z<\/em> with a fresh element \u22a4 added on top. The rank of <em>Z<\/em> is really the same thing as the rank of \u22a4 in <em>Z<\/em><sup>\u22a4<\/sup>!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">That lemma also gives us a practical way of computing rk <em>Z<\/em>.  We label the minimal elements <em>z<\/em> with 0.  Then we look at the elements <em>z<\/em> such that every element strictly below <em>z<\/em> has already been labeled, and we label them with the smallest ordinal strictly larger than all the labels of elements &lt;<em>z<\/em>&#8230; and so on, transfinitely.  The result is the following labeling, shown in green, on our example <strong>N<\/strong>+<strong>N<\/strong>.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/ordrank.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2021\/10\/ordrank.png\" alt=\"\" class=\"wp-image-4248\" width=\"176\" height=\"170\"\/><\/a><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\">Comparing chain length and rank<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The latter picture looks suspiciously like the previous picture, where I had depicted the longest chains in <strong>N<\/strong>+<strong>N<\/strong>, and that is not completely coincidental.  But beware, the chain length <em>l<\/em>(<em>Z<\/em>) of a well-founded poset <em>Z<\/em> is in general distinct from its ordinal rank rk(<em>Z<\/em>), as we will see below.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here are a few results on the relation between chain length and ordinal rank.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fact 1.<\/strong>  For every well-founded poset <em>Z<\/em>, <em>l<\/em>(<em>Z<\/em>)\u2264rk(<em>Z<\/em>).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>Proof.<\/em>  Let us consider any chain (<em>z<\/em><sub>\u03b2<\/sub>)<sub>\u03b2&lt;\u03b1<\/sub>, where for all \u03b2&lt;\u03b3&lt;\u03b1, we have <em>z<\/em><sub>\u03b2<\/sub>&lt;<em>z<\/em><sub>\u03b3<\/sub>. By definition, rk<em><sub>Z<\/sub><\/em>(<em>z<\/em><sub>\u03b2<\/sub>)&lt;rk<em><sub>Z<\/sub><\/em>(<em><em>z<\/em><sub>\u03b3<\/sub><\/em>), and therefore, by induction on \u03b2&lt;\u03b1, we obtain that \u03b2\u2264rk<em><sub>Z<\/sub><\/em>(<em>z<\/em><sub>\u03b2<\/sub>) for every \u03b2&lt;\u03b1. Adding one to both sides and taking suprema, this yields \u03b1\u2264sup<sub>\u03b2&lt;\u03b1<\/sub> (rk<em><sub>Z<\/sub><\/em>(<em>z<\/em><sub>\u03b2<\/sub>)+1)\u2264rk <em>Z<\/em>.  \u2610<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fact 2.<\/strong>  The inequality <em>l<\/em>(<em>Z<\/em>)\u2264rk(<em>Z<\/em>) is strict in general.  We can even chose <em>Z<\/em> so as to be a distributive, complete lattice.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><em>Proof.<\/em>  I will give two proofs.  The first one follows a hint given by D. Schmidt [7, paragraph before Theorem 1].  The second one is a slight modification of one given by K\u0159\u00ed\u017e [5, end of Section 3], who says that a similar counterexample was found by N. Zaguia, and will be a distributive, complete lattice.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>First proof.<\/strong>  In order to find <em>Z<\/em> such that <em>l<\/em>(<em>Z<\/em>)&lt;rk(<em>Z<\/em>), we show that there is a well-founded poset <em>Z<\/em><sub>\u03b1<\/sub> of rank at least \u03b1, for every ordinal \u03b1, and whose chains are all finite (so <em>l<\/em>(<em>Z<\/em><sub>\u03b1<\/sub>)\u2264\u03c9, and the supremum in the definition of <em>l<\/em>(<em>Z<\/em>) is not even attained).  Quite a gap between <em>l<\/em>(<em>Z<\/em><sub>\u03b1<\/sub>) and rk(<em>Z<\/em><sub>\u03b1<\/sub>)!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This is done by induction on \u03b1.  If \u03b1=0, the empty set fits.  For successor ordinals \u03b1+1, we add one element on top of <em>Z<\/em><sub>\u03b1<\/sub> in order to form <em>Z<\/em><sub>\u03b1+1<\/sub> (=<em><em>Z<\/em><sub>\u03b1<\/sub><\/em><sup>\u22a4<\/sup>).  For limit ordinals \u03b1, we define <em>Z<\/em><sub>\u03b1<\/sub> as the disjoint sum of all <em>Z<\/em><sub>\u03b2<\/sub><sup>\u22a4<\/sup>, \u03b2&lt;\u03b1.  We verify that the rank of <em>Z<\/em><sub>\u03b1<\/sub> is the supremum of the ranks of the top elements of each <em>Z<\/em><sub>\u03b2<\/sub><sup>\u22a4<\/sup>, \u03b2&lt;\u03b1, plus 1, namely the supremum of the ranks of <em>Z<\/em><sub>\u03b2<\/sub>, \u03b2&lt;\u03b1, plus 1.  That is at least the supremum of the family of ordinals \u03b2+1 where \u03b2&lt;\u03b1, and that supremum is larger than or equal to \u03b1.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Second proof.<\/strong>  The aim of that second proof is to find <em>Z<\/em> in the form of a distributive, complete lattice (which the posets <em>Z<\/em><sub>\u03b1<\/sub> certainly are not!).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We consider the first uncountable ordinal \u03c9<sub>1<\/sub>; equivalently, this is the poset of all countable ordinals.  We write \u03c9<sub>1cof<\/sub> for \u03c9<sub>1<\/sub> with its cofinite topology, and \u03c9<sub>1\u03c3<\/sub> for \u03c9<sub>1<\/sub> with the Scott topology of its usual ordering.  Those are both Noetherian spaces.  Indeed, every set with the cofinite topology (whose closed sets are the finite subsets, plus the whole set itself) is Noetherian, as one can check by verifying that every descending sequences of closed sets is stationary; and for \u03c9<sub>1\u03c3<\/sub>, we note that the ordering on \u03c9<sub>1<\/sub> is total and well-founded, hence wqo, that the Alexandroff topology of every wqo is Noetherian, and that the Scott topology, being coarser, is also Noetherian.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Then the product \u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub> is Noetherian, too, since finite products of Noetherian spaces are Noetherian (see Proposition 9.7.18 (vii) in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>).  Now a space is Noetherian if and only if every ascending sequence of open sets is stationary (Proposition 9.7.6 in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>), and that is equivalent to: every descending sequence of closed sets is stationary, so the family <strong>H<\/strong><sub>0<\/sub>(\u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub>) of all closed subsets of \u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub> is well-founded under inclusion.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Given any closed subset <em>C<\/em> of \u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub>, let me write supp(<em>C<\/em>) for the set of points \u03b2&lt;\u03c9<sub>1<\/sub> such that <em>C<\/em> contains a pair (\u03b2,\u03b3), for some \u03b3&lt;\u03c9<sub>1<\/sub>.  (Equivalently, the projection of <em>C<\/em> onto the <em>x<\/em>-axis.)  The set supp(<em>C<\/em>) is the <em>support<\/em> of <em>C<\/em>.  Let me consider the subposet <em>Z<\/em><sub>0<\/sub> of <strong>H<\/strong><sub>0<\/sub>(\u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub>) of those closed subsets <em>C<\/em> such that: (i) supp(<em>C<\/em>) is finite, and (ii) every element (\u03b2,\u03b3) of <em>C<\/em> is such that \u03b3&lt;\u03b2+1.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Finally, we let <em>Z<\/em> be the poset obtained from <em>Z<\/em><sub>0<\/sub> by adding a new element \u22a4 above all others.  Since <strong>H<\/strong><sub>0<\/sub>(\u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub>) is well-founded, so is <em>Z<\/em><sub>0<\/sub>, and therefore also <em>Z<\/em>.  One can check that the elements <em>C<\/em> of <em><em>Z<\/em><\/em><sub>0<\/sub> are exactly the finite unions of downward closures \u2193(\u03b2<sub>1<\/sub>,\u03b3<sub>1<\/sub>) \u222a &#8230; \u222a \u2193(\u03b2<sub><em>n<\/em><\/sub>,\u03b3<sub><em>n<\/em><\/sub>), where <em>n<\/em>\u22650, \u03b2<sub>1<\/sub>&lt;&#8230;&lt;\u03b2<sub><em>n<\/em><\/sub> and \u03b3<sub><em>i<\/em><\/sub>&lt;\u03b2<sub><em>i<\/em><\/sub>+1 for every <em>i<\/em>, 1\u2264<em>i<\/em>\u2264<em>n<\/em>.  (Just list the elements of supp(<em>C<\/em>) as \u03b2<sub>1<\/sub>&lt;&#8230;&lt;\u03b2<sub><em>n<\/em><\/sub>, then observe that for each <em>i<\/em>, \u03b2<sub><em>i<\/em><\/sub>+1 is a dcpo; so there is a largest element \u03b3<sub><em>i<\/em><\/sub> in <em>C<\/em> whose first coordinate is \u03b2<sub><em>i<\/em><\/sub>.)  From this description, it is fairly easy to see that <em><em>Z<\/em><\/em><sub>0<\/sub> is a distributive lattice, and therefore so is <em>Z<\/em>.  <em><em>Z<\/em><\/em><sub>0<\/sub> also has suprema of all the families of closed subsets whose supports are included in a common finite subset; all other families have \u22a4 as supremum.  Hence <em>Z<\/em> is a complete lattice.  (Infima are equally easy to compute: the infimum of any family not containing any element of <em><em>Z<\/em><\/em><sub>0<\/sub> is \u22a4, the infimum of any other family is the intersection of its non-\u22a4 elements.)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In order to complete the proof, we will show that rk<em> Z<\/em>\u2265\u03c9<sub>1<\/sub>+1, but <em>l<\/em>(<em>Z<\/em>)\u2264\u03c9<sub>1<\/sub>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For all \u03b2&lt;\u03c9<sub>1<\/sub> and \u03b3&lt;\u03b2+1, let us consider the downward closure \u2193(\u03b2,\u03b3) of (\u03b2,\u03b3) in \u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub>. (Equivalently, the set of pairs (\u03b2,\u03b3&#8221;) with \u03b3&#8221;\u2264\u03b3, since the specialization ordering of \u03c9<sub>1cof<\/sub> \u00d7 \u03c9<sub>1\u03c3<\/sub> is the product = \u00d7 \u2264.) \u2193(\u03b2,\u03b3) is an element of <em>Z<\/em>, since it is the closure of {(\u03b2,\u03b3)}, and its support is the finite set {\u03b2}. If \u03b3&lt;\u03b3'&lt;\u03b2+1, then \u2193(\u03b2,\u03b3) is strictly included in \u2193(\u03b2,\u03b3&#8217;), so rk<em><sub>Z<\/sub><\/em>(\u2193(\u03b2,\u03b3))&lt;rk<em><sub>Z<\/sub><\/em>(\u2193(\u03b2,\u03b3&#8217;)). By induction on \u03b2&lt;\u03c9<sub>1<\/sub>, it follows that rk<em><sub>Z<\/sub><\/em>(\u2193(\u03b2,\u03b3))\u2265\u03b3. In particular, rk<em><sub>Z<\/sub><\/em>(\u2193(\u03b3,\u03b3))\u2265\u03b3 for every \u03b3&lt;\u03c9<sub>1<\/sub>. By adding one to each side of the inequality and taking suprema over \u03b3&lt;\u03c9<sub>1<\/sub>, rk<em><sub>Z<\/sub><\/em>(\u22a4)\u2265\u03c9<sub>1<\/sub>. Therefore rk<em> Z<\/em>\u2265\u03c9<sub>1<\/sub>+1. (As an exercise, you may want to show that rk<em> Z<\/em>=\u03c9<sub>1<\/sub>+1.)<\/li>\n\n\n\n<li>In order to show that <em>l<\/em>(<em>Z<\/em>)\u2264\u03c9<sub>1<\/sub>, it suffices to show that every chain (<em>C<\/em><sub>\u03b2<\/sub>)<sub>\u03b2&lt;\u03b1<\/sub> in <em>Z<\/em> is countable.  Any such chain is a chain in <em>Z<\/em><sub>0<\/sub>, plus possibly one element (\u22a4). Hence, without loss of generality, we will assume that all the elements <em>C<\/em><sub>\u03b2<\/sub> are in <em>Z<\/em><sub>0<\/sub>. For all \u03b2&lt;\u03b3&lt;\u03b1, <em>C<\/em><sub>\u03b2<\/sub> is included in <em>C<\/em><sub>\u03b3<\/sub>, so supp(<em>C<\/em><sub>\u03b2<\/sub>) is included in supp(<em>C<\/em><sub>\u03b3<\/sub>).  This implies that the supports supp(<em>C<\/em><sub>\u03b2<\/sub>) form an ascending chain of finite sets, and that if supp(<em>C<\/em><sub>\u03b2<\/sub>) and supp(<em><em>C<\/em><sub>\u03b3<\/sub><\/em>) have the same number of elements, then supp(<em>C<\/em><sub>\u03b2<\/sub>)=supp(<em><em>C<\/em><sub>\u03b3<\/sub><\/em>).  For each natural number <em>n<\/em>, we look at all the elements <em>C<\/em><sub>\u03b2<\/sub> of the chain such that supp(<em>C<\/em><sub>\u03b2<\/sub>) contains exactly <em>n<\/em> elements.  All those elements have exactly the same support, say \u03b2<sub>1<\/sub>&lt;&#8230;&lt;\u03b2<sub><em>n<\/em><\/sub>, and they will be of the form \u2193(\u03b2<sub>1<\/sub>,\u03b3<sub>1<\/sub>) \u222a &#8230; \u222a \u2193(\u03b2<sub><em>n<\/em><\/sub>,\u03b3<sub><em>n<\/em><\/sub>), for varying values of \u03b3<sub>1<\/sub>&lt;\u03b2<sub>1<\/sub>+1, &#8230;, \u03b3<sub><em>n<\/em><\/sub>&lt;\u03b2<sub><em>n<\/em><\/sub>+1.  Since each \u03b2<sub><em>i<\/em><\/sub>&lt;\u03c9<sub>1<\/sub> is countable, this means we have only countably many possible values for \u03b3<sub>1<\/sub>, &#8230;, \u03b3<sub><em>n<\/em><\/sub>.  Hence the number of elements <em>C<\/em><sub>\u03b2<\/sub> in the chain such that supp(<em>C<\/em><sub>\u03b2<\/sub>) contains exactly <em>n<\/em> elements is countable.  Taking the union over all natural numbers <em>n<\/em>, we obtain that the chain (<em>C<\/em><sub>\u03b2<\/sub>)<sub>\u03b2&lt;\u03b1<\/sub> is countable.  \u2610<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Our final result will be given without proof, since the required arguments are technical.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Fact 3.<\/strong>  Let <em>Z<\/em> be a well-ordered poset.  The equality <em>l<\/em>(<em>Z<\/em>)=rk(<em>Z<\/em>) holds, and in fact there is a chain of maximal length <em>l<\/em>(<em>Z<\/em>)=rk(<em>Z<\/em>), in the following situations:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><em>Z<\/em> is an <em>almost wpo<\/em>, namely: given any sequence <em>z<\/em><sub>0<\/sub>, <em>z<\/em><sub>1<\/sub>, &#8230;, <em>z<sub>n<\/sub><\/em>, &#8230; of points in <em>Z<\/em>, we can find two indices <em>m<\/em>&lt;<em>n<\/em> such that <em>z<sub>m<\/sub><\/em>\u2264<em>z<sub>n<\/sub><\/em> or <em>l<\/em>(\u2193<em>z<sub>m<\/sub><\/em>\u2013{<em>z<sub>m<\/sub><\/em>})\u2265<em>l<\/em>(\u2193<em>z<sub>n<\/sub><\/em>\u2013{<em>z<sub>n<\/sub><\/em>}); in particular if <em>Z<\/em> is a wpo; this is due to Milner and Sauer [6], and cited as Theorem 2.1 in [5];<\/li>\n\n\n\n<li>or <em>Z<\/em> is a (well-founded) countable modular lattice [5, Remark 3.4]; in general, this continues to hold if <em>Z<\/em> if <em>Z<\/em> is a well-founded modular lattice satisfies the so-called HCC condition [5, Theorem 3.1], a technical condition that is automatically satisfied in the countable case.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">For more information on this type of result, [5] is the paper to read.  Its topic is <em>order-perfect<\/em> lattices, namely precisely the lattices that contain a chain of maximal length rk(<em>Z<\/em>) (=<em>l<\/em>(<em>Z<\/em>)).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We are all set!  Let us proceed to the definition of statures.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Statures of wpos, and beyond<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">As I have said already, Blass and Gurevich define the <em>stature<\/em> ||<em>P<\/em>|| of a wpo <em>P<\/em> as the rank of the family <em>D<\/em>(<em>P<\/em>) of all proper downwards-closed subsets of <em>P<\/em>, ordered by inclusion.  A subset of <em>P<\/em> is <em>proper<\/em> if and only if it is different from <em>P<\/em>.  (Well, really, they define the stature as the rank of a poset of so-called bad sequences, but then they show that this definition I am using is equivalent to it.  Note added on Nov. 2, 2021: I once said that proper meant <em>non-empty<\/em> and different from <em>P<\/em>, but I erred.)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The following result is due to them [4, Theorem 10], and before them, to K\u0159\u00ed\u017e [5, Proposition 2.2, last two equalities].  K\u0159\u00ed\u017e gives no proof, and claims that it is clear, given the de Jongh and Parikh theorem, but I must be dumb, and cannot see any simple argument.  The only complete proof I know is Section 7 of [4].<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Theorem.<\/strong>  For every wpo <em>P<\/em>, the stature ||<em>P<\/em>||=rk(<em>D<\/em>(<em>P<\/em>)) of <em>P<\/em> is equal to the maximal order type <em>o<\/em>(<em>P<\/em>) of <em>P<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let <strong>H<\/strong><sub>0<\/sub>(<em>P<\/em>) be the set of all non-empty downwards-closed subsets of <em>P<\/em>.  (Yes, this is the Hoare powerdomain of <em>P<\/em>, with its Alexandroff topology.  Note added on Nov. 2, 2021: plus the empty set, which is usually left out of the Hoare powerdomain.)  <strong>H<\/strong><sub>0<\/sub>(<em>P<\/em>) is <em>D<\/em>(<em>P<\/em>), with just one extra top element, which happens to be <em>P<\/em> itself.  Since <strong>H<\/strong><sub>0<\/sub>(<em>P<\/em>) has a largest element, its rank is a successor ordinal, namely ||<em>P<\/em>||+1.  Hence the stature of <em>P<\/em> is also equal to rk(<strong>H<\/strong><sub>0<\/sub>(<em>P<\/em>))\u20131, where the &#8220;\u20131&#8221; operation is only meaningful for successor ordinals.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The nice thing is that this definition extends to Noetherian spaces: we only need to define the stature ||<em>X<\/em>|| of a Noetherian space <em>X<\/em> as rk(<strong>H<\/strong><sub>0<\/sub>(<em>X<\/em>))\u20131.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">This makes sense because a topological space <em>X<\/em> is Noetherian if and only if every ascending sequence <em>U<\/em><sub>0<\/sub> \u2286 <em>U<\/em><sub>1<\/sub> \u2286 &#8230; \u2286 <em>U<\/em><sub><em>n<\/em><\/sub> \u2286 &#8230; of open subsets of <em>X<\/em> is stationary.  By taking complements, that is equivalent to requiring that every descending sequence <em>C<\/em><sub>0<\/sub> \u2287 <em>C<\/em><sub>1<\/sub> \u2287 &#8230; \u2287 <em>C<\/em><sub><em>n<\/em><\/sub> \u2287 &#8230; of closed subsets is stationary; or to say that <strong>H<\/strong><sub>0<\/sub>(<em>X<\/em>) is well-founded with respect to the inclusion ordering.  Moreover, <strong>H<\/strong><sub>0<\/sub>(<em>X<\/em>) has a largest element, so rk(<strong><strong>H<\/strong><\/strong><sub>0<\/sub>(<em>X<\/em>))\u20131 makes sense.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The nice thing with that definition is that it makes sense on all Noetherian spaces <em>X<\/em> (even those that are not T<sub>0<\/sub>).  Of course! you will say.  The point is that the other equivalent definitions of stature on wqos do <em>not<\/em> make sense on Noetherian spaces <em>X<\/em>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The maximal order type of <em>X<\/em>, say with its specialization ordering \u2264, does not exist&#8230; unless \u2264 is a wpo.  Indeed, in order to make sense, we must require that all linearizations of \u2264 are well-founded, and Wolk&#8217;s theorem tells us that this only happens when \u2264 is wpo.  This excludes any infinite space with its cofinite topology, for example.  Such spaces are Noetherian, but their specialization ordering is equality, which is not wpo, because the space is infinite.<\/li>\n\n\n\n<li>One may think of replacing linearizations by some equivalent notion in topology.  I have already argued <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2702\">here<\/a> that a reasonable analogue would be that of a <em>minimal T<sub>0<\/sub> topology<\/em>.  Unfortunately, there is no analogue of the de Jongh-Parikh theorem in the setting of T<sub>0<\/sub> Noetherian spaces (the topological analogue of wpos).  That would say that every T<sub>0<\/sub> Noetherian space has a minimal T<sub>0<\/sub> topology coarser than the original topology.  But, as Larson showed, this is not true, see Counterexample F in the post on <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2702\">chains and nested spaces<\/a>.  (By the way, that counterexample is uncountable, and also has un uncoutable topology.  I conjecture that every T<sub>0<\/sub> Noetherian space <em>with a countable topology<\/em> [equivalently, second-countable] has a minimal T<sub>0<\/sub> topology coarser than the original topology.)<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">The statures of some standard constructions<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">For every Noetherian space <em>X<\/em>, the space <em>X<\/em>* of finite words over <em>X<\/em> with the so-called word topology is Noetherian (Theorem 9.7.33 in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>).  What is its stature?  Can it be expressed as a function of the stature of <em>X<\/em> only?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">When <em>X<\/em> is a wpo in its Alexandroff topology, <em>X<\/em>* is also a wpo in its Alexandroff topology, and the question was settled by Schmidt [8]: ||<em>X<\/em>*|| is equal to \u03c9 to the power \u03c9<sup>\u03b1&#8217;<\/sup>, where \u03b1\u225d||<em>X<\/em>||, and the notation \u03b1&#8217; denotes \u03b1\u20131 if \u03b1 is finite and non-zero, \u03b1+1 if \u03b1 is of the form \u03b5<sub>\u03b2<\/sub>+<em>n<\/em> (with <em>n<\/em> a natural number; the numbers \u03b5<sub>\u03b2<\/sub> are the fixed points of the map <em>x<\/em> \u2192 \u03c9<sup><em>x<\/em><\/sup>), and \u03b1 otherwise.  Schmidt worked with maximal order types, not statures, but as we have seen, this is equivalent.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">I started this post by mentioning that Bastien Laboureix made quite some progress on the question.  He showed that the same holds for all second-countable Noetherian spaces: ||<em>X<\/em>*|| is equal to \u03c9 to the power \u03c9<sup>\u03b1&#8217;<\/sup>, where \u03b1\u225d||<em>X<\/em>||, for every second-countable Noetherian space <em>X<\/em>.  Oh, of course, there is this nasty restriction of second countability (equivalently, that the topology contains only countably many open sets\u2014the equivalence only holds for Noetherian spaces).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In practice, that is not that much of a problem.  Even the powerset <strong>P<\/strong>(<em>X<\/em>) of <em>X<\/em>, with the lower Vietoris topology, is second-countable (and Noetherian) provided that <em>X<\/em> is second-countable and Noetherian.  The reason is that the sobrification <strong>S<\/strong>(<strong>P<\/strong>(<em>X<\/em>)) of <strong>P<\/strong>(<em>X<\/em>) is isomorphic to the finite powerset <strong>P<\/strong><sub>fin<\/sub>(<strong>S<\/strong>(<em>X<\/em>)), that <strong>S<\/strong>(<em>X<\/em>) is countable (since its elements are certain closed subsets of <em>X<\/em>, and there are only countably many), and that, since <strong>P<\/strong>(<em>X<\/em>) is Noetherian (assuming that <em>X<\/em> is), its closed subsets are the downward closures of <em>finite<\/em> subsets of <strong>P<\/strong><sub>fin<\/sub>(<strong>S<\/strong>(<em>X<\/em>)).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bastien&#8217;s proof is completely different from Schmidt&#8217;s.  For one, Schmidt reasons on maximal order types, and I have argued that this has no direct analogue in the topological world.  Hence Bastien reasons directly on <strong><strong>H<\/strong><\/strong><sub>0<\/sub>(<em>X<\/em>*).  Fortunately, I had worked out explicit descriptions of the elements of <strong><strong>H<\/strong><\/strong><sub>0<\/sub>(<em>X<\/em>*), in collaboration with Alain Finkel [9, Section 7].  But a lot more work remained!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bastien and I should write up a polished version of his work later this year, and I am pretty sure we can get rid of this second-countability restriction, but we will see.  Bastien also managed to compute the ordinal rank of <strong>S<\/strong>(<em>X<\/em>*) as a function of that of <strong>S<\/strong>(<em>X<\/em>), the ordinal rank of <strong>S<\/strong>(<em>X<\/em><sup>\u235f<\/sup>) as a function of <strong>S<\/strong>(<em>X<\/em>) (where <em>X<\/em><sup>\u235f<\/sup> is the space of finite multisets of elements of <em>X<\/em>), and has partial results on the stature of <em>X<\/em><sup>\u235f<\/sup> as a function of that of <em>X<\/em>.  As far as the former is concerned, the wpo subcase was dealt with by Weiermann [10, Theorem 2].<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Schmidt also addressed the question of the stature of <strong>T<\/strong>(<em>X<\/em>), the set of finite trees on function symbols taken from <em>X<\/em>, again when <em>X<\/em> is a wpo.  The result is a complicated formula in terms of Schwichtenberg&#8217;s <em>Klammersymbol<\/em> notation for ordinals.  Weiermann recasts the results in terms of a more readable ordinal notation [10, Examples 1].  One would like to explore the question for Noetherian spaces, and that would most certainly be based on the explicit description of the elements of <strong><strong>H<\/strong><\/strong><sub>0<\/sub>(<strong>T<\/strong>(<em>X<\/em>)) given in [9, Section 11].  I expect this endeavor to be a nightmare.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Funnily, the case of statures of finite coproducts is trivial, but the question of statures of finite products looks a lot more complicated.  This is also one question we haven&#8217;t settled with Bastien yet.  We expect the answers to generalize the well-known formulae in the case of wpos (Hessenberg sum for coproducts, Hessenberg product for products).<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Edward Szpilrajn. &nbsp;<a href=\"https:\/\/eudml.org\/doc\/212499\">Sur l\u2019extension de l\u2019ordre partiel<\/a>. &nbsp;Fundamenta Mathematicae 16(1):386\u2013389, 1930.<\/li>\n\n\n\n<li>Elliott S. Wolk.  <a href=\"https:\/\/eudml.org\/doc\/213955\">Partially well ordered sets and partial ordinals<\/a>.  <a href=\"https:\/\/www.impan.pl\/en\/publishing-house\/journals-and-series\/fundamenta-mathematicae\">Fundamenta Mathematicae<\/a>, 60(2):175\u2013186, 1967.<\/li>\n\n\n\n<li>Dick Herman Jacobus de Jongh and Rohit Parikh. <a href=\"https:\/\/doi.org\/10.1016\/1385-7258(77)90067-1\">Well-partial orderings and hierarchies<\/a>. Indagationes Mathematicae 80(3):195\u2013207, 1977.<\/li>\n\n\n\n<li>Andreas Blass and Yuri Gurevich.&nbsp;<a href=\"https:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.219.4886&amp;rep=rep1&amp;type=pdf\">Program termination and well partial orderings<\/a>. ACM Transactions on Computational Logic 9(3) Art.18, 2008.<\/li>\n\n\n\n<li>Igor&nbsp;K\u0159\u00ed\u017e.  <a href=\"https:\/\/doi.org\/10.1007\/978-3-642-60406-5_35\">On order-perfect lattices<\/a>.  In: Ronald L. Graham, Jaroslav Ne\u0161et\u0159il (eds.) <a href=\"https:\/\/link.springer.com\/book\/10.1007\/978-3-642-60406-5\">The Mathematics of Paul Erd\u00f6s II<\/a>. Algorithms and Combinatorics, vol 14. Springer, Berlin, Heidelberg, 1997. <a href=\"https:\/\/doi.org\/10.1007\/978-3-642-60406-5_35\">https:\/\/doi.org\/10.1007\/978-3-642-60406-5_35<\/a><\/li>\n\n\n\n<li>Eric C. Milner and Norbert Sauer.  On chains and antichains in well-founded partially ordered sets.  J. London Math. Soc. 24(2):15\u201333, 1981.<\/li>\n\n\n\n<li>Diana Schmidt.  The relation between the height of a well-founded partial ordering and the order types of its chains and antichains.  Journal of Combinatorial theory, series B, 31:183\u2013189 , 1981.<\/li>\n\n\n\n<li>Diana Schmidt.  Well-partial orderings and their maximal order types.  Habilitationsschrift, Universit\u00e4t Heidelberg, 1979.<\/li>\n\n\n\n<li>Alain Finkel and Jean Goubault-Larrecq. <a href=\"https:\/\/www.cambridge.org\/core\/journals\/mathematical-structures-in-computer-science\/article\/abs\/forward-analysis-for-wsts-part-i-completions\/E7183B3BE4D6B55364B06265E692638A\">Forward analysis for WSTS, part I: Completions<\/a>.&nbsp;<em><a href=\"https:\/\/www.cambridge.org\/core\/journals\/mathematical-structures-in-computer-science\">Mathematical Structures in Computer Science<\/a>,<\/em>&nbsp;30(7):752\u2013832, 2020.  <a href=\"doi:10.1017\/S0960129520000195\">doi:10.1017\/S0960129520000195<\/a><\/li>\n\n\n\n<li>Andreas Weiermann.  A <a href=\"https:\/\/www.researchgate.net\/publication\/221653011_A_Computation_of_the_Maximal_Order_Type_of_the_Term_Ordering_on_Finite_Multisets\">computation of the maximal order type of the term ordering on finite multisets<\/a>.  Mathematical Theory and Computational Practice, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, July 19-24, 2009. Proceedings, Springer Verlag LNCS 5635, pages 488\u2013498.  <a href=\"https:\/\/dx.doi.org\/10.1007\/978-3-642-03073-4_50\">doi:10.1007\/978-3-642-03073-4_50<\/a><\/li>\n<\/ol>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"alignright is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2016\/08\/jgl-2011.png\" alt=\"jgl-2011\" class=\"wp-image-993\" width=\"60\" height=\"83\"\/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">\u2014 <a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~goubault\/?l=en\">Jean Goubault-Larrecq<\/a> (October 23rd, 2021)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Quite some time ago, I posted a list of open problems under the heading of &#8220;ordinal heights of Noetherian spaces&#8220;. I am happy to say that a masters student of mine, Bastien Laboureix, made quite some forays in the field. &hellip; <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=4209\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-4209","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/4209","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4209"}],"version-history":[{"count":138,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/4209\/revisions"}],"predecessor-version":[{"id":5883,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/4209\/revisions\/5883"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}