nLab BoolAlg

Redirected from "free Boolean algebras".
The category of Boolean algebras

The category of Boolean algebras

Definition

BoolAlgBool 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. BoolAlgBool Alg is a subcategory of Pos, in fact a replete subcategory of both DistLat and HeytAlg.

BoolAlgBool 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.

Free Boolean algebras

The free Boolean algebra Bool(X)Bool(X) generated by a finite set XX is isomorphic to the double power set 𝒫𝒫X\mathcal{P}\mathcal{P}X of XX; an element aa of XX is interpreted as the set of all those subsets of XX to which aa belongs, and the boolean algebra operations on the intersection and union as usual.

The free Boolean algebra on an arbitrary set XX 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βŠ† finXBool(S)Bool(X) = colim_{S \subseteq_{fin} X} Bool(S)

(where βŠ† fin\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)=𝒫 fin𝒫 finXBool(X) = \mathcal{P}_{fin} \mathcal{P}_{fin} X

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

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 𝒫 fin:Setβ†’Set\mathcal{P}_{fin}: Set \to Set into the monad for commutative idempotent monoids (that is, semilattices). Here we use the fact that that 𝒫 finX\mathcal{P}_{fin} X with the monoid operation given by union, is the free semilattice on XX. Call 𝒫 fin\mathcal{P}_{fin} with this monad structure MM, for β€œmultiplication”.

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

Finally, note that there is a distributive law M∘Sβ‡’S∘MM \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∘M:Setβ†’SetS \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 𝒫 fin𝒫 fin:Setβ†’Set\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∘S:Setβ†’SetM \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 BoolAlgBoolAlg.

(A more naive prescription, where one uses the usual intersection and union on the Boolean algebra 𝒫 finY\mathcal{P}_{fin} Y for Y=𝒫 finXY = \mathcal{P}_{fin} X, is guaranteed to fail because this is an atomic Boolean algebra, whereas the free Boolean algebra on an infinite set XX 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 2\mathbf{2} in the category of compact Hausdorff spaces CHCH. Thus, for each finitary Boolean algebra operation ΞΈ:2 nβ†’2\theta\colon \mathbf{2}^n \to \mathbf{2}, there is a corresponding operation on the representable functor CH(βˆ’,2):CH opβ†’SetCH(-, \mathbf{2}): CH^{op} \to Set given by

CH(βˆ’,2) nβ‰…CH(βˆ’,2 n)β†’CH(βˆ’,ΞΈ)CH(βˆ’,2)CH(-, \mathbf{2})^n \cong CH(-, \mathbf{2}^n) \stackrel{CH(-, \theta)}{\to} CH(-, \mathbf{2})

and therefore we obtain a lift

CH(βˆ’,2):CH opβ†’BoolAlgCH(-, \mathbf{2}): CH^{op} \to BoolAlg

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

Theorem

The representable functor CH(βˆ’,2):CH opβ†’BoolAlgCH(-, \mathbf{2}): CH^{op} \to BoolAlg restricts to an equivalence of categories Stone opβ†’BoolAlgStone^{op} \to BoolAlg.

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

Bool(X)β‰…CH(2 X,2)Bool(X) \cong CH(2^X, \mathbf{2})

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

BoolAlg op→StoneBoolAlg^{op} \to Stone

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

BoolAlg(B,2)β‰…Set(X,2)=2 XBoolAlg(B, 2) \cong Set(X, 2) = 2^X

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

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

Bool op→CHBool^{op} \to CH

and in fact part of the Stone representation theorem is that this factors through the inclusion Stoneβ†ͺCHStone \hookrightarrow CH as the inverse equivalence Bool opβ†’StoneBool^{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

Boolean algebras are less interesting in constructive mathematics, since power sets are not boolean algebras. However, they are still a perfectly good algebraic construct, and 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.

category: category

Last revised on May 22, 2023 at 23:26:21. See the history of this page for a list of all contributions to it.