{"id":865,"date":"2016-01-27T14:25:28","date_gmt":"2016-01-27T13:25:28","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=865"},"modified":"2022-11-19T15:25:46","modified_gmt":"2022-11-19T14:25:46","slug":"remainders-bqos-and-quasi-polish-spaces-again","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=865","title":{"rendered":"Remainders, bqos, and quasi-Polish spaces again"},"content":{"rendered":"

In my first post on ideal domains<\/a>, I thought I would be able to extend Keye Martin’s result from metric to quasi-metric spaces. Of course, the set Max Y<\/em> of maximal elements of a dcpo Y<\/em> cannot yield an arbitrary quasi-metric space X<\/em>, since Max Y<\/em> is always a T1<\/sub> space.\u00a0 I think I am on my way to obtain that generalization, but let us not go too fast.<\/p>\n

Let us ponder at other ways to look at what an ideal domain really is.<\/p>\n

In an ideal domain Y<\/em>, X<\/em> = Max Y<\/em> occurs as the set-theoretic difference Y \u2014 Y<\/em>0<\/sub>, where Y<\/em>0<\/sub> is the set of finite elements of Y<\/em>. As for any algebraic domain, Y<\/em> is then isomorphic to the ideal completion I<\/strong>(Y<\/em>0<\/sub>) of Y<\/em>0<\/sub> (Exercise 5.1.47 in the book<\/a>).<\/p>\n

This leads to the following question: what topological spaces arise as ideal completion remainders<\/em>, that is, as the difference I<\/strong>(P<\/em>) \u2014 P<\/em> for some poset P<\/em>?<\/p>\n

A few years ago, I would have thought the question was silly. However, it arises here and there, possibly under slightly different forms. Let me start with a curious result, due to P\u00e9quignot and Carroy [4].<\/p>\n

Wqos, bqos and ideal completion remainders<\/h2>\n

A well-quasi-order (wqo, for short) is a quasi-ordered set P<\/em> which has no infinite strictly descending chain and no infinite antichain. This is, by the way, a special case of a Noetherian space (see Proposition 9.7.17 in the book<\/a>). I will assume that P<\/em> is actually a poset. That does not do much harm, since otherwise we may quotient P<\/em> by the equivalence relation induced by the quasi-ordering.<\/p>\n

There is a much stronger notion, due to Nash-Williams, and called better quasi-ordering<\/em>, or bqo. The definition is pretty complex. Let me just say that every bqo is wqo, that every total well-founded order is bqo, that every naturally occurring wqo is in fact bqo (to the exception of the graph minor relation, which is wqo by a celebrated result of Robertson and Seymour, but not known to be bqo), and that being bqo is preserved by many constructions.<\/p>\n

The ideal completion I<\/strong>(P<\/em>) of P<\/em> is in general not a wqo. In fact, it is a wqo if and only if P<\/em> is what is known as an \u03c92<\/sup>-wqo, a notion stronger than wqo but weaker than bqo; equivalently, if and only if P<\/em> does not embed the so-called Rado counter-example: see Exercise 9.7.25 in the book<\/a>.<\/p>\n

What Yann P\u00e9quignot and Rapha\u00ebl Carroy prove [4] is that the ideal completion remainder I<\/strong>(P<\/em>) \u2014 P<\/em> of a wqo P<\/em> is bqo if and only if P<\/em> is already a bqo.<\/p>\n

I am not going to expand on this result right now. It is a nifty result, and one that shows that ideal completion remainders do sometimes crop up.<\/p>\n

Let me return to the original question: what spaces are the ideal completion remainders of posets?<\/p>\n

Sobrification remainders<\/h2>\n

A very similar question was studied by Rudolf-Eberhard Hoffmann [2]. A sobrification remainder<\/em> is a topological space that arises as the difference S<\/strong>(Z<\/em>) \u2014 Z<\/em> for some T0<\/sub> topological space Z<\/em>. Here S<\/strong> is sobrification, and the analogy comes from the fact that if P<\/em> is a poset with its Alexandroff topology, then S<\/strong>(P<\/em>)=I<\/strong>(P<\/em>) (Fact 8.2.49 in the book<\/a>).<\/p>\n

If we agree to replace ideal completion by sobrification, then R.-E. Hoffmann solved the problem completely:<\/p>\n

Theorem [2, Theorem 1.6].<\/strong> The sobrification remainders are exactly the T0<\/sub> topological spaces.<\/p>\n

Proof.<\/strong> Clearly, every sobrification remainder is T0<\/sub>. Conversely, let X<\/em> be an arbitrary T0<\/sub> topological space. Let N<\/strong> be the poset of natural numbers, in its usual ordering. S<\/strong>(N<\/strong>)=I<\/strong>(N<\/strong>) is just N<\/strong> U {+\u221e<\/em>}. Let Y<\/em> be the space (S<\/strong>(N<\/strong>) x S<\/strong>(X<\/em>)) \u2014 ({+\u221e<\/em>} x X<\/em>), seen as a subspace of S<\/strong>(N<\/strong>) x S<\/strong>(X<\/em>). We show that S<\/strong>(Y<\/em>) is isomorphic to S<\/strong>(N<\/strong>) x S<\/strong>(X<\/em>), from which it will follow that S<\/strong>(Y<\/em>)\u2014Y<\/em> is isomorphic to X<\/em>.<\/p>\n

Hoffmann does it via a detour through the Skula topology, but there is a simpler (and more categorical) way. This is pictured below: take S<\/strong>(X<\/em>), and represent it as a horizontal slab; make infinitely many copies of this slab, all stacked up at levels 0, 1, 2, 3, 4, …, plus a new level at +infinity. Y<\/em> is the space delimited by the red boundary. We shall show that S<\/strong>(Y<\/em>) is equal to the outer square, and this will be because it will be contain the sobrification of the smaller rounded square N<\/strong> x X<\/em>, and is contained in the same sobrification already (the outer square). Now S<\/strong>(Y<\/em>)\u2014Y<\/em> will be the copy of X<\/em> at level +infty, the one that is not surrounded by any red.<\/p>\n

\"sobrification_remainder\"<\/a><\/p>\n

Let us do that formally. First, recall that S<\/strong>(N<\/strong>) x S<\/strong>(X<\/em>) is isomorphic to S<\/strong>(N<\/strong> x X<\/em>) (Theorem 8.4.8 in the book<\/a>). Since N<\/strong> x X<\/em> is T0<\/sub>, the map \u03b7S<\/sup><\/strong>X<\/sub><\/em> : N<\/strong> x X<\/em> \u2192 S<\/strong>(N<\/strong> x X<\/em>), which sends every element to its closure, is an embedding (Theorem 8.2.44). This yields an embedding of N<\/strong> x X<\/em> into S<\/strong>(N<\/strong>) x S<\/strong>(X<\/em>), which we also write as \u03b7S<\/sup><\/strong>X<\/sub><\/em>, and which maps (n<\/em>, x<\/em>) to (n<\/em>, \u2193x<\/em>). No element (n<\/em>, \u2193x<\/em>) is in {+\u221e<\/em>} x X<\/em>, so \u03b7S<\/sup><\/strong>X<\/sub><\/em>, also defines an embedding of N<\/strong> x X<\/em> into Y<\/em>.<\/p>\n

There is also a subspace embedding j<\/em> of Y<\/em> into S<\/strong>(N<\/strong>) x S<\/strong>(X<\/em>) = S<\/strong>(N<\/strong> x X<\/em>). We now use the fact that the S<\/strong> functor preserves embeddings (Lemma 8.4.11): S<\/strong>(\u03b7S<\/sup><\/strong>X<\/sub><\/em>) is an embedding of S<\/strong>(N<\/strong> x X<\/em>) into S<\/strong>(Y<\/em>), and S<\/strong>(j<\/em>) is an embedding of S<\/strong>(Y<\/em>) into S<\/strong>(S<\/strong>(N<\/strong> x X<\/em>)) \u2245 S<\/strong>(N<\/strong> x X<\/em>). Their composition is easily seen to be the identity map, so they are inverse of each other. In particular, S<\/strong>(Y<\/em>) is isomorphic to S<\/strong>(N<\/strong> x X<\/em>), and we are done. \u2610<\/p>\n

Hoffmann’s construction does not build the space Y<\/em> as a poset, hence that does not the answer the question of which spaces are ideal completion<\/em> remainders. However, we do have partial answers.<\/p>\n

Quasi-Polish spaces<\/h2>\n

I have already mentioned quasi-Polish spaces<\/a> [3]. One of the things mentioned in that paper, and which I have not cited yet, is the following: the spaces that are homeomorphic to the subspace of non-finite elements of an \u03c9-algebraic dcpo are exactly the quasi-Polish spaces.<\/p>\n

A dcpo is \u03c9-algebraic if and only if it is algebraic and has a countable<\/em> basis, equivalently, it has countably many finite elements. In other words, an \u03c9-algebraic dcpo is the same thing as the ideal completion of a countable<\/em> poset. Let us reformulate:<\/p>\n

Theorem (de Brecht).<\/strong> The ideal completion remainders of countable posets are (up to homeomorphism) exactly the quasi-Polish spaces.<\/p>\n

This is Theorem 53, Item 3, of [3]. I will give you an idea of Matthew de Brecht’s proof below. Before that, let me mention that this allows Matthew de Brecht to characterize completely the spaces that have an \u03c9-ideal model, that is, an ideal model with only countably many finite elements:<\/p>\n

Corollary (de Brecht, Corollary 54).<\/strong> The spaces with an \u03c9-ideal model are exactly the T1<\/sub> quasi-Polish spaces.<\/p>\n

Recall that a space is quasi-Polish if and only if it is obtained from a second-countable Smyth-complete quasi-metric space X<\/em>, d<\/em>, forgetting about the quasi-metric d<\/em> and keeping the topology.<\/p>\n

We first imitate Alexandroff’s Theorem (Theorem 7.7.11 in the book<\/a>). That says that the Polish (not quasi-Polish) spaces are, up to homeomorphism, the G<\/em>\u03b4<\/sub> subsets of the Hilbert cube [0, 1]N<\/sup><\/strong>. Matthew de Brecht shows instead that the quasi-Polish spaces are the \u03a0<\/strong>0<\/sup>2<\/sub> subsets of the dcpo P<\/strong>(N<\/strong>) of all subsets of N<\/strong> (ordered under inclusion). Standardly, that is, in metric spaces, “\u03a0<\/strong>0<\/sup>2<\/sub>” is synonymous with “G<\/em>\u03b4<\/sub>“, but, as discovered by Victor Selivanov earlier on, it is more meaningful to define “\u03a0<\/strong>0<\/sup>2<\/sub>” differently in non-T2<\/sub> spaces. (“\u03a0<\/strong>0<\/sup>2<\/sub>” and “G<\/em>\u03b4<\/sub>” will still be equivalent properties on T2<\/sub> spaces.)<\/p>\n

Accordingly, a subset A<\/em> of a topological space X<\/em> is called \u03a0<\/strong>0<\/sup>2<\/sub> if and only if there is a countable family of pairs of opens U<\/em>i<\/sub>, Vi<\/sub><\/em>, i<\/em> \u2208 N<\/strong>, such that, for every x<\/em> \u2208 X<\/em>, x<\/em> is in A<\/em> if and only if for every i<\/em> \u2208 N<\/strong>, x<\/em> \u2208 Ui<\/sub><\/em> \u21d2 x<\/em> \u2208 Vi<\/sub><\/em>.<\/p>\n

If X<\/em>, d<\/em> is second-countable, then we can embed X<\/em> into P<\/strong>(N<\/strong>) in the usual way: index a countable base (Ui<\/sub><\/em>)i \u2208 N<\/strong><\/sub><\/em> by natural numbers, and map each point x<\/em> of X<\/em> to the collection of indices i<\/em> such that x<\/em> \u2208 Ui<\/sub><\/em>. When X<\/em>, d<\/em> is also Smyth-complete, this is really an embedding, so we can see X<\/em> as a subspace of P<\/strong>(N<\/strong>). Using the strong Choquet game, M. de Brecht shows that a subspace of a quasi-Polish space is quasi-Polish if and only if it is \u03a00<\/sup>2<\/sub> (if and only if it is convergence Choquet complete). Every \u03c9-continuous dcpo, in particular P<\/strong>(N<\/strong>), is quasi-Polish, so X<\/em> arises as a \u03a0<\/strong>0<\/sup>2<\/sub> subset of P<\/strong>(N<\/strong>).<\/p>\n

This shows that every quasi-Polish space X<\/em> embeds as a \u03a0<\/strong>0<\/sup>2<\/sub> subset of P<\/strong>(N<\/strong>). There is a countable family of pairs of opens U<\/em>i<\/sub>, Vi<\/sub><\/em>, i<\/em> \u2208 N<\/strong>, in P<\/strong>(N<\/strong>) such that, for every a<\/em> \u2208 P<\/strong>(N<\/strong>), a<\/em> is in X<\/em> if and only if for every i<\/em> \u2208 N<\/strong>, a<\/em> \u2208 Ui<\/sub><\/em> \u21d2 a<\/em> \u2208 Vi<\/sub><\/em>. Let F<\/em> be the set of finite subsets E<\/em> of P<\/strong>(N<\/strong>) such that E<\/em> is contained in some x<\/em> \u2208 X<\/em> (or rather, in the element of P<\/strong>(N<\/strong>) that x<\/em> is mapped to by the embedding). Matthew de Brecht builds a poset P<\/em> = F<\/em> x N<\/strong>, with a specific ordering: (E<\/em>, n<\/em>) is below (E<\/em>‘, n<\/em>‘) if and only if either they are equal, or E<\/em> \u2286 E<\/em>‘ and n<\/em><n<\/em>‘ and for every i<\/em>\u2264n<\/em> such that E<\/em> \u2286 Ui<\/sub><\/em>, E’<\/em> \u2286 Ui<\/sub><\/em>. He then shows that X<\/em> embeds in I<\/strong>(P<\/em>) through the map that sends x<\/em> to the set of all pairs (E<\/em>, n<\/em>) such that E<\/em> is included in x<\/em>. Moreover, that set is a non-principal ideal, and that shows that X<\/em> embeds into the ideal completion remainder I<\/strong>(P<\/em>) \u2014 P<\/em>. Note also that P<\/em> is countable.<\/p>\n

We now know one direction of the theorem: every quasi-Polish space embeds into the ideal completion remainder of a countable poset.<\/p>\n

For the converse direction… let us pause for a minute.\u00a0 Matthew observes that every second-countable, locally compact sober space X<\/em> is quasi-Polish [3, Theorem 44], and we shall use that. That result should be compared with the fact that every second-countable, locally compact T3<\/sub> space is Polish (Corollary 8.3.28 in the book<\/a>). Matthew proves that theorem by embedding X<\/em> into P<\/strong>(N<\/strong>) using the countable base, and then characterizing the image of the embedding as an explicitly constructed \u03a0<\/strong>0<\/sup>2<\/sub> subset. P<\/strong>(N<\/strong>) is quasi-Polish, either by realizing it is a countable product of copies of Sierpi\u0144ski space, or directly, by defining the quasi-metric d<\/em> by d<\/em>(A<\/em>, B<\/em>) = 1\/2n<\/sup><\/em>, where n<\/em> is the least natural number that is in A<\/em> but not in B<\/em>, and 0 if A<\/em> \u2286 B<\/em>. Since every \u03a00<\/sup>2<\/sub> subset of a quasi-Polish space is quasi-Polish, the second-countable, locally compact sober space X<\/em> is quasi-Polish.<\/p>\n

We can now finish. Let P<\/em> be a countable poset. I<\/strong>(P<\/em>) is \u03c9-algebraic, hence \u03c9-continuous, hence second-countable (by Norberg’s Lemma 7.7.13 in the book<\/a>), and continuous hence locally compact sober. Therefore, as we have just seen, I<\/strong>(P<\/em>) is quasi-Polish. Now enumerate the (countably many) finite points pi<\/sub><\/em> of P<\/em>. Ui<\/sub><\/em> = \u2191pi<\/sub><\/em> of P<\/em> (the upward-closure of pi<\/sub><\/em> in I<\/strong>(P<\/em>)) is open, because pi<\/sub><\/em> is finite, and Vi<\/sub><\/em> = Ui<\/sub><\/em> \u2014 {pi<\/sub><\/em>}. The points x<\/em> of I<\/strong>(P<\/em>) such that for every i<\/em> \u2208 N<\/strong>, x<\/em> \u2208 Ui<\/sub><\/em> \u21d2 x<\/em> \u2208 Vi<\/sub><\/em>. are exactly the points of I<\/strong>(P<\/em>) that are not in P<\/em>, and, by definition, they form a \u03a00<\/sup>2<\/sub> subset of the quasi-Polish space I<\/strong>(P<\/em>). In other words, the ideal completion remainder I<\/strong>(P<\/em>) \u2014 P<\/em> is quasi-Polish.<\/p>\n

That finishes our tour of Matthew de Brecht’s proof that the ideal completion remainders of countable posets are exactly the quasi-Polish spaces.<\/p>\n

Next time…<\/h2>\n

Next time, I may explain how we can generalize the first part of the proof, and obtain ideal completion remainders (not necessarily of countable posets) from continuous Yoneda-complete quasi-metric spaces. That is, if all goes well: I am not completely sure that everything works. If that works, we shall see that those ideal completion remainders can even be made to resemble ideal domains, in a sense that I will make precise.<\/p>\n

(Note added, Dec 23rd, 2019. \u00a0It seems that the bibliographic references were absent. \u00a0Putting them back:)<\/p>\n

    \n
  1. Keye Martin. \u00a0Ideal models of spaces<\/a>. \u00a0Theoretical Computer Science<\/a>,\u00a0Volume 305, Issues 1\u20133<\/a>, 18 August 2003, pages 277\u2013297.<\/li>\n
  2. Rudolf-Eberhard Hoffmann. On the Sobrification Remainder s<\/sup>X<\/em>\u2013X<\/em>. Pacific Journal of Mathematics, 83(1), 145\u2013156, 1979.<\/li>\n
  3. Matthew de Brecht. \u00a0Quasi-Polish spaces<\/a>. \u00a0Annals of Pure and Applied Logic, Volume 164, Issue 3<\/a>, March 2013, pages 356-381.<\/li>\n
  4. Rapha\u00ebl Carroy and Yann P\u00e9quignot. \u00a0From Well to Better, the Space of Ideals<\/a>. Fundamenta Mathematicae, 2014, 227 (3), pages 247-270.<\/li>\n<\/ol>\n

    \u2014 Jean Goubault-Larrecq<\/a>\u00a0(January 27th, 2016)\"jgl-2011\"<\/p>\n","protected":false},"excerpt":{"rendered":"

    In my first post on ideal domains, I thought I would be able to extend Keye Martin’s result from metric to quasi-metric spaces. Of course, the set Max Y of maximal elements of a dcpo Y cannot yield an arbitrary … Continue reading →<\/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-865","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/865","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=865"}],"version-history":[{"count":7,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/865\/revisions"}],"predecessor-version":[{"id":5951,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/865\/revisions\/5951"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=865"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}