On countability

Everyone has its own prejudices.  One of mine is that countability assumptions are usually superfluous.  E.g., instead of defining convergence with sequences, and then realizing that closed sets can only be characterized by sequences in first-countable spaces, it is better to define convergence using nets, or using filters—that works in every space.

However, there are some places in mathematics where you really need countability assumptions, and some of them are somehow unexpected.

The expected places

You would expect countability to be important in questions related to ℚ or ℝ.  Metric spaces are first-countable, and that is because metrics take their values in ℝ+ ∪ {∞}.  Measures, which also take their values in ℝ+ ∪ {∞}, are σ-additive, i.e., they map countable disjoint unions to sums, for some pretty good reasons, too, related to the existence of non-measurable sets, and results such as the monotone convergence theorem, which applies to countable sequences of maps to be integrated.

But there are some places where countability is important, and neither ℚ or ℝ is involved.

Projective limits

I have spent quite some time on projective limits already.  Remember: the projective limit of a projective system of non-empty topological spaces may be empty.  It is non-empty if all the spaces involved are compact and sober—this is part II of my previous series posts on Steenrod’s Theorem—or if the system has a cofinal countable subsystem.  And we have seen one counterexample, which indeed has no cofinal countable subsystem.

Note that countability is not required.  What is required is countability or the fact that all spaces are compact and sober.  All the examples that we shall see will be of this form: we will need either a pretty strong topological condition (here, compactness and sobriety), or a countability condition.

The Plotkin powerdomain

The Plotkin powerdomain was introduced so as to give semantics to non-deterministic choice in semantics.  I will not describe what this is, because this is a pretty complicated subject (see Section 6.2.1 of [1]), and I will describe a better example, where countability makes wonders, in the next section.

Let me just say that this is one of the first examples I saw where countability (or coherence) was required.  To wit, Theorem 6.2.19 of [1] states that the Plotkin powerdomain of a continuous dcpo X, which is defined there as a certain continuous dcpo (by construction, as the rounded ideal completion of an abstract basis), is isomorphic to a space of so-called lenses over X, provided that X is ω-continuous, not just continuous.  This is where the countability condition comes into play.

Again, countability is not really needed.  Instead, if X is not only a continuous dcpo, but also a coherent one, then the Plotkin powerdomain is also isomorphic to the space of lenses (Theorem 6.2.22 of [1]; see also Proposition 4.45 of [3], and its corrigendum, for a complete proof that the space of lenses is a continuous dcpo in this case).  If we do not wish to require coherence, countability in the form of ω-continuity is necessary, as the pretty sophisticated construction of Exercise 6.2.23(11) of [1] shows.

The Smyth powerdomain

The Smyth powerdomain Q(X) is the set of compact saturated subsets of X.  (Usually the empty set is excluded.  I will not do this.)  It can be equipped with either one of two classical topologies:

  • the upper Vietoris topology, whose subbasic open sets ☐U, where U is open in X, are defined as {Q ∈ Q(X) | Q ⊆ U} (those are even basic open sets, since ☐U ∩ ☐V= ☐(U ∩ V)); its specialization ordering is reverse inclusion ⊇;
  • the Scott topology of reverse inclusion ⊇.

It is easy to see that every set ☐U, where U is open in X, is Scott-open in Q(X), provided that X is well-filtered.  Hence the Scott topology is finer than the upper Vietoris topology.

The following properties are stated in Proposition 8.3.25 of the book:

  • If X is well-filtered, then Q(X) under reverse inclusion is a dcpo, where directed suprema are intersections.
  • If X is well-filtered and locally compact (equivalently, sober and locally compact), then Q(X) is a continuous dcpo, and QQ’ if and only if the interior of Q contains Q’.

It follows that, if X is well-filtered and locally compact, then the upper Vietoris and the Scott topologies coincide on Q(X).  Indeed, a base of the Scott topology is given by the sets ↟Q, and those are equal to ☐int(Q).

The following result, due to de Brecht and Kawai [2, Proposition 6], is a remarkable example which shows that second countability can be taken as an alternative to local compactness.

(Note added on April 1, 2019: Matthew de Brecht told me that it should be fair to mention Matthias Schröder’s work, from which he claims to have taken some of the techniques.  Indeed, the argument that K’n is compact in the proof below is similar to one found in Proposition 2.3 of [4].)

Proposition (de Brecht, Kawai)   If X is well-filtered and second countable, then the upper Vietoris and Scott topologies coincide on Q(X).

De Brecht and Kawai’s argument is a clever one, and I feel it should be described slowly, and in detail.  They require X to be sober, but well-filteredness is enough.  In fact we only need well-filteredness to make sure that the Scott topology is finer than the upper Vietoris topology, and we will only use second countability in the rest of this post.

Proof. We reason by contradiction, and we assume that there is a Scott-open subset H of Q(X) which is not upper Vietoris open. This implies that there is an element K of H which has no upper Vietoris open neighborhood ☐U included in H.  Indeed, otherwise every element K of H would have an upper Vietoris open neighborhood ☐UK included in H, and the union of the sets ☐UK would be equal to H and upper Vietoris open.

Because X is second countable, we claim that K has a countable base of open neighborhoods in X.  In other words, there is a countable family F of open neighborhoods Un, nN, of K in X such that every open neighborhood U of K contains some Un.  This is built as follows.  Let (Vn)nN be a countable base of the topology of X.  The family F consists of all the finite unions of sets Vthat cover K.  We check that every open neighborhood U of K contains some element of FU is a union of sets Vn, and since K is compact, we can extract a finite subcover, whose union is then in F and included in U.

Furthermore, by replacing each Un with U∩ U∩ … ∩ Un, we may assume that U⊇ U⊇ … ⊇ Un.

Using that countable base F=(Un)nN  of open neighborhoods of K, we build a sequence of elements Kn, nN, of elements of Q(X) as follows.  Recall that K has no upper Vietoris open neighborhood ☐U included in H.  In particular, ☐Un, which is an upper Vietoris open neighborhood of K, is not included in H.  We can therefore find an element Kn of Q(X), included in Un, but not in H.  By replacing Kn by K ∪ Kn, which is still included in Un, and still not in H (since H is upwards-closed in the reverse inclusion ordering), we can also assume that every Kn contains K.

The sequence (Kn)nN lies entirely outside H.  While we will not use it literally, it is interesting to note (as de Brecht and Kawai do) that it converges to K in the upper Vietoris topology.  This is by definition: every open neighborhood of K in the open Vietoris topology must contain a basic open set ☐containing K.  Since K is included in U, Un is included in U for n large enough, hence Kn is included in U for n large enough.

Notice also that ∩nKn = K.  Indeed, we have made sure that every Kn contains K, and conversely ∩nKn ⊆ ∩nUn is the intersection of all the open neighborhoods of K (since F=(Un)nN is a base of open neighborhoods of K), which is just K since K is saturated.

If the sequence (Kn)nN were monotone, then we could observe that it would have K as least upper bound.  Since K is in the Scott-open set H, some Kn would be in H, contradiction.

However, there is no reason why (Kn)nN would be monotone.  Hence we will build another sequence (K’n)nN in Q(X) with K as least upper bound again, and which will consist of elements outside H as well, but this one will be monotone.

There are two ways one can build the sets K’n a priori.  The most obvious one, perhaps, would be to define K’n as K∩ K∩ … ∩ Kn.  This would ensure that (K’n)nN is monotone indeed, but this suffers from two problems: there is no reason to believe that K’n would be compact, unless we assume X coherent; and K’n is above Kn  in the reverse inclusion ordering, so there is no reason to believe that K’n would still be outside H.

The other way, which is what de Brecht and Kawai use, is to define K’n as Kn ∪ Kn+1 ∪ … ∪ K∪ …  Now it is even less obvious that the sets K’n would be compact, but if they are, they will indeed form a monotone sequence, and outside H.

Why is K’n = Kn ∪ Kn+1 ∪ … ∪ K∪ … compact, then?  Let (Vi)iI be an open cover of K’n, and let V be the union ∪iVi.  We will even assume that (Vi)iI is directed, and our goal is to show that K’n is included in some Vi (Proposition 4.4.7 of the book).

Since every Kcontains KV also contains K.  Since K is compact, K is included in some Vj, j in I.  Let us recall that F=(Um)mN is a base of open neighborhoods of K: so Vj contains Um for some mN.  Then it also contains Um+1, Um+2, etc., because Um ⊇ Um+1 ⊇ Um+2 ⊇ …, and therefore all the sets KmKm+1, Km+2, …, are in Vj.  This was the hard part.

We only have the finitely many sets KnKn+1, …, Km-1, to take care of.  They are all compact and included in V, so: Kn is included in Vi[n] for some i[n] in IKn+1 is included in Vi[n+1] for some i[n+1] in I, …, Km-1 is included in Vi[m-1] for some i[m-1] in I.  By directedness, there is an index i in I such that Vj, Vi[n], Vi[n+1], …, Vi[m-1are all included in Vi, and therefore K’n is included in Vi.

Let us resume—and conclude—the proof.  We have obtained a monotone sequence (K’n)nN in Q(X), and since every K’n contains (i.e., lies below) Kn, no K’n is in H.  The intersection ∩nK’n contains ∩nKn = K.   Conversely, each K’= Kn ∪ Kn+1 ∪ … ∪ K∪ … is included in Un ∪ Un+1 ∪ … ∪ U∪ … = Un, so ∩nK’n is included in ∩nUK.  Hence ∩nK’n = K, which shows in particular that K is the supremum of (K’n)nN in Q(X).  Because K is in H and H is Scott-open, some K’must be in H: contradiction.  ☐

I encourage you to try and remove the second countability assumption in the above proof, and to realize why this fails.  You would need to replace the countable base F=(Um)mN by some other, not necessarily countable, base F’ of open neighborhoods of K, for example the collection of all open neighborhoods of K.  Instead of a sequence (Kn)nN, you would obtain a net (KU)UF’,⊑ (and ⊑ would have to be reverse inclusion).  The key point is in defining the analogue of (K’n)nN.  You should soon realize that this only works provided that given any U in F’, there are only finitely many elements V in F’ such that UV (replacing the fact that we had only finitely many sets KnKn+1, …, Km-1, to take care of in the second half of the argument that showed that K’n is compact) … and that forces the family F’ to be countable—see the Appendix below if you need a proof.

Merry Christmas, and a Happy New Year 2019!

  1. Samson Abramsky and Achim Jung. Domain Theory. Pages 1–168 of Abramsky, S., Gabbay, D. M., and Maibaum, T. S. E. (eds.), Handbook of Logic in Computer Science, vol. 3. Oxford University Press, 1994.  Corrected and expanded version.
  2. Matthew de Brecht and Tatsuji Kawai.  On the commutativity of the powerspace constructions.  arXiv 1709.06226, 2017.
  3. Mike Mislove.  Topology, domain theory and theoretical computer science.  Topology and its Applications 89(1-2), pages 3-59, 1998.  See also the ENTCS version, and the corrigendum.
  4. Matthias Schröder.  A Hofmann-Mislove theorem for Scott-open sets.  arXiv 1501.06452 , 2015.

Appendix

Here is a proof of the fact that every poset F’ such that for every U in F’, there are only finitely many elements V in F’ such that UV, is countable.  For every U in F’, let A(U) be the finite set of elements V in F’ such that UV.  If UU’ [strictly] in F’, then A(U) is included in A(U’), and strictly so since U is in the latter and not in the former.  It follows that the set B(n) of those elements U of F’ such that card A(U)=n is an antichain: it cannot have distinct comparable elements.  But every antichain of F’ is finite: if U is any element of that antichain, the whole antichain must be contained in the finite set A(U).  Finally, F’ is the union of the antichains B(n), nN, and since each of them is finite, F’ is countable.

Jean Goubault-Larrecq (December 25th, 2018)jgl-2011