Boolean algebras canonically defined

Boolean algebra treats the equational theory of the maximal two-element finitary algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras.[3] These terms are defined as follows.

An algebra is a family of operations on a set, called the underlying set of the algebra. We take the underlying set of the Boolean prototype to be {0,1}.

An algebra is finitary when each of its operations takes only finitely many arguments. For the prototype each argument of an operation is either 0 or 1, as is the result of the operation. The maximal such algebra consists of all finitary operations on {0,1}.

The number of arguments taken by each operation is called the arity of the operation. An operation on {0,1} of arity n, or n-ary operation, can be applied to any of 2ⁿ possible values for its n arguments. For each choice of arguments, the operation may return 0 or 1, whence there are 2²ⁿ n-ary operations.

The prototype therefore has two operations taking no arguments, called zeroary or nullary operations, namely zero and one. It has four unary operations, two of which are constant operations, another is the identity, and the most commonly used one, called negation, returns the opposite of its argument: 1 if 0, 0 if 1. It has sixteen binary operations; again two of these are constant, another returns its first argument, yet another returns its second, one is called conjunction and returns 1 if both arguments are 1 and otherwise 0, another is called disjunction and returns 0 if both arguments are 0 and otherwise 1, and so on. The number of (n+1)-ary operations in the prototype is the square of the number of n-ary operations, so there are 16² = 256 ternary operations, 256² = 65,536 quaternary operations, and so on.

A family is indexed by an index set. In the case of a family of operations forming an algebra, the indices are called operation symbols, constituting the language of that algebra. The operation indexed by each symbol is called the denotation or interpretation of that symbol. Each operation symbol specifies the arity of its interpretation, whence all possible interpretations of a symbol have the same arity. In general it is possible for an algebra to interpret distinct symbols with the same operation, but this is not the case for the prototype, whose symbols are in one-one correspondence with its operations. The prototype therefore has 2²ⁿ n-ary operation symbols, called the Boolean operation symbols and forming the language of Boolean algebra. Only a few operations have conventional symbols, such as ¬ for negation, ∧ for conjunction, and ∨ for disjunction.[4] It is convenient to consider the i-th n-ary symbol to be ⁿf_i as done below in the section on truth tables.

An equational theory in a given language consists of equations between terms built up from variables using symbols of that language. Typical equations in the language of Boolean algebra are x∧y = y∧x, x∧x = x, x∧¬x = y∧¬y, and x∧y = x.

An algebra satisfies an equation when the equation holds for all possible values of its variables in that algebra when the operation symbols are interpreted as specified by that algebra. The laws of Boolean algebra are the equations in the language of Boolean algebra satisfied by the prototype. The first three of the above examples are Boolean laws, but not the fourth since 1∧0 ≠ 1.

The equational theory of an algebra is the set of all equations satisfied by the algebra. The laws of Boolean algebra therefore constitute the equational theory of the Boolean prototype.

A model of a theory is an algebra interpreting the operation symbols in the language of the theory and satisfying the equations of the theory.

A Boolean algebra is any model of the laws of Boolean algebra.

That is, a Boolean algebra is a set and a family of operations thereon interpreting the Boolean operation symbols and satisfying the same laws as the Boolean prototype.[5]

If we define a homologue of an algebra to be a model of the equational theory of that algebra, then a Boolean algebra can be defined as any homologue of the prototype.

Example 1. The Boolean prototype is a Boolean algebra, since trivially it satisfies its own laws. It is thus the prototypical Boolean algebra. We did not call it that initially in order to avoid any appearance of circularity in the definition.

The operations need not be all explicitly stated. A basis is any set from which the remaining operations can be obtained by composition. A "Boolean algebra" may be defined from any of several different bases. Three bases for Boolean algebra are in common use, the lattice basis, the ring basis, and the Sheffer stroke or NAND basis. These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.

• The lattice basis originated in the 19th century with the work of Boole, Peirce, and others seeking an algebraic formalization of logical thought processes.
• The ring basis emerged in the 20th century with the work of Zhegalkin and Stone and became the basis of choice for algebraists coming to the subject from a background in abstract algebra. Most treatments of Boolean algebra assume the lattice basis, a notable exception being Halmos[1963] whose linear algebra background evidently endeared the ring basis to him.[6]
• Since all finitary operations on {0,1} can be defined in terms of the Sheffer stroke NAND (or its dual NOR), the resulting economical basis has become the basis of choice for analyzing digital circuits, in particular gate arrays in digital electronics.

The common elements of the lattice and ring bases are the constants 0 and 1, and an associative commutative binary operation, called meet x∧y in the lattice basis, and multiplication xy in the ring basis. The distinction is only terminological. The lattice basis has the further operations of join, x∨y, and complement, ¬x. The ring basis has instead the arithmetic operation x⊕y of addition (the symbol ⊕ is used in preference to + because the latter is sometimes given the Boolean reading of join).

To be a basis is to yield all other operations by composition, whence any two bases must be intertranslatable. The lattice basis translates x∨y to the ring basis as x⊕y⊕xy, and ¬x as x⊕1. Conversely the ring basis translates x⊕y to the lattice basis as (x∨y)∧¬(x∧y).

Both of these bases allow Boolean algebras to be defined via a subset of the equational properties of the Boolean operations. For the lattice basis, it suffices to define a Boolean algebra as a distributive lattice satisfying x∧¬x = 0 and x∨¬x = 1, called a complemented distributive lattice. The ring basis turns a Boolean algebra into a Boolean ring, namely a ring satisfying x² = x.

Emil Post gave a necessary and sufficient condition for a set of operations to be a basis for the nonzeroary Boolean operations. A nontrivial property is one shared by some but not all operations making up a basis. Post listed five nontrivial properties of operations, identifiable with the five Post's classes, each preserved by composition, and showed that a set of operations formed a basis if, for each property, the set contained an operation lacking that property. (The converse of Post's theorem, extending "if" to "if and only if," is the easy observation that a property from among these five holding of every operation in a candidate basis will also hold of every operation formed by composition from that candidate, whence by nontriviality of that property the candidate will fail to be a basis.) Post's five properties are:

• monotone, no 0-1 input transition can cause a 1-0 output transition;
• affine, representable with Zhegalkin polynomials that lack bilinear or higher terms, e.g. x⊕y⊕1 but not xy;
• self-dual, so that complementing all inputs complements the output, as with x, or the median operator xy⊕yz⊕zx, or their negations;
• strict (mapping the all-zeros input to zero);
• costrict (mapping all-ones to one).

The NAND (dually NOR) operation lacks all these, thus forming a basis by itself.

The finitary operations on {0,1} may be exhibited as truth tables, thinking of 0 and 1 as the truth values false and true.[7] They can be laid out in a uniform and application-independent way that allows us to name, or at least number, them individually.[8] These names provide a convenient shorthand for the Boolean operations. The names of the n-ary operations are binary numbers of 2ⁿ bits. There being 2²ⁿ such operations, one cannot ask for a more succinct nomenclature. Note that each finitary operation can be called a switching function.

This layout and associated naming of operations is illustrated here in full for arities from 0 to 2.

Truth tables for the Boolean operations of arity up to 2

Constants ${\displaystyle {}^{0}\!f_{0}}$ ${\displaystyle {}^{0}\!f_{1}}$ 0 1

Unary operations ${\displaystyle x_{0}}$ ${\displaystyle {}^{1}\!f_{0}}$ ${\displaystyle {}^{1}\!f_{1}}$ ${\displaystyle {}^{1}\!f_{2}}$ ${\displaystyle {}^{1}\!f_{3}}$ 0 0 1 0 1 1 0 0 1 1

Binary operations ${\displaystyle x_{0}}$ ${\displaystyle x_{1}}$ ${\displaystyle {}^{2}\!f_{0}}$ ${\displaystyle {}^{2}\!f_{1}}$ ${\displaystyle {}^{2}\!f_{2}}$ ${\displaystyle {}^{2}\!f_{3}}$ ${\displaystyle {}^{2}\!f_{4}}$ ${\displaystyle {}^{2}\!f_{5}}$ ${\displaystyle {}^{2}\!f_{6}}$ ${\displaystyle {}^{2}\!f_{7}}$ ${\displaystyle {}^{2}\!f_{8}}$ ${\displaystyle {}^{2}\!f_{9}}$ ${\displaystyle {}^{2}\!f_{10}}$ ${\displaystyle {}^{2}\!f_{11}}$ ${\displaystyle {}^{2}\!f_{12}}$ ${\displaystyle {}^{2}\!f_{13}}$ ${\displaystyle {}^{2}\!f_{14}}$ ${\displaystyle {}^{2}\!f_{15}}$ 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

These tables continue at higher arities, with 2ⁿ rows at arity n, each row giving a valuation or binding of the n variables x₀,...x_n−1 and each column headed ⁿf_i giving the value ⁿf_i(x₀,...,x_n−1) of the i-th n-ary operation at that valuation. The operations include the variables, for example ¹f₂ is x₀ while ²f₁₀ is x₀ (as two copies of its unary counterpart) and ²f₁₂ is x₁ (with no unary counterpart). Negation or complement ¬x₀ appears as ¹f₁ and again as ²f₅, along with ²f₃ (¬x₁, which did not appear at arity 1), disjunction or union x₀∨x₁ as ²f₁₄, conjunction or intersection x₀∧x₁ as ²f₈, implication x₀→x₁ as ²f₁₃, exclusive-or symmetric difference x₀⊕x₁ as ²f₆, set difference x₀−x₁ as ²f₂, and so on.

As a minor detail important more for its form than its content, the operations of an algebra are traditionally organized as a list. Although we are here indexing the operations of a Boolean algebra by the finitary operations on {0,1}, the truth-table presentation above serendipitously orders the operations first by arity and second by the layout of the tables for each arity. This permits organizing the set of all Boolean operations in the traditional list format. The list order for the operations of a given arity is determined by the following two rules.

(i) The i-th row in the left half of the table is the binary representation of i with its least significant or 0-th bit on the left ("little-endian" order, originally proposed by Alan Turing, so it would not be unreasonable to call it Turing order).

(ii) The j-th column in the right half of the table is the binary representation of j, again in little-endian order. In effect the subscript of the operation is the truth table of that operation. By analogy with Gödel numbering of computable functions one might call this numbering of the Boolean operations the Boole numbering.

When programming in C or Java, bitwise disjunction is denoted x|y, conjunction x&y, and negation ~x. A program can therefore represent for example the operation x∧(y∨z) in these languages as x&(y|z), having previously set x = 0xaa, y = 0xcc, and z = 0xf0 (the "0x" indicates that the following constant is to be read in hexadecimal or base 16), either by assignment to variables or defined as macros. These one-byte (eight-bit) constants correspond to the columns for the input variables in the extension of the above tables to three variables. This technique is almost universally used in raster graphics hardware to provide a flexible variety of ways of combining and masking images, the typical operations being ternary and acting simultaneously on source, destination, and mask bits.

The n-ary Boolean operations themselves constitute a power set algebra 2^W, namely when W is taken to be the set of 2ⁿ valuations of the n inputs. In terms of the naming system of operations ⁿf_i where i in binary is a column of a truth table, the columns can be combined with Boolean operations of any arity to produce other columns present in the table. That is, we can apply any Boolean operation of arity m to m Boolean operations of arity n to yield a Boolean operation of arity n, for any m and n.

The practical significance of this convention for both software and hardware is that n-ary Boolean operations can be represented as words of the appropriate length. For example, each of the 256 ternary Boolean operations can be represented as an unsigned byte. The available logical operations such as AND and OR can then be used to form new operations. If we take x, y, and z (dispensing with subscripted variables for now) to be 10101010, 11001100, and 11110000 respectively (170, 204, and 240 in decimal, 0xaa, 0xcc, and 0xf0 in hexadecimal), their pairwise conjunctions are x∧y = 10001000, y∧z = 11000000, and z∧x = 10100000, while their pairwise disjunctions are x∨y = 11101110, y∨z = 11111100, and z∨x = 11111010. The disjunction of the three conjunctions is 11101000, which also happens to be the conjunction of three disjunctions. We have thus calculated, with a dozen or so logical operations on bytes, that the two ternary operations

${\displaystyle (x\land y)\lor (y\land z)\lor (z\land x)}$

and

${\displaystyle (x\lor y)\land (y\lor z)\land (z\lor x)}$

are actually the same operation. That is, we have proved the equational identity

${\displaystyle (x\land y)\lor (y\land z)\lor (z\land x)=(x\lor y)\land (y\lor z)\land (z\lor x)}$,

for the two-element Boolean algebra. By the definition of "Boolean algebra" this identity must therefore hold in every Boolean algebra.

This ternary operation incidentally formed the basis for Grau's [1947] ternary Boolean algebras, which he axiomatized in terms of this operation and negation. The operation is symmetric, meaning that its value is independent of any of the 3! = 6 permutations of its arguments. The two halves of its truth table 11101000 are the truth tables for ∨, 1110, and ∧, 1000, so the operation can be phrased as if z then x∨y else x∧y. Since it is symmetric it can equally well be phrased as either of if x then y∨z else y∧z, or if y then z∨x else z∧x. Viewed as a labeling of the 8-vertex 3-cube, the upper half is labeled 1 and the lower half 0; for this reason it has been called the median operator, with the evident generalization to any odd number of variables (odd in order to avoid the tie when exactly half the variables are 0).

The technique we just used to prove an identity of Boolean algebra can be generalized to all identities in a systematic way that can be taken as a sound and complete axiomatization of, or axiomatic system for, the equational laws of Boolean logic. The customary formulation of an axiom system consists of a set of axioms that "prime the pump" with some initial identities, along with a set of inference rules for inferring the remaining identities from the axioms and previously proved identities. In principle it is desirable to have finitely many axioms; however as a practical matter it is not necessary since it is just as effective to have a finite axiom schema having infinitely many instances each of which when used in a proof can readily be verified to be a legal instance, the approach we follow here.

Boolean identities are assertions of the form s = t where s and t are n-ary terms, by which we shall mean here terms whose variables are limited to x₀ through x_n-1. An n-ary term is either an atom or an application. An application ^mf_i(t₀,...,t_m-1) is a pair consisting of an m-ary operation ^mf_i and a list or m-tuple (t₀,...,t_m-1) of m n-ary terms called operands.

Associated with every term is a natural number called its height. Atoms are of zero height, while applications are of height one plus the height of their highest operand.

Now what is an atom? Conventionally an atom is either a constant (0 or 1) or a variable x_i where 0 ≤ i < n. For the proof technique here it is convenient to define atoms instead to be n-ary operations ⁿf_i, which although treated here as atoms nevertheless mean the same as ordinary terms of the exact form ⁿf_i(x₀,...,x_n-1) (exact in that the variables must listed in the order shown without repetition or omission). This is not a restriction because atoms of this form include all the ordinary atoms, namely the constants 0 and 1, which arise here as the n-ary operations ⁿf₀ and ⁿf₋₁ for each n (abbreviating 2²ⁿ−1 to −1), and the variables x₀,...,x_n-1 as can be seen from the truth tables where x₀ appears as both the unary operation ¹f₂ and the binary operation ²f₁₀ while x₁ appears as ²f₁₂.

The following axiom schema and three inference rules axiomatize the Boolean algebra of n-ary terms.

A1. ^mf_i(ⁿf_j0,...,ⁿf_jm-1) = ⁿf_ioĵ where (ioĵ)_v = i_ĵv, with ĵ being j transpose, defined by (ĵ_v)_u = (j_u)_v.

R1. With no premises infer t = t.

R2. From s = u and t = u infer s = t where s, t, and u are n-ary terms.

R3. From s₀ = t₀ , ... , s_m-1 = t_m-1 infer ^mf_i(s₀,...,s_m-1) = ^mf_i(t₀,...,t_m-1), where all terms s_i, t_i are n-ary.

The meaning of the side condition on A1 is that ioĵ is that 2ⁿ-bit number whose v-th bit is the ĵ_v-th bit of i, where the ranges of each quantity are u: m, v: 2ⁿ, j_u: 2²ⁿ, and ĵ_v: 2^m. (So j is an m-tuple of 2ⁿ-bit numbers while ĵ as the transpose of j is a 2ⁿ-tuple of m-bit numbers. Both j and ĵ therefore contain m2ⁿ bits.)

A1 is an axiom schema rather than an axiom by virtue of containing metavariables, namely m, i, n, and j₀ through j_m-1. The actual axioms of the axiomatization are obtained by setting the metavariables to specific values. For example, if we take m = n = i = j₀ = 1, we can compute the two bits of ioĵ from i₁ = 0 and i₀ = 1, so ioĵ = 2 (or 10 when written as a two-bit number). The resulting instance, namely ¹f₁(¹f₁) = ¹f₂, expresses the familiar axiom ¬¬x = x of double negation. Rule R3 then allows us to infer ¬¬¬x = ¬x by taking s₀ to be ¹f₁(¹f₁) or ¬¬x₀, t₀ to be ¹f₂ or x₀, and ^mf_i to be ¹f₁ or ¬.

For each m and n there are only finitely many axioms instantiating A1, namely 2^2m × (2²ⁿ)^m. Each instance is specified by 2^m+m2ⁿ bits.

We treat R1 as an inference rule, even though it is like an axiom in having no premises, because it is a domain-independent rule along with R2 and R3 common to all equational axiomatizations, whether of groups, rings, or any other variety. The only entity specific to Boolean algebras is axiom schema A1. In this way when talking about different equational theories we can push the rules to one side as being independent of the particular theories, and confine attention to the axioms as the only part of the axiom system characterizing the particular equational theory at hand.

This axiomatization is complete, meaning that every Boolean law s = t is provable in this system. One first shows by induction on the height of s that every Boolean law for which t is atomic is provable, using R1 for the base case (since distinct atoms are never equal) and A1 and R3 for the induction step (s an application). This proof strategy amounts to a recursive procedure for evaluating s to yield an atom. Then to prove s = t in the general case when t may be an application, use the fact that if s = t is an identity then s and t must evaluate to the same atom, call it u. So first prove s = u and t = u as above, that is, evaluate s and t using A1, R1, and R3, and then invoke R2 to infer s = t.

In A1, if we view the number n^m as the function type m→n, and m_n as the application m(n), we can reinterpret the numbers i, j, ĵ, and ioĵ as functions of type i: (m→2)→2, j: m→((n→2)→2), ĵ: (n→2)→(m→2), and ioĵ: (n→2)→2. The definition (ioĵ)_v = i_ĵv in A1 then translates to (ioĵ)(v) = i(ĵ(v)), that is, ioĵ is defined to be composition of i and ĵ understood as functions. So the content of A1 amounts to defining term application to be essentially composition, modulo the need to transpose the m-tuple j to make the types match up suitably for composition. This composition is the one in Lawvere's previously mentioned category of power sets and their functions. In this way we have translated the commuting diagrams of that category, as the equational theory of Boolean algebras, into the equational consequences of A1 as the logical representation of that particular composition law.

Underlying every Boolean algebra B is a partially ordered set or poset (B,≤). The partial order relation is defined by x ≤ y just when x = x∧y, or equivalently when y = x∨y. Given a set X of elements of a Boolean algebra, an upper bound on X is an element y such that for every element x of X, x ≤ y, while a lower bound on X is an element y such that for every element x of X, y ≤ x.

A sup of X is a least upper bound on X, namely an upper bound on X that is less or equal to every upper bound on X. Dually an (inf) of X is a greatest lower bound on X. The sup of x and y always exists in the underlying poset of a Boolean algebra, being x∨y, and likewise their inf exists, namely x∧y. The empty sup is 0 (the bottom element) and the empty inf is 1 (top). It follows that every finite set has both a sup and an inf. Infinite subsets of a Boolean algebra may or may not have a sup and/or an inf; in a power set algebra they always do.

Any poset (B,≤) such that every pair x,y of elements has both a sup and an inf is called a lattice. We write x∨y for the sup and x∧y for the inf. The underlying poset of a Boolean algebra always forms a lattice. The lattice is said to be distributive when x∧(y∨z) = (x∧y)∨(x∧z), or equivalently when x∨(y∧z) = (x∨y)∧(x∨z), since either law implies the other in a lattice. These are laws of Boolean algebra whence the underlying poset of a Boolean algebra forms a distributive lattice.

Given a lattice with a bottom element 0 and a top element 1, a pair x,y of elements is called complementary when x∧y = 0 and x∨y = 1, and we then say that y is a complement of x and vice versa. Any element x of a distributive lattice with top and bottom can have at most one complement. When every element of a lattice has a complement the lattice is called complemented. It follows that in a complemented distributive lattice, the complement of an element always exists and is unique, making complement a unary operation. Furthermore, every complemented distributive lattice forms a Boolean algebra, and conversely every Boolean algebra forms a complemented distributive lattice. This provides an alternative definition of a Boolean algebra, namely as any complemented distributive lattice. Each of these three properties can be axiomatized with finitely many equations, whence these equations taken together constitute a finite axiomatization of the equational theory of Boolean algebras.

In a class of algebras defined as all the models of a set of equations, it is usually the case that some algebras of the class satisfy more equations than just those needed to qualify them for the class. The class of Boolean algebras is unusual in that, with a single exception, every Boolean algebra satisfies exactly the Boolean identities and no more. The exception is the one-element Boolean algebra, which necessarily satisfies every equation, even x = y, and is therefore sometimes referred to as the inconsistent Boolean algebra.

A Boolean homomorphism is a function h: A→B between Boolean algebras A,B such that for every Boolean operation ^mf_i:

$${\displaystyle h(^{m}\!f_{i}(x_{0},...,x_{m-1}))={}^{m}\!f_{i}(h(x_{0},...,x_{m-1}))}$$

The category Bool of Boolean algebras has as objects all Boolean algebras and as morphisms the Boolean homomorphisms between them.

There exists a unique homomorphism from the two-element Boolean algebra 2 to every Boolean algebra, since homomorphisms must preserve the two constants and those are the only elements of 2. A Boolean algebra with this property is called an initial Boolean algebra. It can be shown that any two initial Boolean algebras are isomorphic, so up to isomorphism 2 is the initial Boolean algebra.

In the other direction, there may exist many homomorphisms from a Boolean algebra B to 2. Any such homomorphism partitions B into those elements mapped to 1 and those to 0. The subset of B consisting of the former is called an ultrafilter of B. When B is finite its ultrafilters pair up with its atoms; one atom is mapped to 1 and the rest to 0. Each ultrafilter of B thus consists of an atom of B and all the elements above it; hence exactly half the elements of B are in the ultrafilter, and there as many ultrafilters as atoms.

For infinite Boolean algebras the notion of ultrafilter becomes considerably more delicate. The elements greater than or equal to an atom always form an ultrafilter, but so do many other sets; for example, in the Boolean algebra of finite and cofinite sets of integers, the cofinite sets form an ultrafilter even though none of them are atoms. Likewise, the powerset of the integers has among its ultrafilters the set of all subsets containing a given integer; there are countably many of these "standard" ultrafilters, which may be identified with the integers themselves, but there are uncountably many more "nonstandard" ultrafilters. These form the basis for nonstandard analysis, providing representations for such classically inconsistent objects as infinitesimals and delta functions.

Recall the definition of sup and inf from the section above on the underlying partial order of a Boolean algebra. A complete Boolean algebra is one every subset of which has both a sup and an inf, even the infinite subsets. Gaifman [1964] and Hales [1964] independently showed that infinite free complete Boolean algebras do not exist. This suggests that a logic with set-sized-infinitary operations may have class-many terms—just as a logic with finitary operations may have infinitely many terms.

There is however another approach to introducing infinitary Boolean operations: simply drop "finitary" from the definition of Boolean algebra. A model of the equational theory of the algebra of all operations on {0,1} of arity up to the cardinality of the model is called a complete atomic Boolean algebra, or CABA. (In place of this awkward restriction on arity we could allow any arity, leading to a different awkwardness, that the signature would then be larger than any set, that is, a proper class. One benefit of the latter approach is that it simplifies the definition of homomorphism between CABAs of different cardinality.) Such an algebra can be defined equivalently as a complete Boolean algebra that is atomic, meaning that every element is a sup of some set of atoms. Free CABAs exist for all cardinalities of a set V of generators, namely the power set algebra 2^2V, this being the obvious generalization of the finite free Boolean algebras. This neatly rescues infinitary Boolean logic from the fate the Gaifman–Hales result seemed to consign it to.

The nonexistence of free complete Boolean algebras can be traced to failure to extend the equations of Boolean logic suitably to all laws that should hold for infinitary conjunction and disjunction, in particular the neglect of distributivity in the definition of complete Boolean algebra. A complete Boolean algebra is called completely distributive when arbitrary conjunctions distribute over arbitrary disjunctions and vice versa. A Boolean algebra is a CABA if and only if it is complete and completely distributive, giving a third definition of CABA. A fourth definition is as any Boolean algebra isomorphic to a power set algebra.

A complete homomorphism is one that preserves all sups that exist, not just the finite sups, and likewise for infs. The category CABA of all CABAs and their complete homomorphisms is dual to the category of sets and their functions, meaning that it is equivalent to the opposite of that category (the category resulting from reversing all morphisms). Things are not so simple for the category Bool of Boolean algebras and their homomorphisms, which Marshall Stone showed in effect (though he lacked both the language and the conceptual framework to make the duality explicit) to be dual to the category of totally disconnected compact Hausdorff spaces, subsequently called Stone spaces.

Another infinitary class intermediate between Boolean algebras and complete Boolean algebras is the notion of a sigma-algebra. This is defined analogously to complete Boolean algebras, but with sups and infs limited to countable arity. That is, a sigma-algebra is a Boolean algebra with all countable sups and infs. Because the sups and infs are of bounded cardinality, unlike the situation with complete Boolean algebras, the Gaifman-Hales result does not apply and free sigma-algebras do exist. Unlike the situation with CABAs however, the free countably generated sigma algebra is not a power set algebra.

We have already encountered several definitions of Boolean algebra, as a model of the equational theory of the two-element algebra, as a complemented distributive lattice, as a Boolean ring, and as a product-preserving functor from a certain category (Lawvere). Two more definitions worth mentioning are:.

Stone (1936)

A Boolean algebra is the set of all clopen sets of a topological space. It is no limitation to require the space to be a totally disconnected compact Hausdorff space, or Stone space, that is, every Boolean algebra arises in this way, up to isomorphism. Moreover, if the two Boolean algebras formed as the clopen sets of two Stone spaces are isomorphic, so are the Stone spaces themselves, which is not the case for arbitrary topological spaces. This is just the reverse direction of the duality mentioned earlier from Boolean algebras to Stone spaces. This definition is fleshed out by the next definition.

Johnstone (1982)

A Boolean algebra is a filtered colimit of finite Boolean algebras.

(The circularity in this definition can be removed by replacing "finite Boolean algebra" by "finite power set" equipped with the Boolean operations standardly interpreted for power sets.)

To put this in perspective, infinite sets arise as filtered colimits of finite sets, infinite CABAs as filtered limits of finite power set algebras, and infinite Stone spaces as filtered limits of finite sets. Thus if one starts with the finite sets and asks how these generalize to infinite objects, there are two ways: "adding" them gives ordinary or inductive sets while "multiplying" them gives Stone spaces or profinite sets. The same choice exists for finite power set algebras as the duals of finite sets: addition yields Boolean algebras as inductive objects while multiplication yields CABAs or power set algebras as profinite objects.

A characteristic distinguishing feature is that the underlying topology of objects so constructed, when defined so as to be Hausdorff, is discrete for inductive objects and compact for profinite objects. The topology of finite Hausdorff spaces is always both discrete and compact, whereas for infinite spaces "discrete"' and "compact" are mutually exclusive. Thus when generalizing finite algebras (of any kind, not just Boolean) to infinite ones, "discrete" and "compact" part company, and one must choose which one to retain. The general rule, for both finite and infinite algebras, is that finitary algebras are discrete, whereas their duals are compact and feature infinitary operations. Between these two extremes, there are many intermediate infinite Boolean algebras whose topology is neither discrete nor compact.

• Birkhoff, Garrett (1935). "On the structure of abstract algebras". Proc. Camb. Phil. Soc. 31 (4): 433–454. Bibcode:1935PCPS...31..433B. doi:10.1017/s0305004100013463. ISSN 0008-1981. S2CID 121173630.
• Boole, George (2003) [1854]. An Investigation of the Laws of Thought. Prometheus Books. ISBN 978-1-59102-089-9.
• Dwinger, Philip (1971). Introduction to Boolean algebras. Würzburg: Physica Verlag.
• Gaifman, Haim (1964). "Infinite Boolean Polynomials, I". Fundamenta Mathematicae. 54 (3): 229–250. doi:10.4064/fm-54-3-229-250. ISSN 0016-2736.
• Givant, Steven; Halmos, Paul (2009). Introduction to Boolean Algebras. Undergraduate Texts in Mathematics. Springer. ISBN 978-0-387-40293-2.
• Grau, A.A. (1947). "Ternary Boolean algebra". Bull. Am. Math. Soc. 33 (6): 567–572. doi:10.1090/S0002-9904-1947-08834-0.
• Hales, Alfred W. (1964). "On the Non-Existence of Free Complete Boolean Algebras". Fundamenta Mathematicae. 54: 45–66. doi:10.4064/fm-54-1-45-66. ISSN 0016-2736.
• Halmos, Paul (1963). Lectures on Boolean Algebras. van Nostrand. ISBN 0-387-90094-2.
• Givant, Steven; Halmos, Paul (1998). Logic as Algebra. Dolciani Mathematical Exposition. Mathematical Association of America. ISBN 978-0-883-85327-6.
• Johnstone, Peter T. (1982). Stone Spaces. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-33779-3.
• Ketonen, Jussi (1978). "The structure of countable Boolean algebras". Annals of Mathematics. 108 (1): 41–89. doi:10.2307/1970929. JSTOR 1970929.
• Koppelberg, Sabine (1989) "General Theory of Boolean Algebras" in Monk, J. Donald, and Bonnet, Robert, eds., Handbook of Boolean Algebras, Vol. 1. North Holland. ISBN 978-0-444-70261-6.
• Peirce, C. S. (1989) Writings of Charles S. Peirce: A Chronological Edition: 1879–1884. Kloesel, C. J. W., ed. Indianapolis: Indiana University Press. ISBN 978-0-253-37204-8.
• Lawvere, F. William (1963). "Functorial semantics of algebraic theories". Proceedings of the National Academy of Sciences. 50 (5): 869–873. Bibcode:1963PNAS...50..869L. doi:10.1073/pnas.50.5.869. PMC 221940. PMID 16591125.
• Schröder, Ernst (1890–1910). Vorlesungen über die Algebra der Logik (exakte Logik), I–III. Leipzig: B.G. Teubner.
• Sikorski, Roman (1969). Boolean Algebras (3rd. ed.). Berlin: Springer-Verlag. ISBN 978-0-387-04469-9.
• Stone, M. H. (1936). "The Theory of Representation for Boolean Algebras". Transactions of the American Mathematical Society. 40 (1): 37–111. doi:10.2307/1989664. ISSN 0002-9947. JSTOR 1989664.
• Tarski, Alfred (1983). Logic, Semantics, Metamathematics, Corcoran, J., ed. Hackett. 1956 1st edition edited and translated by J. H. Woodger, Oxford Uni. Press. Includes English translations of the following two articles:
  • Tarski, Alfred (1929). "Sur les classes closes par rapport à certaines opérations élémentaires". Fundamenta Mathematicae. 16: 195–97. ISSN 0016-2736.
  • Tarski, Alfred (1935). "Zur Grundlegung der Booleschen Algebra, I". Fundamenta Mathematicae. 24: 177–98. doi:10.4064/fm-24-1-177-198. ISSN 0016-2736.
• Vladimirov, D.A. (1969). булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974). Nauka (German translation Akademie-Verlag).