Boolean algebras canonically defined

Boolean algebra is a branch of abstract algebra closely related to other branches such as group theory and linear algebra. Common to these subjects is the notion of an algebra as a set together with a family of operations on that set satisfying certain equations. Just as group theory deals with groups, and linear algebra with vector spaces, so does Boolean algebra treat Boolean algebras.

Just as there are basic examples of groups such as the group Z of integers and the group S_n of permutations of n objects, so does Boolean algebra have its basic examples, in particular the Boolean algebra of binary digits or bits 0 and 1 under the logical operations including (but not restricted to) disjunction, conjunction, and negation, and the algebra of sets under the set operations including (but not restricted to) union, intersection, and complement. The former example finds applications to both propositional calculus and digital circuits, the latter to any area of mathematics for which sets form a natural foundation. Boolean algebra thus permits the general methodology of abstract algebra to be applied to mathematical logic, digital logic, and the set-theoretic foundations of mathematics, among other applications. Boolean algebra has a rich mathematical theory, ranging from simple observations to sophisticated and sometimes deep theorems, though not to the same extent as the theories of groups, rings, fields, etc.

History

Boolean algebra was introduced by the Irish mathematician George Boole, initially in a small pamphlet published in 1847 in response to an ongoing controversy between Augustus De Morgan and William Hamilton, and later as a more substantial book, The Laws of Thought, published in 1854. It was put in its present form in the latter third of that century by Charles Sanders Peirce (truth tables), William Jevons, and Ernst Schröder. It then languished until it was revived in the 1930s by Garrett Birkhoff (lattice theoretic aspects), Alfred Tarski (foundational aspects), Marshall Stone (topological aspects), and Claude Shannon and John von Neumann (application to digital circuits). In consequence most of the subject matter of Boolean algebra only emerged during the latter half of the maturation of abstract algebra. Both Boolean algebra and abstract algebra are relative newcomers to the mathematical scene, experiencing their major growth spurts some two centuries later than for example calculus.

Nature

Boolean algebras have traditonally been defined analogously to other structures such as groups, rings, vector spaces, and lattices. These others all have canonical definitions reflecting their nature and indicating their usage, with no reason to suppose that there might be better operations or equations on which to base the definition. In striking contrast Boolean algebras have a wide range of both operations and axioms to choose from for their definition. One famous operation is Sheffer stroke, NAND or ¬(x∧y), and Boolean algebras can be completely axiomatized in terms of equational properties of that operation alone!

This difference is not apparent from the traditional choice of definition of Boolean algebra as a complemented distributive lattice. This definition, selected by weight of tradition from a large number of available alternatives, closely parallels that of a ring, having two commutative binary operations of addition x+y and multiplication xy, and a unary operation of negation x′, alternatively written x∨y, x∧y, and ¬x. The definition starts out with those ring axioms that don't mention negation, and adds axioms x+x = x and x² = x of idempotence. But instead of defining negation as additive inverse, it is axiomatized by x+x′ = 1 (the multiplicative identity) and xx′ = 0 (the additive identity), thus declaring x and x′ to be mutual complements.

In 1936 Marshall Stone, in the course of pointing out this analogy with rings while writing his celebrated paper on the duality of Boolean algebras and Stone spaces, discovered an even more ring-like choice of operations and axioms. He started from all the ring axioms including those involving negation, and added just one more axiom, x²=x. A ring with this additional property is called a Boolean ring. In this definition addition is interpreted as exclusive-or instead of inclusive-or, ring negation becomes the identity operation, that is, −x = x, and logical negation ¬x is then defined as x+1. Although the ring of integers fails to be a Boolean ring since 2² ≠ 2, the ring of integers mod 2 does form a Boolean ring and hence a Boolean algebra by Stone's definition. Inclusive-or is now definable as x+y+xy. (We shall write exclusive-or in the sequel as x⊕y to avoid confusion with the other common use of x+y as inclusive-or.)

This multiplicity of choices of both operations and axioms makes the notion of Boolean algebra seem a chameleon, capable of changing its appearance to blend in with the ambient background. The question then arises as to whether Boolean algebras have an essential nature independently of the choice of operations and equations on which their definition is based.

In his 1963 Ph.D. thesis William Lawvere defined a Boolean algebra to be a product preserving set-valued functor on a certain category. In this article we translate Lawvere's category-theoretic definition into the language of algebra in a way that states in a mathematically rigorous way that a Boolean algebra is simply any model of two-valued logic. The translation retains the independence of Lawvere's definition from arbitrary choices of either operations or axioms, and can therefore be said to be canonical at least in those regards.

Algebraic preliminaries

An algebra is a set X and an indexed family of operations on X. Algebra has traditionally confined itself to operations of finite arity, but this restriction can no longer be taken for granted in view of the emergence of such useful infinitary algebras as sigma-algebras.

A homologue (or homolog) of a given algebra called the prototype is any algebra whose operations correspond to those of the prototype by virtue of using the same index set, with corresponding operations having the same arity, and with the operations of the homologue having all the equational properties of those of the prototype (and possibly more). The traditional index set for an algebra with n operations is {1,2,…,n}, in that case organizing the operations as a list, but any set may serve. The indexed family of arities common to the prototype and its homologues is called the signature.

For example the algebra (Z₃, +, 0, 1) of integers mod n for n = 3 under addition with constants or nullary operations 0 and 1 is a homologue of the algebra (Z, +, 0, 1) of integers under addition with constants 0 and 1 because their corresponding operations agree in arity, that is, they have the same signature 2-0-0, the traditional universal algebra notation. Furthermore the operations of the homologue satisfy all the equational laws satisfied by those of the prototype, for example x+y = y+x, but not conversely since 1+(1+1) = 0 is true in the homologue but false in the prototype. Another example is the ring of integers as a homologue of the 2×2 matrix ring over the integers, satisfying all the equational laws of the matrix ring but having the additional property xy = yx, matrix multiplication not being commutative.

Boolean algebras

A Boolean algebra is any homologue of the algebra of finitary operations on the set {0, 1} (see Boolean domain).

(As a secondary detail, we consider the algebra of finitary operations on a set to have as index set the set of operations themselves, at least for now; the next section considers an alternative indexing.)

Example 1. Any algebra being trivially a homologue of itself, the algebra of finitary operations on {0, 1} qualifies as a Boolean algebra, which we may therefore call the prototypical Boolean algebra. The equational properties of Boolean operations being those of the prototype, to understand those properties it suffices to study the operations of the prototype.

There being k^k^ⁿ n-ary operations f: Xⁿ→X on a k-element set X, there are therefore 2²^ⁿ n-ary operations on {0,1}. Thus every Boolean algebra, however small or large, has two constants or "nullary" operations, four unary operations, 16 binary operations, 256 ternary, etc., called the Boolean operations of the given Boolean algebra.

Some Boolean operations can be obtained as composites of others. A set of Boolean operations sufficient to obtain the remainder is called a basis. Emil Post gave a necessary and sufficient condition for a set of operations to be a basis. He listed five nontrivial properties of operations, each preserved by composition, and showed that a set of operations formed a basis when for each property the set contained an operation lacking that property. (For the converse, if one of the five properties holds for every operation of a set of operations then it holds for all operations formed by composition from that set, whence any Boolean operation lacking that property cannot be so formed. Since the property is nontrivial the set therefore cannot be a basis.) The NAND operation, defined by f(x,y) = 0 if and only if x = y = 1, lacks all five properties and so can form a basis all by itself.

There are many other interesting bases, but there is no compelling reason to tie the definition of Boolean algebra to one of them as is traditionally done. Instead we have taken the Boolean operations to be what is sometimes called the clone (for "closed nest", meaning closed under composition) of Boolean operations, also called the polynomials of the Boolean algebra.

Truth Tables

The finitary operations on {0,1} may be exhibited as truth tables, thinking of 0 and 1 as the truth values false and true.

Truth tables for the Boolean operations of arity up to 2

Constants
	⁰f₀	⁰f₁
	0	1

Unary Operations
x₀	¹f₀	¹f₁	¹f₂	¹f₃
0	0	1	0	1
1	0	0	1	1

Binary Operations
x₀	x₁	²f₀	²f₁	²f₂	²f₃	²f₄	²f₅	²f₆	²f₇	²f₈	²f₉	²f₁₀	²f₁₁	²f₁₂	²f₁₃	²f₁₄	²f₁₅
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 or symmetric difference x₀⊕x₁ as ²f₆, set difference x₀−x₁ as ²f₂, and so on.

As remarked earlier it is not essential in the definition of homologue that its operations be listed in a specific order, since the operations of the homologue can be indexed or "named" by the operations of the prototype. Nevertheless there is a certain canonicality to the particular ordering implied by these tables that allows us to stick to the tradition of organizing the signature as a list without being completely arbitrary about it, namely in the order of operations shown in the above tables. The conditions determining this order are as follows.

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

An alternative to this linear disposition of the Boolean operations is to view each operation as one of the ways of labeling the 2ⁿ vertices of the n-dimensional unit cube with a bit at each vertex. A natural orientation of this cube is with the origin, corresponding to all inputs being 0, at the bottom and the vertex furthest from the origin, all inputs 1, at the top. An operation is called monotone when every path from bottom to top of the cube so oriented encounters only a run of zero of more 0 labels followed by a run of zero or more 1 labels, that is, there is no transition from 1 to 0 along any such path. Disjunction labels only the bottom element 0, while conjunction labels only the top element 1, both being monotone. Exclusive-or labels the elements of the cube with the parity of their height: 0 at the bottom element, 1 at the atoms, 0 at the next row up, alternating at each row to create strata. The minimal negation operator of arity n is obtained by labeling the coatoms of the cube (the elements immediately below the top) 1 and the rest 0; when n = 1 this operation reduces to ordinary negation.

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. This technique is almost universally used in raster graphics hardware to provide a flexible variety of ways of combining and masking images.

Examples

Example 2. All bit vectors of a given length form a Boolean algebra "pointwise", meaning that any n-ary Boolean operation can be applied to n bit vectors one bit position at a time. For example the ternary OR of three bit vectors each of length 4 is the bit vector of length 2 formed by oring the three bits in each of the four bit positions, thus 0100∨1000∨1001 = 1101. This works equally well for bit vectors of finite and infinite length, the only rule being that the bit positions all be indexed by the same set in order that "corresponding position" be well defined.

The atoms of such an algebra are the bit vectors containing exactly one 1. In general the atoms of a Boolean algebra are those elements x such that x∧y has only two possible values, x or 0.

Example 3. The set 2^W of all subsets of a given set W, called the power algebra. This is just Example 2 in disguise, with W serving to index the bit positions. Any subset X of W can be viewed as the bit vector having 1's in just those bit positions indexed by elements of X. Thus the all-zero vector is the empty subset of W while the all-ones vector is W itself, these being the constants 0 and 1 respectively of the power algebra. The counterpart of disjunction x∨y is union X∪Y, while that of conjunction x∧y is intersection X∩Y. Negation ¬x becomes ~X, complement relative to W. There is also set difference X∖Y = X∩~Y, symmetric difference (X∖Y)∪(Y∖X), ternary union X∪Y∪Z, and so on. The atoms here are the singletons, those subsets with exactly one element.

Examples 2 and 3 are special cases of a general construct of algebra called direct product, applicable not just to Boolean algebras but all kinds of algebra including groups, rings, etc. The direct product of any family B_i of Boolean algebras where i ranges over some index set I (not necessarily finite or even countable) is a Boolean algebra consisting of all I-tuples (…x_i,…) whose i-th element is taken from B_i. The operations of a direct product are the corresponding operations of the constituent algebras acting within their respective coordinates; in particular operation ⁿf_j of the product operates on n I-tuples by applying operation ⁿf_j of B_i to the n elements in the i-th coordinate of the n tuples, for all i in I.

When all the algebras being multiplied together in this way are the same algebra A we call the direct product a direct power of A. The Boolean algebra of all 32-bit bit vectors is the two-element Boolean algebra raised to the 32nd power, or power algebra of a 32-element set, denoted 2³². The Boolean algebra of all sets of integers is 2^Z. All Boolean algebras we have exhibited thus far have been direct powers of the two-element Boolean algebra, justifying the name "power algebra".

Representability of Boolean algebras

It can be shown that every finite Boolean algebra is isomorphic to some power algebra. Hence the cardinality (number of elements) of a finite Boolean algebra is a power of 2, namely one of 1,2,4,8,…,2ⁿ,… This is called a representation theorem as it gives insight into the nature of finite Boolean algebras by giving a representation of them as power algebras.

This representation theorem does not extend to infinite Boolean algebras: although every power algebra is a Boolean algebra, not every Boolean algebra need be isomorphic to a power algebra. In particular, whereas there can be no countably infinite power algebras (the smallest infinite power algebra is the power algebra 2^N of sets of natural numbers, shown by Cantor to be uncountable), there exist various countably infinite Boolean algebras.

To go beyond power algebras we need another construct. A subalgebra of an algebra A is any subset of A closed under the operations of A. Every subalgebra of a Boolean algebra A must still satisfy the equations holding of A, since any violation would constitute a violation for A itself. Hence every subalgebra of a Boolean algebra is a Boolean algebra.

A subalgebra of a power algebra is called a field of sets. Birkhoff's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets.

It is convenient when talking about a set X of natural numbers to view it as a sequence x₀,x₁,x₂,… of bits, with x_i = 1 if and only if i ∈ X. This viewpoint will make it easier to talk about subalgebras of the power algebra 2^N, which this viewpoint makes the Boolean algebra of all sequences of bits.

Example 4. Ultimately constant sequences. Any Boolean combination of ultimately constant sequences is ultimately constant, whence these form a Boolean algebra. We can identify these with the integers by viewing the ultimately-zero sequences as nonnegative binary numerals (bit 0 of the sequence being the low-order bit) and the ultimately-one sequences as negative binary numerals (think two's complement arithmetic with the all-ones sequence being −1). This makes the integers a Boolean algebra, with union being bit-wise OR and complement being −x−1. There are only countably many integers, so this infinite Boolean algebra is countable. The atoms are the powers of two, namely 1,2,4,…. Another way of describing this algebra is as the set of all finite and cofinite sets of natural numbers, with the ultimately all-ones sequences corresponding to the cofinite sets, those sets omitting only finitely many natural numbers.

Example 5. Periodic sequences. A sequence is called periodic when there exists some number n > 0, called a witness to periodicity, such that x_i = x_i+n for all i ≥ 0. The period of a periodic sequence is its least witness. Negation leaves period unchanged, while the disjunction of two periodic sequences is periodic, with period at most the least common multiple of the periods of the two arguments (the period can be as small as 1, as happens with the union of any sequence and its complement). Hence the periodic sequences form a Boolean algebra.

Example 5 resembles Example 4 in being countable, but differs in being atomless. The latter is because the conjunction of any nonzero periodic sequence x with a sequence of greater period is neither 0 nor x. It can be shown that all countably infinite atomless Boolean algebras are isomorphic, that is, up to isomorphism there is only one such algebra.

Example 6. Example 5 has a proper subalgebra ("proper" meaning that at least one element has been omitted) consisting of the periodic sequences with period a power of two. These can be understood as the finitary operations, with the first period of such a sequence giving the truth table of the operation it represents. For example the truth table of x₀ in the table of binary operations, namely ²f₁₀, has period 2 (and so can be recognized as using only the first variable) even though 12 of the binary operations have period 4. When the period is 2ⁿ the operation only depends on the first n variables, the sense in which the operation is finitary. This example is also a countably infinite atomless Boolean algebra. Hence Example 5 is isomorphic to a proper subalgebra of itself! Example 6, and hence Example 5, constitutes the free Boolean algebra on countably many generators, meaning the Boolean algebra of all finitary operations on a countably infinite set of generators or variables.

Example 7. Example 5 has a proper extension (the converse of the subalgebra relation) obtained by combining it with Example 4, namely the ultimately periodic sequences. These are sequences that become periodic after an initial finite bout of lawlessness. Sequences may vary as to when they settle down, but any finite set of sequences will all eventually settle down no later than their slowest-to-settle member, whence ultimately periodic sequences are closed under all Boolean operations and so form a Boolean algebra. This algebra also extends Example 4 by virtue of ultimately constant sequences being ultimately periodic, namely with period 1. Thus it has the same atoms and coatoms as Example 4, whence it is not atomless and therefore not isomorphic to Example 5/6. However it contains an infinite atomless subalgebra, namely Example 5, and so is not isomorphic to Example 4, every subalgebra of which must be a Boolean algebra of finite sets and their complements and therefore atomic. Example 7 is isomorphic to the direct product of Examples 4 and 5, furnishing another description of it.

Example 8. The direct product of Example 5 with a finite Boolean algebra (other than the degenerate one-element Boolean algebra, which is the unique finite atomless Boolean algebra). This resembles Example 7 in having both atoms and an atomless subalgebra, but differs in only having finitely many atoms. Example 8 is an infinite family of examples, one for each possible finite number of atoms.

Boolean algebras of Boolean operations

The n-ary Boolean operations themselves constitute a power 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 perform Boolean operations of arity m on Boolean operations 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), 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

(x∧y)∨(y∧z)∨(z∧x)

and

(x∨y)∧(y∨z)∧(z∨x)

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

(x∧y)∨(y∧z)∨(z∧x) = (x∨y)∧(y∨z)∧(z∨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 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 operation, with the evident generalization to any odd number of variables (odd in order to avoid the tie when exactly half the variables are 0).

Axiomatizing Boolean algebras

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 an 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 form ⁿf_i(x₀,…,x_n−1). These 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 two axiom schemas (or schemata) and two inference rules axiomatize the Boolean algebra of n-ary terms.

A1. ⁿf_i = ⁿf_i.

A2. ^mf_i(ⁿf_j_₀,…,ⁿf_j_{_m−1}) = ⁿf_ioĵ where (ioĵ)_v = i_ĵ_{_v}, with ĵ being j transpose, defined by (ĵ_v)_u = (j_u)_v.

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

R2. From s₀ = t₀,…,s_m−1 = t_m−1 infer ^{m^{f_i(s₀,…,s_m−1) = ^{m^{f_i(t₀,…,t_m−1), where all terms s_i, t_i are n-ary.}}}}

The meaning of the side condition on A2 is that ioĵ is a 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.)

Items A1 and A2 are axiom schemas rather than axioms by virtue of containing metavariables. The metavariables of A1 are n and i while those of A2 are 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 (10 as a two-bit number). The resulting instance, namely ¹f₁(¹f₁) = ¹f₂, expresses the familiar axiom ¬¬x = x of double negation. Rule R2 then allows us to infer ¬¬¬x = ¬x by taking s₀ to be ¹f₁(¹f₁) or ¬¬x₀, t₀ to be ¹f₂ or x₀, and ^{m^{f_i to be ^{1^{f₁ or ¬.}}}}

Schema A1 ensures that we can prove even those identities whose left hand side is of height zero, such as x₀ = x₀∧x₀. It is necessary because the left hand side of A2 is of height one and the inference rules cannot produce a conclusion with a left hand side of height zero from premises all of whose left hand sides have nonzero height. Alternatively we could have dealt with this by including a rule for inferring t = s from s = t. However with A1 this rule becomes derivable and therefore not needed in the basic system.

For each n there are only finitely many axioms instantiating A1, namely 2²^ⁿ. However there are infinitely many instances of A2 because there are instances for every possible m. For any given m there are 2²^{^m} × (2²^ⁿ)^m instances of A2, each containing 2^m+m2ⁿ bits.

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 A1 for the base case (s atomic) and A2 and R2 for the induction step (s an application). This proof strategy amounts to a recursive procedure for evaluating s. 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, and then invoke R1 to infer s = t.

In A2, if we view 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 A2 translates here to (ioĵ)(v) = i(ĵ(v)), that is, ioĵ is defined to be composition of i and ĵ understood as functions. So the content of A2 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.

Underlying lattice structure

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 (supremum) 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 (infimum) 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 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.

Boolean homomorphisms

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

h(^mf_i(x₀,…,x_m−1)) = ^mf_i(h(x₀),…,h(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. One simple-minded ultrafilter of the Boolean algebra of finite and cofinite sets of integers is the set of cofinite integers, but there are many more. 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.

Infinitary extensions

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 and Hales independently showed in 1964 that infinite free complete Boolean algebras did not exist. This suggests that it is impossible to have an infinitary Boolean logic for lack of terms.

There is however another approach to introducing infinitary Boolean operations: simply drop "finitary" from the definition of Boolean algebra. An algebra that is a homologue of the algebra of all operations on {0,1} of arity up to the cardinality of the homologue is called a complete atomic Boolean algebra, or CABA. (An awkward detail here is that algebras of different cardinality have different signatures, whence to make "homomorphism" well-defined the signature of the smaller algebra needs to be extended up to that of the larger.) 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 algebra 2²^{^V}, 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 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 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. However the situation parallels that with complete Boolean algebras vs. CABAs to a limited extent. We can define a countably distributive sigma-algebra to be one that satisfies distributivity of countable sups over countable infs and vice versa, or equivalently as a homologue of the algebra of all operations on {0,1} of countable arity. The free countably generated countably distributive sigma-algebra has the same nice structure as free CABAs, being the power algebra 2²^{^N}. The free countably generated sigma algebra on the other hand is not a power algebra, and neither are the free uncountably generated countably distributive sigma-algebras, just as the free countably generated Boolean algebras are not power algebras.

Other definitions of Boolean algebra

There are many other definitions of a Boolean algebra besides the ones already encountered. We list four of the more important here.

(Stone): A Boolean algebra is an idempotent ring, one satisfying x² = x, called a Boolean ring. The ring multiplication is ∧and addition is ⊕ (exclusive-or). The two-element Boolean ring is the only ring that is a field, namely the Galois field GF(2). GF(4) has the same addition as the four-element Boolean algebra, namely the Klein four-group Z₂⊕Z₂, but its multiplication is not idempotent.

The respective definitions of a Boolean algebra as a Boolean ring and a complemented distributive lattice are similar in character, the most prominent difference being that whereas x⊕y is invertible, namely (x⊕y)⊕y = x (y being its own inverse), its counterpart x∨y is idempotent, namely x∨x = x. The algebra (B,⊕,∨,∧) combining both notions is noteworthy for being a semiring in two ways, (B,⊕,∧) and (B,∨,∧), both of which have the same multiplication ∧ (bearing in mind that ∧ distributes over both ⊕ and ∨); this answers in the negative whether the multiplicative structure of a semiring uniquely determines its additive structure.

(Lawvere): A Boolean algebra is a product-preserving set-valued functor F from the category of finite power sets 2⁰,2¹,2²,… and all functions between them. Because it preserves products, F(2ⁿ) = F(2¹)ⁿ, whence F is determined by the set X = F(2¹), which serves as the underlying set of the Boolean algebra represented by F. The 2²^ⁿ functions f:2ⁿ→2¹ become the n-ary Boolean operations F(f): Xⁿ→X. More generally functions f:2ⁿ→2^m are interpreted by F as m-tuples of n-ary Boolean operations, cf. j vs. ĵ in axiom A2 of the axiomatization above.

The "canonical" definition of Boolean algebra adopted in the present article amounts to Lawvere's definition translated from the language of category theory to that of algebra, with all the benefits of Italian opera sung in English.

(Stone): 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. 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): A Boolean algebra is a filtered colimit of finite Boolean algebras.

To put this in perspective, infinite sets arise as filtered colimits of finite sets, infinite CABAs as filtered limits of finite Boolean algebras, and infinite Stone spaces as filtered limits of finite sets. Thus if one starts with 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 Boolean algebras as the duals of finite sets: addition yields Boolean algebras as inductive objects while multiplication yields CABAs as profinite objects.

A characteristic distinguishing feature is that the underlying topology when defined to make it 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 ways, and one must decide which to follow. The general rules, for both finite and infinite algebras, are that finitary algebras are discrete, whereas for their duals, compactness and infinitary operations come with the territory. These are only the two extremes, there are many infinite algebras whose topology is neither discrete nor compact.

References

Birkhoff, Garrett (1935). "On the structure of abstract algebras". Proc. Camb. Phil. Soc. 31: 433–454.
Boole, George (1854). An Investigation of the Laws of Thought. London: Macmillan.
Gaifman, Haim (1964). "Infinite Boolean Polynomials, I". Fundamenta Mathematicae. 54: 229–250. ISSN 0016-2736.
Hales, Alfred W. (1964). "On the Non-Existence of Free Complete Boolean Algebras". Fundamenta Mathematicae. 54: 45–66. ISSN 0016-2736.
Johnstone, Peter T. (1982). Stone Spaces. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-33779-3.
Kloesel, Christian (1986). Writings of Charles S. Peirce: A Chronological Edition: 1879-1884. Bloomington, Indiana: Indiana University Press.
Lawvere, F. William (1963). "Functorial semantics of algebraic theories". 50: 869–873. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |booktitle= ignored (help)
Schröder, Ernst (1895). Vorlesungen über die Algebra der Logik (Exakte Logik). B.G. Teubner. {{cite book}}: Unknown parameter |address= ignored (|location= suggested) (help); Unknown parameter |booktitle= ignored (help)
Stone, Marshall (1936). "The Theory of Representations for Boolean Algebras". Transactions of the American Mathematical Society. 40: 37–111. ISSN 0002-9947.
Tarski, Alfred (1929). "Sur les classes closes par rapport à certaines opérations élémentaires". Fundamenta Mathematicae. 16: 181–305.
Tarski, Alfred (1935). "Zur Grundlegung der Boolesche Algebra, I". Fundamenta Mathematicae. 24: 177–198.