Boolean algebras canonically defined

Boolean algebras are models of the equational theory of two values; this definition is equivalent to the lattice and ring definitions.

Boolean algebrais a mathematically rich branch ofabstract algebra.Stanford Encyclopaedia of Philosophydefines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.'Just asgroup theorydeals withgroups,andlinear algebrawithvector spaces,Boolean algebrasare models of theequational theoryof the two values 0 and 1 (whose interpretation need not be numerical). Common to Boolean algebras, groups, and vector spaces is the notion of analgebraic structure,asetclosed under someoperationssatisfying certain equations.

Just as there are basic examples of groups, such as the group$\mathbb {Z}$ofintegersand thesymmetric groupS_nofpermutationsofnobjects, there are also basic examples of Boolean algebras such as the following.

• The algebra ofbinary digitsor bits 0 and 1 under the logical operations including disjunction, conjunction, and negation. Applications include thepropositional calculusand the theory of digital circuits.
• Thealgebra of setsunder the set operations includingunion,intersection,andcomplement.Applications are far-reaching becauseset theoryis the standardfoundations of mathematics.

Boolean algebra thus permits applying the methods ofabstract algebratomathematical logicanddigital logic.

Unlike groups of finiteorder,which exhibit complexity and diversity and whosefirst-ordertheory isdecidableonly in special cases, all finite Boolean algebras share the same theorems and have a decidable first-order theory. Instead, the intricacies of Boolean algebra are divided between the structure of infinite algebras and thealgorithmiccomplexity of theirsyntacticstructure.

Definition

Boolean algebra treats theequational theoryof the maximal two-elementfinitaryalgebra, called theBoolean prototype,and the models of that theory, calledBoolean algebras.These terms are defined as follows.

Analgebrais afamilyof 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 isfinitarywhen each of its operations takes only finitely many arguments. For the prototype each argument of an operation is either0or1,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 thearityof the operation. An operation on {0,1} of arityn,orn-ary operation, can be applied to any of2ⁿpossible values for itsnarguments. For each choice of arguments, the operation may return0or1,whence there are2²ⁿn-ary operations.

The prototype therefore has two operations taking no arguments, calledzeroaryornullaryoperations, namely zero and one. It has fourunary operations,two of which are constant operations, another is the identity, and the most commonly used one, callednegation,returns the opposite of its argument:1if0,0if1.It has sixteenbinary operations;again two of these are constant, another returns its first argument, yet another returns its second, one is calledconjunctionand returns 1 if both arguments are 1 and otherwise 0, another is calleddisjunctionand 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 ofn-ary operations, so there are16²= 256ternary operations,256²= 65,536quaternary operations, and so on.

Afamilyis indexed by anindex set.In the case of a family of operations forming an algebra, the indices are calledoperation symbols,constituting thelanguageof that algebra. The operation indexed by each symbol is called the denotation orinterpretationof 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 has2²ⁿn-ary operation symbols, called theBoolean operation symbolsand forming the language of Boolean algebra. Only a few operations have conventional symbols, such as¬for negation,∧for conjunction, and∨for disjunction.It is convenient to consider thei-thn-ary symbol to beⁿf_ias done below in the section ontruth tables.

Anequational theoryin 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 arex∧y=y∧x,x∧x=x,x∧¬x=y∧¬y,andx∧y=x.

An algebrasatisfiesan 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 since1∧0 ≠ 1.

Theequational theoryof 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.

Amodel of a theoryis 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.

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.

Basis

The operations need not be all explicitly stated. Abasisis 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 theSheffer strokeor NAND basis. These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.

• Thelatticebasis originated in the 19th century with the work ofBoole,Peirce,and others seeking an algebraic formalization of logical thought processes.
• Theringbasis emerged in the 20th century with the work ofZhegalkinandStoneand became the basis of choice for algebraists coming to the subject from a background inabstract algebra.Most treatments of Boolean algebra assume the lattice basis, a notable exception beingHalmos[1963] whose linear algebra background evidently endeared the ring basis to him.
• Since all finitary operations on {0,1} can be defined in terms of theSheffer strokeNAND (or its dual NOR), the resulting economical basis has become the basis of choice for analyzingdigital circuits,in particulargate arraysindigital electronics.

The common elements of the lattice and ring bases are the constants 0 and 1, and anassociativecommutativebinary operation,calledmeetx∧yin the lattice basis, andmultiplicationxyin the ring basis. The distinction is only terminological. The lattice basis has the further operations ofjoin,x∨y,andcomplement,¬x.The ring basis has instead the arithmetic operationx⊕yofaddition(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 translatesx∨yto the ring basis asx⊕y⊕xy,and¬xasx⊕1.Conversely the ring basis translatesx⊕yto 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 adistributive latticesatisfyingx∧¬x= 0andx∨¬x= 1,called acomplementeddistributive lattice. The ring basis turns a Boolean algebra into aBoolean ring,namely a ring satisfyingx²=x.

Emil Postgave a necessary and sufficient condition for a set of operations to be a basis for the nonzeroary Boolean operations. Anontrivialproperty is one shared by some but not all operations making up a basis. Post listed five nontrivial properties of operations, identifiable with the fivePost'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 withZhegalkin polynomialsthat lack bilinear or higher terms, e.g.x⊕y⊕1but notxy;
• self-dual,so that complementing all inputs complements the output, as withx,or themedian operatorxy⊕yz⊕zx,or their negations;
• strict(mapping the all-zeros input to zero);
• costrict (mapping all-ones to one).

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

Truth tables

The finitary operations on {0,1} may be exhibited astruth tables,thinking of 0 and 1 as thetruth valuesfalseandtrue.They can be laid out in a uniform and application-independent way that allows us to name, or at least number, them individually.These names provide a convenient shorthand for the Boolean operations. The names of then-ary operations are binary numbers of2ⁿbits. There being2²ⁿsuch operations, one cannot ask for a more succinct nomenclature. Note that each finitary operation can be called aswitching 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 ${}^{0}\!f_{0}$ ${}^{0}\!f_{1}$ 0 1

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

Binary operations $x_{0}$ $x_{1}$ ${}^{2}\!f_{0}$ ${}^{2}\!f_{1}$ ${}^{2}\!f_{2}$ ${}^{2}\!f_{3}$ ${}^{2}\!f_{4}$ ${}^{2}\!f_{5}$ ${}^{2}\!f_{6}$ ${}^{2}\!f_{7}$ ${}^{2}\!f_{8}$ ${}^{2}\!f_{9}$ ${}^{2}\!f_{10}$ ${}^{2}\!f_{11}$ ${}^{2}\!f_{12}$ ${}^{2}\!f_{13}$ ${}^{2}\!f_{14}$ ${}^{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, with2ⁿrows at arityn,each row giving a valuation or binding of thenvariablesx₀,...x_n−1and each column headedⁿf_igiving the valueⁿf_i(x₀,...,x_n−1)of thei-thn-ary operation at that valuation. The operations include the variables, for example¹f₂isx₀while²f₁₀isx₀(as two copies of its unary counterpart) and²f₁₂isx₁(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 unionx₀∨x₁as²f₁₄,conjunction or intersectionx₀∧x₁as²f₈,implicationx₀→x₁as²f₁₃,exclusive-or symmetric differencex₀⊕x₁as²f₆,set differencex₀−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) Thei-th row in the left half of the table is the binary representation ofiwith its least significant or0-th bit on the left ( "little-endian" order, originally proposed byAlan Turing,so it would not be unreasonable to call it Turing order).

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

When programming in C or Java, bitwise disjunction is denotedx|y,conjunctionx&y,and negation~x.A program can therefore represent for example the operationx∧(y∨z)in these languages asx&(y|z),having previously setx= 0xaa,y= 0xcc,andz= 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.

Examples

Bit vectors

Example 2.Allbit vectorsof a given length form a Boolean algebra "pointwise", meaning that anyn-ary Boolean operation can be applied tonbit 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 4 formed by oring the three bits in each of the four bit positions, thus0100∨1000∨1001 = 1101.Another example is the truth tables above for then-ary operations, whose columns are all the bit vectors of length2ⁿand which therefore can be combined pointwise whence then-ary operations form a Boolean algebra. 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.

Theatomsof such an algebra are the bit vectors containing exactly one 1. In general the atoms of a Boolean algebra are those elementsxsuch thatx∧yhas only two possible values,xor0.

Power set algebra

Example 3.Thepower set algebra,the set2^Wof all subsets of a given setW.This is just Example 2 in disguise, withWserving to index the bit positions. Any subsetXofWcan be viewed as the bit vector having 1's in just those bit positions indexed by elements ofX.Thus the all-zero vector is the empty subset ofWwhile the all-ones vector isWitself, these being the constants 0 and 1 respectively of the power set algebra. The counterpart of disjunctionx∨yis unionX∪Y,while that of conjunctionx∧yis intersectionX∩Y.Negation¬xbecomes~X,complement relative toW.There is also set differenceX\Y=X∩~Y,symmetric difference(X\Y)∪(Y\X),ternary unionX∪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 calleddirect product,applicable not just to Boolean algebras but all kinds of algebra including groups, rings, etc. The direct product of any familyB_iof Boolean algebras whereiranges over some index setI(not necessarily finite or even countable) is a Boolean algebra consisting of allI-tuples(...x_i,...)whosei-th element is taken fromB_i.The operations of a direct product are the corresponding operations of the constituent algebras acting within their respective coordinates; in particular operationⁿf_jof the product operates onnI-tuples by applying operationⁿf_jofB_ito thenelements in thei-th coordinate of thentuples, for alliinI.

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

Representation theorems

It can be shown that every finite Boolean algebra isisomorphicto some power set algebra.Hence the cardinality (number of elements) of a finite Boolean algebra is a power of2,namely one of1,2,4,8,...,2ⁿ,...This is called arepresentation theoremas it gives insight into the nature of finite Boolean algebras by giving arepresentationof them as power set algebras.

This representation theorem does not extend to infinite Boolean algebras: although every power set algebra is a Boolean algebra, not every Boolean algebra need be isomorphic to a power set algebra. In particular, whereas there can be nocountably infinitepower set algebras (the smallest infinite power set algebra is the power set algebra2^Nof sets of natural numbers,shownbyCantorto beuncountable), there exist various countably infinite Boolean algebras.

To go beyond power set algebras we need another construct. Asubalgebraof an algebraAis any subset ofAclosed under the operations ofA.Every subalgebra of a Boolean algebraAmust still satisfy the equations holding ofA,since any violation would constitute a violation forAitself. Hence every subalgebra of a Boolean algebra is a Boolean algebra.

Asubalgebraof a power set algebra is called afield of sets;equivalently a field of sets is a set of subsets of some setWincluding the empty set andWand closed under finite union and complement with respect toW(and hence also under finite intersection). Birkhoff's [1935] representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. NowBirkhoff's HSP theoremfor varieties can be stated as, every class of models of the equational theory of a classCof algebras is the Homomorphic image of aSubalgebraof adirect Productof algebras ofC.Normally all three of H, S, and P are needed; what the first of these two Birkhoff theorems shows is that for the special case of the variety of Boolean algebrasHomomorphismcan be replaced byIsomorphism.Birkhoff's HSP theorem for varieties in general therefore becomes Birkhoff's ISP theorem for thevarietyof Boolean algebras.

Other examples

It is convenient when talking about a setXof natural numbers to view it as a sequencex₀,x₁,x₂,...of bits, withx_i= 1if and only ifi∈X.This viewpoint will make it easier to talk aboutsubalgebrasof the power set algebra2^N,which this viewpoint makes the Boolean algebra of all sequences of bits.It also fits well with the columns of a truth table: when a column is read from top to bottom it constitutes a sequence of bits, but at the same time it can be viewed as the set of those valuations (assignments to variables in the left half of the table) at which the function represented by that column evaluates to 1.

Example 4.Ultimately constant sequences.Any Boolean combination of ultimately constant sequences is ultimately constant; hence these form a Boolean algebra. We can identify these with the integers by viewing the ultimately-zero sequences as nonnegative binary numerals (bit0of the sequence being the low-order bit) and the ultimately-one sequences as negative binary numerals (thinktwo's complementarithmetic 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 sequence.A sequence is calledperiodicwhen there exists some numbern> 0,called a witness to periodicity, such thatx_i=x_i+nfor alli≥ 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 as1,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 sequencexwith a sequence of coprime period (greater than 1) is neither0norx.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.Periodic sequence with period a power of two.This is a propersubalgebraof Example 5 (a proper subalgebra equals the intersection of itself with its algebra). 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 ofx₀in the table of binary operations, namely²f₁₀,has period2(and so can be recognized as using only the first variable) even though 12 of the binary operations have period4.When the period is2ⁿthe operation only depends on the firstnvariables, 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.Ultimately periodic sequences,sequences that become periodic after an initial finite bout of lawlessness. They constitute a proper extension of Example 5 (meaning that Example 5 is a propersubalgebraof Example 7) and also of Example 4, since constant sequences are periodic with period one. 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 example 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 atomlesssubalgebra,namely Example 5, and so is not isomorphic to Example 4, everysubalgebraof which must be a Boolean algebra of finite sets and their complements and therefore atomic. This example is isomorphic to the direct product of Examples 4 and 5, furnishing another description of it.

Example 8.Thedirect productof a Periodic Sequence (Example 5) with any finite but nontrivial Boolean algebra. (The trivial one-element Boolean algebra is the unique finite atomless Boolean algebra.) This resembles Example 7 in having both atoms and an atomlesssubalgebra,but differs in having only finitely many atoms. Example 8 is in fact an infinite family of examples, one for each possible finite number of atoms.

These examples by no means exhaust the possible Boolean algebras, even the countable ones. Indeed, there are uncountably many nonisomorphic countable Boolean algebras, which Jussi Ketonen [1978] classified completely in terms of invariants representable by certain hereditarily countable sets.

Boolean algebras of Boolean operations

Then-ary Boolean operations themselves constitute a power set algebra2^W,namely whenWis taken to be the set of2ⁿvaluations of theninputs. In terms of the naming system of operationsⁿf_iwhereiin 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 aritymtomBoolean operations of aritynto yield a Boolean operation of arityn,for anymandn.

The practical significance of this convention for both software and hardware is thatn-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 takex,y,andz(dispensing with subscripted variables for now) to be10101010,11001100,and11110000respectively (170, 204, and 240 in decimal,0xaa,0xcc,and0xf0in hexadecimal), their pairwise conjunctions arex∧y= 10001000,y∧z= 11000000,andz∧x= 10100000,while their pairwise disjunctions arex∨y= 11101110,y∨z= 11111100,andz∨x= 11111010.The disjunction of the three conjunctions is11101000,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\land y)\lor (y\land z)\lor (z\land x)$

and

$(x\lor y)\land (y\lor z)\land (z\lor x)$

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

$(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 the3! = 6permutations of its arguments. The two halves of its truth table11101000are the truth tables for∨,1110,and∧,1000,so the operation can be phrased asifzthenx∨yelsex∧y.Since it is symmetric it can equally well be phrased as either ofifxtheny∨zelsey∧z,orifythenz∨xelsez∧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 themedian 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).

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 completeaxiomatizationof, oraxiomatic systemfor, the equational laws ofBoolean 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 finiteaxiom schemahaving 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 forms=twheresandtaren-ary terms, by which we shall mean here terms whose variables are limited tox₀throughx_n-1.Ann-arytermis either an atom or an application. An application^mf_i(t₀,...,t_m-1)is a pair consisting of anm-ary operation^mf_iand a list orm-tuple(t₀,...,t_m-1)ofmn-ary terms calledoperands.

Associated with every term is a natural number called itsheight.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 variablex_iwhere0 ≤i<n.For the proof technique here it is convenient to define atoms instead to ben-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 then-ary operationsⁿf₀andⁿf₋₁for eachn(abbreviating2²ⁿ−1to−1), and the variablesx₀,...,x_n-1as can be seen from the truth tables wherex₀appears as both the unary operation¹f₂and the binary operation²f₁₀whilex₁appears as²f₁₂.

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

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

R1.With no premises infert=t.

R2.Froms=uandt=uinfers=twheres,t,anduaren-ary terms.

R3.Froms₀=t₀,...,s_m-1=t_m-1infer^mf_i(s₀,...,s_m-1) =^mf_i(t₀,...,t_m-1),where all termss_i,t_iaren-ary.

The meaning of the side condition onA1is thatioĵis that2ⁿ-bit number whosev-th bit is theĵ_v-th bit ofi,where the ranges of each quantity areu:m,v:2ⁿ,j_u:2²ⁿ,andĵ_v:2^m.(Sojis anm-tuple of2ⁿ-bit numbers whileĵas the transpose ofjis a2ⁿ-tuple ofm-bit numbers. Bothjandĵtherefore containm2ⁿbits.)

A1is an axiom schema rather than an axiom by virtue of containingmetavariables,namelym,i,n,andj₀throughj_m-1.The actual axioms of the axiomatization are obtained by setting the metavariables to specific values. For example, if we takem=n=i=j₀= 1,we can compute the two bits ofioĵfromi₁= 0andi₀= 1,soioĵ= 2(or10when written as a two-bit number). The resulting instance, namely¹f₁(¹f₁) =¹f₂,expresses the familiar axiom¬¬x=xof double negation. RuleR3then allows us to infer¬¬¬x= ¬xby takings₀to be¹f₁(¹f₁)or¬¬x₀,t₀to be¹f₂orx₀,and^mf_ito be¹f₁or¬.

For eachmandnthere are only finitely many axioms instantiatingA1,namely2^2m× (2²ⁿ)^m.Each instance is specified by2^m+m2ⁿbits.

We treatR1as an inference rule, even though it is like an axiom in having no premises, because it is a domain-independent rule along withR2andR3common to all equational axiomatizations, whether of groups, rings, or any other variety. The only entity specific to Boolean algebras is axiom schemaA1.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 laws=tis provable in this system. One first shows by induction on the height ofsthat every Boolean law for whichtis atomic is provable, usingR1for the base case (since distinct atoms are never equal) andA1andR3for the induction step (san application). This proof strategy amounts to a recursive procedure for evaluatingsto yield an atom. Then to proves=tin the general case whentmay be an application, use the fact that ifs=tis an identity thensandtmust evaluate to the same atom, call itu.So first proves=uandt=uas above, that is, evaluatesandtusingA1,R1,andR3,and then invokeR2to infers=t.

InA1,if we view the numbern^mas the function typem→n,andm_nas the applicationm(n),we can reinterpret the numbersi,j,ĵ,andioĵas functions of typei:(m→2)→2,j:m→((n→2)→2),ĵ:(n→2)→(m→2),andioĵ:(n→2)→2.The definition(ioĵ)_v=i_ĵvinA1then translates to(ioĵ)(v) =i(ĵ(v)),that is,ioĵis defined to be composition ofiandĵunderstood as functions. So the content ofA1amounts to defining term application to be essentially composition, modulo the need to transpose them-tuplejto 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 ofA1as the logical representation of that particular composition law.

Underlying lattice structure

Underlying every Boolean algebraBis apartially ordered setorposet(B,≤).Thepartial orderrelation is defined byx≤yjust whenx=x∧y,or equivalently wheny=x∨y.Given a setXof elements of a Boolean algebra, anupper boundonXis an elementysuch that for every elementxofX,x≤y,while a lower bound onXis an elementysuch that for every elementxofX,y≤x.

AsupofXis a least upper bound onX,namely an upper bound onXthat is less or equal to every upper bound onX.Dually aninfofXis a greatest lower bound onX.The sup ofxandyalways exists in the underlying poset of a Boolean algebra, beingx∨y,and likewise their inf exists, namelyx∧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 pairx,yof elements has both a sup and an inf is called alattice.We writex∨yfor the sup andx∧yfor the inf. The underlying poset of a Boolean algebra always forms a lattice. The lattice is said to bedistributivewhenx∧(y∨z) = (x∧y)∨(x∧z),or equivalently whenx∨(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 pairx,yof elements is calledcomplementarywhenx∧y= 0andx∨y= 1,and we then say thatyis a complement ofxand vice versa. Any elementxof 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, evenx=y,and is therefore sometimes referred to as the inconsistent Boolean algebra.

Boolean homomorphisms

A Booleanhomomorphismis a functionh:A→Bbetween Boolean algebrasA,Bsuch that for every Boolean operation^mf_i:

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

ThecategoryBoolof 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 algebra2to every Boolean algebra, since homomorphisms must preserve the two constants and those are the only elements of2.A Boolean algebra with this property is called aninitialBoolean algebra. It can be shown that any two initial Boolean algebras are isomorphic, so up to isomorphism2istheinitial Boolean algebra.

In the other direction, there may exist many homomorphisms from a Boolean algebraBto2.Any such homomorphism partitionsBinto those elements mapped to 1 and those to 0. The subset ofBconsisting of the former is called anultrafilterofB.WhenBis finite its ultrafilters pair up with its atoms; one atom is mapped to 1 and the rest to 0. Each ultrafilter ofBthus consists of an atom ofBand all the elements above it; hence exactly half the elements ofBare 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 fornonstandard 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. Acomplete Boolean algebrais one every subset of which has both a sup and an inf, even the infinite subsets. Gaifman [1964] andHales[1964] independently showed that infinitefreecomplete Boolean algebrasdo 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 ofalloperations on {0,1} of arity up to the cardinality of the model is called a complete atomic Boolean algebra, orCABA.(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 differentcardinality.) Such an algebra can be defined equivalently as acomplete Boolean algebrathat isatomic,meaning that every element is a sup of some set of atoms. Free CABAs exist for all cardinalities of a setVofgenerators,namely thepower setalgebra2^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 offreecomplete Boolean algebrascan 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 calledcompletely distributivewhen 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 categoryCABAof 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 categoryBoolof Boolean algebras and their homomorphisms, whichMarshall Stoneshowed in effect (though he lacked both the language and the conceptual framework to make the duality explicit) to be dual to the category oftotally disconnectedcompact Hausdorff spaces,subsequently calledStone spaces.

Another infinitary class intermediate between Boolean algebras andcomplete Boolean algebrasis the notion of asigma-algebra.This is defined analogously to complete Boolean algebras, but withsupsandinfslimited to countable arity. That is, asigma-algebrais a Boolean algebra with all countable sups and infs. Because the sups and infs are of boundedcardinality,unlike the situation withcomplete Boolean algebras,the Gaifman-Hales result does not apply andfreesigma-algebrasdo exist. Unlike the situation with CABAs however, the free countably generated sigma algebra is not a power set algebra.

Other definitions of Boolean 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 allclopen setsof atopological space.It is no limitation to require the space to be a totally disconnected compactHausdorff space,orStone space,that is, every Boolean algebra arises in this way, up toisomorphism.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 toStone spaces.This definition is fleshed out by the next definition.

Johnstone (1982)

A Boolean algebra is afiltered colimitof 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 givesStone spacesorprofinite 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 beHausdorff,isdiscretefor inductive objects andcompactfor 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.

See also

• Boolean domain
• Boolean function
• Boolean-valued function
• Boolean-valued model
• Cartesian closed category
• Closed monoidal category
• Complete Boolean algebra
• Elementary topos
• Field of sets
• Filter (mathematics)
• Finitary boolean function
• Free Boolean algebra
• Functional completeness
• Ideal (order theory)
• Lattice (order)
• Lindenbaum–Tarski algebra
• List of Boolean algebra topics
• Monoidal category
• Propositional calculus
• Robbins algebra
• Truth table
• Ultrafilter
• Universal algebra

References

• 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.ISSN0008-1981.S2CID121173630.
• Boole, George(2003) [1854].An Investigation of the Laws of Thought.Prometheus Books.ISBN978-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.ISSN0016-2736.
• Givant, Steven; Halmos, Paul (2009).Introduction to Boolean Algebras.Undergraduate Texts in Mathematics.Springer.ISBN978-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.ISSN0016-2736.
• Halmos, Paul(1963).Lectures on Boolean Algebras.van Nostrand.ISBN0-387-90094-2.
• Givant, Steven; Halmos, Paul (1998).Logic as Algebra.Dolciani Mathematical Exposition.Mathematical Association of America.ISBN978-0-883-85327-6.
• Johnstone, Peter T.(1982).Stone Spaces.Cambridge, UK: Cambridge University Press.ISBN978-0-521-33779-3.
• Ketonen, Jussi (1978). "The structure of countable Boolean algebras".Annals of Mathematics.108(1): 41–89.doi:10.2307/1970929.JSTOR1970929.
• Koppelberg, Sabine (1989) "General Theory of Boolean Algebras" in Monk, J. Donald, and Bonnet, Robert, eds.,Handbook of Boolean Algebras, Vol. 1.North Holland.ISBN978-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.ISBN978-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.PMC221940.PMID16591125.
• 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.ISBN978-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.ISSN0002-9947.JSTOR1989664.
• 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.ISSN0016-2736.
  • Tarski, Alfred(1935)."Zur Grundlegung der Booleschen Algebra, I".Fundamenta Mathematicae.24:177–98.doi:10.4064/fm-24-1-177-198.ISSN0016-2736.
• Vladimirov, D.A. (1969).булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974).Nauka (German translation Akademie-Verlag).