{"id":1134,"date":"2017-02-23T18:52:33","date_gmt":"2017-02-23T17:52:33","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1134"},"modified":"2022-11-19T15:22:18","modified_gmt":"2022-11-19T14:22:18","slug":"ordinal-heights-of-noetherian-spaces","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1134","title":{"rendered":"Ordinal heights of Noetherian spaces"},"content":{"rendered":"<p><strong>Update.<\/strong>\u00a0 These problems (and a few others) were solved, by Bastien Laboureix and me: see this <a href=\"https:\/\/arxiv.org\/abs\/2112.06828\">arXiv paper<\/a>. \u00a0Bastien 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. \u00a0Bastien is also a coauthor of an <a href=\"https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/14489\/\">award-winning paper<\/a> on a new, intriguing model of computation, with Yoan G\u00e9ran, 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. \u00a0As 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. \u00a0He had already coauthored a <a href=\"https:\/\/dgci2019.sciencesconf.org\/252469\">paper<\/a> with Eric Domenjoud and Laurent Vuillon, in that area, while an L3 (license, 3rd year) research intern in Nancy.<\/p>\n<p>The only remaining problems is to determine the stature (and dimension) of finite trees, and a few other Noetherian spaces of interest. \u00a0See the <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=4549\">followup<\/a>\u00a0to this post<\/p>\n<p>~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~<\/p>\n<p>The ordinal height (or length, or rank) of a well-founded poset <em>Z<\/em> is the supremum of the ordinal lengths of its chains.\u00a0 This can be defined explicitly by first defining the rank of an element <em>z<\/em> in <em>Z<\/em> by well-founded induction by rk <em>z<\/em> = sup {rk <em>y<\/em>+1 | <em>y<\/em>&lt;<em>z<\/em>} (a suprema of a family of ordinals), and defining the rank of the whole space <em>Z<\/em> by rk <em>Z<\/em> = sup {rk <em>z<\/em>+1 | <em>z<\/em> in <em>Z<\/em>}.<\/p>\n<p>A Noetherian space <em>X<\/em> is the same thing as a topological space whose lattice of closed subsets\u00a0<strong>H<\/strong><em>X<\/em> is well-founded.\u00a0 Hence rk\u00a0<strong>H<\/strong><em>X<\/em> makes sense.<\/p>\n<p>Also, the sobrification <strong>S<\/strong><em>X<\/em> of <em>X<\/em> is well-founded, so rk <strong>S<\/strong><em>X<\/em> makes sense.\u00a0 Indeed <strong>S<\/strong><em>X<\/em> is a sublattice of <strong>H<\/strong><em>X<\/em>, consisting of irreducible closed subsets.<\/p>\n<p>There is a list of standard constructions of Noetherian spaces in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a> [1]: finite products, finite coproducts, words with the subword topology, terms with the tree topology, etc.\u00a0 The questions I would like to solve is:<\/p>\n<blockquote><p>Given a construction <em>X<\/em>=C(<em>X<sub>1<\/sub><\/em>,&#8230;,<em>X<sub>n<\/sub><\/em>) of a Noetherian space from Noetherian spaces <em>X<sub>1<\/sub><\/em>,&#8230;,<em>X<sub>n<\/sub><\/em>, can you express rk <em>X<\/em> as a function of rk<em> X<sub>1<\/sub>,&#8230;,rk X<sub>n<\/sub><\/em>?<\/p>\n<p>Can you express rk <strong>S<\/strong><em>X<\/em> as a function of rk<em> <strong>S<\/strong>X<sub>1<\/sub>,&#8230;,rk <strong>S<\/strong>X<sub>n<\/sub><\/em>?<\/p>\n<p>Can you express rk <strong>H<\/strong><em>X<\/em> as a function of rk<em> <strong>H<\/strong>X<sub>1<\/sub>,&#8230;,rk <strong>H<\/strong>X<sub>n<\/sub><\/em>?<\/p><\/blockquote>\n<p>The purposes of those questions are the following:<\/p>\n<ul>\n<li>For a wqo <em>X<\/em> (not a general Noetherian space), <strong>H<\/strong><em>X<\/em> is the collection of downwards-closed subsets of <em>X<\/em>, and then rk <strong>H<\/strong><em>X<\/em> is equal to the maximal order type of <em>X<\/em>.\u00a0 This theorem is usually credited to [2], where maximal order type is called <em>stature<\/em> instead.\u00a0 The notion of maximal order type has a rich theory, starting from [3,4],\u00a0 and is key to understanding the complexity of algorithms in the theory of well-structured transition systems.\u00a0 See the <a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/Stages\/Fichier\/m2-16-jgss.pdf\">M1\/M2 internship<\/a> I am proposing with Sylvain Schmitz on this topic.<\/li>\n<li>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 <em>X<\/em> would terminate if and only if rk (<strong>S<\/strong><em>X<\/em>) &lt; \u03c9<sup>2<\/sup> [5]. Here <em>X<\/em> has to be a countable \u03c9<sup>2<\/sup>-wqo.\u00a0 What kind of space <em>X<\/em> satisfies that inequality?<\/li>\n<\/ul>\n<p>Partial answers include (disclaimer: this list may contain mistakes):<\/p>\n<ul>\n<li>rk <strong>N<\/strong> = \u03c9, where <strong>N<\/strong> is the poset of natural numbers<\/li>\n<li>rk <strong>SN<\/strong> = \u03c9+1<\/li>\n<li>rk <strong>HN<\/strong> = \u03c9+1<\/li>\n<li>rk (<em>X<\/em> + <em>Y<\/em>) = max (rk <em>X<\/em>, rk <em>Y<\/em>), where + is coproduct (every element of <em>X<\/em> is incomparable with every element of <em>Y<\/em>)<\/li>\n<li>rk (<strong>S<\/strong>(<em>X<\/em> +\u00a0<em>Y<\/em>)) = max (rk <strong>S<\/strong><em>X<\/em>, rk <strong>S<\/strong><em>Y<\/em>), because <strong>S<\/strong>(<em>X<\/em> +\u00a0<em>Y<\/em>)\u2245<strong>S<\/strong><em>X<\/em>+<strong>S<\/strong><em>Y<\/em><\/li>\n<li>rk (<strong>H<\/strong>(<em>X<\/em> +\u00a0<em>Y<\/em>)) =\u00a0rk <strong>H<\/strong><em>X\u00a0<\/em>\u2295 rk <strong>H<\/strong><em>Y<\/em>, because <strong>H<\/strong>(<em>X<\/em> + <em>Y<\/em>)\u2245<strong>H<\/strong><em>X<\/em>\u00d7<strong>H<\/strong><em>Y<\/em> (see below for \u2295)<\/li>\n<li>rk (<em>X<\/em> \u00d7 <em>Y<\/em>) = rk <em>X\u00a0<\/em>\u2295 rk <em>Y<\/em>, where \u00d7 denotes poset product (not lexicographic product), and \u2295 is the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ordinal_arithmetic\">natural sum<\/a> of ordinals<\/li>\n<li>rk (<strong>S<\/strong>(<em>X<\/em>\u00a0\u00d7 <em>Y<\/em>)) =\u00a0rk <strong>S<\/strong><em>X\u00a0<\/em>\u2295 rk <strong>S<\/strong><em>Y<\/em>, because <strong>S<\/strong>(<em>X<\/em>\u00a0\u00d7 <em>Y<\/em>)\u2245<strong>S<\/strong><em>X<\/em>\u00d7<strong>S<\/strong><em>Y<\/em><\/li>\n<li>rk (\u03a3*) = \u03c9<em><sup>k<\/sup><\/em>, where \u03a3 is a discrete set of cardinality <em>k<\/em>, and \u03a3* 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<\/li>\n<li>rk (<strong>S<\/strong>(\u03a3*)) = \u03c9<em><sup>k<\/sup><\/em> + 1, where \u03a3 is a discrete set of cardinality <em>k<\/em> (unpublished).<\/li>\n<\/ul>\n<p>Some special cases include:<\/p>\n<ul>\n<li>What is rk (<strong>H<\/strong>(<em>X<\/em>\u00a0\u00d7 <em>Y<\/em>))?\u00a0 The answer is known for wqos: this is equal to rk <strong>H<\/strong><em>X\u00a0<\/em>\u2297 rk <strong>H<\/strong><em>Y<\/em>, where \u2297 is natural product of ordinals.\u00a0 (This follows from the correspondence with maximal order types [2], and Theorem 7 of [4].)\u00a0 That the same formula would hold for general Noetherian spaces is likely, but unknown.<\/li>\n<li>What is rk (<strong>S<\/strong>(<em>X<\/em>*)) for <em>X<\/em> a general Noetherian space?<\/li>\n<li>What is rk (<strong>H<\/strong>(<em>X<\/em>*)) for <em>X<\/em> a general Noetherian space?<\/li>\n<li>What about spaces of trees?<\/li>\n<li>Note that, for a wqo <em>X<\/em> (not a general Noetherian space), rk (<strong>H<\/strong><em>X<\/em>) is equal to the maximal order type of <em>X<\/em> [2].\u00a0 Can a similar characterization be obtained for arbitrary Noetherian spaces?<\/li>\n<\/ul>\n<ol>\n<li>Jean Goubault-Larrecq. <a href=\"https:\/\/www.cambridge.org\/fr\/academic\/subjects\/mathematics\/geometry-and-topology\/non-hausdorff-topology-and-domain-theory-selected-topics-point-set-topology?format=HB&amp;isbn=9781107034136\">Non-Hausdorff Topology and Domain Theory \u2014 Selected Topics in Point-Set Topology<\/a>. New Mathematical Monographs\u00a0 22. Cambridge University Press, 2013.<\/li>\n<li>Andreas Blass, Yuri Gurevich. <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<li>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\u2013207, 1977.<\/li>\n<li>\n<div>D. Schmidt. Well-partial orderings and their maximal order types. Habilitation, University of Heidelberg, Heidelberg, 1979.<\/div>\n<\/li>\n<li><span class=\"authors\"> <span class=\"auteur\"><a href=\"https:\/\/www7.in.tum.de\/%7eblondin\/\">M. Blondin<\/a><\/span>, <span class=\"auteur\"><a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~finkel\/\">A. Finkel<\/a><\/span> and <span class=\"auteur\"><a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~goubault\/\">J. Goubault-Larrecq<\/a><\/span><\/span>.\u00a0 <span class=\"titre\">Forward Analysis for WSTS, Part III: Karp-Miller Trees<\/span>.\u00a0 <em>In<\/em> <span class=\"booktitle\"><acronym title=\"Proceedings of the 36th Conference on Foundations of Software\n  Technology and Theoretical Computer Science (FSTTCS'17), Kanpur,\n  India, December 2017\">FSTTCS&#8217;17<\/acronym><\/span>, Leibniz International Proceedings in Informatics. Leibniz-Zentrum f\u00fcr Informatik, <span class=\"year\">2017<\/span>.<\/li>\n<\/ol>\n<p style=\"text-align: right;\">\u2014 <a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~goubault\/?l=en\" rel=\"attachment wp-att-993\">Jean Goubault-Larrecq<\/a>\u00a0(February 23rd, 2017)<img loading=\"lazy\" decoding=\"async\" class=\"wp-image-993 alignright\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2016\/08\/jgl-2011.png\" alt=\"jgl-2011\" width=\"32\" height=\"44\" \/><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update.\u00a0 These problems (and a few others) were solved, by Bastien Laboureix and me: see this arXiv paper. \u00a0Bastien is a gifted young man, whom I have had the pleasure to have had as a student in various courses at &hellip; <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1134\">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":{"footnotes":""},"class_list":["post-1134","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/1134","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=1134"}],"version-history":[{"count":18,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/1134\/revisions"}],"predecessor-version":[{"id":5941,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/1134\/revisions\/5941"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}