Every dcpo can be seen as a topological space, once we equip it with the Scott topology. And every topological space can be seen as a convergence space, so every dcpo can be seen as a convergence space. Reinhold Heckmann observed that we could see dcpos as convergence spaces in another way [1], with some serendipitous properties. We shall see what serendipitous properties next time. This month, we shall prepare the grounds for that piece of work, by investigating various convergences that can be put on dcpos.
I should say that, as I was writing this, I realized that extensions of those constructions are now being actively researched by Hadrian Andradi and Weng Kin Ho: see H. Andradi’s arXiv reports. I won’t discuss what they do here, but you may be interested.
Convergence spaces
In previous posts, I called convergence spaces filter spaces, following Hyland, but I now prefer to use the term “convergence space”, as in the standard reference [2]. What I used to call convergence spaces are nowadays called limit spaces.
A convergence space is a set X together with a relation → between filters F of subsets and points x, satisfying the following two axioms:
- (x) → x, where (x) is the filter of all subsets of X that contain x (this is called the principal ultrafilter at x; the standard notation is x with a dot, but I don’t know how to typeset that in a blog)
- If F → x and F’ is a filter of subsets that contains F, then F’ → x.
Alternatively, we may specify → by instead positing an operator lim : FP(X) → P(X) that sends every filter of subsets to the set of its limits. (P(X) is the powerset of X, and FP(X) is the set of all filters of subsets of X. Both are ordered by inclusion.) We may restate the above axioms as:
- x ∈ lim (x), and
- lim is monotonic.
A limit space additionally satisfies the following axiom: lim preserves binary intersections. A pretopological space additionally satisfies: lim preserves all intersections.
For every topological space X, its associated notion of convergence is given by: lim F is the set of points x such that Nx is included in in F, where Nx is the set of neighborhoods of x. This way, every topological space is pretopological—but the converse fails.
Note that, on a topological space X, lim F = {x ∈ X | ∀ U ∈ OX, x∈U ⇒ U∈F} is the complement of {x ∈ X | ∃ U ∈ OX, x∈U and U∉F}. The latter is the union of all the open sets that fail to be in F. Hence lim F is the intersection of all the closed sets C such that X—C∉F. Alternatively, this is the smallest closed set whose complement is not in F.
Conversely, any notion of convergence gives rise to a notion of open set: U is said to be open if and only if for every filter of subsets F, for every point x in lim F, if x is in U then U is in F. In other words, an open set is a set U that belongs to every filter F such that lim F intersects U. The collection of open sets obtained that way is a topology, the so-called topological modification of the convergence space X.
Given a topology on a set X, the topological modification of the notion of convergence on X is the original topology. However, given a convergence space, the notion of convergence obtained from its topological modification will not in general be the original convergence: we lose some information by passing to topological modifications.
Topological convergence on dcpos
The traditional topology on a dcpo X, in fact on a poset X when looked from a domain-theoretical angle, is the Scott topology. That determines a notion of convergence that we shall call topological convergence. Let us write limT for it.
That is usually defined on nets, see [3], Section II.1. On filters, we merely follow the recipe given above for topological spaces: for every filter of subsets F, limT F is the smallest Scott-closed set whose complement is not in F.
There are many other notions of convergence on dcpos, and we shall say that a notion of convergence is admissible if its topological modification is the Scott topology.
In addition to topological convergence limT, we willl investigate at least Scott convergence and Heckmann convergence.
Scott convergence
Scott had introduced a notion of convergence on complete lattices, whereby a net (xi)i∈I, ⊑ converges to x if and only if x is below the liminf of the net, supi∈I infj⊒i xj. Beware that this is not convergence in the Scott topology (but its topological modification is the Scott topology).
On dcpos, that generalizes to: (xi)i∈I, ⊑ converges to x if and only if there is a directed family D whose supremum is above x, and such that for each element d of D, d is below xi for i large enough. One may instead use ideals instead of directed families, as ideals are exactly the downward closures of directed families.
Weck [5] gave the corresponding definition of Scott convergence in terms of filters. Erné generalized that to the case of posets, not just dcpos [4]. To make it clear, our notion of Scott convergence is his notion of s2-convergence, which relies on ideals. (The other choices use Frink ideals instead of ideals, and ideals with a supremum instead of all ideals. The latter choice does not make any difference in dcpos.)
Let us call Scott convergence the resulting notion of convergence. That is given as follows: a filter of subsets F Scott-converges to x if and only if there is an ideal I such that x≤sup I and such that for every element z of I, ↑z is in F. We write limS F for the set of points that F Scott-converges to.
Lemma 1. For every filter of subsets F, limS F ⊆ limT F.
Proof. Every point x of limS F is in limT F. Indeed, let I be an ideal as given above. For every Scott-open neighborhood U of x, I intersects U, say at z. By definition, ↑z is in F. Hence the larger set U is also in F. ☐
Lemma 2. limS is admissible.
Proof. It is a general fact that lim ⊆ lim’ implies that all lim’-open sets are lim-open. (Exercise!) Using Lemma 1, and the fact that the limT-open subsets are the open subsets of the original (Scott) topology, every Scott-open subset is limS-open. Conversely, let U be limS-open. That means that U is in every filter of subsets F such that limS F intersects U. Then:
- U is upwards-closed: if x≤y and x in U, let F be the filter of all sets that contain y. One checks that limS F = ↓y, hence intersects U. So U is in F, and that means that U contains y.
- U is Scott-open: let D=(xi)i∈I be a directed set, with supremum x in U, and assume that no xi is in U. Let F be the filter of all sets that contain some xi. Then x is in limS F, as one sees by taking I=↓D. Since U be limS-open, U is in F, and that means that some xi is in F. ☐
The converse of Lemma 1 fails in general, meaning that limS and limT and in general two different notions of convergence with the same topological modification. This is because of the following theorem, whose net-theoretical counterpart can be found in [3, Theorem II-1.9]. In particular, any non-continuous dcpo will provide a counterexample.
Theorem. For a dcpo X, limS=limT if and only if X is continuous.
Proof. Assume X continuous. We show that limS=limT by contradiction. Imagine there were a point x of X, and a filter of subsets F such that x is in limT F but not in limS F. For every ideal I such that x≤sup I, there is an element z of I such that ↑z is not in F. We consider the ideal I of all elements way-below x. This is an ideal and x≤sup I precisely because X is continuous. We obtain that there is a z≪x such that ↑z is not in F. Hence the smaller set ↟z is not in F either. However, ↟z is a Scott-open neighborhood of x, hence must be in F since x is in limT F: contradiction.
In the converse direction, assume that limS=limT. Fix a point x of X. Let F be the filter Nx of all neighborhoods U of x in the Scott topology. Then x is in limT F, hence in limS F. By definition, there is an ideal I such that x≤sup I and ↑z is in F for every z in I. Now ↑z is in F means that ↑z is a neighborhood of x, namely contains a Scott-open neighborhood of x; in turn, that implies that z is way-below x. Hence I is an ideal of elements way-below x. In passing, that implies that sup I≤x, hence x=sup I. Hence X is continuous. ☐
Note also that limS is topological (equal to the notion of convergence of its topological modification) if and only if limS=limT, if and only if X is continuous. Hence limS is not topological in general. In fact, it is not even a limitierung in the sense of Weck [5], i.e., X with Scott convergence is not even a limit space, unless X is meet-continuous.
Heckmann convergence
Heckmann uses another notion of convergence [1, Definition 18]. Here is how it is defined. For every subset A of X, let us write A↓ for the set of lower bounds of A (i.e., of points that are below every point of A). If A⊆B, then A↓ contains B↓. Hence given any filter of subsets F, the family {A↓ | A ∈ F} of downwards-closed subsets A↓ when A ranges over F is directed.
Heckmann defines his notion of convergence by:
Definition. limH F = cl (∪ {A↓ | A ∈ F}).
It is interesting to relate this definition to that of Scott convergence. As we shall see, the two notions are very close.
To that end, let us define the adherence adh B of a subset B as the set of points x such that x≤sup D for some directed family D included in B. Clearly, adh B ⊆ cl (B). In general, the inclusion is proper, and cl (B) is obtained by iterating adherences, possibly transfinitely. (Formally, cl (B) is the least fixed point of the adherence operator containing B.)
However, in a continuous dcpo, adh B = cl (B) for every downwards-closed subset B. Indeed, consider any point x of cl (B) outside adh B, and let D=↡x. Since x is not in adh B, and x≤sup D, D cannot be included in B. Let y in D (namely, y≪x) be outside B. Since B is downwards-closed, ↟y does not intersect B, and being open, it does not intersect cl (B) either: contradiction, since x is both in ↟y and in cl (B).
Lemma 3. For every filter of subsets F, ∪ {A↓ | A ∈ F} is also the union of all ideals I such that for every element z of I, ↑z is in F. Hence limS F = adh (∪ {A↓ | A ∈ F}).
Proof. Let x belong to some ideal I such that for every element z of I, ↑z is in F. Note that (↑z)↓ = ↓z, so x is in A↓ where A=↑x is in F. Conversely, let x belong to some A↓ with A ∈ F. Let I be the ideal ↓x. For every z in I, z is below x, which is a lower bound of A, so z is also a lower bound of A. It follows that A is included in ↑z, so ↑z is in F. Moreover, x is clearly in I. That proves the first part of the lemma. The second part follows immediately. ☐
We refine Lemma 1 as follows.
Lemma 4. For every filter of subsets F, limS F ⊆ limH F ⊆ limT F.
Proof. limS F ⊆ limH F using Lemma 3, since adherence is included in closure. We must then show that every point x of limH F is in limT F. Consider an open neighborhood U of x. Since U intersects limH F = cl (∪ {A↓ | A ∈ F}) (at x), U must also intersect ∪ {A↓ | A ∈ F}. So U must contain a lower bound z of some A ∈ F. Then U must contain ↑z, which contains A. It follows that U is in F, which shows that x is in limT F. ☐
Lemma 5. limH is admissible.
Proof. Recall that lim⊆lim’ implies that all lim’-open subsets are lim-open. By Lemma 4, the topological modification of limH is therefore sandwiched between those of limT and of limS—which are both equal to the Scott topology, by Lemma 2. ☐
As a variant of our previous theorem, we have the following which is (of course) due to Heckmann [1, Theorem 25].
Theorem. For a dcpo X, limH=limT if and only if X is continuous.
Proof. If X continuous, then limS=limT by our previous theorem, hence limH=limT by Lemma 4.
In the converse direction, assume that limH=limT. Fix a point x of X. Let F be the filter Nx of all neighborhoods U of x in the Scott topology. Then x is in limT F, hence in limH F. For every open neighborhood U of x, U intersects limH F = cl (∪ {A↓ | A ∈ F}) (at x), hence also ∪ {A↓ | A ∈ F}. By Lemma 3, U must then intersect some ideal I such that for every element z of I, ↑z is in F. In particular, there is a point z in U such that ↑z is in F, namely such that ↑z is a neighborhood of x, and, as in the proof of the previous theorem, that implies z≪x.
Consider the family D of points z such that ↑z is a neighborhood of x. That is non-empty, by the argument we have just seen with U=X. D is directed: for all z’, z” in D, the interiors int (↑z’) and int (↑z”) both contain x, so U=int (↑z’) ∩ int (↑z”) is an open neighborhood of x; applying the argument we have just seen, there is a point z in U such that ↑z is a neighborhood of x, namely such that z is in D. We also know that every element of D is way-below x. Since the intersection of all open neighborhoods of x is ↑x, and each contains some ↑z with z in D, the intersection of all sets ↑z with z in D is included in ↑x, hence equal to it. It follows that x=sup D. This exhibits x as the supremum of a directed family of elements way-below x, so X is continuous. ☐
As for limS, limH is topological if and only if limH=limT, if and only if X is continuous. Hence limH is not topological in general.
- Reinhold Heckmann. A Non-Topological View of Dcpos as Convergence Spaces.
Theoretical Computer ScienceVolume 305, Issues 1–3, 18 August 2003, Pages 159-186. - Szymon Dolecki and Frédéric Mynard. Convergence foundations of topology. World scientific, July 2016, 568 pages.
- Gerhard Gierz, Karl Heinrich Hofmann, Klaus Keimel, Jimmie D. Lawson, Michael W. Mislove, and Dana S. Scott. Continuous Lattices and Domains. Number 93 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2003.
- Marcel Erné. Scott convergence and Scott topology in partially ordered sets ii. In Continuous Lattices, volume 871, pages 61–96. Springer-Verlag Berlin, Heidelberg, New York, 1981.
- S. Weck. Scott convergence and Scott topology in partially ordered sets I, in: B. Banaschewski, R.-E. Homann (Eds.), Continuous Lattices, Proc. Conf. Bremen, 1979, Lecture Notes in Mathematics, volume 871, Springer, Berlin, 1981, pages 372–383.
— Jean Goubault-Larrecq (May 21st, 2018)