Well-filtered dcpos

I have just returned from the International Symposium on Domain Theory, which took place in Shijiazhuang, Hebei, China.  I met plenty of fine people there, some I knew, some I didn’t know.  First and foremost, Achim Jung, Xiaodong Jia and I took the same plane to Beijing, and then we traveled together.  Xiaodong helped us a lot through: I cannot think how I would have fared without him; thanks Xiaodong!

I have also met plenty of other people, as I just said, and by some stroke of luck, two of them found new results related to a very recent post: Xiaoyong Xi has just had a paper with Jimmie Lawson [1] where one learns that every complete lattice is well-filtered in its Scott topology (in particular).

Complete lattices, bounded-complete dcpos

The very recent post I just mentioned was about a result by A. Jung, X. Jia, and Q. Li [2], stating the following: let X be a well-filtered dcpo, then X is coherent if and only if ↑x ∩ ↑y is compact for any two points x and y.

As I’ve said last month, this raises the question which dcpos are well-filtered.  I must admit that I had the (yet unpublished) Xi-Lawson paper in mind when I said the following last month:

But what about other dcpos? For example, what about complete lattices? In that case ↑x ∩ ↑y = (x y) is trivially compact, but it was unknown until recently whether there were any non-coherent complete lattices in their Scott topology. (I have got some inside information about that… but I cannot speak about that yet.)

So now we know: all complete lattices are well-filtered and coherent in their Scott topology.

One can say a bit more.  A bounded-complete dcpo is one in which every family that has an upper bound has a least upper bound.  (The bc-domains considered in the book are the bounded-complete continuous dcpo.)  The results of [1] also imply that every bounded-complete dcpo is well-filtered.  In a bounded-complete dcpo, ↑x ∩ ↑y is either empty or of the form ↑z for some element z, and is compact in any case.  Hence the results of [2] imply that every bounded-complete dcpo is well-filtered and coherent.

As another application, consider the question of non-sober dcpos.  Johnstone’s dcpo J (Exercise 5.2.14 in the book) is non-sober (Exercise 8.2.14) and not well-filtered (Exercise 8.3.9).  Isbell gave a much more complicated example of a complete lattice that is not sober.  The above results show that, in spite of that, that lattice must be well-filtered.  In particular, well-filteredness does not imply sobriety in dcpos, solving a pretty long-standing open problem in the negative.

The mysterious property (*)

Xi and Lawson’s argument is a clever one.  I don’t know where they got the idea from.

Maybe one of the initial ideas could have been the following.  In a topological space, the closure cl(A) of a subset A is of course closed, in particular downwards-closed with respect to the specialization preorder.  Therefore ↓A is included in cl(A), and in general strictly so.

There are cases where ↓A coincides with cl(A), for example when A is a patch-closed subset of a stably compact space (Exercise 9.1.43 in the book).

The first observation Xi and Lawson make (rather, one of the last, actually: see their Proposition 3.1) is that this also happens for subsets A built as intersections of a compact saturated subset Q and a closed subset C (a prototypical instance of a patch-closed subset), provided the ambient space X is a dcpo with a strange property.

Write Xλ for X with its Lawson topology, the topology whose subbasis is given by Scott-open subsets and sets of the form ∁(↑x), x in X.  (The ∁ sign means complement.) The strange property is:

Property (*): for every x in X, ↑x is compact in Xλ.

(This is not a theorem, just a property we shall assume in some theorems, and which we shall be able to prove of certain spaces.)

All complete lattices, and more generally, all bounded-complete dcpos satisfy property (*).  Here is why.

Lemma. Every bounded-complete dcpo X is compact in its Lawson topology.

Proof. We use Alexander’s Subbase Lemma (Theorem 4.4.29 in the book).  Consider a cover of X by subbasic Scott-opens Ui, i ∈ I, and by sets ∁(↑xj), j J.  By Boolean reasoning, the intersection K of the sets ↑xj is included in the union U of the opens Ui.

If there is a finite subset J’ of J such that the points xj with j in J’ (not the whole of J) have no common upper bound, then the sets ∁(↑xj), j ∈ J’, form a finite subcover of X.

Otherwise, write xJ’ for the supremum of xj, jJ’ .  The family of points xJ’, where J’ ranges over the finite subsets of J, is directed.  Let x be its supremum.  Clearly, x is in ∩j Jxj, hence in U, hence in some open Ui.  Since Ui is Scott-open, so some xJ’ is in Ui.  Then Ui and the sets ∁(↑xj), j J’, form the desired finite subcover.  ☐

Corollary. Every bounded-complete dcpo satisfies Property (*).

Proof. For every x in X, ↑x is closed in Xλ by definition, hence compact by the previous lemma.  ☐

What property (*) implies, and the Trick

We come to the promised lemma. The proof will make use of the following fact (Proposition 4.4.9 of the book): for every filtered family of closed sets Ai, iI, which all intersect a given compact set K, the intersection ∩i ∈ I Ai must also intersect K.

Call that the Trick.

That is really a useful trick.  For example, given a filtered family of points (xi)i ∈ I in a compact subset K of a topological space X, taking Ai=↓xi shows that every such family has a lower bound in K.

That is not how we shall use the Trick, but we shall definitely use it, over and over!  Three times in the proof of the following Lemma, first on the Lawson topology, then on the Scott topology, finally on the Lawson topology again; and we shall again use it to prove another lemma below.

Lemma. Let X be a dcpo satisfying Property (*).  For every subset A of X of the form Q ∩ C, where Q is compact saturated (with respect to the Scott topology) and C is Scott-closed, ↓A is Scott-closed.

Proof.  We first prove the announced claim in the special case where Q=↑y for some point y.  In other words, we show that if A=↑y ∩ C then ↓A is Scott-closed.  Note that A is Lawson-closed, that is, it is closed in Xλ.  By Property (*) ↑y is compact in Xλ, and since C is closed in Xλ, A is Lawson-compact, namely, A is compact in Xλ. (See Corollary 4.4.10 of the book: the intersection of a compact set with a closed set is compact, in any topological space.)  Consider a directed family (xi)i ∈ I in ↓A, and let x be its supremum in X.  Then ↑x is the intersection of the filtered family of subsets ↑xi, iI, each of which is closed in Xλ.  By assumption, each of the sets ↑xi intersects A.  By the Trick, ↑x intersects A, showing that x is in ↓A.

We now deal with the general case: A = Q ∩ C, where Q is compact saturated (with respect to the Scott topology) and C is Scott-closed.  Consider a directed family (xi)i ∈ I in ↓A, and let x be its supremum in X.  Let Ai xi C.  The special case we have just examined shows that ↓Ai is Scott-closed.  They also form a filtered family, and each ↓Ai intersects Q (since xi is in ↓A, there is a point y above xi in A, namely both in Q and in C; then y is in Ai hence in ↓Ai).  Again we have a filtered family of closed sets that intersect a compact set Q, this time in the Scott topology.  By the Trick, their intersection must intersect Q as well.

We are not through yet.  We know there is a point z in the intersection: z is in Q, and for every iI, z is below some point zi in C above xi.  The set xi ∩ ↑z ∩ C is therefore non-empty (it contains zi), it is Lawson-closed, and it intersects the Lawson-compact set ↑z (that is Lawson-compact by Property (*)).  Moreover the family (xi ∩ ↑z ∩ C)i ∈ I is filtered, and its intersection is ↑x ∩ ↑z ∩ C.  We use the Trick a third and final time: ↑x ∩ ↑z ∩ C intersects ↑z.  This means that there is a point above x that is above z (hence in Q) and in C.  That point is above x and in A = Q ∩ C.  Therefore x is in ↓A.  ☐

The final step

So Property (*) on a dcpo X implies the even more mysterious property that, for every subset A of X of the form Q ∩ C, where Q is compact saturated and C is closed, ↓A is Scott-closed.  What this buys us is that X will be well-filtered—even though X may well be non-sober.

I will state that for dcpos again.  Xi and Lawson prove it for more general monotone convergence spaces (Proposition 2.4 in [1]), but it should be clear that the following argument, altough given for dcpos only, also works on arbitrary monotone convergence spaces.

Lemma. Let X be a dcpo with the property that for every subset A of X of the form Q ∩ C, where Q is compact saturated and C is closed, ↓A is closed.  Then X is well-filtered.

Proof. We assume that X is not well-filtered, and aim to find a contradiction.  Since X is not well-filtered, there is a filtered family (Qi)i ∈ I of compact saturated sets and an open set U such that ∩i ∈ I Qi is included in U but no Qi is included in U.  Equivalently, by letting C be the complement of U (C is a closed set), every Qi intersects C, but ∩i ∈ I Qi does not.

We fix (Qi)i ∈ I, but make C vary.  Let C be the family of closed sets C such that every Qi intersects C, but ∩i ∈ I Qi does not.  We have just observed that C is non-empty.

Order C by reverse inclusion ⊇.  We claim that C is a dcpo.  Indeed, let (Cj)j ∈ J be a directed family in C (hence a filtered family of closed sets, since the order is reversed), and let C be ∩j ∈ J Cj.  By the Trick, Qi intersects C, for every i ∈ I.  ∩i ∈ I Qi cannot intersect C, otherwise it would intersect Cj (for some arbitrary j in J).  Therefore C is in C.  This shows that C is a dcpo, where suprema are computed as intersections.

We can now use Zorn’s Lemma: every dcpo (being inductive) has a maximal element.  In other words, there is a maximal element C of C, or, explicitly, a minimal closed set C (with respect to inclusion) that intersects every Qi but does not intersect ∩i ∈ I Qi.

Since C intersects Qi (for any fixed i in I), C is in particular non-empty.  Again using Zorn’s Lemma, and since a closed subset of a dcpo is itself a dcpo, C contains a maximal element x.

Since C does not intersect ∩i ∈ I Qi, x cannot be in ∩i ∈ I Qi, so there is an index i0 in I such that x is not in Qi0.

At last we use our assumption: let A = Qi0C, then ↓A is closed.  Clearly ↓A is included in C, since every closed set is downwards-closed.  The element x cannot be in ↓A: otherwise there would be an element y in A = Qi0C above x; since x is maximal in C, y=x, so x would be in Qi0.  But x is in C, so the inclusion of ↓A in C is strict.

Since C is a maximal element of C (with respect to reverse inclusion), no closed subset strictly contained in C can be in C.  In other words, ↓A is not in C.

By definition of C, this means that ↓A intersects ∩i ∈ I Qi or that ↓A does not intersect some Qi.  The first case is impossible since ↓A is included in C, which does not intersect ∩i ∈ I Qi.  So ↓A must fail to intersect some Qi.

In other words, (Qi0C) ∩ Qi is empty.  Equivalently, (Qi0Qi) ∩ C is empty.  Now recall that the family (Qi)i ∈ I is filtered, so there is an index k in I such that Qk is included in Qi0Qi.  That implies that QkC is empty.  But C is in C, so C intersects every Qi: contradiction.  ☐

Putting everything together, we obtain:

Proposition. Every dcpo satisfying property (*) (e.g., every complete lattice, every bounded-complete dcpo) is well-filtered.

That is a pretty remarkable result.  I hope this convinced you to read [1]: the authors also examine questions of patch-compactness and Lawson-compactness of dcpos there, which I’ll let you discover by yourselves.  They are really immediate consequences of the previous results.

 

Jean Goubault-Larrecqjgl-2011

 

  1. Jimmie Lawson and Xiaoyong Xi. On well-filtered spaces and ordered sets. Topology and its Applications 228(1), September 2017, pages 139-144.
  2. Xiaodong Jia, Achim Jung, and Qingguo Li. A note on the coherence of dcpos.
    Topology and its Applications, Volume 209, 15 August 2016, Pages 235–238.
  3. John Isbell. Completion of a construction of Johnstone. Proceedings of the AMS 85, 1982, pages 333-334.