Chains and nested spaces

nested space is any topological space in which the lattice of open sets is totally ordered.  My purpose this month is to show that this concept, which perhaps looks strange at first:

  • is related to the familiar concept of a chain (a totally ordered set) in order theory, and that chains and nested spaces have very strong topological properties;
  • is related to the notion of minimal Tand TD topologies, a concept first introduced by Larson [1].

I will start with a nifty, and perhaps surprising, observation about chains.

A nifty observation about chains

A chain is a totally ordered set. Can you find one that is not continuous, as a poset? Well, do not think too much. There is none. If I remember well, the following was told to me by Xiaodong Jia.

Proposition A. Let P be a chain, and < be its strictly smaller than relation. Then: (i) if x<y then xy; (ii) P is a continuous poset.

Proof. (i) Let D be any directed family with a supremum sup D such that y≤sup D. (Note that “directed” is almost entirely irrelevant, here, by the way: every non-empty family in P is automatically directed.) We claim that xd for some element d of D. What would happen if that were not the case? Well, using the totality of ≤, for every d in D, we would have d<x, in particular dx. Then sup Dx, which is impossible since x<y≤sup D.

(ii) Let x be any point of P. If x is finite, namely if xx, then {x} is a directed family of elements way-below x whose supremum is x. Otherwise, x is not finite, so by definition there is a directed family D with a supremum, such that x≤sup D, but for every d in D, it is not the case that xd. Using totality, for every d in Dd<x. By (i), for every d in Ddx, so D is a family of elements way-below xD is also directed, since in a chain every non-empty set is directed. It remains to note that sup D=x. Since d<x for every d in D, we have sup Dx, and we already know that x≤sup D. ☐

If P is not only a chain, but also a pointed dcpo, then we have even more.  Remember that a poset is pointed if and only if it has a least element ⊥.  First, every family at all has a supremum: if that family is empty, then the supremum is ⊥, otherwise the family is directed… because P is a chain.  Hence P is a complete lattice.

Let me also recall that, for any two points x and y of a complete lattice Px is way-way-below y (in notation, xy), if and only if for every family D (not necessarily directed) such that y≤sup D, some element of D is already above x.  A complete lattice is prime-continuous if and only if every element is the supremum of the elements way-way-below x.  And Raney’s theorem (Exercise 8.3.16 in the book) states that a complete lattice is prime-continuous if and only if it is completely distributive.

If P is a chain and a pointed dcpo, we have xy if and only if xy and y≠⊥ (the latter is dictated by the case where D is empty).  Every element different from ⊥ is then the (directed) supremum of a family of elements way-below (hence way-way-below) itself, by Proposition A.  And ⊥ itself is the supremum of the empty family.  Hence we obtain the following.

Corollary B.  Every chain that is also a pointed dcpo is a completely distributive complete lattice.  ☐

Nested spaces

Can we find a topological analogue of the notion of a chain? Surely yes. That is the notion of a nested space: a space X whose lattice of open sets is a chain, in other words, such that given any two open sets U and V, one of them is included in the other.

That may seem like a strange condition, but look: every chain is nested in its Scott topology (and also, in its Alexandroff topology, and in its upper topology).

If X is a nested space, then OX is a chain, hence is a continuous complete lattice. We know that the spaces whose lattices of open sets are continuous (Definition 5.2.3) are exactly the core-compact spaces, so every nested space is core-compact.

But we can say much more.  OX is not only a chain, but also a pointed dcpo, so Corollary B applies: OX is a completely distributive complete lattice.  This suggests that X is a c-space, as suggested by Lemma 8.3.42 of the book… which however requires X to be sober.  We confirm this intuition, and give a direct proof of it.

Proposition C. Every nested space is a c-space.

Let me recall that a c-space is a space in which for every point x, for every open neighborhood U of x, one can find a point y such that x ∈ int(↑y) ⊆ ↑y ⊆ U. Being a c-space is a much stronger condition than being core-compact.

Proof.  Let X be a nested space, and let ≤ be its specialization preordering. We first claim that ≤ is total, namely that for any pair of points xy, we have xy or yx. Let us imagine that xy. Then there is an open neighborhood U of x that does not contain y. For every open neighborhood V of y, we cannot have V ⊆ U, since that would force U to contain y. By nestedness, U is included in V. Since U contains xV must also contain x. This shows that yx.

Next, we claim that for every point y, the set ↑< y of all the points x such that y<x is open. Oh, I write y<x for “yx and xy“. Since ≤ is a preordering, not necessarily an ordering, this is not equivalent to “yx and xy“. However, since ≤ is total, y<x actually simplifies to “xy“. Therefore ↑< y is just the complement of ↓y, which is the closure of {y}, so indeed ↑< y is open.

As a third point, we make a detour through the following situation. Let us imagine an open subset U of X with a minimal point x. By minimal, I mean that x is in U, but all the points y<x are outside U. I claim that, in this case, U=↑x. That ↑x is included in U is clear, since U is upwards-closed. In the converse direction, any point y in U that is not in ↑x satisfies y<x, since ≤ is total, and this is impossible.

We can now show that X is a c-space. Let x be a point of X, and U be an open neighborhood of x. If x is minimal in U, then we have seen that U=↑x. Hence, taking y=x, we obtain x ∈ int(↑y) ⊆ ↑y ⊆ U rather vacuously. Otherwise, there is a point y<x in U. Then x is in ↑< y, which is open, as we have seen earlier, hence included in int(↑y). Finally, ↑y ⊆ U since y is in U. ☐

I have said that every chain is a nested space in its Scott, Alexandroff, or upper topology.  We can say something much more precise than that!  The following is Lemma 2 of [1], up to some rephrasing.

Lemma D. Let X be a Tspace.  X is nested if and only if X is a chain in its specialization ordering.

Proof. Assume that X is not a chain in its specialization ordering.  Then it has two incomparable points, x and y.  From x≰y we deduce that there is an open set U that contains x but not y.  Symmetrically, there is an open set V that contains y but not x.  Then U is not included in V, since x is in U but not in V, and V is not included in U, since y is in V but not in U.

Conversely, assume that X is not nested.  It has two incomparable open subsets U and V.  Since U is not included in V, there is a point x in U that is not in V.  Symmetrically, there is a point y in V that is not in U.  Since x is in U and y is not in Ux≰y.  Since y is in V, and x is not in Vyx. ☐

Minimal T0 topologies

If you start from an ordering ≤ on a set P, it is a standard result, due to Szpilrajn [2], that (the graph of) ≤ is included in (the graph of) some total ordering ⪯. In other words, ≤ has a linearization. In computer science, ⪯ is known as a topological sort of ≤.  (Apparently, Szpilrajn remarked that Banach, Kuratowski, and Tarski already knew of the result, although none published it.)

The proof of this fact is an application of Zorn’s Lemma. The family of all orderings that contain ≤ is a dcpo, hence an inductive poset, under inclusion. And every maximal ordering in that dcpo must be a total ordering.  In order to prove the latter, given any ordering ≤’ for which x and y are incomparable points, we can build a new ordering ≤’’  by z ≤’’ t if and only z ≤’ t or (z ≤’ x and y ≤’ t), and ≤’’ is strictly larger than ≤’. If ≤’ is maximal, then the existence of two incomparable points for ≤’ would then lead to a contradiction.

The topological analogue is the notion of a coarsest Ttopology, usually called a minimal T0 topology. Indeed, if you remove some open sets, then the specialization ordering (not preordering: this is why we only consider T0 topologies) grows under inclusion.

The notion of a minimal Ttopology was first studied by R. E. Larson [1], as far as I know.  He also studied minimal TD topologies, which we will do next.

I will proceed differently from Larson, in order to show the connection with linearizations of orderings (and I will mention Larson’s simpler argument later).  The following is Theorem 1 of [1], more or less.  Let me recall that the upper topology of an ordering ≤ is the coarsest topology such that ↓x is closed for every point x.  Explicitly, its closed sets are intersections of sets of the form ↓EE finite and non-empty.  (If ≤ is total, then every such set ↓E can be written as ↓x for a unique point x.)  The upper topology of ≤ is the coarsest topology that has ≤ as specialization (pre)ordering (see Proposition 4.2.12 in the book).

Proposition E.  The minimal Ttopologies on any fixed set X are exactly the upper topologies of total orderings on X.

Proof.  Let τ’ be a minimal Ttopology on X.  The upper topology of its specialization ordering ≤’ is even coarser.  Minimality then implies that τ’ is the upper topology of ≤’.

Now let us imagine that ≤’ is not a total ordering.  We have two points x and y of X such that y ≰’ x and x ≰’ y.  As in the proof of Szpilrajn’s theorem, we build a new ordering ≤’’  by z ≤’’ t if and only z ≤’ t or (z ≤’ x and y ≤’ t); then ≤’’ is strictly larger than ≤’.  The downward closure ↓’’of any point t with respect to ≤’’  is equal to its downward closure ↓’with respect to ≤’ if y ≰’ t, and to ↓’ ∪ ↓’x if y ≤’ t.  In particular, whichever the case is, ↓’’t is always closed in the upper topology of ≤’, namely in τ’.  This shows that the upper topology of ≤’’ is coarser than τ’.  By minimality, those two topologies are equal.  In particular, their specialization orderings coincide, namely ≤’’ and ≤’ coincide: but this is impossible, since ≤’’ is strictly larger than ≤’.

Therefore ≤’ is a chain.  This shows that any minimal Ttopology τ’ is indeed the upper topology of some total ordering ≤’.

Conversely, let ≤’ be any total ordering, and τ’ be its upper topology.  Let us imagine that there is a coarser Ttopology τ’’.  Its specialization ordering ≤’’ must contain ≤’.  But any total ordering is maximal with respect to inclusion (among ordering relations, not preordering relations).  Therefore ≤’’ is equal to ≤’.  Then, the upper topology of ≤’ is the coarsest topology whose specialization ordering is ≤’, so τ’ is coarser than τ’’.  It follows that τ’=τ’’.  This allows us to assert that τ’ is minimal T.  ☐

One would expect to obtain an analogue of Szpilrajn’s theorem, typically that every Ttopology on a fixed set X is finer than some minimal Ttopology.  However, that is wrong.  This is explained in the second part of Example 6 of [1].  Let me make that explicit.

Counterexample F.  The cofinite topology on the real line R is not finer than any minimal Ttopology.

Proof.  Imagine there were such a minimal Ttopology τ.  It is the upper topology of some total ordering ≤.  Let us write ↓x for the downward closure of x with respect to ≤.  Since τ is coarser than the cofinite topology, ↓x must be either finite or the whole of R, for each real number x.  Let us define #x as the cardinality of ↓x.  If xy then #x≤#y (with the usual ordering on N ∪ {∞}), and if x<y then #x is strictly smaller than #y.  In particular, the map x ↦ #x is an injective map from R to N ∪ {∞}.  That is impossible, since R is uncountable.  ☐

In Counterexample F, of course the cofinite topology is T0: it is even T1.  (In fact, on any set, the cofinite topology is the minimal Ttopology.)

Minimal TD topologies

Larson also studied minimal TD topologies.  I have talked about TD topologies last time [3].  Those are the topologies in which ↓x–{x} is closed for every point x.  Every such topology is T0.  The Alexandroff topology of any partial ordering is TD.

Larson proved that a TD topology is minimal TD, that is, it is TD and no strictly coarser topology is TD, if only if it is nested [1, Theorem 2].  We can say more: they are all Alexandroff topologies.

Proposition E’.  The minimal TD topologies on any fixed set X are exactly the Alexandroff topologies of total orderings on X.

Proof. We reuse Larson’s construction.  Given any topology τ on X, and any open subset U in τ, let τ* be {V ∈ τ | V ⊆ U or U ⊆ V}.  It is easy to see that τ* is a topology, and that it is coarser than τ.  Let C be the complement of U.  Then the τ*-closed sets are the τ-closed sets D such that D ⊆ C or C ⊆ D.  It follows that the τ*-closure ↓*of any point x is its τ-closure ↓x if x ∈ C, otherwise it is C ∪ ↓x.

In particular, if τ is TD, then so is τ*: if x ∈ C, then ↓*x–{x}=↓x–{x} is τ-closed and included in C, hence τ*-closed; otherwise, ↓*x–{x}=C ∪ (↓x–{x}), which is τ-closed and contains C, hence is also τ*-closed.  (One can also show that if τ is T0, then so is τ*, and this is how Larson proves Proposition E.)

If τ is minimal TD, then τ* cannot be strictly coarser than τ, so τ*=τ.  This means that for every V ∈ τ, V ⊆ U or U ⊆ V.  Since U is arbitrary, τ is nested.

Finally, we show that τ is the Alexandroff topology of its specialization ordering ≤.  By Lemma D, ≤ is total.  Hence the upward closure ↑x of any point x is also equal to the complement of ↓x–{x}, which is τ-closed.  In other words, ↑x is open.  Since every upward-closed set A is a union of sets of the form ↑x, x ∈ A, it is open.   ☐

The argument of Counterexample F immediately leads to the following similar counterexample, showing that again there is no analogue of Szpilrajn’s theorem in the class of TD topologies.

Counterexample F’.  The cofinite topology on the real line R is not finer than any minimal TD topology.   ☐

We note that the cofinite topology, by the way, is TD, because Timplies TD.

Counterexamples F and F’ are pretty depressing observations: they show that there is no topological generalization of Szpilrajn’s (order-theoretic) theorem.

I cannot finish on such a sad note, so let me mention a remarkable application of Corollary B.

Mislove’s observation

A continuous valuation is an analogue of a measure. Formally, a valuation ν on a topological space X is a map from the lattice OX of open subsets of X to R+ (the dcpo of non-negative real numbers, plus ∞) that is monotonic, strict (ν(∅)=0), and modular (ν(U)+ν(V)=ν(U ∪ V)+ν(U ∩ V)). A continuous valuation is a valuation that is Scott-continuous.

The set VX can be ordered by the stochastic ordering, whereby μ≤ν if and only if μ(U)ν(U) for every U ∈ OX.  With that ordering, VX is a pointed dcpo, and Claire Jones proved that it is a continuous dcpo if X is a continuous dcpo.  But VX is not a complete lattice, and not a bc-domain, except in some specific cases: see [4] for some of the best results we know in this area, still today.  (There were some others, including some that I am the author of, but this is not the topic I want to develop.)

Pretty recently, Mike Mislove proved that VP is a continuous complete lattice in case P is a chain, in its Scott topology [5], with applications to a domain-theoretic approach to Skorokhod’s theorem.  Proposition A (or Corollary B) allows us to give a simple proof of this fact, and actually the following slight generalization.

Theorem. For every nested space X, the space VX of continuous valuations on X is a continuous, complete lattice.

Proof. We observe that any Scott-continuous map from OX to R+ is modular. Hence VX can be equated with the dcpo of all the strict Scott-continuous maps from OX to R+. Now we notice that OX is a chain, hence is a continuous poset by Proposition A; it is also a complete lattice.  (Or: it is a chain and a pointed dcpo, hence a completely distributive complete lattice by Corollary B; in particular, a continuous, complete lattice again.)  Now, both OX and R+ are objects in the Cartesian-closed category of continuous complete lattices (Exercise 5.7.17 in the book), so the dcpo [OX → R+] is also a continuous complete lattice. The subdcpo of those maps that are strict is closed under arbitrary suprema, and downwards-closed, and from that it is easy to deduce that it is also a continuous complete lattice. ☐

  1. Roland Edwin Larson.  Minimal T0 spaces and minimal TD spaces. Pacific Journal of Mathematics 31(2), 1969, pages 451-458.
  2. Edward Szpilrajn.  Sur l’extension de l’ordre partiel.  Fundamenta Mathematicae 16, pages 386–389, 1930.
  3. Charles Edward Aull and Wolfgang Joseph Thron. Separation axioms between T0 and T1. Indagationes Mathematicae 23, pages 26-37, 1962.
  4. Achim Jung and Regina Tix. The Troublesome Probabilistic Powerdomain. In A. Edalat, A. Jung, K. Keimel, and M. Kwiatkowska, editors, Proceedings of the Third Workshop on Computation and Approximation, volume 13 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers B.V., 1998. 23 pages.
  5. Michael W. Mislove. Domains and stochastic processes. Theoretical Computer Science, 807, pages 284–297, 2020. Available on arXiv.
jgl-2011

Jean Goubault-Larrecq (August 23rd, 2020)