Alex Simpson has a lot of slides with very interesting ideas. One of them is what he calls the locale of random sequences. (Update, November 19th, 2022: this link now points nowhere. I am unable to find his slides nowadays. However, look at [1].) This is a terribly clever idea that aims at solving the question “what are random sequences?”, using locale theory.
I will not repeat the first 18 slides, which explain the problem: have a look by yourselves.
However, simply imagine you are given an infinite sequence, or a real number between 0 and 1. Is it random? There are notions like Kolmogorov randomness which will tell you whether it is or not, in a very precise sense, but the simplest answer is no: since you know what it is, and you can always read the next bit or the next digit, it is completely deterministic, hence not random. Alex’s brilliant idea is that the space of random sequences (or numbers) cannot have points. And a nice way to produce a non-trivial space without points is as a locale.
The construction itself is pretty simple. Consider a topological space X, which may be Cantor space (for random sequences) or [0, 1] (for random numbers) for example, and let μ be some continuous probability valuation on X (I will give the definition below, but imagine a uniform distribution). Define an equivalence relation on the frame OX of open subsets of X by U≡V if and only if μ(U∪V)=μ(U∩V), and then build the sublocale OX/≡ (see below). I will try to explain why this is a good idea below, but first, a few definitions.
Continuous valuations
A continuous valuation μ is something like a measure, but better suited to topological spaces: it is a map from OX to ℝ+ ∪ {∞} that is:
- strict (μ(∅)=0),
- monotonic (if U is included in V, then μ(U)≤μ(V)),
- modular (μ(U)+μ(V)=μ(U∪V)+μ(U∩V)),
- and Scott-continuous (for every directed family of open sets Ui, i∈I, μ(∪iUi)=supi μ(∪Ui)).
I will sometimes say that U has μ-measure equal to a if μ(U)=a. If you are afraid that this does not quite look like a measure, please note that (σ-finite) measures and (σ-finite) continuous valuations are in one-to-one correspondence on Polish spaces, and even more, on all completely metrizable spaces. This and much more can be found in [3] (well, what I have just said is there, but is pretty much hidden: read Corollary 4.5 there, together with the first paragraph of Section 4 for the existence of measure extensions in the case of completely metrizable spaces; read the final paragraph of that same section for uniqueness).
A continuous probability valuation additionally satisfies μ(X)=1. I will not require that, but I will need μ to be bounded, namely to satisfy μ(X)<∞. It is likely that one can push what will follow to locally finite continuous valuations, namely to continuous valuations such that every point has an open neighborhood of finite μ-measure, but I will not pursue this.
Lebesgue measure on [0, 1] defines a continuous probability valuation, when restricted to the open sets, for example. In general, every τ-smooth probability measure does—a τ-smooth measure is, by definition, a measure that is Scott-continuous once restricted to the open sets.
The need for a sublocale
The sublocale OX/≡ is certainly not the set of equivalence classes of open subsets of X modulo ≡. That would be the order-theoretic quotient. What we really want to build is something like a subspace of X, not OX, inside the category of locales. Hence we should build a sublocale—or, preferably, a nucleus, since that will be easier—, not a quotient. One way of doing so is by defining a suitable equivalence relation ≡ on OX, and defining the corresponding nucleus as mapping every open set U to the largest open set equivalent to U, then the desired sublocale as the set of fixed points of that nucleus.
As I have already mentioned, we will define ≡ by: U≡V if and only if μ(U∪V)=μ(U∩V). The idea is that we would like to build the “subspace of random elements” as the “subspace” of those points x such that for every open neighborhood U of x, every smaller open neighborhood V with the same μ-measure should also contain x. This is equivalent to saying that if x is in U, then x is in every open set equivalent to U.
As we have already announced, the resulting “subspace” will not have any point, and this justifies the quotes. In fact, if we do not use locales, there is no non-empty subspace satisfying the above property in general. For example, with the Lebesgue measure on [0, 1], for any “random element” x, take U=[0, 1] and V=[0, x) ∪ (x, 1]: U and V have the same measure but one contains x and the other does not.
The sublocale of random elements as a nucleus
Recall that U≡V if and only if μ(U∪V)=μ(U∩V). We first check that:
Lemma 1. ≡ is an equivalence relation on OX.
Proof. The only non-trivial fact to check is transitivity. Let us assume U≡V and V≡W. Since U≡V, U∪V and U∩V have the same μ-measure. By monotonicity, the μ-measures of U and of V are inbetween. Therefore U∪V, U∩V, U, V all have the same μ-measure. Similarly, V∪W, V∩W, V, W all have the same μ-measure. Since V is in both lists, all those sets have the same μ-measure. Call it a. Now:
2a = μ(U∩V)+μ(V∩W)
= μ((U∩V)∪(V∩W))+μ((U∩V)∩(V∩W)) [modularity]
= μ(V∩(U∪W))+μ(U∩V∩W)
≤ 2a [monotonicity],
so all those values are equal. In particular, μ(V∩(U∪W))+μ(U∩V∩W)=2a. By monotonicity, μ(V∩(U∪W)) and μ(U∩V∩W) are both less than or equal to a. Since μ is bounded, a≠∞, so they are both equal to a. Then all the open sets inbetween U∩V∩W and U (or W) have the same μ-measure, in particular U∩W. Finally, 2a = μ(U)+μ(W) = μ(U∩W)+μ(U∪W) = a+μ(U∪W) by modularity, so μ(U∪W) is also equal to a, hence to μ(U∩W). ☐
Lemma 2. If U≡V and U≡V’ then U≡V∪V’ and U≡V∩V’.
Proof. By transitivity (Lemma 1), V≡V’, so V∪V’, V∩V’, V, V’ all have the same μ-measure. Note that for any two open subsets A and B such that A is included in B, A≡B if and only if μ(A)=μ(B). Hence V∪V’≡V, V∪V’≡V’, V≡V∩V’, and V’≡V∩V’. We conclude by Lemma 1. ☐
Proposition 3. For every open subset U of X, there is a largest open subset ν(U) of X such that U≡ν(U). The map ν : U ↦ ν(U) is a nucleus.
Proof. Let D be the family of open subsets V of X such that U≡V. It is non-empty, since it contains U. Given two elements V and V’ of D, V∪V’ is also in D by Lemma 2, first part. This shows that D is directed. Note that all the elements V of D have the same μ-measure, which is also equal to μ(U). Since D is directed, it has a supremum, which is the union of the elements of D. We call it ν(U). Since μ is Scott-continuous, we obtain that μ(ν(U)) is the supremum of the μ-measures of elements of D, which are all equal to μ(U). Since U is included in ν(U), μ(U∪ν(U))=μ(ν(U))=μ(U)=μ(U∩ν(U)), so U≡ν(U). It follows that ν(U) is in D, hence is the largest element of D.
It is easy to see that ν : U ↦ ν(U) is monotonic, inflationary, and idempotent. It remains to show that ν(U∩V)=ν(U)∩ν(V) for all open sets U and V. To that end, it is enough to show that ν(U∩V) contains ν(U)∩ν(V), since the other direction follows from monotonicity. That amounts to showing that every open set W such that W≡U and W≡V also satisfies W≡U∩V: this is given by Lemma 2, second part. ☐
The sublocale of random elements as a sieve
Given a nucleus ν on a frame Ω, we recall that it can be represented in an alternate way as a sieve Sν, defined as the set of formal crescents (u, v) such that u ≰ ν(v). Here Ω=OX, and u and v are actual open subsets U and V.
Lemma 4. U ⊊ ν(V) if and only if μ(U)>μ(U ∩ V).
Proof. U ⊆ ν(V) iff ν(U) ⊆ ν(V) [using the fact that ν is a nucleus] iff ν(U) = ν(U) ∩ ν(V) iff ν(U) = ν(U ∩ V) iff U≡U ∩ V iff μ(U)=μ(U ∩ V). ☐
There is a theorem due independently to Pettis, Smiley, and Horn-Tarski which says that every bounded valuation μ (not necessarily continuous) extends to an additive measure, again written μ, on the smallest Boolean algebra of subsets containing the open sets. The elements of that algebra are the finite disjoint unions of crescents U–V. What Lemma 4 says is that Sν is the set of formal crescents (U, V) such that μ(U–V)≠0.
I will not formally need that theorem, but I will reuse the convention of writing μ(U–V)≠0 instead of μ(U)>μ(U ∩ V). That is somehow more readable.
Since a sieve is a collection of formal crescents that is closed under equivalence of formal crescents, and equivalence of formal crescents of the form (U, V) is just equality of the corresponding crescents U–V, an alternative description of Sν is as the collection of (actual) crescents Sν of non-zero μ-measure.
The points of the sublocale of random elements
We have already argued that a subspace of random elements would have to be empty, at least on [0, 1] with Lebesgue measure. Correspondingly, the sublocale of random elements has no points in general, as we shall see.
First, any nucleus ν determines a sublocale Ων, consisting of the fixed points (equivalently, the image) of the nucleus. Every sublocale is a frame (exercise, or see [2, Proposition 2.2]), hence it makes sense to explore what its points are.
We work directly with the nucleus ν. A nucleus preserves all finite infima, so the finite infima of Ων are computed as in the ambient frame—in our case, as finite intersections. Suprema, on the other hand, are computed by taking suprema in the ambient frame (union, in our case) and then taking the image by ν.
A point of Ων is described by a prime element of Ων (Proposition 8.1.20 in the book). Here this is an open subset P of X that is different from X, inside Ων (namely, P=ν(P)), and such that for all open subsets U, V in Ων (i.e., such that U=ν(U) and V=ν(V)), if U ∩ V ⊆ P then U or V is included in P.
Proposition 5. The prime elements of Ων are the open subsets of the form ν(P), where P is an open subset of X such that for all open subsets U and V of X such that μ(U–P)≠0 and μ(V–P)≠0, then μ(U∩V–P)≠0.
Proof. Assume P prime in Ων, μ(U–P)≠0 and μ(V–P)≠0. By Lemma 4, neither U nor V is included in ν(P). Then neither ν(U) nor ν(V) is included in ν(P). Since ν(U) and ν(V) are in Ων, and since P is prime, ν(U) ∩ ν(V) = ν(U ∩ V) is not included in ν(P) either, so U ∩ V is not included in ν(P) either, and therefore μ(U∩V–P)≠0 by Lemma 4.
In the converse direction, if P satisfies the stated property, we consider any two elements U, V of Ων such that U ∩ V ⊆ ν(P). If neither U nor V is included in ν(P), then μ(U–P)≠0 and μ(V–P)≠0 by Lemma 4. Using the stated property, μ(U∩V–P)≠0, so U ∩ V is not included in ν(P) either by Lemma 4: contradiction. ☐
Proposition 5 sounds like irreducibility: the prime elements of Ων are the prime open subsets of X “up to measure 0 sets” (whatever that means).
At least, given a prime element P of Ων, Proposition 5 shows that the set F(P) of open subsets U of X such that μ(U–P)≠0 is a filter. Since μ is Scott-continuous, F(P) is Scott-open (you need to realize that μ(U–P)≠0 is equivalent to μ(U ∪ P)>μ(P) for that: use modularity). The empty set is not in F(P), and if U ∪ V is in F(P) then μ(U–P)+μ(V–P) ≥ μ((U∪V)–P) > 0, so U or V is in F(P). It follows that F(P) is a completely prime filter of open sets.
If X is sober, then that implies that there is a unique point x in X such that F(P) is the collection of open neighborhoods of x. It follows that, for every open subset U of X, x is in U if and only if μ(U–P)≠0. Consider the open subset U0 equal to the complement of ↓x. Since x is not in U0, μ(U0–P)=0, or equivalently (by Lemma 4), U0⊆ν(P)=P. Conversely, since μ(P–P)=0, x is not in P. Since P is upwards-closed, every element y of P is in U0, otherwise it would be below x, and that would entail that x is in P. Hence P is included in U0. Together with U0⊆P, we obtain that U0=P.
Summing up, (if X is sober,) P is the complement of ↓x, where x is a point such that every open neighborhood U of x containing P has strictly larger μ-measure than P. Let us call such a point x a μ-atom: this is, roughly, a point that carries some μ-mass by itself.
We have proved one half of:
Proposition 6. If X is sober, then the prime elements P of Ων are the complements of ↓x, where x is a μ-atom. (More succinctly: the points of Ων are the μ-atoms.)
Proof. It remains to show that if P is the complement of ↓x, where x is a μ-atom, then P is a prime element of Ων. Let U be any open subset of X such that U≡P. If x is in U, then μ(U ∪ P)>μ(U) since x is a μ-atom. However U≡P implies that μ(U ∪ P)=μ(U ∩ P)≤μ(U), so x cannot be in U. By definition of P, U is then included in P: for every y in U, y cannot be below x otherwise x would be in U, so y is in P. We have just shown that P is the largest open set in its ≡-equivalence class, namely that P=ν(P). Therefore P is in Ων.
Assume now, with the aim of applying Proposition 5, that we are given two open subsets U and V of X such that μ(U–P)≠0 and μ(V–P)≠0. Then x must be in U, since otherwise U would be included in P, and therefore μ(U–P) would be equal to 0. Similarly, x is in V, hence x is in U∩V. Since x is a μ-atom, μ(U∩V–P)≠0. Hence P is prime. ☐
Consider again Lebesgue measure μ on [0, 1]. [0, 1], with its usual metric topology, is T2 hence sober, and we claim that there is no μ-atom. Imagine there were one, call it x. The complement P of ↓x is [0, x) ∪ (x, 1], whose μ-measure is 1, and it is not true that every open neighborhood U of x containing P has strictly larger μ-measure: the only such U is [0, 1], and it also has μ-measure equal to 1.
Hence Ων simply has no points in this (important) case… but it is a very large sublocale. Seen as a sieve, this is the collection of all crescents U–V of non-zero measure.
- Alex Simpson. The locale of random sequences. Invited talk, Continuity, Computability, Constructivity, From Logic to Algorithms Cologne, July 2009. (Updated, November 19th, 2023: rather, see Alex Simpson, Measure, randomness and sublocales, Annals of Pure and Applied Logic 163(11):1642-1659, 2012.)
- Jorge Picado and Aleš Pultr. Frames and locales — topology without points. Birkhäuser, 2010.
- Klaus Keimel and Jimmie Lawson. Measure extension theorems for T0-spaces. Topology and its Applications, 149(1–3), 57–83, 2005.
— Jean Goubault-Larrecq (November 26th, 2018)