Quasi-Polish spaces as rounded ideal completions

The rounded ideal completion RI(B,≺) of a transitive, interpolative relation ≺ on a set B (an abstract basis), is always a continuous dcpo, and every continuous dcpo can be written this way, up to isomorphism. Quite some time ago, Matthew de Brecht mentioned the following pearl to me: if you remove the interpolation requirement, and ask B to be countable, then the rounded ideal completions of transitive relations on a countable set B (with a suitable topology) are exactly the quasi-Polish spaces. This can be found in [1], amidst some computability considerations which I will ignore here.

The rounded ideal completion

Let ≺ be a transitive relation on a set B. While the rounded ideals of B,≺ are usually defined when ≺ is not just transitive but also interpolative, the definition makes perfect sense without interpolation. Let me recall that a rounded ideal in B,≺ is a subset I of B that is:

  • downwards-closed: for all x, yB such that xy and yI, x is in I;
  • and directed: for every finite collection of elements x1, …, xn of I, there is an element x of I such that x1, …, xnx. When n=0, this means that I is non-empty. When n=2, this is the usual directedness condition that any two elements of I have a common upper bound in I. When n=1, this says that for every element x of I, there is an element y of I such that xy: that would come for free if ≺ were reflexive, but, precisely, ≺ is not reflexive in general.

It is traditional to equip RI(B,≺), the set of rounded ideals of B,≺, with the Scott topology of the inclusion ordering. That works marvelously well when B,≺ is an abstract basis, that is, when ≺ is not only transitive but interpolative: ≺ is interpolative if and only if for all elements x1, …, xn and x such that x1, …, xnx, there is an element y of B such that x1, …, xnyx. In that case, RI(B,≺) is a continuous dcpo, and conversely, every continuous dcpo X can be obtained this way up to isomorphism (Proposition 5.1.33 in the book).

However, in the case where ≺ is transitive but not necessarily interpolative, we must equip RI(B,≺) with another topology [1, Definition 1], which I will call the weak topology. This is the topology generated by the subbasic open sets [x], xB, where [x] is the collection of rounded ideals that contain x.

The weak topology is always coarser (weaker) than the Scott topology of inclusion, and coincides with it if B,≺ is an abstract basis. Indeed, by Proposition 5.1.33 of the book, a basis of RI(B,≺) is given by the sets ⇓x = {yB | yx}, xB; the sets ↟⇓x = {IRI(B,≺) | ⇓xI} form a base of the Scott topology, and one checks easily that those sets ↟⇓x are simply the sets [x].

Henceforth, we will always equip RI(B,≺) with the weak topology. This will cover both the interpolative and the non-interpolative cases.

Embedding RI(B,≺) inside a continuous (even algebraic) dcpo

We wish to show that, when B is countable and ≺ is merely transitive, then RI(B,≺) is quasi-Polish. It suffices to embed it as a some Π02 subspace (see later) of an ω-continuous dcpo, because every Π02 subspace of an ω-continuous dcpo is quasi-Polish [2, Corollary 45+Corollary 23]. (I will say that again below.)

Working our way towards that result, will embed RI(B,≺), where ≺ is transitive but not necessarily interpolative, inside a continuous dcpo. This is remarkably simple.

Let ⪯ be the reflexive closure of ≺. In other words, xy if and only if xy or x=y. We will simply embed RI(B,≺) inside RI(B,⪯).

The relation ⪯ is of course transitive, and it is also trivially interpolative: for all elements x1, …, xn and x such that x1, …, xnx, there is an element y of B such that x1, …, xnyx… namely x itself. As we noticed earlier, every reflexive relation is interpolative.

Then RI(B,⪯) is a continuous dcpo, as we have recalled above, and its weak topology coincides with the Scott topology of inclusion. Even better: since ⪯ is a preordering, RI(B,⪯) is simply the ideal completion I(B,⪯), which is an algebraic dcpo, whose finite elements are the sets ↓x = {yB | yx}, xB. The (rounded) ideals of B,⪯ are simply its ideals.

Let us keep the notation [x] for the subbasic open subsets of RI(B,≺), namely the set of rounded ideals I of B,≺ that contain x, and let us use the new notation [x]’ for the corresponding subbasic open subsets of RI(B,⪯), namely the set of ideals I’ of B,⪯ (not ≺) that contain x.

We consider the function i : RI(B,≺) → RI(B,⪯) that maps every rounded ideal I of B,≺ to itself, seen as an ideal of B,⪯. I will let you check that this is well-defined, and continuous: the inverse image i-1([x]’) is [x].

The map i is also almost open, namely every open subset U of RI(B,≺) is the inverse image of some open subset V of RI(B,⪯). Indeed, U is a union of finite intersections of sets of the form [x], and it suffices to take the union of finite intersections of the corresponding sets [x]’ for V. Let me recall that the continuous, almost open, and injective maps are exactly the topological embeddings (Proposition 4.10.9 in the book).

And precisely, i is injective, as should be clear. This gives us the desired embedding. We sum up the results we have obtained so far as follows.

Lemma A. For every set B, for every transitive relation ≺ on B, the inclusion map i : RI(B,≺) → RI(B,⪯) is a topological embedding, and RI(B,⪯) is an algebraic dcpo with the Scott topology of inclusion.

Characterizing the image of i

When B is countable, RI(B,⪯) is ω-continuous (even ω-algebraic): that simply means that it has a countable basis, and that basis is just B. We need to show that its subspace RI(B,≺) has a special shape, namely that it is a Π02 subspace (again, see later).

To this end, we characterize RI(B,≺) as a subset of RI(B,⪯). That is easy: an ideal I’ of RI(B,⪯) is in RI(B,≺) if and only if it is rounded with respect to ≺. I claim that this is equivalent to the following formula:

  • (R) for every xB, if xI’ then there is a yB such that xy and yI’.

Let us check the equivalence. Every rounded ideal I of B,≺ satisfies (R): this is the special case n=1 of the definition of directedness for ≺. Conversely, if I’ is an ideal of B,⪯ that satisfies (R), then for every finite collection of points x1, …, xn in I’, since I’ is an ideal of B,⪯, there is a point x’ of I’ such that x1, …, xnx’. We now use (R) and find a point y in I’ such that x’y, whence x1, …, xny.

The formula (R) can be restated by noticing that atomic subformulae such as ” xI’ ” are equivalent to ” I’ ∈ [x]’ “. When U and V are open sets, we have already used the notation UV in the past to denote the set of elements that are in V or not in U (i.e., such that, if they are in U, then they are in V), and we have called them UCO subsets, following R. Heckmann: see this post on countably presented locales or that post on sober subspaces and the Skula topology, for example.

Hence an ideal I’ of B,⪯ is in RI(B,≺) if and only if it is in all the UCO subsets [x]’ ⇒ ∪ {[y]’ | yB such that xy}, where x ranges over the elements of B.

Just before the section on “The Skula topology” in the second post I cited above, I said that any intersection of UCO sets in a sober space is sober. And certainly, RI(B,⪯) is sober, since any continuous dcpo is sober in its Scott topology (see Proposition 8.2.12 (b) in the book), and its Scott topology coincides with the weak topology (Lemma A). This allows us to obtain the following result easily (although not by elementary means).

Lemma B. For every set B, for every transitive relation ≺ on B, RI(B,≺) is a sober space in the weak topology.

When B is countable, RI(B,≺) is not just an intersection of UCO subsets, but a countable intersection of UCO subsets, namely a so-called Π02 subspace (the definition, at last!). In that case, also, RI(B,⪯) is also not just a continuous dcpo, but an ω-continuous dcpo: in other words, it has a countable basis, isomorphic to B. But every ω-continuous dcpo is a quasi-Polish space with its Scott topology [2, Corollary 45], and quasi-Polishness is preserved by taking Π02 subspaces [2, Corollary 23]. Hence we obtain one half of the promised result by M. de Brecht.

Proposition C. For every countable set B, for every transitive relation ≺ on B, RI(B,≺) is a quasi-Polish space in the weak topology.

One may wonder whether we could embed B, with a suitable topology, inside RI(B,≺), just as we can do for an abstract basis B,≺, but now without interpolation. I do not think you can. For one, we will now prove a converse to Proposition C, and none of the elements of B we will obtain will come from the quasi-Polish space we will be given. That will be essential. Another reason is sketched in the Appendix at the end of this post.

Quasi-Polish spaces as rounded ideals

In order to show the promised converse of Proposition C, we need to have a look back at quasi-ideal domains.

A quasi-ideal domain is any algebraic dcpo in which every element below a finite element is finite. The other elements are called limit elements, and the definition means that you have a lower stratum of finite elements, and an upper stratum of limit elements, and they do not mix: no limit element is below any finite element.

In the Ideal Domains III post, I have shown that every continuous Yoneda-complete quasi-metric space X embeds into an algebraic dcpo, and in fact, in a very specific way: as the subspace of limit elements of a quasi-ideal domain. The construction shows that every ω-continuous Yoneda-complete quasi-metric space X (in particular, every quasi-Polish space) embeds as the subspace of limit elements of a quasi-ideal domain with countably many finite elements. This appears explicitly as Theorem 8.18 of [4].

Hence, let X be a quasi-Polish space. Up to isomorphism, we can equate X with the set YB of limit elements of some quasi-ideal domain Y, with a countable set B of finite elements. Let ≤ be the ordering on Y, and < be its strict part, namely x<y if and only if xy and xy.

In general, that is, ignoring the countability of B, we have the following.

Proposition D. Let Y be a quasi-ideal domain, with set B of finite elements. Equip Y with the Scott topology, and let X be YB with the subspace topology. Let also < be the strict part of the ordering ≤ on Y. Then X and RI(B,<) are homeomorphic.

Proof. Let us examine the shape of rounded ideals I of B,<. I is non-empty, so let us pick b1 in I. By the n=0 case of directedness, there is an element b2 in I such that b1<b2. Similarly, there is an element b3 in I such that b2<b3, and so on. This allows us to build an infinite, strictly increasing sequence b1 < … < bn < … of elements of I. Let x be the supremum of that sequence in Y. If x were a finite element of Y, then we would have xbi for some index i, whence x < bi+1x, which is impossible. Therefore x is a limit element, in X. Also, x ≤ sup I, since x is obtained as the supremum of a subset of I. Since Y is a quasi-ideal domain, sup I must also be in X.

This defines a function sup : RI(B,<) → X, which maps every rounded ideal of B to its supremum, which lies in X, as we have just seen.

Let us verify that this function is continuous. The topology of X has a base of sets of the form ↑bX, bB. Then sup-1(↑bX) is the set of rounded ideals I of B,< such that b≤sup I, or equivalently such that bI, since b is a finite element of Y. In other words, sup-1(↑bX) = [b].

Since every subbasic open set [b] of RI(B,<) is the inverse image of some open subset (namely ↑bX) of X, the function sup is almost open, too. The argument is as for the function i, dealt with earlier.

It is also clear that sup is surjective. Every point x of X is by definition the supremum of the directed (with respect to ≤) family Dx of points bB below x. Dx is an ideal of B,≤, and we claim that it is a rounded ideal of B,<. To this end, we have already noticed that it was enough to check that Dx satisfies formula (R), namely: for every b in Dx, there is an element b’ in Dx such that b<b’. This is easy. We assume, on the contrary that Dx has an element b such that b<b’ for no b’ in Dx; in other words, that Dx has a maximal element b. Since Dx is directed with respect to ≤, b would be the largest element of Dx, so that b=sup Dx=x, which is impossible since b is finite and x is not.

Finally, we claim that sup is injective. Let I be a rounded ideal of B,<, x be its supremum. We only have to show that I is equal to Dx. The inclusion IDx is obvious, so it suffices to show that DxI. For every b in Dx, bx = sup I, and since b is finite, there is an element b’ of I such that bb’. If b=b’, then b is in I. Otherwise, b<b’, and since I is downwards-closed with respect to <, b is again in I. ☐

In summary, sup is a homeomorphism. As we have said above, every quasi-Polish space X is representable, up to homeomorphism, as the set X=YB of limit elements of some quasi-ideal domain Y with a countable set B of finite elements. Together with Proposition C, Proposition D therefore implies the following.

Theorem (de Brecht, [1]). The rounded ideal completions RI(B,≺) of countable sets B equipped with a transitive relation ≺ (with the weak topology) are exactly the quasi-Polish spaces, up to homeomorphism.

Open questions

Naturally, this begs the question of what the rounded ideal completions of not necessarily countable sets B, with a transitive relation ≺, can be.

  • We know (Lemma A) that those spaces are all sober. Are all sober spaces representable as RI(B,≺) up to homeomorphism for some B,≺ with ≺ transitive? I tend to doubt it.
  • We also know that all the continuous Yoneda-complete quasi-metric spaces, with their d-Scott topology, have a quasi-ideal domain (see Ideal Domains III, or Section 8 of [4]). Hence, by Proposition D, they can all be represented as RI(B,≺) up to homeomorphism for some B,≺ with ≺ transitive. Are those the only such spaces? In other words, can we always equip any rounded ideal completion RI(B,≺) (where ≺ is transitive) with a quasi-metric d that makes it Yoneda-complete, and such that the resulting d-Scott topology coincides with the weak topology? I also doubt it.

Appendix: you (probably) cannot embed B into RI(B,≺) without interpolation

I said that I do not think you can embed B into RI(B,≺) when ≺ is not interpolative. Here is another reason.

Jimmie Lawson (see [3], or Exercise 8.2.48 in the book) showed that, for any abstract basis B,≺, RI(B,≺) is the sobrification S(B) of B. Here B is given the pseudoScott topology, whose subbasic open sets are the sets ⇑x = {yB | xy}. In the book, I use the so-called rounded topology instead, but, thanks to interpolation, the two topologies coincide, if we start from an abstract basis.

Generalizing away from this situation, and merely assuming ≺ transitive, not necessarily interpolative, I will let you verify that the function c : RI(B,≺) → S(B) that maps every rounded ideal I in B to its closure in B (with the pseudoScott topology; the rounded ‘topology’ is not even a topology without interpolation) is continuous and almost open. You should first show that the sets ♢⇑x of irreducible closed subsets of B that intersect ⇑x form a base, not just a subbase of the topology on S(B); then, that c-1(♢⇑x)=[x] for every x.

The function c is also injective, so c is a topological embedding.

Now imagine that there were an embedding ε of B into RI(B,≺) which, composed with c, yielded the usual embedding η of B into S(B). Up to homeomorphism, this allows us to consider B as a subspace of RI(B,≺), itself a subspace of S(B). Since RI(B,≺) is sober (Lemma A), it would be Skula-closed in the sober space S(B), and S(B) would be the Skula-closure of B in S(B), namely the smallest Skula-closed subset containing B; that would imply that c is surjective, hence a homeomorphism.

You can show that the inverse j of c would necessarily map every point x of B (equated with its image cl({x}) in S(B)) to ⇓x. This is by Stone duality. The Stone dual O(c) : O(S(B)) → O(RI(B,≺)) maps ♢⇑y to [y] for every point y of B, hence the Stone dual O(j) of j would have to map [y] to ♢⇑y. Then, for all x, y in B, y is in j(x) if and only if j(x) is in [y], if and only if cl({x}) is in ♢⇑y, if and only if yx; that indeed shows that j(x) must be equal to ⇓x.

The issue is that ⇓x is not a rounded ideal for every x in B, unless ≺ is interpolative. Therefore, if ≺ is not interpolative, then the inverse j cannot exist; in particular, there cannot be any embedding ε of B into RI(B,≺) such that c o ε = η.

I am leaving out a lot of details, and this is also perhaps not the most direct argument. I am only mentioning this to stress that, without interpolation, embedding B into RI(B,≺) is quite probably hopeless; and if you succeed in doing it, it will probably be very unnatural anyway, in the sense that the embedding ε will not satisfy c o ε = η.

  1. Matthew de Brecht.  Some notes on spaces of ideals and computable topology. arXiv 2004.13375, April 2020.
  2. Matthew de Brecht.  Quasi-Polish spaces.  Annals of Pure and Applied Logic, Volume 164, Issue 3, March 2013, pages 356-381.
  3. Jimmie D. Lawson. The round ideal completion via sobrification. Topology Proceedings, volume 22, 1997, pages 261-274.
  4. Jean Goubault-Larrecq and Kok Min Ng. A few notes on formal balls. Logical Methods in Computer Science, 13(4:18), pages 1-34, November 2017. Special Issue of the Domains XII Workshop. 
jgl-2011

Jean Goubault-Larrecq (May 20th, 2020)