Statures of Noetherian spaces I: maximal order types of wpos

Quite some time ago, I posted a list of open problems under the heading of “ordinal heights of Noetherian spaces“. 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.

By the way, I will change some of the notions of the aforementioned page of open problems—because they are not really suitable. The main theme of Bastien’s work is about a generalization of the theory of maximal order types of well-quasi-orders to the setting of Noetherian spaces.

Well-quasi-orders

A well-quasi-order is a preordered set (P,≤), or simply P, that is well-founded (there is no strictly descending sequence p₀ > p₁ > … > p_n > …) and has no infinite antichain (an antichain is a set of pairwise incomparable elements).

There is an amazing collection of equivalent characterizations of well-quasi-orders (for short, wqos). Some of them are given in the book, see Proposition 9.7.17:

• A wqo is a preordered set P that is Noetherian in its Alexandroff topology. This is probably the weirdest possible characterization of wqos. Explicitly, that means that every ascending sequence U₀ ⊆ U₁ ⊆ … ⊆ U_n ⊆ … of upwards-closed subsets of P (=of open subsets in its Alexandroff topology) is stationary: after some rank n₀, all the sets U_n must be equal. Equivalently, by taking complements, every descending sequence C₀ ⊇ C₁ ⊇ … ⊇ C_n ⊇ … of downwards-closed subsets (=closed sets in the Alexandroff topology) is stationary.
• A wqo is a preordered set P in which every (countably infinite) sequence p₀, p₁, …, p_n, … of points is good: there must be two points p_m and p_n, with m<n and p_m≤p_n. 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 p_n that is above some point p_m that you have played earlier.
• A wqo is a preordered set P in which every (countably infinite) sequence p₀, p₁, …, p_n, … of points is perfect: there must be an (infinite) subsequence that is monotonic.
• A wqo is a preordered set P in which every upwards-closed subset is finitary, namely of the form ↑A with A finite.

I have been teaching a masters 2 course on the topic for a few years. If you are curious, maybe the easiest introduction is to browse through the slides (part 1, part 2, part 3, and part 4).

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’t; or what I call “magic algorithms”—efficient algorithms that provably exist, but which nobody can implement, since nobody knows what they are.

I am only teaching the mathematical basis of wqo theory, and Philippe Schnoebelen 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—a question that can be solved with a very simple, 3-line algorithm—is 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 maximal order types of wqos… and here we come to the topic of the current post.

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

Wolk’s theorem

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 well partial orders, namely to wqos whose preordering is an ordering (i.e., is antisymmetric).

Every well-partial-order (wpo, for short) is well-founded, and Szpilrajn’s theorem [1] states that every well-founded partial ordering ≤ on a set P has at least one well-founded linearization ⊑; a linearization is a total extension of ≤, namely a total ordering ⊑ such that for all p, q in P such that p≤q, we have p⊑q. I have already mentioned this theorem in the post on chains and nested spaces.

In 1967, Wolk showed the following.

Theorem (Wolk [2]). A partial ordering ≤ on a set P is a wpo if and only if all its linearizations are well-founded.

Every partial ordering ≤ has at least one linearization, by Zorn’s Lemma: Szpilrajn’s theorem states that if ≤ is well-founded, at least one of them is well-founded, while Wolk’s theorem states that ≤ is wpo if and only if all those linearizations are well-founded.

Proof.

• In one direction, we assume that ≤ is wpo on P, and that ⊑ is a linearization of ≤. We consider an infinite (strictly) descending sequence p₀ ⊐ p₁ ⊐ … ⊐ p_n ⊐ … with respect to ⊑. Since ≤ is wpo, we can find two indices m<n such that p_m≤p_n, and therefore p_m⊑p_n, which is impossible since p_m⊐p_n.
• In the other direction, we show that if ≤ is not wpo on P, then it has a linearization that is not well-founded. Since ≤ is assumed not to be wpo, there is a sequence p₀, p₁, …, p_n, … that is bad (i.e., not good): for no pair of indices m<n does p_m≤p_n hold. We define a new relation ≤’ on P by p≤’q if and only if p≤q (case 1) or there are two indices m<n such that p≤p_n and p_m≤q (case 2). The following picture may help one understand case 2:

• We verify the following:
  • ≤’ is transitive. We assume that p≤’q≤’r and we wish to show that p≤’r. There are four cases to consider, depending on whether p≤’q was obtained in case 1 or in case 2, and similarly for q≤’r. Only of those cases is interesting, and this is the case 2/case 2 situation: then there are indices m<n and i<j such that p≤p_n and p_m≤q, and q≤p_j and p_i≤r. In particular, p_m≤p_j, and that cannot happen if m<j, so m≥j. In that case, we have i<n (since i<j≤m<n), and also p≤p_n and p_i≤r, so that p≤r.
  • ≤’ is antisymmetric: we again have four cases to consider. We start with p≤’q≤’r as above, where now r=p. In the case 2/case 2 situation (profiting from the fact that the situation is still fresh in your memory!), we have p≤p_n and p_i≤r, where now r=p; this implies p_i≤p_n, which is impossible since i<n. 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 p≤q≤r=p, so p=q, since ≤ is a partial ordering.
  • The sequence p₀, p₁, …, p_n, … is an infinite sequence that is strictly decreasing with respect to ≤’: it suffices to show that for every natural number n, p_n≥’p_n+1 (a typical case 2 situation) and p_n≰’p_n+1. We claim that the latter cannot happen, and for that, we assume that p_n≤’p_n+1, aiming (again) for a contradiction. Since we started with a bad sequence, p_n≤’p_n+1 cannot have been obtained from a case 1 situation (since p_n≰p_n+1); therefore there are two indices i<j such that p_n≤p_j and p_i≤p_n+1. Again since the original sequence is bad, and p_n≤p_j, we cannot have n<j, so n≥j; similarly, i≥n+1. It follows that i>j, which is absurd since i<j.
  • We now consider any linear extension ⊑ of ≤’. I have already said that every partial ordering has at least one linear extension. Since p₀ >’ p₁ >’ … >’ p_n >’ …, we also have p₀ ⊐ p₁ ⊐ … ⊐ p_n ⊐ … We have therefore reached our goal of proving that ≤ has a linear extension (⊑) that is not well-founded.

Maximal order types of wpos

So let (P, ≤) be a wpo. By Wolk’s theorem, all the linear extensions ⊑ of ≤ are well-founded. Every total well-founded ordering ⊑ is isomorphic to a unique ordinal α, which is fancy way to say that you can enumerate the elements of P as (p_β)_β<α in such a way that p_β⊑p_γ if and only if β≤γ, for all β,γ<α; in other words, p₀ ⊏ p₁ ⊏ … ⊏ p_ω ⊏ p_ω+1 ⊏ … ⊏ p_ω.2 ⊏ p_ω.2+1 ⊏ … (and so on and so forth).

Such ordinals are called the order types of (linear extensions of) ≤.

What kinds of ordinals α can you obtain this way? In other words, what do the order types of (linear extensions of) ≤ look like?

When P is finite, say of cardinality n, any enumeration of P will be of the form p₀ ⊏ p₁ ⊏ … ⊏ p_n–1, and the only possible order type you will ever get is n (= the ordinal {0, 1, …, n–1}).

When ≤ is a total well-founded ordering (in particular, a wpo, as one can check—even when P is infinite), then (P, ≤) is itself isomorphic to a unique ordinal α, which is its unique order type. For example, the order type of N with its usual ordering is ω, the first infinite ordinal; the order type of N², with the lexicographic ordering, is ω² (the first ordinal strictly larger than every ordinal ω.i+j with i,j ∈ N; the isomorphism maps the pair (i,j) to ω.i+j); the order type of N³, with the lexicographic ordering, is ω³; … and so on.

The situation gets more interesting with infinite, partially ordered wpos. Let me illustrate this with the example of N+N, the coproduct of two copies of N, each one with its usual ordering. The elements of N+N are pairs (0,m) and (1,n), where m,n ∈ N; 0 means “coming from the left copy”, 1 means “coming from the right copy”. We order them by: (i,m) ≤ (i,n) if and only if m≤n in N (whether i is 0 or 1), and (0,m) and (1,n) are always incomparable. The left part of the following figure should help you picture this.

The ordering we have just defined is a wpo. One can see this directly: any infinite sequence in N+N 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:

• We can enumerate the elements of N+N by taking one from the left side, and one from the right side in alternation. Namely, we enumerate them as (0,0) ⊏ (1,0) ⊏ (0,1) ⊏ (1,1) ⊏ (0,2) ⊏ (1,2) ⊏ … ⊏ (0,m) ⊏ (1,m) ⊏ (0,m+1) ⊏ (1,m+1) ⊏ … This has order type ω. I have shown this in blue above (the middle part).
• 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) ⊏ (0,1) ⊏ … ⊏ (0,m) ⊏ … (infinitely many elements here) ⊏ (1,0) ⊏ (1,1) ⊏ … ⊏ (1,n) ⊏ … (infinitely many elements again). The order type of this enumeration is ω.2, the first ordinal larger than all the ordinals ω+n, n ∈ N. Explicitly, the elements of the form (0,m) receive number m in that enumeration, while the elements of the form (1,n) receive number ω+n. This is shown on the right part of the above figure, in red.

A remarkable result in the theory of well-partial-orders is the following theorem, due to de Jongh and Parikh:

Theorem [3, Theorem 2.13]. Given any wpo (P,≤), there is a linearization ≤ whose order type is the largest among all order types of linearizations of ≤.

The corresponding order type is called the maximal order type of ≤ on P, and is written as o(P). In the example of N+N, that maximal order type is o(N+N)=ω.2.

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.

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.

However, what Blass and Gurevich show is a more general result pertaining to the so-called stature 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říž [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’s theorem.

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.

Measuring the height of well-founded sets

There are at least two ways one can measure the height of a well-founded poset. We start with the easy one—which happens not to be the right one, but at least it is probably easier to understand.

A chain in a poset Z is a total well-founded subset. It is equivalent to say that this is a family (z_β)_β<α, indexed by the ordinals smaller than some ordinal α, such that for all β,γ<α, β<γ implies z_β<z_γ. The ordinal α is the length of the family. Let me call the chain length of Z the supremum of the lengths of all the chains included in Z, and let me write it as l(Z).

That may sound similar to the maximal order type of Z, but that is very different. Looking at N+N 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 N+N on the left, in green. Each one has length ω, and therefore l(N+N)=ω.

As you see, the green arrows are required to connect comparable elements; roughly, all the green arrows are drawn next to some 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 every black line is colored blue or red.

Let me proceed with the second measure of the height of a well-founded poset Z, which I will call its rank, and is sometimes called its height as well. That has two equivalent definitions. Let me start with the more abstract one: the rank rk Z of Z is the smallest ordinal α such that one can number each element z of Z with an ordinal φ(z)<α, in such a way that z<z’ implies φ(z)<φ(z‘).

In other words, rk Z is the smallest ordinal α such that there is a strictly monotonic map from Z to α. (For that, you have to know that an ordinal is equal to the set of all ordinals strictly less than itself.)

That smallest ordinal exists by the following argument. First, there is an ordinal α at all such that there is a strictly monotonic map from Z to α: we use Szpilrajn’s theorem to find a well-founded linearization of Z, and the order type of that linearization is such an ordinal. Second, there is a least such ordinal because the class of ordinals is well-founded.

Note again the different between rank, chain length, and maximal order type:

• The rank rk(Z) is the least ordinal α such that there is a strictly monotonic map φ : Z → α.
• The chain length l(Z) is the supremum of all the ordinals α such that there is a strictly monotonic map φ : α → Z. (Note that α and Z have switched sides.)
• The maximal order type o(P) (of a wpo P) is the largest ordinal α such that there is there is a bijective, strictly monotonic map φ : Z → α.

Here is the other definition or rank. That one is a lot more concrete, and more operational.

For each element z of Z, we define its rank rk_Z(z) (relative to Z) by well-founded induction (namely, knowing that we already know the rank of all strictly lower elements) by: rk_Z(z) is the smallest ordinal strictly larger than rk_Z(z‘), for all elements z‘<z. In other words:

rk_Z(z) = sup_z‘<z (rk_Z(z‘)+1).

Oh, please, do not write this as (sup_z‘<z rk_Z(z‘))+1. Although that would give the same value in most cases, those two values differ when z is minimal; the latter would be equal to 1, whereas the rank of a minimal element is really equal to 0.

Let us show that the two definitions are equivalent.

Lemma. For every well-founded poset Z, rk Z = sup_z∈Z (rk_Z(z)+1).

Proof sketch. The map rk_Z is a strictly monotonic map from Z to α≝sup_z∈Z (rk_Z(z)+1). Therefore rk Z≤α. In the reverse direction, let φ be any strictly monotonic map from Z to some ordinal α’. By well-founded induction on z in Z, it is easy to see that rk_Z(z) ≤ φ(z). Therefore rk_Z(z)+1 ≤ α’ for every z in Z, and by taking suprema, we obtain that α≤α’. ☐

This leads to a useful trick. Given a poset Z, let Z^⊤ be Z with a fresh element ⊤ added on top. The rank of Z is really the same thing as the rank of ⊤ in Z^⊤!

That lemma also gives us a practical way of computing rk Z. We label the minimal elements z with 0. Then we look at the elements z such that every element strictly below z has already been labeled, and we label them with the smallest ordinal strictly larger than all the labels of elements <z… and so on, transfinitely. The result is the following labeling, shown in green, on our example N+N.

Comparing chain length and rank

The latter picture looks suspiciously like the previous picture, where I had depicted the longest chains in N+N, and that is not completely coincidental. But beware, the chain length l(Z) of a well-founded poset Z is in general distinct from its ordinal rank rk(Z), as we will see below.

Here are a few results on the relation between chain length and ordinal rank.

Fact 1. For every well-founded poset Z, l(Z)≤rk(Z).

Proof. Let us consider any chain (z_β)_β<α, where for all β<γ<α, we have z_β<z_γ. By definition, rk_Z(z_β)<rk_Z(z_γ), and therefore, by induction on β<α, we obtain that β≤rk_Z(z_β) for every β<α. Adding one to both sides and taking suprema, this yields α≤sup_β<α (rk_Z(z_β)+1)≤rk Z. ☐

Fact 2. The inequality l(Z)≤rk(Z) is strict in general. We can even chose Z so as to be a distributive, complete lattice.

Proof. 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říž [5, end of Section 3], who says that a similar counterexample was found by N. Zaguia, and will be a distributive, complete lattice.

First proof. In order to find Z such that l(Z)<rk(Z), we show that there is a well-founded poset Z_α of rank at least α, for every ordinal α, and whose chains are all finite (so l(Z_α)≤ω, and the supremum in the definition of l(Z) is not even attained). Quite a gap between l(Z_α) and rk(Z_α)!

This is done by induction on α. If α=0, the empty set fits. For successor ordinals α+1, we add one element on top of Z_α in order to form Z_α+1 (=Z_α^⊤). For limit ordinals α, we define Z_α as the disjoint sum of all Z_β^⊤, β<α. We verify that the rank of Z_α is the supremum of the ranks of the top elements of each Z_β^⊤, β<α, plus 1, namely the supremum of the ranks of Z_β, β<α, plus 1. That is at least the supremum of the family of ordinals β+1 where β<α, and that supremum is larger than or equal to α.

Second proof. The aim of that second proof is to find Z in the form of a distributive, complete lattice (which the posets Z_α certainly are not!).

We consider the first uncountable ordinal ω₁; equivalently, this is the poset of all countable ordinals. We write ω_1cof for ω₁ with its cofinite topology, and ω_1σ for ω₁ 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 ω_1σ, we note that the ordering on ω₁ 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.

Then the product ω_1cof × ω_1σ is Noetherian, too, since finite products of Noetherian spaces are Noetherian (see Proposition 9.7.18 (vii) in the book). Now a space is Noetherian if and only if every ascending sequence of open sets is stationary (Proposition 9.7.6 in the book), and that is equivalent to: every descending sequence of closed sets is stationary, so the family H₀(ω_1cof × ω_1σ) of all closed subsets of ω_1cof × ω_1σ is well-founded under inclusion.

Given any closed subset C of ω_1cof × ω_1σ, let me write supp(C) for the set of points β<ω₁ such that C contains a pair (β,γ), for some γ<ω₁. (Equivalently, the projection of C onto the x-axis.) The set supp(C) is the support of C. Let me consider the subposet Z₀ of H₀(ω_1cof × ω_1σ) of those closed subsets C such that: (i) supp(C) is finite, and (ii) every element (β,γ) of C is such that γ<β+1.

Finally, we let Z be the poset obtained from Z₀ by adding a new element ⊤ above all others. Since H₀(ω_1cof × ω_1σ) is well-founded, so is Z₀, and therefore also Z. One can check that the elements C of Z₀ are exactly the finite unions of downward closures ↓(β₁,γ₁) ∪ … ∪ ↓(β_n,γ_n), where n≥0, β₁<…<β_n and γ_i<β_i+1 for every i, 1≤i≤n. (Just list the elements of supp(C) as β₁<…<β_n, then observe that for each i, β_i+1 is a dcpo; so there is a largest element γ_i in C whose first coordinate is β_i.) From this description, it is fairly easy to see that Z₀ is a distributive lattice, and therefore so is Z. Z₀ also has suprema of all the families of closed subsets whose supports are included in a common finite subset; all other families have ⊤ as supremum. Hence Z is a complete lattice. (Infima are equally easy to compute: the infimum of any family not containing any element of Z₀ is ⊤, the infimum of any other family is the intersection of its non-⊤ elements.)

In order to complete the proof, we will show that rk Z≥ω₁+1, but l(Z)≤ω₁.

• For all β<ω₁ and γ<β+1, let us consider the downward closure ↓(β,γ) of (β,γ) in ω_1cof × ω_1σ. (Equivalently, the set of pairs (β,γ”) with γ”≤γ, since the specialization ordering of ω_1cof × ω_1σ is the product = × ≤.) ↓(β,γ) is an element of Z, since it is the closure of {(β,γ)}, and its support is the finite set {β}. If γ<γ'<β+1, then ↓(β,γ) is strictly included in ↓(β,γ’), so rk_Z(↓(β,γ))<rk_Z(↓(β,γ’)). By induction on β<ω₁, it follows that rk_Z(↓(β,γ))≥γ. In particular, rk_Z(↓(γ,γ))≥γ for every γ<ω₁. By adding one to each side of the inequality and taking suprema over γ<ω₁, rk_Z(⊤)≥ω₁. Therefore rk Z≥ω₁+1. (As an exercise, you may want to show that rk Z=ω₁+1.)
• In order to show that l(Z)≤ω₁, it suffices to show that every chain (C_β)_β<α in Z is countable. Any such chain is a chain in Z₀, plus possibly one element (⊤). Hence, without loss of generality, we will assume that all the elements C_β are in Z₀. For all β<γ<α, C_β is included in C_γ, so supp(C_β) is included in supp(C_γ). This implies that the supports supp(C_β) form an ascending chain of finite sets, and that if supp(C_β) and supp(C_γ) have the same number of elements, then supp(C_β)=supp(C_γ). For each natural number n, we look at all the elements C_β of the chain such that supp(C_β) contains exactly n elements. All those elements have exactly the same support, say β₁<…<β_n, and they will be of the form ↓(β₁,γ₁) ∪ … ∪ ↓(β_n,γ_n), for varying values of γ₁<β₁+1, …, γ_n<β_n+1. Since each β_i<ω₁ is countable, this means we have only countably many possible values for γ₁, …, γ_n. Hence the number of elements C_β in the chain such that supp(C_β) contains exactly n elements is countable. Taking the union over all natural numbers n, we obtain that the chain (C_β)_β<α is countable. ☐

Our final result will be given without proof, since the required arguments are technical.

Fact 3. Let Z be a well-ordered poset. The equality l(Z)=rk(Z) holds, and in fact there is a chain of maximal length l(Z)=rk(Z), in the following situations:

1. Z is an almost wpo, namely: given any sequence z₀, z₁, …, z_n, … of points in Z, we can find two indices m<n such that z_m≤z_n or l(↓z_m–{z_m})≥l(↓z_n–{z_n}); in particular if Z is a wpo; this is due to Milner and Sauer [6], and cited as Theorem 2.1 in [5];
2. or Z is a (well-founded) countable modular lattice [5, Remark 3.4]; in general, this continues to hold if Z if Z 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.

For more information on this type of result, [5] is the paper to read. Its topic is order-perfect lattices, namely precisely the lattices that contain a chain of maximal length rk(Z) (=l(Z)).

We are all set! Let us proceed to the definition of statures.

Statures of wpos, and beyond

As I have said already, Blass and Gurevich define the stature ||P|| of a wpo P as the rank of the family D(P) of all proper downwards-closed subsets of P, ordered by inclusion. A subset of P is proper if and only if it is different from P. (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 non-empty and different from P, but I erred.)

The following result is due to them [4, Theorem 10], and before them, to Kříž [5, Proposition 2.2, last two equalities]. Kříž 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].

Theorem. For every wpo P, the stature ||P||=rk(D(P)) of P is equal to the maximal order type o(P) of P.

Let H₀(P) be the set of all non-empty downwards-closed subsets of P. (Yes, this is the Hoare powerdomain of P, with its Alexandroff topology. Note added on Nov. 2, 2021: plus the empty set, which is usually left out of the Hoare powerdomain.) H₀(P) is D(P), with just one extra top element, which happens to be P itself. Since H₀(P) has a largest element, its rank is a successor ordinal, namely ||P||+1. Hence the stature of P is also equal to rk(H₀(P))–1, where the “–1” operation is only meaningful for successor ordinals.

The nice thing is that this definition extends to Noetherian spaces: we only need to define the stature ||X|| of a Noetherian space X as rk(H₀(X))–1.

This makes sense because a topological space X is Noetherian if and only if every ascending sequence U₀ ⊆ U₁ ⊆ … ⊆ U_n ⊆ … of open subsets of X is stationary. By taking complements, that is equivalent to requiring that every descending sequence C₀ ⊇ C₁ ⊇ … ⊇ C_n ⊇ … of closed subsets is stationary; or to say that H₀(X) is well-founded with respect to the inclusion ordering. Moreover, H₀(X) has a largest element, so rk(H₀(X))–1 makes sense.

The nice thing with that definition is that it makes sense on all Noetherian spaces X (even those that are not T₀). Of course! you will say. The point is that the other equivalent definitions of stature on wqos do not make sense on Noetherian spaces X:

• The maximal order type of X, say with its specialization ordering ≤, does not exist… unless ≤ is a wpo. Indeed, in order to make sense, we must require that all linearizations of ≤ are well-founded, and Wolk’s theorem tells us that this only happens when ≤ 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.
• One may think of replacing linearizations by some equivalent notion in topology. I have already argued here that a reasonable analogue would be that of a minimal T₀ topology. Unfortunately, there is no analogue of the de Jongh-Parikh theorem in the setting of T₀ Noetherian spaces (the topological analogue of wpos). That would say that every T₀ Noetherian space has a minimal T₀ topology coarser than the original topology. But, as Larson showed, this is not true, see Counterexample F in the post on chains and nested spaces. (By the way, that counterexample is uncountable, and also has un uncoutable topology. I conjecture that every T₀ Noetherian space with a countable topology [equivalently, second-countable] has a minimal T₀ topology coarser than the original topology.)

The statures of some standard constructions

For every Noetherian space X, the space X* of finite words over X with the so-called word topology is Noetherian (Theorem 9.7.33 in the book). What is its stature? Can it be expressed as a function of the stature of X only?

When X is a wpo in its Alexandroff topology, X* is also a wpo in its Alexandroff topology, and the question was settled by Schmidt [8]: ||X*|| is equal to ω to the power ω^α’, where α≝||X||, and the notation α’ denotes α–1 if α is finite and non-zero, α+1 if α is of the form ε_β+n (with n a natural number; the numbers ε_β are the fixed points of the map x → ω^x), and α otherwise. Schmidt worked with maximal order types, not statures, but as we have seen, this is equivalent.

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: ||X*|| is equal to ω to the power ω^α’, where α≝||X||, for every second-countable Noetherian space X. Oh, of course, there is this nasty restriction of second countability (equivalently, that the topology contains only countably many open sets—the equivalence only holds for Noetherian spaces).

In practice, that is not that much of a problem. Even the powerset P(X) of X, with the lower Vietoris topology, is second-countable (and Noetherian) provided that X is second-countable and Noetherian. The reason is that the sobrification S(P(X)) of P(X) is isomorphic to the finite powerset P_fin(S(X)), that S(X) is countable (since its elements are certain closed subsets of X, and there are only countably many), and that, since P(X) is Noetherian (assuming that X is), its closed subsets are the downward closures of finite subsets of P_fin(S(X)).

Bastien’s proof is completely different from Schmidt’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 H₀(X*). Fortunately, I had worked out explicit descriptions of the elements of H₀(X*), in collaboration with Alain Finkel [9, Section 7]. But a lot more work remained!

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 S(X*) as a function of that of S(X), the ordinal rank of S(X^⍟) as a function of S(X) (where X^⍟ is the space of finite multisets of elements of X), and has partial results on the stature of X^⍟ as a function of that of X. As far as the former is concerned, the wpo subcase was dealt with by Weiermann [10, Theorem 2].

Schmidt also addressed the question of the stature of T(X), the set of finite trees on function symbols taken from X, again when X is a wpo. The result is a complicated formula in terms of Schwichtenberg’s Klammersymbol 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 H₀(T(X)) given in [9, Section 11]. I expect this endeavor to be a nightmare.

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

1. Edward Szpilrajn.  Sur l’extension de l’ordre partiel.  Fundamenta Mathematicae 16(1):386–389, 1930.
2. Elliott S. Wolk. Partially well ordered sets and partial ordinals. Fundamenta Mathematicae, 60(2):175–186, 1967.
3. Dick Herman Jacobus de Jongh and Rohit Parikh. Well-partial orderings and hierarchies. Indagationes Mathematicae 80(3):195–207, 1977.
4. Andreas Blass and Yuri Gurevich. Program termination and well partial orderings. ACM Transactions on Computational Logic 9(3) Art.18, 2008.
5. Igor Kříž. On order-perfect lattices. In: Ronald L. Graham, Jaroslav Nešetřil (eds.) The Mathematics of Paul Erdös II. Algorithms and Combinatorics, vol 14. Springer, Berlin, Heidelberg, 1997. https://doi.org/10.1007/978-3-642-60406-5_35
6. Eric C. Milner and Norbert Sauer. On chains and antichains in well-founded partially ordered sets. J. London Math. Soc. 24(2):15–33, 1981.
7. 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–189 , 1981.
8. Diana Schmidt. Well-partial orderings and their maximal order types. Habilitationsschrift, Universität Heidelberg, 1979.
9. Alain Finkel and Jean Goubault-Larrecq. Forward analysis for WSTS, part I: Completions. Mathematical Structures in Computer Science, 30(7):752–832, 2020. doi:10.1017/S0960129520000195
10. Andreas Weiermann. A computation of the maximal order type of the term ordering on finite multisets. 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–498. doi:10.1007/978-3-642-03073-4_50

— Jean Goubault-Larrecq (October 23rd, 2021)