Ordinal heights of Noetherian spaces

Update.  These problems (and a few others) were solved, by Bastien Laboureix and me: see this arXiv paper.  Bastien is a gifted young man, whom I have had the pleasure to have had as a student in various courses at ENS Paris-Saclay, and who spent his M2 (masters, second year) research internship in the Spring of 2021 on those questions with me.  Bastien is also a coauthor of an award-winning paper on a new, intriguing model of computation, with Yoan Géran, Corto Mascle, and Valentin Richard; they discovered it after spilling a cup of coffee on a computer keyboard, and asking themselves what kinds of languages one could produce with a partially dysfunctional keyboard.  As of late 2021, Bastien is a PhD student with Isabelle Debled-Rennesson and Eric Domenjoud at LORIA, in Nancy, France, and works in a third area of research: discrete geometry.  He had already coauthored a paper with Eric Domenjoud and Laurent Vuillon, in that area, while an L3 (license, 3rd year) research intern in Nancy.

The only remaining problems is to determine the stature (and dimension) of finite trees, and a few other Noetherian spaces of interest.  See the followup to this post.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The ordinal height (or length, or rank) of a well-founded poset Z is the supremum of the ordinal lengths of its chains.  This can be defined explicitly by first defining the rank of an element z in Z by well-founded induction by rk z = sup {rk y+1 | y<z} (a suprema of a family of ordinals), and defining the rank of the whole space Z by rk Z = sup {rk z+1 | z in Z}.

A Noetherian space X is the same thing as a topological space whose lattice of closed subsets HX is well-founded.  Hence rk HX makes sense.

Also, the sobrification SX of X is well-founded, so rk SX makes sense.  Indeed SX is a sublattice of HX, consisting of irreducible closed subsets.

There is a list of standard constructions of Noetherian spaces in the book [1]: finite products, finite coproducts, words with the subword topology, terms with the tree topology, etc.  The questions I would like to solve is:

Given a construction X=C(X1,…,Xn) of a Noetherian space from Noetherian spaces X1,…,Xn, can you express rk X as a function of rk X1,…,rk Xn?

Can you express rk SX as a function of rk SX1,…,rk SXn?

Can you express rk HX as a function of rk HX1,…,rk HXn?

The purposes of those questions are the following:

  • For a wqo X (not a general Noetherian space), HX is the collection of downwards-closed subsets of X, and then rk HX is equal to the maximal order type of X.  This theorem is usually credited to [2], where maximal order type is called stature instead.  The notion of maximal order type has a rich theory, starting from [3,4],  and is key to understanding the complexity of algorithms in the theory of well-structured transition systems.  See the M1/M2 internship I am proposing with Sylvain Schmitz on this topic.
  • With Michael Blondin and Alain Finkel, I have recently shown that a certain form of the Karp-Miller procedure for general well-structured transition systems on state space X would terminate if and only if rk (SX) < ω2 [5]. Here X has to be a countable ω2-wqo.  What kind of space X satisfies that inequality?

Partial answers include (disclaimer: this list may contain mistakes):

  • rk N = ω, where N is the poset of natural numbers
  • rk SN = ω+1
  • rk HN = ω+1
  • rk (X + Y) = max (rk X, rk Y), where + is coproduct (every element of X is incomparable with every element of Y)
  • rk (S(X + Y)) = max (rk SX, rk SY), because S(X + Y)≅SX+SY
  • rk (H(X + Y)) = rk HX ⊕ rk HY, because H(X + Y)≅HX×HY (see below for ⊕)
  • rk (X × Y) = rk X ⊕ rk Y, where × denotes poset product (not lexicographic product), and ⊕ is the natural sum of ordinals
  • rk (S(X × Y)) = rk SX ⊕ rk SY, because S(X × Y)≅SX×SY
  • rk (Σ*) = ωk, where Σ is a discrete set of cardinality k, and Σ* is the set of words under word embedding (also known as scattered word embedding, subword ordering, divisibility ordering, Higman ordering: a word is below another another if it can be obtained by removing zero, one or more letters at any position); this is folklore
  • rk (S(Σ*)) = ωk + 1, where Σ is a discrete set of cardinality k (unpublished).

Some special cases include:

  • What is rk (H(X × Y))?  The answer is known for wqos: this is equal to rk HX ⊗ rk HY, where ⊗ is natural product of ordinals.  (This follows from the correspondence with maximal order types [2], and Theorem 7 of [4].)  That the same formula would hold for general Noetherian spaces is likely, but unknown.
  • What is rk (S(X*)) for X a general Noetherian space?
  • What is rk (H(X*)) for X a general Noetherian space?
  • What about spaces of trees?
  • Note that, for a wqo X (not a general Noetherian space), rk (HX) is equal to the maximal order type of X [2].  Can a similar characterization be obtained for arbitrary Noetherian spaces?
  1. Jean Goubault-Larrecq. Non-Hausdorff Topology and Domain Theory — Selected Topics in Point-Set Topology. New Mathematical Monographs  22. Cambridge University Press, 2013.
  2. Andreas Blass, Yuri Gurevich. Program Termination and Well Partial Orderings. ACM Transactions on Computational Logic 9(3) Art.18, 2008.
  3. D. H. J. de Jongh and R. Parikh. Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80=Indag. Math., 39(3):195–207, 1977.
  4. D. Schmidt. Well-partial orderings and their maximal order types. Habilitation, University of Heidelberg, Heidelberg, 1979.
  5. M. Blondin, A. Finkel and J. Goubault-Larrecq.  Forward Analysis for WSTS, Part III: Karp-Miller Trees.  In FSTTCS’17, Leibniz International Proceedings in Informatics. Leibniz-Zentrum für Informatik, 2017.

— Jean Goubault-Larrecq (February 23rd, 2017)jgl-2011