nLab BoolAlg

Definition

$Bool Alg$ is the category whose objects are boolean algebras and whose morphisms are lattice homomorphisms, that is functions which preserve finitary meets and joins (equivalently, binary meets and joins and the top and bottom elements); it follows that the homomorphisms preserve negation. $Bool Alg$ is a subcategory of Pos, in fact a replete subcategory of both DistLat and HeytAlg.

$Bool Alg$ is given by a finitary variety of algebras, or equivalently by a Lawvere theory, so it has all the usual properties of such categories. As usual, the Lawvere theory is the category opposite to the category of finitely generated free Boolean algebras.

Definition via Lawvere theories

The concrete category $U: BoolAlg \to Set$ is monadic: the category of Boolean algebras is the category of algebras for a finitary monad, or equivalently it is the category of algebras for a Lawvere theory. In this case the Lawvere theory is very easily described.

The Lawvere theory is equivalent to the category opposite to the category of finitely generated free Boolean algebras, or of finitely generated free Boolean rings. As we observed earlier, the free Boolean algebra on $n$ elements is therefore isomorphic to $P(2^n)$, the power set of a $2^n$-element set. Applying a “toy” form of Stone duality, the opposite of the category of finitely generated free Boolean algebras is equivalent to the category of finite sets of cardinality $2^n$.

Hence the Lawvere theory is identified with the category $Fin_{2^n}$ of finite sets of cardinality $2^n$, and the category of Boolean algebras is equivalent to the category of product-preserving functors

$$Fin_{2^n} \to Set.$$

Unbiased Boolean algebras

Observe that the Cauchy completion of $Fin_{2^n}$ is $Fin_+$, the category of nonempty finite sets. (Indeed, every nonempty finite set is the retract of some set with $2^n$ elements.)

Proposition

Let $C$ be a category with finite products, and let $i: C \hookrightarrow \widebar{C}$ be its Cauchy completion. Then $\widebar{C}$ has finite products, and the category of product-preserving functors $\widebar{C} \to Set$ is equivalent to the category of product-preserving functors $C \to Set$, via restriction along $i$.

By this proposition, the category of Boolean algebras is equivalent to the category of product-preserving functors

$$Fin_+ \to Set$$

We call a product-preserving functor $Fin_+ \to Set$ an unbiased Boolean algebra. The idea here is that the usual concrete way of viewing Boolean algebras is inherently biased towards sets of cardinality $2^n$. Passing to the Cauchy completion removes that bias.

$k$-valued Post algebras

Alternatively, we could apply the previous proposition in reverse and view Boolean algebras as a concrete category in an entirely different way. For example, the Lawvere theory given by the category of finite sets of cardinality $3^n$ has the same Cauchy completion $Fin_+$. Therefore, the category of product-preserving functors

$$X: Fin_{3^n} \to Set$$

is also equivalent to the category of Boolean algebras. Only here, the appropriate underlying set functor sends $X$ to $X(3)$, the value at the generator $3$.

Similarly, for each fixed cardinality $k \gt 1$, there is a Lawvere theory $Fin_{k^n}$, and they all lead to Boolean algebras as the category of algebras for the theory. The difference is in the associated monadic functor, $U_k \colon Prod(Fin_{k^n}, Set) \to Set$. This concrete category is perhaps better known as the category of $k$-valued Post algebras (and is better known still when the letter $k$ is replaced by $n$).

A curious phenomenon that holds for each $k \geq 3$ (but not for $k = 2$) is as follows. Let $Un_k$ be the Lawvere subtheory of $Fin_{k^n}$ generated by just the unary operations, so that the algebras of $Un_k$ are identified with sets equipped with actions of the monoid $M_k = \hom(k, k)$ (endofunctions of the $k$-element set under composition), aka $M_k$-sets. By restriction of operations, there is an evident forgetful functor

$$BoolAlg \simeq PostAlg_k \to M_k\text{-}Set$$

Proposition

For each $k \geq 3$, the forgetful functor from $BoolAlg \to$ $M_k$-$Set$ realizes $BoolAlg$ as a full subcategory of $M_k$-Set.

Free Boolean algebras

The free Boolean algebra $Bool(X)$ generated by a finite set $X$ is isomorphic to the double power set $\mathcal{P}\mathcal{P}X$ of $X$; an element $a$ of $X$ is interpreted as the set of all those subsets of $X$ to which $a$ belongs, and the boolean algebra operations on the intersection and union as usual. This is equivalently the function set $\mathbb{2}^{\mathbb{2}^X}$ of functions $\mathbb{2}^X$ to the boolean domain $\mathbb{2}$.

The free Boolean algebra on an arbitrary set $X$ is more complicated; it can be described in several ways. By abstract nonsense, it can be described as a filtered colimit of finitely generated free Boolean algebras

$$Bool(X) = colim_{S \subseteq_{fin} X} Bool(S)$$

(where $\subseteq_{fin}$ indicates a finite subset) in the category of Boolean algebras; here the colimit is over the poset of finite subsets and inclusions between them.

A second, more concrete description is

$$Bool(X) = \mathcal{P}_{fin} \mathcal{P}_{fin} X$$

where $\mathcal{P}_{fin}(X)$ denotes the set of Dedekind finite subsets of $X$.

However, the Boolean operations are not what one might naively expect. The simplest way of describing the operations is to consider Boolean algebras as equivalent to Boolean rings where binary addition is given by symmetric difference, as explained further at Boolean algebra. We can construct free Boolean rings by analogy with the polynomial algebra construction, where one forms the free vector space generated by a monoid of monomials.

To do this, we first make $\mathcal{P}_{fin}: Set \to Set$ into the monad for commutative idempotent monoids (that is, semilattices). Here we use the fact that that $\mathcal{P}_{fin} X$ with the monoid operation given by union, is the free semilattice on $X$. Call $\mathcal{P}_{fin}$ with this monad structure $M$, for “multiplication”.

Next, let $S: Set \to Set$ be the monad for vector spaces over $\mathbb{F}_2$. We can take the functor $S$ to have the same action on objects as $\mathcal{P}_{fin}$, since $\mathcal{P}_{fin}X$ with symmetric difference as addition gives the free $\mathbb{F}_2$-vector space on $X$. But beware: $S$ acts differently on morphisms.

Finally, note that there is a distributive law $M \circ S \Rightarrow S \circ M$ that maps any product of sums to a sum of products in the usual way. This makes the composite $S \circ M \colon Set \to Set$ into a monad, which in fact is the monad for Boolean rings. This monad has the same action on objects as the functor $\mathcal{P}_{fin} \mathcal{P}_{fin}: Set \to Set$, but it behaves differently on morphisms.

Using the equivalence between Boolean rings and Boolean algebras, we thus obtain:

Theorem

The functor $M \circ S \colon Set \to Set$ has a monad structure making it into the monad for Boolean algebras. That is, the Eilenberg-Moore category of this monad is equivalent to $BoolAlg$.

(A more naive prescription, where one uses the usual intersection and union on the Boolean algebra $\mathcal{P}_{fin} Y$ for $Y = \mathcal{P}_{fin} X$, is guaranteed to fail because this is an atomic Boolean algebra, whereas the free Boolean algebra on an infinite set $X$ is atomless.)

A third description comes from Stone duality (see below).

Stone duality

Classical Stone duality comes about as follows. The two-element Boolean algebra can be regarded as a Boolean algebra object $\mathbf{2}$ in the category of compact Hausdorff spaces $CH$. Thus, for each finitary Boolean algebra operation $\theta\colon \mathbf{2}^n \to \mathbf{2}$, there is a corresponding operation on the representable functor $CH(-, \mathbf{2}): CH^{op} \to Set$ given by

$$CH(-, \mathbf{2})^n \cong CH(-, \mathbf{2}^n) \stackrel{CH(-, \theta)}{\to} CH(-, \mathbf{2})$$

and therefore we obtain a lift

$$CH(-, \mathbf{2}): CH^{op} \to BoolAlg$$

A Stone space is by definition a totally disconnected compact Hausdorff space. Let $Stone \hookrightarrow CH$ denote the full subcategory of Stone spaces.

Theorem

The representable functor $CH(-, \mathbf{2}): CH^{op} \to BoolAlg$ restricts to an equivalence of categories $Stone^{op} \to BoolAlg$.

This important theorem can be exploited to give a third description of the free Boolean algebra on a set $X$:

$$Bool(X) \cong CH(2^X, \mathbf{2})$$

where $2$ denotes the 2-element compact Hausdorff space, and $2^X$ the product space $\prod_X 2$. Indeed, the inverse equivalence

$$BoolAlg^{op} \to Stone$$

takes a Boolean algebra $B$ to its spectrum, i.e., the space of Boolean algebra maps $Bool(B, 2)$ (this $2$ is the two-element Boolean algebra $\mathbb{Z}_2$!) equipped with the Zariski topology. Applied to $B = Bool(X)$, we have

$$BoolAlg(B, 2) \cong Set(X, 2) = 2^X$$

where the Zariski topology coincides with the product topology on $2^X$. By the equivalence, we therefore retrieve $Bool(X)$ as $CH(2^X, \mathbf{2})$. This in turn is identified with the Boolean algebra of clopen subsets of the generalised Cantor space $2^X$.

A second description of the inverse equivalence $BoolAlg^{op} \to Stone$ comes about through the yoga of ambimorphic objects. Namely, the Boolean compact Hausdorff space $\mathbf{2}$ can equally well be seen as a compact Hausdorff object in the category of Boolean algebras. Thus, the representable functor $Bool(-, \mathbf{2}): Bool^{op} \to Set$ lifts canonically to a functor

$$Bool^{op} \to CH$$

and in fact part of the Stone representation theorem is that this factors through the inclusion $Stone \hookrightarrow CH$ as the inverse equivalence $Bool^{op} \to Stone$. In particular this lift determines the topology, providing an description alternative to the description in terms of the Zariski topology (although they are of course the same).

In weak foundations

In constructive mathematics, while power sets are not boolean algebras, the function set $\mathbb{2}^X$ from the set $X$ to the boolean domain $\mathbb{2}$ is still a Boolean algebra, and so the definitions involving the function set $\mathbb{2}^{\mathbb{2}^X}$ is still correct. Furthermore, the explicit construction of free algebras in terms of finite subsets is still correct. Stone duality also works in constructive mathematics, but it must be done using locales instead of standard topological spaces.

In predicative mathematics, the explicit construction of free algebras works if we have general inductive object?s; the natural numbers object alone is not enough.

Related concepts

• Boolean algebra

• double power set

category: category