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 p0 > p1 > … > pn > …) 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 U0U1 ⊆ … ⊆ Un ⊆ … of upwards-closed subsets of P (=of open subsets in its Alexandroff topology) is stationary: after some rank n0, all the sets Un must be equal. Equivalently, by taking complements, every descending sequence C0C1 ⊇ … ⊇ Cn ⊇ … 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 p0, p1, …, pn, … of points is good: there must be two points pm and pn, with m<n and pmpn. 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 pn that is above some point pm that you have played earlier.
  • A wqo is a preordered set P in which every (countably infinite) sequence p0, p1, …, pn, … 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 pq, we have pq. 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 p0p1 ⊐ … ⊐ pn ⊐ … with respect to ⊑. Since ≤ is wpo, we can find two indices m<n such that pmpn, and therefore pmpn, which is impossible since pmpn.
  • 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 p0, p1, …, pn, … that is bad (i.e., not good): for no pair of indices m<n does pmpn hold. We define a new relation ≤’ on P by p≤’q if and only if pq (case 1) or there are two indices m<n such that ppn and pmq (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 ppn and pmq, and qpj and pir. In particular, pmpj, and that cannot happen if m<j, so mj. In that case, we have i<n (since i<jm<n), and also ppn and pir, so that pr.
    • ≤’ 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 ppn and pir, where now r=p; this implies pipn, 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 pqr=p, so p=q, since ≤ is a partial ordering.
    • The sequence p0, p1, …, pn, … is an infinite sequence that is strictly decreasing with respect to ≤’: it suffices to show that for every natural number n, pn≥’pn+1 (a typical case 2 situation) and pn≰’pn+1. We claim that the latter cannot happen, and for that, we assume that pn≤’pn+1, aiming (again) for a contradiction. Since we started with a bad sequence, pn≤’pn+1 cannot have been obtained from a case 1 situation (since pnpn+1); therefore there are two indices i<j such that pnpj and pipn+1. Again since the original sequence is bad, and pnpj, we cannot have n<j, so nj; similarly, in+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 p0 >’ p1 >’ … >’ pn >’ …, we also have p0p1 ⊐ … ⊐ pn ⊐ … 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, p0p1 ⊏ … ⊏ pωpω+1 ⊏ … ⊏ pω.2pω.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 p0p1 ⊏ … ⊏ pn–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 N2, with the lexicographic ordering, is ω2 (the first ordinal strictly larger than every ordinal ω.i+j with i,jN; the isomorphism maps the pair (i,j) to ω.i+j); the order type of N3, with the lexicographic ordering, is ω3; … 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,nN; 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 mn 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, nN. 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 rkZ(z) (relative to Z) by well-founded induction (namely, knowing that we already know the rank of all strictly lower elements) by: rkZ(z) is the smallest ordinal strictly larger than rkZ(z‘), for all elements z‘<z. In other words:

rkZ(z) = supz‘<z (rkZ(z‘)+1).

Oh, please, do not write this as (supz‘<z rkZ(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 = supz∈Z (rkZ(z)+1).

Proof sketch. The map rkZ is a strictly monotonic map from Z to α≝supz∈Z (rkZ(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 rkZ(z) ≤ φ(z). Therefore rkZ(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, rkZ(zβ)<rkZ(zγ), and therefore, by induction on β<α, we obtain that β≤rkZ(zβ) for every β<α. Adding one to both sides and taking suprema, this yields α≤supβ<α (rkZ(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 ω1; equivalently, this is the poset of all countable ordinals. We write ω1cof for ω1 with its cofinite topology, and ω for ω1 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 ω, we note that the ordering on ω1 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 × ω 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 H01cof × ω) of all closed subsets of ω1cof × ω is well-founded under inclusion.

Given any closed subset C of ω1cof × ω, let me write supp(C) for the set of points β<ω1 such that C contains a pair (β,γ), for some γ<ω1. (Equivalently, the projection of C onto the x-axis.) The set supp(C) is the support of C. Let me consider the subposet Z0 of H01cof × ω) 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 Z0 by adding a new element ⊤ above all others. Since H01cof × ω) is well-founded, so is Z0, and therefore also Z. One can check that the elements C of Z0 are exactly the finite unions of downward closures ↓(β11) ∪ … ∪ ↓(βnn), where n≥0, β1<…<βn and γii+1 for every i, 1≤in. (Just list the elements of supp(C) as β1<…<β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 Z0 is a distributive lattice, and therefore so is Z. Z0 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 Z0 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+1, but l(Z)≤ω1.

  • For all β<ω1 and γ<β+1, let us consider the downward closure ↓(β,γ) of (β,γ) in ω1cof × ω. (Equivalently, the set of pairs (β,γ”) with γ”≤γ, since the specialization ordering of ω1cof × ω 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 rkZ(↓(β,γ))<rkZ(↓(β,γ’)). By induction on β<ω1, it follows that rkZ(↓(β,γ))≥γ. In particular, rkZ(↓(γ,γ))≥γ for every γ<ω1. By adding one to each side of the inequality and taking suprema over γ<ω1, rkZ(⊤)≥ω1. Therefore rk Z≥ω1+1. (As an exercise, you may want to show that rk Z1+1.)
  • In order to show that l(Z)≤ω1, it suffices to show that every chain (Cβ)β<α in Z is countable. Any such chain is a chain in Z0, plus possibly one element (⊤). Hence, without loss of generality, we will assume that all the elements Cβ are in Z0. 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 β1<…<βn, and they will be of the form ↓(β11) ∪ … ∪ ↓(βnn), for varying values of γ11+1, …, γnn+1. Since each βi1 is countable, this means we have only countably many possible values for γ1, …, γ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 z0, z1, …, zn, … of points in Z, we can find two indices m<n such that zmzn or l(↓zm–{zm})≥l(↓zn–{zn}); 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 H0(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.) H0(P) is D(P), with just one extra top element, which happens to be P itself. Since H0(P) has a largest element, its rank is a successor ordinal, namely ||P||+1. Hence the stature of P is also equal to rk(H0(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(H0(X))–1.

This makes sense because a topological space X is Noetherian if and only if every ascending sequence U0U1 ⊆ … ⊆ Un ⊆ … of open subsets of X is stationary. By taking complements, that is equivalent to requiring that every descending sequence C0C1 ⊇ … ⊇ Cn ⊇ … of closed subsets is stationary; or to say that H0(X) is well-founded with respect to the inclusion ordering. Moreover, H0(X) has a largest element, so rk(H0(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 T0). 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 T0 topology. Unfortunately, there is no analogue of the de Jongh-Parikh theorem in the setting of T0 Noetherian spaces (the topological analogue of wpos). That would say that every T0 Noetherian space has a minimal T0 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 T0 Noetherian space with a countable topology [equivalently, second-countable] has a minimal T0 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 Pfin(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 Pfin(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 H0(X*). Fortunately, I had worked out explicit descriptions of the elements of H0(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 H0(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. rEdward 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: CompletionsMathematical 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
jgl-2011

Jean Goubault-Larrecq