(0,1)-category

(0,1)-topos

# Contents

## Definition

A completely distributive lattice is a complete lattice $L$ in which arbitrary joins and arbitrary meets distribute over each other.

More formally: given a complete lattice $L$ and functions $p: J \to I$ and $f: J \to L$, we have

$\bigwedge_{i \in I} \bigvee_{j \in p^{-1}(i)} f(j) \geq \bigvee_{sections\; s: I \to J} \bigwedge_{i \in I} f(s(i))$

where “section” means section of $p$. Complete distributivity states that this inequality is an equality, for all $f, p$. The same statement then holds upon switching $\bigwedge$ and $\bigvee$, i.e., complete distributivity is a self-dual property.

## Properties

### Algebraic lattices

###### Proposition

The category of Alexandroff locales is equivalent to that of completely distributive algebraic lattices.

This appears as remark 4.3 in (Caramello 2011).

### Completely distributive Boolean algebras

###### Lemma

A complete totally ordered poset is completely distributive.

###### Proof

(Note: this uses the axiom of choice.) Suppose we had a strict inequality

$\bigwedge_{i \in I} \bigvee_{j \in p^{-1}(i)} f(j) \gt \bigvee_{sections\; s: I \to J} \bigwedge_{i \in I} f(s(i)).$

Denote the left side by $x$ and the right by $y$. Either there is no element $z$ strictly between $x$ and $y$, or there is. In the former case, we have for each $i$ that $\bigvee_{j \in p^{-1}(i)} f(j) \geq x$, and so (using trichotomy) we have $f(j) \gt y$ for some $j \in p^{-1}(i)$. Choosing such a $j$ for each $i$, we obtain a section $s$ with $f(s(i)) \gt y$ for all $y$, whence $f(s(i)) \geq x$ for this case, so that $\bigvee_{sections\; s: I \to J} \bigwedge_{i \in I} f(s(i)) \geq x \gt y$, contradiction. If there is $z$ with $x \gt z \gt y$, we argue similarly to obtain a section $s$ with $f(s(i)) \gt z$ for all $i$, whence $\bigwedge_{i \in I} f(s(i)) \geq z$, and we obtain a contradiction as before with $z$ replacing $x$.

###### Proposition

A complete Boolean algebra $B$ is completely distributive iff it is atomic (a CABA), i.e., is a power set as a Boolean algebra.

###### Proof

For a complete atomic Boolean algebra $B$, it is classical that the canonical map $B \to P(atoms(B))$, sending each $b \in B$ to the set of atoms below it, is an isomorphism. Such power sets are products of copies of $\mathbf{2} = \{0 \leq 1\}$, which is completely distributive by the lemma, and products of completely distributive lattices are completely distributive.

In the other direction, suppose $B$ is completely distributive. Take $p = \pi_2: \mathbf{2} \times B \to B$, and $\alpha: \mathbf{2} \times B \to B$ by $\alpha(0, b) \coloneqq \neg b$ and $\alpha(1, b) \coloneqq b$. Sections of $p$ correspond to functions $g: B \to \mathbf{2}$, and so complete distributivity gives

$1 = \bigwedge_{b \in B} (b \vee \neg b) = \bigvee_{g: B \to \mathbf{2}} \bigwedge_{b \in B} \alpha(g(b), b).$

Write $a(g)$ as abbreviation for $\bigwedge_{b \in B} \alpha(g(b), b)$, we have

$b = b \wedge 1 = b \wedge \bigvee_{g: B \to \mathbf{2}} a(g) = \bigvee_{g: B \to \mathbf{2}} b \wedge a(g)$

so $b \wedge a(g) \neq 0$ for some $g$ if $b \neq 0$. Notice that $b \wedge a(g) \neq 0$ implies $g(b) = 1$, from which we infer two things:

• Whenever $b \leq a(g)$ with $b \neq 0$, then $a(g) \leq \alpha(g(b), b) = \alpha(1, b) = b$; therefore $a(g)$ is an atom whenever $a(g) \neq 0$;

• Provided that $b \wedge a(g) \neq 0$, the preceding point gives that $a(g)$ is an atom below $b \wedge a(g) \leq b$.

The last point shows every element $b$ has an atom $a(g)$ below it, so that $B$ is atomic, as was to be shown.

### Constructive complete distributivity

A complete lattice $A$ is called constructively completely distributive (CCD) if the join-assigning morphism $D A \to A$ has a left adjoint, with $D A$ the poset of downsets.

Constructive complete distributivity is equivalent to complete distributivity if and only if the axiom of choice holds (Wood&Fawcett (1990)).

Constructively completely distributive lattices are an example of continuous algebras for a lax-idempotent 2-monad.

### Remark

Completely distributive lattices correspond to tight Galois connections (Raney 1953). This generalizes to a correspondence between totally distributive toposes and essential localizations (Lucyshyn-Wright 2011).

CCD lattices are precisely the nuclear objects in the category of complete lattices.

The (bi-) category $\mathfrak{CCD}$ with CCD lattices and sup-preserving maps is the idempotent splitting of the (bi-) category of relations $\mathfrak{Rel}$. This plays an important role in domain-theoretical approaches to the semantics of linear logic.

## References

• B. Fawcett, R. J. Wood, Constructive complete distributivity I , Math. Proc. Camb. Phil. Soc. 107 (1990) pp.81-89.
• R. Guitart, J. Riguet, Enveloppe Karoubienne de Catégories de Kleisli , Cah. Top. Geom. Diff. Cat. XXXIII no.3 (1992) pp.261-266. (pdf)

• R. Lucyshyn-Wright, Totally Distributive Toposes , arXiv.1108.4032 (2011). (pdf)

• G. N. Raney, Tight Galois Connections and Complete Distributivity , Trans.Amer.Math.Soc 97 (1960) pp.418-426. (pdf)

• R. Rosebrugh, R. J. Wood, Constructive complete distributivity IV , App. Cat. Struc. 2 (1994) pp.119-144. (preprint)

• I. Stubbe, Towards “Dynamic Domains”: Totally Continuous Complete Q-Categories , Theo. Comp. Sci. 373 no.1-2 (2007) pp.142-160.

Revised on April 18, 2015 17:51:36 by Todd Trimble (67.81.95.215)