Dcpos built as graphs of functions

Last year [1], I found a construction that allows one to prove the following: every space that arises as a Π02 subset of a continuous dcpo X also arises (up to homeomorphism) as a Gδ subset of some other continuous dcpo Z. The key point is the construction of the required new continuous dcpo, Z, from X.

My initial proof was monolithic, and the anonymous referee suggested a simplification of the proof. This prompted some further work, which was profitable! Refining the proof, as with sculpting, eventually revealed the shape that was hidden deep inside the rock.

In the end, the construction is essentially this: we have a continuous dcpo P, a map ψ : XP, and we build Z as the graph G(ψ) of ψ, namely as the set of pairs (x, ψ(x)), xX. Under what conditions does this give you a continuous dcpo? Note that I haven’t required ψ to be Scott-continuous—that is crucial for the application I have in mind [1].

Subdcpos

I will show that, under suitably weak assumptions, G(ψ) is not just a dcpo, but a subdcpo of X × P. (I will deal with continuity later, and only briefly.)

A subdcpo G of a dcpo X is a subset of X that is closed under directed suprema. In particular, every subdcpo of X is a dcpo, with the ordering induced from that of X, but it is important to note that it is one in which directed suprema are computed exactly as in X.

The latter is not true of every subposet of X that happens to be a dcpo. For example, if X is the complete lattice H(Y) of closed subsets of some topological space Y, then directed suprema in H(Y) are computed as closures of unions, while directed suprema in the larger complete lattice P(Y) of all subsets of Y are computed as mere unions. Hence H(Y) is a subposet of P(Y), and a dcpo (even a complete lattice), but not a subdcpo.

One can also say that a subdcpo is a subset such that the inclusion map is not just monotonic, but Scott-continuous.

All right. Now, under what conditions is G(ψ) a subdcpo of X × P? This certainly holds when ψ is Scott-continuous, as I will let you check by yourself, but does this hold more generally?

The answer is yes, but we will have to talk about the d-topology first. I have already said a word about it at the end of a recent post on dcpo quotients.

The d-topology

The d-topology on a dcpo X is the topology whose closed sets are exactly the subdcpos of X. In other words, the d-closed subsets of X are those subsets C that are closed under directed suprema. Hence the d-open subsets (the open subsets in the d-topology) are the subsets U of X such that, for every directed family (xi)i ∈ I in X whose supremum lies in U, some xi already lies in U.

Clearly, every Scott-open subset of X is d-open. Conversely, every upwards-closed d-open set is Scott-open. But there are plenty of other, non-upwards-closed, d-open subsets. Notably, every downwards-closed subset is d-open, for a rather trivial reason: for every directed family (xi)i ∈ I in X whose supremum lies in the downwards-closed subset, every xi is below that supremum, hence also in that subset.

It follows that the d-topology is not just finer than the Scott topology, but also than the Skula topology obtained from the Scott topology. (The Skula topology is the coarsest topology that makes both the original open and the original closed sets open.) The Skula topology is always Hausdorff, hence so is the d-topology. A more elementary argument is as follows. If s and t are different points of P, say st, then ↓t and its complement are both d-open (its complement is Scott-open, since ↓t is Scott-closed), they are disjoint, and contain t and s respectively.

Oh… but I have not said why the d-topology is a topology. Any union of d-open sets is d-open, but it is slightly harder to show that the intersection of two d-open sets is d-open. The key is the following.

Fact A. A subset U of a dcpo X is d-open if and only if, for every monotone net (xi)i ∈ I, ⊑ in X whose supremum is in U, xi is in U for i large enough.

“Large enough”, as usual, means: there is an index i0I such that for every iI with i0i, xi is in U. In the definition, we required that xi is in U for some i in I, but it is equivalent to require xi to be in U for every large enough i.

Also, a monotone net (see Exercise 4.7.8 in the book) is a net in which ij implies xixj. Every monotone net defines a directed family, and conversely every directed family (xi)i ∈ I defines a monotone net by letting ij if and only if xixj. I will use the two notions interchangeably.

The proof of Fact A runs by contradiction. If the conclusion failed, there would be a monotone net (xi)i ∈ I, ⊑ in X whose supremum is in U, but such that for every i0I, there would be a larger index i in I such that xi is not in U. In other words, the family J of all the indices i in I such that xi is not in U would be cofinal in I. Then J would be directed, therefore (xi)i ∈ J,  would be a monotone subnet of our original monotone net, and its supremum would be the same as that of the original net. Since that supremum is in U, by definition of d-open sets, xi would be in U for some i in J. But that would contradict the definition of J. ☐

It is now easy to show that the intersection of two d-open sets U, V is d-open: given a monotone net (xi)i ∈ I, ⊑ whose supremum is in UV, xi is in U for i large enough, say i above i0, and xi is in V for i large enough, say i above i1. By directedness, one can find an i in I above both i0 and i1, and then xi is both in U and in V.

Now let ψ be any map from a dcpo X to some space Y, and let us write Xd for X with the d-topology. We have:

Fact B. ψ is continuous from Xd to Y if and only if ψ maps directed suprema to limits (namely: for every monotone net (xi)i ∈ I, ⊑ in X, ψ(supi ∈ I xi) is a limit of the net (ψ(xi))i ∈ I, ⊑).

Proof. If: for every open subset V of Y, for every monotone net (xi)i ∈ I, ⊑ in X whose supremum x is in ψ-1(V), (ψ(xi))i ∈ I, ⊑ converges to ψ(x) in V, so ψ(xi) is in V for i large enough, hence xi is in ψ-1(V) for i large enough (in particular, for some i).

Only if: let us assume that ψ is continuous from Xd to Y. For every monotone net (xi)i ∈ I, ⊑ in X with supremum x, for every open neighborhood V of ψ(x), x is in the d-open set ψ-1(V). By Fact A, xi is in ψ-1(V) for i large enough, so ψ(xi) is in V for i large enough. This shows that (ψ(xi))i ∈ I, ⊑ converges to ψ(x). ☐

G(ψ) as a subdcpo of X × P

Let me recall that, for a map ψ : XP between dcpos, G(ψ) is a subdcpo of X × P provided that ψ is Scott-continuous. More generally, we have the following, where both the d-topology and Hausdorffness play an important role.

Proposition 1. Let X and P be two dcpos. Equip P with a Hausdorff topology coarser than the d-topology, and write P’ for P with that topology. If ψ is a continuous map from Xd to P‘, then G(ψ) is a subdcpo of X × P.

Proof. The argument is very short. We consider any monotone net (xi, ψ(xi))i ∈ I, ⊑ in G(ψ). Let (x,t) be its supremum in X × P. In order to show that this is in G(ψ), we must show that t=ψ(x).

We reason by contradiction, and we assume that t is different from ψ(x). Since P’ is Hausdorff, there is P’-open neighborhood U of t and a P’-open neighborhood V of ψ(x) such that U and V are disjoint. Now:

  • The net (ψ(xi))i ∈ I, ⊑ is a monotone net. If that puzzles you, this is probably because you think “let me see, (xi)i ∈ I, ⊑ is monotone net… but then you need ψ to be monotonic to conclude, but I cannot prove that…”. No, it is a monotone net because it is the net of second components of the monotone net (xi, ψ(xi))i ∈ I, ⊑.
  • Now t is a supremum of the monotone net (ψ(xi))i ∈ I, ⊑, and is in U. U, being open in the topology of P’, is in particular d-open, so ψ(xi) must be in U for i large enough, by Fact A.
  • The net (xi)i ∈ I, ⊑ is also a monotone net. Its supremum x is in the d-open set ψ-1(V), so xi is in ψ-1(V) for i large enough, by Fact A. It follows that ψ(xi) is in V for i large enough.
  • Hence for i large enough, ψ(xi) is both in U and in V: contradiction, since they are disjoint. ☐

What kind of funny Hausdorff topology can we take in Proposition 1? Well, the d-topology itself qualifies. It is certainly Hausdorff, as we have already seen. Hence:

Corollary 1. Let X and P be two dcpos. For every continuous map ψ from Xd to Pd, G(ψ) is a subdcpo of X × P.

Being continuous from Xd to Pd is relatively restrictive in some applications. We will see one shortly. Proposition 1 allows us to use another Hausdorff topology on P if we need to, and the coarser the topology, the fewer assumptions we make on ψ.

Let us consider the Lawson topology (Exercises 9.1.21, 9.1.36, 9.1.42 in the book). This is the coarsest topology containing all the Scott-open sets and all the complements of sets of the form ↑t (t a point). Let Pλ be P with its Lawson topology.

If P is a continuous dcpo, or even just a quasi-continuous dcpo, then the Lawson topology on P is Hausdorff (see Exercise 9.1.36 in the book). It is also clearly coarser than the d-topology. A direct proof that the Lawson topology is Hausdorff when P is quasi-continuous runs as follows. Let st, say st. By quasi-continuity there is a finite set E={x1, …, xn} such that s is in ↟E, but t is not in ↑E. Indeed, in a quasi-continuous poset, ↑s is the filtered intersection of the sets ↑E, where E ranges over the finite subsets such that Es (Exercise 5.1.34). Then ↟E is Scott-open, hence Lawson-open, and contains s; the complement of ↑E is Lawson-open, and contains t; and those two Lawson-open sets are disjoint. Therefore:

Corollary 2. Let X and P be two dcpos. If P is quasi-continuous, then for every continuous map ψ from Xd to Pλ, G(ψ) is a subdcpo of X × P. ☐

The application I have in mind, and which I will develop further below, is the following.

Example E. Let X be a dcpo, P be the interval [0, 1] with its usual ordering. Every Scott-continuous map f : XP is continuous from Xd to Pλ, in fact even from Xd to Pd. This is because the inverse image of any Scott-open set is Scott-open (clearly) and the inverse image of any downwards-closed set is downwards-closed (every Scott-continuous map is monotonic).
The Lawson topology on P is the usual metric topology, which makes subtraction continuous. It follows that, given any two Scott-continuous maps f, g : XP with fg, the map φ = fg is also continuous from Xd to Pλ.
Corollary 2 then tells us that G(φ) = {(x, f(x)–g(x)) | x in X} is a subdcpo of X × P.

We cannot replace Pλ by Pd in this argument: subtraction is not continuous on Pd (whose topology is a variant of that of the Sorgenfrey line). Indeed, 1–1/n converges to 1 in Pd, but 1 – (1–1/n) does not converge to 0 (consider the d-open set {0}). In other words, Corollary 1 does not apply here.

That’s it! You’ve probably had enough for this month, and at this point we have seen the essential construction I wanted to explain.

If you are curious to know what I do with that, really, in [1], please read on. However, this gets more technical, and perhaps less interesting, and I will gradually leave out more and more details.

Subdomains

Much as subdcpos of X are a bit more than dcpos included in X, let me call subdomain of a domain (=a continuous dcpo) X any subdcpo G whose way-below relation ≪G coincides with the restriction of the way-below relation ≪X on X.

Every subdomain G is a continuous dcpo, and its Scott topology coincides with the subspace topology.

One should not confuse a subdomain with a continuous subdcpo. For example, consider a locally compact space Y, and let X be its powerset lattice P(Y), and let G be its subdcpo O(Y) of open sets. This is a continuous subdcpo, in which U is way-below V if and only if UQV for some compact saturated set Q (Theorem 5.2.9 in the book). But U is way-below V in X=P(Y) if and only if U is finite and included in V. That is a completely different relation.

It is an easy exercise to show that, given a subdcpo G of a continuous dcpo X, G is a subdomain if and only if:

(Cofinality condition) for every g in G, ↡gG is cofinal in ↡g.

In other words, if and only if for every g in G, for every x in X such that xg, there is a g’ in G such that xg’g.

A well-known case is the following: every Scott-closed subset of a continuous dcpo is a subdomain. It is a subdcpo because, being Scott-closed, it is d-closed. The cofinality condition above holds because Scott-closed sets are downwards-closed.

For a subdcpo of the form G(ψ) (under the assumptions of Proposition 1), the cofinality condition expands as the following, rather complicated sentence:

for every x in X, for every yx in X, for every t ≪ ψ(x), there is a point z in X such that yzx and t ≤ ψ(z)≪ ψ(x).

We can simplify this a bit to the following equivalent condition when X and P are continuous (still under the assumptions of Proposition 1), so that no t is mentioned any longer:

(*) for every x in X, for every yx in X, there is a point z in X such that yzx and ψ(z)≪ ψ(x).

That is still dreary, but it is helpful to know that if you want to verify the claims that I am going to make below (and which I won’t give you the proof of!). If you don’t want to know why this is equivalent, please skip to the next section.

(Proof. The previous condition clearly implies (*). Conversely, if (*) holds, and assuming yx and t ≪ ψ(x), x is in the the d-open set ψ-1(↟t) ∩ ↟y. Since X is continuous, x is the supremum the directed family ↡x. We arrange that family as a monotone net (xi)i ∈ I, ⊑ consisting of all points way-below x. Since x is in ψ-1(↟t) ∩ ↟y, xi is in ψ-1(↟t) ∩ ↟y for i large enough. We pick one such xi. Note that xj is also in ψ-1(↟t) ∩ ↟y for every j above i. Now we call y that xi, and we apply (*). The point z we obtain this way is way-below x, hence is equal to some xj, and since y=xiz=xj, we have ij. Since j is larger than i, z=xj is also in ψ-1(↟t) ∩ ↟y. It is now easy to check that yzx and t ≤ ψ(z)≪ ψ(x).)

Application

The main construction of [1] is as follows.

Theorem. Let Y be a continuous dcpo, and φ be a continuous map from Yd to [0, 1]λ. Then the set Z of all pairs (y,r) in Y × [0, +∞) such that φ(y)–r≤0, ordered by (y,r)≤(z,s) if and only if yz, rs, and φ(y)–r≤φ(z)–s, is a continuous dcpo.

You will agree that this looks rather odd. In order to prove this, we first switch to a space with a more casual ordering: note that (y,r)≤(z,s) in Z if and only if the triple (y,–r,φ(y)–r) is componentwise below (z,–s,φ(z)s).

Hence, let X be the continuous dcpo Y × (-∞, 0], P be the continuous dcpo (-∞, 1], ψ be the map (y,–r) ↦ φ(y)–r. One can check that ψ is continuous from Xd to Pλ. Hence, by Corollary 2, G(ψ), which is precisely the set of triples of the form (y,–r,φ(y)–r), is a subdcpo. I will let you check that condition (*) holds, so that is even a subdomain of Y × (-∞, 0] × (-∞, 1].

There is a map from Z from G(ψ), which sends (y,r) ∈ Y × [0, +∞) to (y,–r,φ(y)–r), and that is an order-isomorphism of Z onto… ah, not G(ψ), but the subset Z’ of those triples (y,–r,s) in G(ψ) such that s≤0. But that subset is Scott-closed in G(ψ), because directed suprema are computed componentwise (i.e., as in Y × (-∞, 0] × (-∞, 1] — this is what G(ψ) being a subdcpo of the latter means). Therefore, Z’ is also a subdomain of G(ψ). In particular, it is a continuous dcpo, and therefore so is Z.

As an exercise, I will let you figure out for yourselves how directed suprema are computed in Z, and what the way-below relation is in Z. (Do not compute it by hand: use the order-isomorphism we have just described.) That way, you will be able to check whether you have understood how the whole thing works.

Π02 and Gδ subsets

I invented that construction in order to show that every Π02 subset of a continuous dcpo is homeomorphic to a Gδ subset of some other continuous dcpo. Here is how it works.

We start from a continuous dcpo Y, and a Π02 subset A of Y. Every Π02 subset ∩nN (UnVn) of X, where, without loss of generality, Un is a superset of Vn for each n, can be written as φ-1 ({0}), where φ = fg, and f = ∑n N 1/2n χUn and g = ∑n N 1/2n χVn are lower semicontinuous maps. In Example E, we have seen that such a map φ is continuous from Yd to [0, 1]λ.

Now, one can show that the map yA ↦ (y,0) is a topological embedding of A (with the subspace topology of Y) into Z. Hence it is a homeomorphism onto its image, which happens to be the subspace A’ of those elements (y,r) of Z such that r=0. Hence A’ is equal to the intersection of the sets Vn consisting of those elements (y,r) of Z such that r<1/2n, nN. Each of those sets Vn is Scott-open, so A’ is a Gδ subset of Z, and we conclude.

That theorem implies that Π02 subsets of domain-complete spaces are again domain-complete in the subspace topology. (A domain-complete space is defined as a Gδ subset of a continuous dcpo, in its subspace topology.) Also, if Y is not just continuous, but ω-continuous (equivalently, second-countable in its Scott topology), the continuous dcpo Z we built is also ω-continuous, so every quasi-Polish space (defined, say, as a Π02 subset of P(N)) is also a Gδ subset of some ω-continuous dcpo.

  1. Jean Goubault-Larrecq. Π02 subsets of domain-complete spaces and countably correlated spaces. Submitted to Topology Proceedings (two sites: Auburn University and Nipissing University), 2019.
  2. Klaus Keimel and Jimmie D. Lawson.  D-completions and the d-topology.  Annals of Pure and Applied Logic 159(3), June 2009, pages 292-306.
jgl-2011

Jean Goubault-Larrecq