JOINS IN THE FRAME OF NUCLEI

MARTÍN H. ESCARDÓ

Abstract. Joins in the frame of nuclei are hard to describe explicitly because a pointwise join of a set of closure operators on a complete lattice fails to be idempotent in general. We calculate joins of nuclei as least fixed points of inflationary operators on prenuclei. Using a recent fixed-point theorem due to Pataraia, we deduce an induction principle for joins of nuclei. As an illustration of the technique, we offer a simple (and also intuitionistic) proof of the localic Hofmann–Mislove Theorem.

1. Introduction

A frame, or locale, is a complete lattice in which binary meets distribute over arbitrary joins. A nucleus on a frame is an inflationary and idempotent map that preserves finite meets. Under the pointwise ordering, the nuclei on a frame form themselves a frame. Meets of nuclei are calculated pointwise, but joins are harder to describe explicitly, as pointwise joins fail to be idempotent in general.

Thus, prenuclei are introduced as a tool for calculating joins [14]. A prenucleus on a frame is an inflationary map that preserves finite meets. Banaschewski considers a slightly more general notion with the same terminology [1]. The prenuclei also form a complete lattice. A simple but important technical property of prenuclei is that, as opposed to nuclei, they are closed under composition and under the formation of pointwise directed joins. The inclusion of the frame of nuclei into the lattice of prenuclei has a left adjoint, which, as any left adjoint to an inclusion, assigns to each prenucleus p the least nucleus p̄ with p ≤ p̄, referred to as the nuclear reflection of p. Thus, the join of a set of nuclei in the frame of nuclei is the nuclear reflection of its join in the lattice of prenuclei.

There are at least four ways of obtaining the reflection. Let p be a prenucleus on a frame T. Simmons [13, 14] defines inductively, for all ordinals α and limit ordinals λ,

p^{0}(u) = u,  p^{α+1}(u) = p(p^{α}(u)),  p^{λ}(u) = ⋁{p^{α}(u) | α < λ}.

Then p^{α} must be idempotent for a sufficiently large ordinal α, and p̄ is then p^{α} for such α. Banaschewski [1] shows that

p̄(u) = ⋀{v ∈ T | u ≤ v = p(v)},

Johnstone [9] shows that

p̄(u) = ⋀{((u ⇒ v) ∧ (p(v) ⇒ v)) ⇒ v | v ∈ T },

2000 Mathematics Subject Classification. Primary 06D22, 54D30; Secondary 03G30, 03F55.

Key words and phrases. Frame, locale, compactness, nuclei, closure operator, common fixed point, Hofmann–Mislove Theorem.

and Wilson [17] shows that

p̄(u) = ⋀{(p(v) ⇒ v) ⇒ v | u ≤ v},

where the symbol ⇒ denotes Heyting implication.

We propose a fifth way of obtaining the nuclear reflection, which is based on the observation that p̄ is the least nucleus k satisfying the fixed-point equation p∘k = k. We apply a version of Tarski’s fixed-point theorem due to Pataraia [12] to conclude that p̄ enjoys the following induction principle.

1.1. If p is a prenucleus and Q is an inductive set of prenuclei such that q ∈ Q implies p ∘ q ∈ Q, then p̄ ∈ Q.

Here a set of prenuclei is called inductive if it has the least prenucleus as a member and is closed under the formation of directed joins.

We also propose a related sixth way of computing the join of a set J of nuclei, which is based on the observation that the join is the least nucleus k satisfying the family of fixed-point equations j ∘ k = k with j ∈ J. We apply a generalization of Pataraia’s fixed-point theorem, from single inflationary maps to sets of inflationary maps, to conclude that the join enjoys the following induction principle.

1.2. If J is a set of nuclei and Q is an inductive set of prenuclei such that j ∈ J and q ∈ Q together imply j ∘ q ∈ Q, then ⋁ J ∈ Q.

Although this second induction principle also refers to prenuclei, it avoids the cumbersome detour of calculating the join in the lattice of prenuclei and then reflecting it back to the frame of nuclei.

As an illustration of the technique, we consider the Hofmann–Mislove Theorem [4, Theorem 2.16] [10]. We offer a simple proof of a localic version, first established by Johnstone [8, Lemma 2.4], which is based on the same idea but uses the second induction principle instead of transfinite induction, so that it is intuitionistic in the sense of topos logic [6]. Essentially, this means that the principle of excluded middle, the axiom of choice and proper classes are not allowed—in particular, ordinals are ruled out. For another intuitionistic proof, based on different methods, see Vickers [16], and for a direct intuitionistic proof in the stably locally compact case, see Escardó [3].

Our development is largely self-contained, but we assume that the reader is familiar with basic order-theoretic concepts. The standard reference to locale theory is Johnstone [7], where it is emphasized that many important topological theorems that unavoidably rely on non-constructive principles have intuitionistic localic versions.

In Section 2, we develop Pataraia’s fixed-point theorem in detail because it is unpublished (a brief sketch is published as [15, Exercises 3.44 and 3.45]). But we do include one new result, which is applied in Section 3 to establish the induction principles discussed above. We finish by considering the localic Hofmann–Mislove Theorem in Section 4.

I am grateful to Harold Simmons for discussions on frames. Alex Simpson communicated Pataraia’s theorem to me and indicated that it can often be used as a substitute for arguments based on transfinite induction. Thanks to Dito Pataraia for letting me have a copy of his original manuscript and allowing me to include a proof. Achim Jung is gratefully acknowledged for careful readings of previous versions and various suggestions regarding the presentation of the material.

2. A common-fixed-point theorem

This section is based on Pataraia [12]. A poset is directed complete if it has joins of directed subsets. A monotone endomap f of a poset is said to be inflationary if x ≤ f(x) holds for all elements x of the poset.

Lemma 2.1. The set of all inflationary maps on any non-empty directed complete poset has a common fixed point.

Proof. The set of inflationary maps under the pointwise ordering is directed complete because it is closed under the formation of pointwise directed joins. It is directed because the identity is inflationary and because if f and g are inflationary then f ∘ g is an inflationary map above f and g. By directed completeness, there is a maximum inflationary map ⊤. If f is inflationary then ⊤ ≤ f ∘ ⊤, and, because f ∘ ⊤ is inflationary, f ∘ ⊤ ≤ ⊤ by construction of ⊤. Therefore ⊤(x) is a common fixed point of the inflationary maps for any element x of the poset.

By an inductive poset we mean a directed complete poset with a least element, and by an inductive subset of an inductive poset we mean a subset that has the least element as a member and is closed under the formation of directed joins. The following generalizes a proposition by Pataraia from single inflationary maps to sets of inflationary maps, but we stress that the idea of proof is the same.

Theorem 2.2. Any set F of inflationary maps on an inductive poset D has a least common fixed point. Moreover, any inductive subset of D that is closed under f for each f ∈ F has the least common fixed point as a member.

Proof. Let X be the intersection of the inductive subsets of D that are closed under f for each f ∈ F. Then each f ∈ F restricts to an inflationary map on X, and by Lemma 2.1, the set F has a common fixed point in X, say x. Let y ∈ D be another. The set I = {d ∈ D | d ≤ y} is inductive, and if d ∈ I and f ∈ F then f(d) ≤ f(y) = y which shows that f(d) ∈ I. Therefore x ≤ y because X ⊆ I.

In our applications, the least fixed point is known to exist in advance, and the induction principle formulated in the second clause of the theorem is used in order to deduce properties of it.

We include the following for the sake of completeness, but we remark that is not needed for the purposes of this paper.

Corollary 2.1. Any monotone endomap of an inductive poset has a least fixed point.

Proof. If f : E → E is a monotone endomap of an inductive poset E, then D = {x ∈ E | x ≤ f(x)} is an inductive subset of E and is closed under f, and the restriction of f to D is inflationary. Hence the result follows from Theorem 2.2 and the fact that D contains all fixed points of f.

Notice this does not generalize from single monotone maps to sets of monotone maps, as exemplified by the poset with one minimal and two maximal elements and by the two constant endomaps that fix each maximal element.

3. Joins in the frame of nuclei

Lemma 3.1. For any given prenucleus p, a nucleus k satisfies the inequality p ≤ k if and only if it satisfies the fixed-point equation p ∘ k = k.

Proof. The inequality k ≤ p∘k always holds because p is inflationary. If p ≤ k then p ∘ k ≤ k ∘ k = k. Conversely, if p ∘ k = k then p ≤ p ∘ k = k because p is monotone and k is inflationary.

Theorem 3.2. Let P be a set of prenuclei and k be the least nucleus with p ≤ k for all p ∈ P. If Q is an inductive set of prenuclei such that p ∈ P and q ∈ Q together imply p ∘ q ∈ Q, then k ∈ Q.

Proof. For each p ∈ P, the function q ↦ p ∘ q is an inflationary map of the lattice of prenuclei because p is inflationary. By Theorem 2.2, these maps have a least common fixed point, say r, which belongs to any inductive set Q of prenuclei such that p ∘ q ∈ Q whenever p ∈ P and q ∈ Q. But Lemma 3.1 shows that k is the least nucleus satisfying the family of fixed-point equations p ∘ k = k with p ∈ P. Thus, if we show that the prenucleus r is actually a nucleus, we conclude that k = r and we are done. The set Q′ of prenuclei q with q ∘ r ≤ r is inductive. If p ∈ P and q ∈ Q′ then q ∘ r ≤ r and hence p ∘ q ∘ r ≤ p ∘ r = r, which shows that p ∘ q ∈ Q′. It follows that r ∈ Q′ and hence that r is idempotent, as required.

We are interested in the following two special cases.

Corollary 3.1 (Reflection induction). If p is a prenucleus and Q is an inductive set of prenuclei such that q ∈ Q implies p ∘ q ∈ Q, then p̄ ∈ Q.

Corollary 3.2 (Join induction). If J is a set of nuclei and Q is an inductive set of prenuclei such that j ∈ J and q ∈ Q together imply j ∘ q ∈ Q, then ⋁ J ∈ Q.

The following well-known property of nuclear reflections [9] can be proved by reflection induction.

Proposition 3.3. The fixed points of a prenucleus p coincide with those of its nuclear reflection p̄. In particular, p̄(u) is the least fixed point of p above u.

Proof. Since p ∘ p̄ = p̄ by Lemma 3.1, every fixed point of p̄ is a fixed point of p. Conversely, let u be a fixed point of p. The set Q of prenuclei q with q(u) = u is inductive. If q ∈ Q then q(u) = u and hence p(q(u)) = p(u) = u, which shows that p ∘ q ∈ Q. Therefore p̄(u) = u by the reflection-induction principle. For the particular case, if u ≤ v = p(v) then p̄(u) ≤ p̄(v) = v because p̄ is monotone.

In order to show that (an isomorphic manifestation of) the lattice of nuclei is a frame, Isbell [5] established the frame distributivity law by a rather complicated argument. Johnstone [7, Proposition 2.5] and Simmons [14, Lemma 3.1] obtained simpler proofs by defining Heyting implication, relying on the fact that a complete lattice is a frame if and only if it is a Heyting algebra. The join-induction principle allows us to provide a particularly simple proof of the frame distributivity law.

Let k be a nucleus, J be a set of nuclei, and l denote ⋁{k∧j | j ∈ J}. It is enough to show that k ∧ ⋁ J ≤ l. By the distributivity law of the underlying frame and the fact that finite meets and directed joins of prenuclei are computed pointwise, the set Q of prenuclei q with k ∧ q ≤ l is inductive. If j ∈ J then k ∧ j ≤ l, and hence if q ∈ Q then (k∧j)∘(k∧q) ≤ l∘l = l. But (k∧j)∘(k∧q) = k∘k∧k∘q∧j∘k∧j∘q = k∧j∘q because k ≤ k ∘q and k ≤ j ∘k, which shows that j ∘q ∈ Q and hence that ⋁ J ∈ Q.

The arguments of this section generalize in two directions. Firstly, notice that they only mention existence of finite meets and directed joins, and distributivity of the former over the latter. Posets with such structure are known as preframes.

Thus, the join-induction principle holds for the frame of nuclei on a preframe. Secondly, we can drop the requirement of existence of finite meets and any distributivity law altogether. In this case, we obtain a join-induction principle for the complete lattice of closure operators on a directed complete poset, with prenuclei replaced by inflationary maps.

4. The Hofmann–Mislove–Johnstone Theorem

We finish this paper with a more sophisticated illustration of the join-induction principle. The Hofmann–Mislove Theorem says that the compact saturated subsets of a sober topological space are in order-reversing bijection with the Scott open filters of open sets [4, Theorem 2.16]. Recall that a set is saturated if it is the intersection of its neighbourhoods, and that a filter is Scott open if it is inaccessible by directed joins. Here we prove a localic version due to Johnstone [8, Lemma 2.4].

Theorem 4.1 (Johnstone). The compact fitted quotient frames of any frame are in order-reversing bijection with the Scott open filters of opens.

We begin by discussing the terminology and notation used in the formulation and proof of the theorem. A typical example of a frame is the topology of a topological space, and, in fact, frames can be regarded as generalized (sober) topologies. The elements of a frame are referred to as opens and are ranged over by the letters u, v, w, and the bottom and top opens are denoted by the symbols 0 and 1. A homomorphism of frames is a function that preserves finite meets and arbitrary joins. Topologically, frame homomorphisms correspond to continuous maps in the opposite direction. A quotient of a frame is a direct image of a nucleus on the frame. Topologically, (spatial) quotient frames correspond to (sober) subspaces [2]. Moreover, joins of nuclei correspond to intersections of subspaces. Each open v induces a nucleus v^{∘} defined by

v^{∘}(u) = (v ⇒ u) = ⋁{w | w ∧ v ≤ u}.

Nuclei of this form are called open as they correspond to open subspaces. A fitted nucleus is a join of open nuclei. Thus, fitted nuclei correspond to saturated subspaces. A nucleus j on a frame T is said to be compact if the top open is compact (every open cover has a finite subcover) in the quotient frame j(T).

In what follows, T stands for an arbitrary frame. In order to prove Theorem 4.1, we begin with some standard facts that relate nuclei and filters of opens [11]. For a nucleus j on T and a set ϕ ⊆ T, define

∇j = j^{−1}(1), Δϕ = ⋁{v^{∘} | v ∈ ϕ}.

Notice that if j ≤ k then ∇j ⊆ ∇k, and if ϕ ⊆ γ then Δϕ ≤ Δγ.

Lemma 4.2. 1. ∇j is a filter.

2. Δϕ is a fitted nucleus.

3. Δ∇j ≤ j.

4. ϕ ⊆ ∇Δϕ.

Proof. (1): j preserves finite meets. (2): By definition. (3): If v ∈ ∇j then v^{∘}(u) = (v ⇒ u) ≤ j(v ⇒ u) = j(v ⇒ u) ∧ 1 = j(v ⇒ u) ∧ j(v) = j((v ⇒ u) ∧ v) ≤ j(u) for any u ∈ T, and hence v^{∘} ≤ j. (4): If v ∈ ϕ then Δϕ(v) ≥ v^{∘}(v) = (v ⇒ v) = 1.

Lemma 4.3(2) below is due to Johnstone [8, Lemma 2.4(ii)]. Our proof is based on the same idea, but we use the join-induction principle formulated in Corollary 3.2 instead of ordinals and transfinite induction.

Lemma 4.3. 1. j ≤ Δ∇j if j is fitted.

2. ∇Δϕ ⊆ ϕ if ϕ is a Scott open filter.

Proof. (1): The assumption amounts to j = Δϕ for some ϕ ⊆ T. Hence the claim amounts to Δϕ ≤ Δ∇Δϕ, which follows from Lemma 4.2(4) and monotonicity of Δ. (2): Let Q be the set of prenuclei q with q^{−1}(ϕ) ⊆ ϕ, that is, such that q(u) ∈ ϕ implies u ∈ ϕ. The least prenucleus, being the identity, belongs to Q. If D ⊆ Q is a directed set with (⋁ D)(u) ∈ ϕ then q(u) ∈ ϕ for some q ∈ D because directed joins of prenuclei are computed pointwise and ϕ is Scott open, and u ∈ ϕ because q ∈ Q, which shows that ⋁ D ∈ Q. If v^{∘} ∘q(u) = (v ⇒ q(u)) ∈ ϕ for v ∈ ϕ and q ∈ Q, then q(u) ≥ v ∧ (v ⇒ q(u)) is in ϕ because ϕ is a filter, and hence so is u because q ∈ Q, from which it follows that v^{∘} ∘ q ∈ Q. By the join-induction principle, the nucleus Δϕ is in Q. Therefore (Δϕ)^{−1}(1) ⊆ ϕ because 1 ∈ ϕ.

The following is Lemma 2.4(i) of Johnstone [8] with the same proof.

Lemma 4.4. The nucleus j is compact if and only if the filter ∇j is Scott open.

Proof. (⇒): If ⋁ U ∈ ∇j for U ⊆ T directed, then j(⋁ U) = 1. By compactness of j and the fact that j(⋁ U) is the join of j(U) in j(T), there is some u ∈ U with j(u) = 1 and hence with u ∈ ∇j. (⇐): If V ⊆ j(T) is a directed set whose join in j(T) is 1, then ⋁ V ∈ ∇j because the join of V in j(T) is j(⋁ V). By Scott openness of ∇j, there is some v ∈ V with v ∈ ∇j, that is, with j(v) = 1, and hence with v = 1 as V ⊆ j(T) and j is idempotent.

The Hofmann–Mislove–Johnstone Theorem follows directly from the above three lemmas and the fact that the frame of quotients is dually isomorphic to the frame of nuclei.

References

[1] B. Banaschewski. Another look at the localic Tychonoff theorem. Comment. Math. Univ. Carolin., 29(4):647–656, 1988.

[2] C. H. Dowker and Dona Papert. Quotient frames and subspaces. Proc. London Math. Soc. (3), 16:275–296, 1966.

[3] M.H. Escardó. The regular-locally-compact coreflection of stably locally compact locale. Journal of Pure and Applied Algebra, 157(1):41–55, 2001.

[4] K.H. Hofmann and M. Mislove. Local compactness and continuous lattices. In B. Banaschewski and R.-E. Hoffmann, editors, Continuous Lattices, volume 871 of Lecture Notes in Mathematics, pages 209–248, 1981.

[5] John R. Isbell. Atomless parts of spaces. Math. Scand., 31:5–32, 1972.

[6] P.T. Johnstone. Topos Theory. Academic Press, London, 1977.

[7] P.T. Johnstone. Stone Spaces. Cambridge University Press, Cambridge, 1982.

[8] P.T. Johnstone. Vietoris locales and localic semilattices. In Continuous lattices and their applications (Bremen, 1982), pages 155–180. Dekker, New York, 1985.

[9] P.T. Johnstone. Two notes on nuclei. Order, 7(2):205–210, 1990.

[10] K. Keimel and J. Paseka. A direct proof of the Hofmann–Mislove theorem. Proc. Amer. Math. Soc., 120(1):301–303, 1994.

[11] D.S. MacNab. Modal operators on Heyting algebras. Algebra Universalis, 12(1):5–29, 1981.

[12] D. Pataraia. A constructive proof of Tarski’s fixed-point theorem for dcpo’s. Presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997.

[13] H. Simmons. An algebraic version of Cantor–Bendixson analysis. In Categorical aspects of topology and analysis (Ottawa, Ont., 1980), pages 310–323. Springer, Berlin, 1982.

[14] H. Simmons. Near-discreteness of modules and spaces as measured by Gabriel and Cantor. J. Pure Appl. Algebra, 56(2):119–162, 1989.

[15] P. Taylor. Practical foundations of mathematics. Cambridge University Press, Cambridge, 1999.

[16] S.J. Vickers. Constructive points of powerlocales. Math. Proc. Cambridge Philos. Soc., 122(2):207–222, 1997.

[17] J.T. Wilson. The Assembly Tower and Some Categorical and Algebraic Aspects of Frame Theory. PhD thesis, School of Computer Science, Carnegie Mellon University, May 1994.

School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK

   E-mail address: mhe@cs.bham.ac.uk     http://www.cs.bham.ac.uk/~mhe/