$SEP home page$

The Mathematics of Boolean Algebra

First published Fri Jul 5, 2002; substantive revision Wed Jul 11, 2018

Boolean algebra is the algebra of two-valued logic with onlysentential connectives, or equivalently of algebras of sets underunion and complementation. The rigorous concept is that of a certainkind of algebra, analogous to the mathematical notion of agroup. This concept has roots and applications in logic(Lindenbaum-Tarski algebras and model theory), set theory (fields ofsets), topology (totally disconnected compact Hausdorff spaces),foundations of set theory (Boolean-valued models), measure theory(measure algebras), functional analysis (algebras of projections),and ring theory (Boolean rings). The study of Boolean algebrashas several aspects: structure theory, model theory of Booleanalgebras, decidability and undecidability questions for the class ofBoolean algebras, and the indicated applications. In addition,although not explained here, there are connections to other logics,subsumption as a part of special kinds of algebraic logic, finiteBoolean algebras and switching circuit theory, and Booleanmatrices.

1. Definition and simple properties

A Boolean algebra (BA) is a set $A$ together with binaryoperations + and $\cdot$ and a unary operation $-$, and elements0, 1 of $A$ such that the following laws hold: commutative andassociative laws for addition and multiplication, distributive lawsboth for multiplication over addition and for addition overmultiplication, and the following special laws:

\[\begin{align*}x + (x \cdot y) &= x \\x \cdot(x + y) &= x \\x + (-x) &= 1 \\x \cdot(-x) &= 0\end{align*}\]

These laws are better understood in terms of the basic example of aBA, consisting of a collection $A$ of subsets of a set $X$ closedunder the operations of union, intersection, complementation withrespect to $X$, with members $\varnothing$ and $X$. One caneasily derive many elementary laws from these axioms, keeping in mindthis example for motivation. Any BA has a natural partial order$\le$ defined upon it by saying that $x \le y$ if and only if $x+ y = y$. This corresponds in our main example to $\subseteq$. Ofspecial importance is the two-element BA, formed by taking the set$X$ to have just one element. The two-element BA shows the directconnection with elementary logic. The two members, 0 and 1, correspondto falsity and truth respectively. The Boolean operations then expressthe ordinary truth tables for disjunction (with $+)$, conjunction(with $\cdot)$ and negation (with $-)$. An important elementaryresult is that an equation holds in all BAs if and only if it holds inthe two-element BA. Next, we define $x \oplus y = (x \cdot -y) + (y\cdot -x)$. Then $A$ together with $\oplus$ and $\cdot$, alongwith 0 and 1, forms a ring with identity in which every element isidempotent. Conversely, given such a ring, with addition $\oplus$and multiplication, define $x + y = x \oplus y \oplus(x \cdot y)$and $-x = 1 \oplus x$. This makes the ring into a BA. These twoprocesses are inverses of one another, and show that the theory ofBoolean algebras and of rings with identity in which every element isidempotent are definitionally equivalent. This puts the theory of BAsinto a standard object of research in algebra. An atom in a BA is anonzero element $a$ such that there is no element $b$ with $0 \ltb \lt a$. A BA is atomic if every nonzero element of the BA is abovean atom. Finite BAs are atomic, but so are many infinite BAs. Underthe partial order $\le$ above, $x + y$ is the least upper bound of$x$ and $y$, and $x \cdot y$ is the greatest lower bound of$x$ and $y$. We can generalize this: $\Sigma X$ is the leastupper bound of a set $X$ of elements, and $\Pi X$ is the greatestlower bound of a set $X$ of elements. These do not exist for allsets in all Boolean algebras; if they do always exist, the Booleanalgebra is said to be complete.

2. The elementary algebraic theory

Several algebraic constructions have obvious definitions and simpleproperties for BAs: subalgebras, homomorphisms, isomorphisms, anddirect products (even of infinitely many algebras). Some otherstandard algebraic constructions are more peculiar to BAs. An ideal ina BA is a subset $I$ closed under +, with 0 as a member, and suchthat if $a \le b \in I$, then also $a \in I$. Although notimmediately obvious, this is the same as the ring-theoreticconcept. There is a dual notion of a filter (with no counterpart inrings in general). A filter is a subset $F$ closed under $\cdot$ ,having 1 as a member, and such that if $a \ge b \in F$, then also$a \in F$. An ultrafilter on $A$ is a filter $F$ with thefollowing properties: $0 \not\in F$, and for any $a \in A$, either$a \in F$ or $-a \in F$. For any $a \in A$, let

\[S(a)= \{F : F \text{ is an ultrafilter on } A \text{ and } a \in F\}.\]

Then $S$ is an isomorphism onto a BA of subsets of the set $X$ ofall ultrafilters on $A$. This establishes the basic Stonerepresentation theorem, and clarifies the origin of BAs as concretealgebras of sets. Moreover, the sets $S(a)$ can be declared to be abase for a topology on $X$, and this turns $X$ into a totallydisconnected compact Hausdorff space. This establishes a one-onecorrespondence between the class of BAs and the class of suchspaces. As a consequence, used very much in the theory of BAs, manytopological theorems and concepts have consequences for BAs. If $x$is an element of a BA, we let $0x = -x$ and $1x = x$. If$(x$(0), $\ldots x(m - 1))$ is a finite sequence of elements of aBA $A$, then every element of the subalgebra of $A$ generated by$\{x(0), \ldots, x(m - 1)\}$ can be written as a sum of monomials$e(0)x(0) \cdot \ldots \cdot e(m - 1)x(m - 1)$ for $e$ in some setof functions mapping $m = \{0,\ldots , m - 1\}$ into $2 = \{0,1\}$. This is an algebraic expression of the disjunctive normal formtheorem of sentential logic. A function $f$ from a set $X$ ofgenerators of a BA $A$ into a BA $B$ can be extended to ahomomorphism if and only if

\[e(0)x(0) \cdot \ldots \cdot e(m - 1)x(m - 1) = 0\]

always implies that

\[e(0)f(x(0)) \cdot \ldots \cdot e(m - 1)f(x(m - 1)) = 0.\]

This is Sikorski’s extension criterion. Every BA $A$ can beembedded in a complete BA $B$ in such a way that every element of$B$ is the least upper bound of a set of elements of $A$. $B$ isunique up to $A$-isomorphism, and is called the completion of$A$. If $f$ is a homomorphism from a BA $A$ into a complete BA$B$, and if $A$ is a subalgebra of $C$, then $f$ can beextended to a homomorphism of $C$ into $B$. This isSikorski’s extension theorem. Another general algebraic notionwhich applies to Boolean algebras is the notion of a freealgebra. This can be concretely constructed for BAs. Namely, the freeBA on $\kappa$ is the BA of closed-open subsets of the two elementdiscrete space raised to the $\kappa$ power.

3. Special classes of Boolean algebras

There are many special classes of Boolean algebra which are importantboth for the intrinsic theory of BAs and forapplications:

Atomic BAs, already mentioned above.
Atomless BAs, which are defined to beBAs without any atoms. For example, any infinitefree BA is atomless.
Complete BAs, defined above. These are speciallyimportant in the foundations of set theory.
Interval algebras. These are derived from linearly ordered sets$(L, \lt)$ with a first element as follows. One takes the smallest algebra of subsets of $L$ containing all of the half-openintervals [$a, b)$ with $a$ in $L$ and$b$ in $L$ or equal to $\infty$. These BAs are useful inthe study of Lindenbaum-Tarski algebras. Every countable BA isisomorphic to an interval algebra, and thus a countable BA can bedescribed by indicating an ordered set such that it is isomorphic tothe corresponding interval algebra.
Tree algebras. A tree is a partially ordered set $(T, \lt)$ inwhich the set of predecessors of any element is well-ordered. Givensuch a tree, one considers the algebra of subsets of $T$ generatedby all sets of the form $\{b : a \le b\}$ for some $a$ in$T$.
Superatomic BAs. These are BAswhich are not only atomic, but are such that each subalgebra andhomomorphic image is atomic.

4. Structure theory and cardinal functions on Boolean algebras

Much of the deeper theory of Boolean algebras, telling about theirstructure and classification, can be formulated in terms of certainfunctions defined for all Boolean algebras, with infinite cardinalsas values. We define some of the more important of these cardinalfunctions, and state some of the known structural facts, mostlyformulated in terms of them

The cellularity $c(A)$ of a BA is the supremum ofthe cardinalities of sets of pairwise disjoint elements of $A$.
A subset $X$ of a BA $A$ is independent if$X$ is a set of free generators of the subalgebra that itgenerates. The independence of $A$ is the supremum ofcardinalities of independent subsets of $A$.
A subset $X$ of a BA $A$ is dense in $A$ ifevery nonzero element of $A$ is $\ge$ a nonzero element of$X$. The $\pi$-weight of $A$ is the smallest cardinalityof a dense subset of $A$.
Two elements $x, y$ of $A$ are incomparableif neither one is $\le$ the other. The supremum of cardinalities ofsubset $X$ of $A$ consisting of pairwise incomparableelements is the incomparability of $A$.
A subset $X$ of $A$ is irredundant if no element of$X$ is in the subalgebra generated by the others.

An important fact concerning cellularity is the Erdős-Tarskitheorem: if the cellularity of a BA is a singular cardinal, then thereactually is a set of disjoint elements of that size; for cellularityregular limit (inaccessible), there are counterexamples. Everyinfinite complete BA has an independent subset of the same size as thealgebra. Every infinite BA $A$ has an irredundant incomparablesubset whose size is the $\pi$-weight of $A$. Every intervalalgebra has countable independence. A superatomic algebra does noteven have an infinite independent subset. Every tree algebra can beembedded in an interval algebra. A BA with only the identityautomorphism is called rigid. There exist rigid complete BAs, alsorigid interval algebras and rigid tree algebras.

More recently, many cardinal functions of min-max type have beenstudied. For example, small independence is the smallest size of aninfinite maximal independent set; and small cellularity is thesmallest size of an infinite partition of unity.

5. Decidability and undecidability questions

A basic result of Tarski is that the elementary theory of Booleanalgebras is decidable. Even the theory of Boolean algebras with adistinguished ideal is decidable. On the other hand, the theory of aBoolean algebra with a distinguished subalgebra is undecidable. Boththe decidability results and undecidablity results extend in variousways to Boolean algebras in extensions of first-order logic.

6. Lindenbaum-Tarski algebras

A very important construction, which carries over to many logics andmany algebras other than Boolean algebras, is the construction of aBoolean algebra associated with the sentences in some logic. Thesimplest case is sentential logic. Here there are sentence symbols,and common connectives building up longer sentences from them:disjunction, conjunction, and negation. Given a set $A$ of sentencesin this language, two sentences $s$ and $t$ are equivalent modulo$A$ if and only if the biconditional between them is a logicalconsequence of $A$. The equivalence classes can be made into a BAsuch that + corresponds to disjunction, $\cdot$ to conjunction, and$-$ to negation. Any BA is isomorphic to one of this form. One cando something similar for a first-order theory. Let $T$ be afirst-order theory in a first-order language $L$. We call formulas$\phi$ and $\psi$ equivalent provided that $T \vdash \phi\leftrightarrow \psi$. The equivalence class of a sentence $\phi$is denoted by [$\phi$]. Let $A$ be the collection of allequivalence classes under this equivalence relation. We can make $A$into a BA by the following definitions, which are easilyjustified:

\[\begin{align*}[\phi] + [\psi] &= [\phi \vee \psi] \\[\phi] \cdot[\psi] &= [\phi \wedge \psi] \\-[\phi] &= [\neg \phi] \\0 &= [\mathrm{F}] \\1 &= [\mathrm{T}]\end{align*}\]

Every BA is isomorphic to a Lindenbaum-Tarskialgebra. However, one of the most important uses of these classicalLindenbaum-Tarski algebras is to describe them for important theories(usually decidable theories). For countable languages this can bedone by describing their isomorphic interval algebras. Generally thisgives a thorough knowledge of the theory. Some examples are:

	Theory	Isomorphic to interval algebra on
(1)	essentially undecidable theory	$\mathbb{Q}$, the rationals
(2)	BAs	$\mathbb{N} \times \mathbb{N}$, square of the positive integers, ordered lexicographically
(3)	linear orders	$\mathbf{A} \times \mathbb{Q}$ ordered antilexicographically, where $\mathbf{A}$ is $\mathbb{N}^\mathbb{N}$ in its usual order
(4)	abelian groups	$(\mathbb{Q} + \mathbf{A}) \times \mathbb{Q}$

7. Boolean-valued models

In model theory, one can take values in any complete BA rather thanthe two-element BA. This Boolean-valued model theory was developedaround 1950–1970, but has not been worked on much since. But aspecial case, Boolean-valued models for set theory, is very much atthe forefront of current research in set theory. It actually forms anequivalent way of looking at the forcing construction of Cohen, andhas some technical advantages and disadvantages. Philosophically itseems more satisfactory than the forcing concept. We describe thisset theory case here; it will then become evident why only completeBAs are considered. Let B be a complete BA. First we define theBoolean valued universe $V(B)$. The ordinaryset-theoretic universe can be identified with $V$(2), where 2is the 2-element BA. The definition is by transfinite recursion, where$\alpha , \beta$ are ordinals and $\lambda$ is a limit ordinal:

\[\begin{align*}V(B, 0) &= \varnothing \\V(B, \alpha + 1) &= \{ f : \dom(f) \subset V(B, \alpha) \text{ and } \range(f) \subset B \} \\V(B, \lambda) &= \bigcup_{\beta \lt \lambda} V(B, \beta).\end{align*}\]

where $\dom(f)$ is the domain of function $f$ and $\range(f)$ isthe range of function $f$. The $B$-valued universe is the properclass $V(B)$ which is the union of all of these $V$s. Next, onedefines by a rather complicated transfinite recursion overwell-founded sets the value of a set-theoretic formula with elementsof the Boolean valued universe assigned to its free variables:

\[\begin{align*}\val{x \in y} &= \sum_{t \in \dom(y)} \val{x=t}\cdot y(t) \\\val{x \subseteq y} &= \prod_{t \in \dom(x)} -x(t) + \val{t \in y} \\\val{x = y} &= \val{x \subseteq y} \cdot \val{y \subseteq x} \\\val{\neg \phi} &= -\val{\phi} \\\val{\phi \vee \psi} &= \val{\phi} + \val{\psi} \\\val{\exists x\phi(x)} &= \sum_{a \in V(B)} \val{\phi(a)}.\end{align*}\]

Bibliography

Halmos, P., 1963,Lectures on Boolean Algebras,Princeton: Van Nostrand
Heindorf, L., and Shapiro, L., 1994,Nearly projective Booleanalgebras, Lecture Notes in Mathematics no. 1596, Berlin:Springer-Verlag
Jech, T., 1997,Set Theory, 2nd corrected edition,Berlin, New York: Springer-Verlag
Monk, J. D., and R. Bonnet (eds.), 1989,Handbook of Booleanalgebras, 3 volumes, Amsterdam: North-Holland.
Monk, J. D., 2014,Cardinal Invariants on Boolean Algebras,Second Revised Edition, Basel: Birkaüser

Academic Tools

$sep man icon$ How to cite this entry.
$sep man icon$ Preview the PDF version of this entry at theFriends of the SEP Society.
$inpho icon$ Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO).
$phil papers icon$ Enhanced bibliography for this entryatPhilPapers, with links to its database.

Other Internet Resources

[Please contact the author with suggestions.]

Open access to the SEP is made possible by a world-wide funding initiative.
The Encyclopedia Now Needs Your Support
Please Read How You Can Help Keep the Encyclopedia Free

Browse

About

Support SEP

Mirror Sites

View this site from another server:

USA (Main Site)Philosophy, Stanford University

Info about mirror sites

Library of Congress Catalog Data: ISSN 1095-5054

Movatterモバイル変換