Dcpos and convergence spaces II: preserving products

Let us continue last month’s story.  We had define various structures of convergence spaces on a dcpo, which were all admissible in the sense that their topological modification is the Scott topology.

Amongst those, Heckmann convergence is defined by limF = cl (∪ {A | A ∈ F}), for every filter F of subsets of a dcpo X, where cl is Scott closure.  We had seen that Scott convergence was instead defined by limS = adh (∪ {A | A ∈ F}), where adh(B) is the set of elements below suprema of directed families included in the downwards-closed subset B—in general closure is obtained by iterating adh transfinitely.

The case of products

There is a very nasty pitfall concerning products in domain theory: in general, the product of two dcpos as posets is different from their product as topological spaces.  Explicitly, let us write Zσ for a poset Z seen as a topological space with the Scott topology.  The pitfall is that if you take two dcpos X and Y, build their product XY as dcpos, and then take the Scott topology (XY)σ, then what you will get will of course have the same points as the topological product Xσ x Yσ, but the topology will in general be different (see Exercise 5.2.16 in the book).

This has apparently caught a few people, including myself—and despite me knowing of the problem.

That problem does not occur with continuous dcpos, or even continuous posets.

One nice observation due to Reinhold Heckmann [1] is that the problem disappears completely once you see dcpos as convergence spaces, using Heckmann convergence, instead of topological spaces.

Let us investigate that.  Let us write ZH for a dcpo Z equipped with its Heckmann convergence limH.  Then:

Proposition.  For all dcpos XY, (XY)H=XH x YH.

The product on the right is product of convergence spaces.  Explicitly, for a filter F of subsets of XH x YH, the convergence on the right is given by lim F = limπ1 [F] x limπ2 [F].  (The direct image f[F] of a filter F denotes the filter {A | f-1(A) ∈ F}.)  Equivalently, the proposition means that limπ1 [F] x limπ2 [F] =  limF.

Proof. We recall from last time that ∪ {A | A ∈ F} is also the union of all ideals I such that for every element z of I, ↑z is in F.  Hence limF = cl (∪ {I ideal of X| for every z ∈ I, ↑z ∈ F}).

When F is a filter of subsets of XY, we must therefore examine the ideals I of XY such that for every (x,y) in I, ↑(x,y) is in F.  It is an easy exercise to show that the ideals of XY are exactly the products of two ideals, one in X, the other one in Y.  (Or use Proposition 8.4.7 of the book, which says that the irreducible closed subsets of a product of spaces are the products of irreducible closed subsets; Fact 8.2.49, which implies that the irreducible closed subsets of a poset in its Alexandroff topology are exactly its ideals; and Exercise 4.5.19, which says that products of posets, seen with their Alexandroff topologies, is exactly the topological product.)

Therefore limF = cl (∪ {I x JI ideal of XJ ideal of Y, and for all x ∈ I, y ∈ J,  ↑(x,y) ∈ F}).

For every pair (x,y) in the union inside the closure, there is an ideal I of X containing x, an ideal J of Y containing y such that for all x’ ∈ I, y’ ∈ J, ↑(x’,y’) ∈ F. Now ↑(x’,y’) = ↑x’ x ↑y’ is included in ↑x’ x Y = π1-1(↑x’), so the latter is in F.  In turn, that means that ↑x’ is in π1 [F].  Similarly, ↑y’ is in π2 [F].  We obtain that I is an ideal containing x such that every x’ in I satisfies ↑x’ ∈ π1 [F], so x is in limπ1 [F].  Similarly y is in limπ2 [F].  Hence limF is included in limπ1 [F] x limπ2 [F].

In the converse direction, we first notice that cl(A) x cl(B) = cl (AB), for all subsets A and B.  Indeed, cl(A) x cl(B) is closed and contains A x B, hence cl (AB).  If the inclusion were strict, there would be a point (x,y) in cl(A) x cl(B) but not in cl (AB).  Since the latter is closed, there would be an open rectangle U x V containing (x,y) and which does not intersect cl (AB).  But U intersects cl(A) at x, hence U intersects A, and similarly V intersects B, leading to a contradiction.

Letting A be the union of all ideals I of X such that for every element x of I, ↑x is in π1 [F], and B be the union of all ideals J of Y such that for every element y of J, ↑y is in π2 [F], limπ1 [F] x limπ2 [F] is then equal to cl (AB).  In order to show that limπ1 [F] x limπ2 [F] is included in limF, we only have to show that AB is included in limH F.

Let (x,y) in AB.  There is an ideal I of X such that for every element x’ of I, ↑x’ is in π1 [F].  There is also an ideal J of Y such that for every element y of J, ↑y is in π2 [F].  Then, for every (x’y’) in J, ↑x’ x Y is in F and X x ↑y is in F.  Their intersection ↑x’ x ↑y = ↑(x’,y) is then also in F.  Since IJ is an ideal, (x,y) is in ∪ {I x JI ideal of XJ ideal of Y, and for all x’ ∈ I, y’ ∈ J,  ↑(x’,y’) ∈ F}, hence in its closure limF.  ☐

I will let you check that this works equally well with Scott convergence, namely: not only do we have limH F = limπ1 [F] x limπ2 [F], but limS F = limπ1 [F] x limπ2 [F] is true as well.  The proof is the same, except that we must show that adh(A) x adh(B) = adh (AB), for all downwards-closed subsets A and B (exercise).

The previous proposition also entails that the topological modification of a product of convergence spaces is in general different from the topological product of the topological modifications: otherwise dcpo product would coincide with topological product as well.

A categorical reading of the previous proposition is that:

Proposition [1]. The functor _H, which maps every dcpo X to XH, also preserves products.

Proof.  The only thing that we have not proved here is that _H is indeed a functor.  For that, we should specify its action on morphisms: for every Scott-continuous map f from a dcpo X to a dcpo Y, we let fH be f itself, seen as a continuous map between convergence spaces.  Of course, we need to check that f is continuous in the sense of convergence spaces!  I will let you do the exercise.  This rests on elementary reasoning with ideals and filters of subsets, plus the easily proved inclusion f[cl(A)] ⊆ cl(f[A]).  ☐

Similarly, there is a functor _S, and it too preserves products, because f[adh(A)] ⊆ adh(f[A]).

Function spaces

Both the category Dcpo of dcpos and the category Conv of convergence spaces are Cartesian-closed, and one may therefore wonder whether the functor _also preserves exponential objects (function spaces, either with the pointwise ordering in Dcpo, or with the continuous convergence in Conv).

I do not know whether this is true or not.  (I hope I have not missed anything in [1].)  For the moment, let us see what we can say.

Consider two dcpos X and Y.  Write [X → Y] for the dcpo of Scott-continuous maps from X to Y, and [X→ YH] for the convergence space of all continuous map from the convergence space XH to YH.  The former yields a convergence space [X → Y]H.  Writing App for the application morphism (App sends (f,x) to f(x)) and Λ for currying (“evaluation”: Λ(f)(x) is the map f(x,_)), in any of our two Cartesian-closed categories—this is made possible by the fact that, set-theoretically, those acts on elements in exactly the same way, and will allow us a benign form of cheating below—, we have that:

  • App is a Scott-continuous map from [X → Y] x X to Y;
  • Hence App is a continuous map from ([X → Y] x X)H to YH;
  • Since _preserves product, App is continuous from [X → Y]HXH to YH;
  • So Λ(App), which is just the identity map, is continuous from [X → Y]H  to [X→ YH].

We can say a bit more:

Lemma. For any two dcpos X and Y, every continuous map f from Xto Yis Scott-continuous from X to Y.  (We already know the converse.)

Proof. The map f defines a continuous map from the topological modification of Xto the topological modification of YH.  Indeed, one checks easily that every continuous map in the sense of convergence spaces is also continuous in the topological sense, on the topological modifications.  So f is continuous from X with its Scott topology to Y with its Scott topology.  That implies that f is Scott-continuous (see Proposition 4.3.5 in the book, for example).  ☐

Hence [X → Y]H  and [X→ YH] have exactly the same elements, and since the identity map is continuous from [X → Y]H  to [X→ YH], the Heckmann convergence on [X → Y]is finer than the continuous convergence on [X→ YH].

The same can be said for the Scott convergence.  But this is a consequence of what we have just discovered about the Heckmann convergence.  Indeed, last time, we have seen that limS⊆ limHF for every filter F, and that means that Scott convergence is finer than Heckmann convergence.  Since Heckmann convergence is finer than the continuous convergence, certainly the same holds for Scott convergence.

Although I do not know whether Heckmann convergence coincides with continuous convergence on function spaces, we do know that Scott convergence does not coincide with continuous convergence in general.  Indeed, if it did, then it would also coincide with Heckmann convergence, and we have seen last time that this implies that [X → Y] is a continuous dcpo.  That fails in general even if we assume that X and Y are continuous dcpos.  (The canonical counterexample, which I would say is due to Achim Jung, is given by taking both X and Y equal to the dcpo of negative integers with the usual ordering.)

Conclusion

There is plenty of additional material in [1].  Notably, Heckmann convergence, which is called the cotopological convergence structure on a dcpo by Heckmann, is shown to have a number of intriguing duality properties with respect to the topological view of dcpos X as the topological space Xσ (with the Scott topology).

For example, he shows that for every dcpo X, and every topological space Y, [X→ Y] (as formed in Conv, and writing Y for its topological modification) is topological, and that continuous convergence coincides with pointwise convergence, namely that the convergence on [X→ Y] is convergence for the topology of pointwise convergence, which Heckmann calls the point-open topology: the coarsest topology such that f ↦ f(x) is continuous for every x in X [1, Corollary 43].

He also shows that for every topological space X, and every complete lattice Y (not just dcpo), [X → YH] is itself a complete lattice, and continuous convergence is Heckmann convergence [1, Theorem 33].

Finally, he shows that, for every complete lattice Y, YH is injective in Conv, generalizing the fact that the injective topological spaces are the continuous complete lattices.

  1. Reinhold Heckmann. A Non-Topological View of Dcpos as Convergence Spaces.
    Theoretical Computer ScienceVolume 305, Issues 1–3, 18 August 2003, Pages 159-186.

Jean Goubault-Larrecqjgl-2011