nLab Boolean algebra

Boolean algebras

Boolean algebras

Idea

A Boolean algebra or Boolean lattice is an algebraic structure which models classical propositional calculus, roughly the fragment of the logical calculus which deals with the basic logical connectives “and”, “or”, “implies”, and “not”.

Definitions

General

There are many known ways of defining a Boolean algebra or Boolean lattice. Here are just a few:

  • A Boolean algebra is a complemented distributive lattice.

  • A Boolean algebra is a Heyting algebra HH satisfying the law of excluded middle, which means either

    ¬¬=id:HH\neg \neg = id: H \to H

    or (equivalently)

    xHx¬x=\forall_{x \in H} x \vee \neg x = \top
  • A Boolean algebra is a lattice LL equipped with a function ¬:LL\neg: L \to L satisfying

    abciffa¬bca \wedge b \leq c \qquad iff \qquad a \leq \neg b \vee c

Explicitly

There are even two explicit definitions: order-theoretic and algebraic.

A Boolean lattice is a poset such that:

  • there is an element \top (a top element) such that xx \leq \top always holds;
  • there is an element \bot (a bottom element) such that x\bot \leq x always holds;
  • given elements aa and bb, there is an element aba \wedge b (a meet of aa and bb) such that xabx \leq a \wedge b holds iff xax \leq a and xbx \leq b;
  • given elements aa and bb, there is an element aba \vee b (a join of aa and bb) such that abxa \vee b \leq x holds iff axa \leq x and bxb \leq x;
  • given an element aa, there is an element ¬a\neg{a} (a complement of aa) such that a¬aa \wedge \neg{a} \leq \bot and a¬a\top \leq a \vee \neg{a};
  • given elements aa, bb, and cc, we have a(bc)(ab)(ac)a \wedge (b \vee c) \leq (a \wedge b) \vee (a \wedge c).

Although we don't say so, we can prove that \top, \bot, aba \wedge b, aba \vee b, and ¬a\neg{a} are unique; this makes it more clear what the last two axioms actually mean.

Notice that a poset carries at most one Boolean algebra structure, making it property-like structure. (The same is true of Heyting algebra structure.)

Alternatively, a Boolean algebra is a set equipped with elements \top and \bot, binary operations \wedge and \vee, and a unary operation ¬\neg, satisfying these identities:

  1. a=aa \wedge \top = a,
  2. a=aa \vee \bot = a,
  3. a(bc)=(ab)ca \wedge (b \wedge c) = (a \wedge b) \wedge c,
  4. a(bc)=(ab)ca \vee (b \vee c) = (a \vee b) \vee c,
  5. ab=baa \wedge b = b \wedge a,
  6. ab=baa \vee b = b \vee a,
  7. a(ab)=aa \wedge (a \vee b) = a,
  8. a(ab)=aa \vee (a \wedge b) = a,
  9. a(bc)=(ab)(ac)a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c),
  10. a(bc)=(ab)(ac)a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c),
  11. a¬a=a \wedge \neg{a} = \bot,
  12. a¬a=a \vee \neg{a} = \top.

We can recover the poset structure: aba \leq b iff ab=aa \wedge b = a. There is a certain amount of redundancy or overkill in this axiom list; for example, it suffices to give just axioms 1, 2, 5, 6, 9, 10, 11, 12.

A very distilled algebraic definition was conjectured by Herbert Robbins: any set equipped with a binary operation \vee and a unary operation ¬\neg obeying

  1. associativity: a(bc)=(ab)ca\vee \left(b\vee c\right)=\left(a\vee b\right)\vee c
  2. commutativity: ab=baa \vee b = b \vee a
  3. the Robbins equation: ¬(¬(ab)¬(a¬b))=a\neg \left(\neg \left(a\vee b\right)\vee \neg \left(a\vee \neg b\right)\right)=a

is a Boolean algebra. William McCune proved the conjecture in 1996, using the automated theorem prover EQP. A short proof was found by Allan Mann (see the references).

Principle of duality

However it is defined, the theory of Boolean algebras is self-dual in the sense that for any sentence stated in the language (,,,,,¬)(\leq, \wedge, \vee, \bot, \top, \neg), the sentence is a theorem in the theory of Boolean algebras iff the dual sentence, obtained by interchanging \wedge and \vee, \bot and \top, and replacing \leq by the opposite relation op\leq^{op}, is also a theorem.

This incredibly useful result can be rephrased in several ways; for example, if a poset BB is a Boolean algebra, then so is its opposite B opB^{op}.

Boolean rings

A Boolean ring is a ring (with identity) for which every element is idempotent: x 2=xx^2 = x. Notice that from

x 2+1=x+1=(x+1) 2=x 2+2x+1x^2 + 1 = x + 1 = (x + 1)^2 = x^2 + 2 x + 1

the equation 2x=02 x = 0 follows. Also notice that commutativity comes for free, since

x 2+y 2=x+y=(x+y) 2=x 2+xy+yx+y 2x^2 + y^2 = x + y = (x + y)^2 = x^2 + x y + y x + y^2

whence xy+yx=0=xy+xyx y + y x = 0 = x y + x y.

Parallel to the way free commutative rings are polynomial rings, which are free \mathbb{Z}-modules generated from free commutative monoids, the free Boolean ring on nn generators may be constructed, à la Beck distributive laws, as the free 2\mathbb{Z}_2-vector space 2[M n]\mathbb{Z}_2[M_n] generated from the commutative idempotent monoid M nM_n on nn generators. The latter can be identified with the power set on an nn-element set with multiplication given by intersection, and 2[M n]\mathbb{Z}_2[M_n] therefore has 2 2 n2^{2^n} elements.

The theory of Boolean algebras is equivalent to the theory of Boolean rings in the sense that their categories of models are equivalent. Given a Boolean ring, we define the operation \wedge to be multiplication, and the operation \vee by xy=x+y+xyx \vee y = x + y + x y, and the operation ¬\neg by ¬x=1+x\neg x = 1 + x. The relation xyx \leq y may be defined by the condition xy=xx y = x. In the other direction, given a Boolean algebra, we may define addition by symmetric difference: x+y=(xy)¬(xy)x + y = (x \vee y) \wedge \neg(x \wedge y). According to this equivalence, the free Boolean ring on nn generators may be identified with the Boolean algebra P(2 n)P(2^n), the power set on a set with 2 n2^n elements.

Elements of Stone duality

The equivalence of Boolean rings and Boolean algebras was exploited by Marshall Stone to give his theory of Stone duality, in which every Boolean algebra BB is a Boolean algebra of sets; more particularly the Boolean algebra of clopen (closed and open) sets of a topological space Spec(B)Spec(B), the Stone space of BB. The notation intentionally suggests that the Stone space is the underlying space of the spectrum of BB as Boolean ring, taking “spectrum” in the sense of algebraic geometry.

A Stone space may be characterized abstractly as a topological space that is compact, Hausdorff, and totally disconnected. Stone duality asserts among other things that every such space is the prime spectrum of the Boolean algebra of its clopen subsets.

Lemma

All prime ideals in BB are kernels ϕ 1(0)\phi^{-1}(0) of homomorphisms ϕ:B2\phi: B \to \mathbf{2} (and thus are maximal ideals, in bijective correspondence with ultrafilters ϕ 1(1)\phi^{-1}(1) in BB).

Proof

If pp is a prime ideal in a Boolean ring, then B/pB/p is an integral domain in which every element xx is idempotent: x(x1)=0x(x-1) = 0. Hence B/p={0,1}B/p = \{0, 1\}.

(To be continued at some point.)

Homomorphisms

Any lattice homomorphism automatically preserves ¬\neg and is therefore a Boolean algebra homomorphism.

Boolean algebras and Boolean algebra homomorphisms form a concrete category BoolAlg.

Definition via Lawvere theories

The concrete category U:BoolAlgSetU: 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 nn elements is therefore isomorphic to P(2 n)P(2^n), the power set of a 2 n2^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 n2^n.

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

Fin 2 nSet.Fin_{2^n} \to Set.

Unbiased Boolean algebras

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

Proposition

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

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

Fin +SetFin_+ \to Set

We call a product-preserving functor Fin +SetFin_+ \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 n2^n. Passing to the Cauchy completion removes that bias.

kk-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 n3^n has the same Cauchy completion Fin +Fin_+. Therefore, the category of product-preserving functors

X:Fin 3 nSetX: Fin_{3^n} \to Set

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

Similarly, for each fixed cardinality k>1k \gt 1, there is a Lawvere theory Fin k nFin_{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:Prod(Fin k n,Set)SetU_k \colon Prod(Fin_{k^n}, Set) \to Set. This concrete category is perhaps better known as the category of kk-valued Post algebras (and is better known still when the letter kk is replaced by nn).

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

BoolAlgPostAlg kM k-SetBoolAlg \simeq PostAlg_k \to M_k\text{-}Set
Proposition

For each k3k \geq 3, the forgetful functor from BoolAlgBoolAlg \to M kM_k-SetSet realizes BoolAlgBoolAlg as a full subcategory of M kM_k-Set.

See also

References

  • Allan Mann, A complete proof of the Robbins conjecture. (pdf)

Last revised on January 24, 2024 at 00:52:43. See the history of this page for a list of all contributions to it.