Boolean algebras canonically defined
Encyclopedia
Boolean algebra
is a mathematically rich branch of abstract algebra
. Just as group theory
deals with groups
, and linear algebra
with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1 (whose interpretation need not be numerical). Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure
, a set closed under zero or more operations
satisfying certain equations.
Just as there are basic examples of groups, such as the group Z of integer
s and the permutation group
Sn of permutation
s of n objects, there are also basic examples of Boolean algebra such as the following.
Boolean algebra thus permits applying the methods of abstract algebra
to mathematical logic
, digital logic, and the set-theoretic foundations of mathematics
.
Unlike groups
of finite order
, which exhibit complexity and diversity and whose first-order
theory is decidable
only 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 the algorithm
ic complexity of their syntactic
structure.
algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras. 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 2n possible values for its n arguments. For each choice of arguments the operation may return 0 or 1, whence there are 22n 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 operation
s, 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 operation
s; 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 162 = 256 ternary operations, 2562 = 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 22n 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. It is convenient to consider the i-th n-ary symbol to be nfi 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.
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.
or NAND basis. These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.
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 x2 = 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:
The NAND
(dually NOR) operation lacks all these, thus forming a basis by itself.
s, thinking of 0 and 1 as the truth values false and true. 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 the n-ary operations are binary numbers of 2n bits. There being 22n 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.
These tables continue at higher arities, with 2n rows at arity n, each row giving a valuation or binding of the n variables x0,…xn−1 and each column headed nfi giving the value nfi(x0,…,xn−1) of the i-th n-ary operation at that valuation. The operations include the variables, for example 1f2 is x0 while 2f10 is x0 (as two copies of its unary counterpart) and 2f12 is x1 (with no unary counterpart). Negation or complement ¬x0 appears as 1f1 and again as 2f5, along with 2f3 (¬x1, which did not appear at arity 1), disjunction or union x0∨x1 as 2f14, conjunction or intersection x0∧x1 as 2f8, implication x0→x1 as 2f13, exclusive-or symmetric difference x0⊕x1 as 2f6, set difference x0−x1 as 2f2, 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 clone 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.
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).
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 number
ing 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.
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.
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 Bi 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 (…xi,…) whose i-th element is taken from Bi. The operations of a direct product are the corresponding operations of the constituent algebras acting within their respective coordinates; in particular operation nfj of the product operates on n I-tuples by applying operation nfj of Bi 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 set algebra of a 32-element set, denoted 232. The Boolean algebra of all sets of integers is 2Z. All Boolean algebras we have exhibited thus far have been direct powers of the two-element Boolean algebra, justifying the name "power set algebra".
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 no countably infinite power set algebras (the smallest infinite power set algebra is the power set algebra 2N of sets of natural numbers, shown by Cantor
to be uncountable), there exist various countably infinite Boolean algebras.
To go beyond power set 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 set algebra is called a field of sets; equivalently a field of sets is a set of subsets of some set W including the empty set and W and closed under finite union and complement with respect to W (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. Now Birkhoff's HSP theorem
for varieties can be stated as, every class of models of the equational theory of a class C of algebras is the Homomorphic image of a Subalgebra
of a direct Product
of algebras of C. 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 algebras Homomorphism
can be replaced by Isomorphism
. Birkhoff's HSP theorem for varieties in general therefore becomes Birkhoff's ISP theorem for the variety
of Boolean algebras.
s of the power set algebra 2N, 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 (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 sequence. A sequence is called periodic when there exists some number n > 0, called a witness to periodicity, such that xi = xi+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. Periodic sequence with period a power of two. This is a proper subalgebra
of 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 of x0 in the table of binary operations, namely 2f10, 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 2n 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. 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 proper subalgebra
of 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 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. This example is isomorphic to the direct product of Examples 4 and 5, furnishing another description of it.
Example 8. The direct product
of 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 atomless subalgebra
, 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.
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
and
are actually the same operation. That is, we have proved the equational identity
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).
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 x0 through xn-1. An n-ary term is either an atom or an application. An application mfi(t0,…,tm-1) is a pair consisting of an m-ary operation mfi and a list or m-tuple (t0,…,tm-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 xi where 0 ≤ i < n. For the proof technique here it is convenient to define atoms instead to be n-ary operations nfi, which although treated here as atoms nevertheless mean the same as ordinary terms of the exact form nfi(x0,…,xn-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 nf0 and nf−1 for each n (abbreviating 22n−1 to −1), and the variables x0,…,xn-1 as can be seen from the truth tables where x0 appears as both the unary operation 1f2 and the binary operation 2f10 while x1 appears as 2f12.
The following axiom schema and three inference rules axiomatize the Boolean algebra of n-ary terms.
The meaning of the side condition on A1 is that ioĵ is that 2n-bit number whose v-th bit is the ĵv-th bit of i, where the ranges of each quantity are u: m, v: 2n, ju: 22n, and ĵv: 2m. (So j is an m-tuple of 2n-bit numbers while ĵ as the transpose of j is a 2n-tuple of m-bit numbers. Both j and ĵ therefore contain m2n bits.)
A1 is an axiom schema rather than an axiom by virtue of containing metavariables, namely m, i, n, and j0 through jm-1. The actual axioms of the axiomatization are obtained by setting the metavariables to specific values. For example if we take m = n = i = j0 = 1, we can compute the two bits of ioĵ from i1 = 0 and i0 = 1, so ioĵ = 2 (or 10 when written as a two-bit number). The resulting instance, namely 1f1(1f1) = 1f2, expresses the familiar axiom ¬¬x = x of double negation. Rule R3 then allows us to infer ¬¬¬x = ¬x by taking s0 to be 1f1(1f1) or ¬¬x0, t0 to be 1f2 or x0, and mfi to be 1f1 or ¬.
For each m and n there are only finitely many axioms instantiating A1, namely 22m × (22n)m. Each instance is specified by 2m+m2n 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 nm as the function type m→n, and mn 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.
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 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.
is a function h: A→B between Boolean algebras A, B such that for every Boolean operation mfi,
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 or equal than 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.
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 algebra
s 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 22V, 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 algebra
s 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 algebra
s 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 algebra
s, the Gaifman-Hales result does not apply and free
sigma-algebra
s do exist. Unlike the situation with CABAs however, the free countably generated sigma algebra is not a power set algebra.
Stone (1936): A Boolean algebra is the set of all clopen set
s 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.
Boolean algebra
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets...
is a mathematically rich branch of abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
. Just as group theory
Group theory
In mathematics and abstract algebra, group theory studies the algebraic structures known as groups.The concept of a group is central to abstract algebra: other well-known algebraic structures, such as rings, fields, and vector spaces can all be seen as groups endowed with additional operations and...
deals with groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, and linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1 (whose interpretation need not be numerical). Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure
Algebraic structure
In abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
, a set closed under zero or more operations
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....
satisfying certain equations.
Just as there are basic examples of groups, such as the group Z of integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s and the permutation group
Permutation group
In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G ; the relationship is often written as...
Sn of permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s of n objects, there are also basic examples of Boolean algebra such as the following.
- The algebra of binary digits or bits 0 and 1 under the logical operations including disjunction, conjunction, and negation. Applications include the propositional calculusPropositional calculusIn mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
and the theory of digital circuits. - The algebra of setsAlgebra of setsThe algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion...
under the set operations including unionUnion (set theory)In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
, intersectionIntersection (set theory)In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....
, and complementComplement (set theory)In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
. Applications include any area of mathematics for which sets form a natural foundation.
Boolean algebra thus permits applying the methods of abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
to mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, digital logic, and the set-theoretic foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...
.
Unlike groups
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
of finite order
Order (group theory)
In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....
, which exhibit complexity and diversity and whose first-order
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
theory is decidable
Decidable
The word decidable may refer to:* Decidable language*Decidability for the equivalent in mathematical logic*Gödel's incompleteness theorem, a theorem on the indecidability of languages consisting of "true statements" in mathematical logic....
only 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 the algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
ic complexity of their syntactic
Syntax
In linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....
structure.
Definition
Boolean algebra treats the equational theory of the maximal two-element finitaryFinitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...
algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras. These terms are defined as follows.
An algebra
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
is a family
Indexed family
In mathematics, an indexed family is a collection of values that are associated with indexes. For example, a family of real numbers, indexed by the integers is a collection of real numbers, where each integer is associated with one of the real numbers....
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
Finitary
In mathematics or logic, a finitary operation is one, like those of arithmetic, that takes a finite number of input values to produce an output. An operation such as taking an integral of a function, in calculus, is defined in such a way as to depend on all the values of the function , and is so...
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
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
of the operation. An operation on {0,1} of arity n, or n-ary operation, can be applied to any of 2n possible values for its n arguments. For each choice of arguments the operation may return 0 or 1, whence there are 22n 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 operation
Unary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
s, 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 operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
s; 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 162 = 256 ternary operations, 2562 = 65,536 quaternary operations, and so on.
A family
Indexed family
In mathematics, an indexed family is a collection of values that are associated with indexes. For example, a family of real numbers, indexed by the integers is a collection of real numbers, where each integer is associated with one of the real numbers....
is indexed by an index set
Index set
In mathematics, the elements of a set A may be indexed or labeled by means of a set J that is on that account called 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 22n 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. It is convenient to consider the i-th n-ary symbol to be nfi 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.
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. A basis is any set from which the remaining operations can be obtained by composition. A "Boolean algebra" may be defined from any basis. Three bases for Boolean algebra are in common use, the lattice basis, the ring basis, and the Sheffer strokeSheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...
or NAND basis. These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.
- The latticeLattice (order)In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
basis originated in the 19th century with the work of Boole, Peirce, and others seeking an algebraic formalization of logical thought processes. - The ringBoolean ringIn mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists only of idempotent elements....
basis emerged in the 20th century with the work of ZhegalkinIvan Ivanovich ZhegalkinIvan Ivanovich Zhegalkin was a Russian mathematician...
and Stone and became the basis of choice for algebraists coming to the subject from a background in abstract algebraAbstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
. Most treatments of Boolean algebra assume the lattice basis, a notable exception being HalmosPaul HalmosPaul Richard Halmos was a Hungarian-born American mathematician who made fundamental advances in the areas of probability theory, statistics, operator theory, ergodic theory, and functional analysis . He was also recognized as a great mathematical expositor.-Career:Halmos obtained his B.A...
[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 the Sheffer strokeSheffer strokeIn Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...
NAND (or its dual NOR), the resulting economical basis has become the basis of choice for analyzing digital circuitDigital circuitDigital electronics represent signals by discrete bands of analog levels, rather than by a continuous range. All levels within a band represent the same signal state...
s, in particular gate arrayGate arrayA gate array or uncommitted logic array is an approach to the design and manufacture of application-specific integrated circuits...
s in digital electronics.
The common elements of the lattice and ring bases are the constants 0 and 1, and an associative commutative binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
, called meet
Meet (mathematics)
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
x∧y in the lattice basis, and multiplication
Multiplication
Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....
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
Addition
Addition is a mathematical operation that represents combining collections of objects together into a larger collection. It is signified by the plus sign . For example, in the picture on the right, there are 3 + 2 apples—meaning three apples and two other apples—which is the same as five apples....
(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
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
satisfying x∧¬x = 0 and x∨¬x = 1, called a complemented
Complemented lattice
In the mathematical discipline of order theory, a complemented lattice is a bounded lattice in which every element a has a complement, i.e. an element b satisfying a ∨ b = 1 and a ∧ b = 0....
distributive lattice. The ring basis turns a Boolean algebra into a Boolean ring
Boolean ring
In mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists only of idempotent elements....
, namely a ring satisfying x2 = 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
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
," 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:
- monotoneMonotonic functionIn mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....
, no 0-1 input transition can cause a 1-0 output transition; - affineAffine transformationIn geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...
, representable with Zhegalkin polynomialZhegalkin polynomialZhegalkin polynomials form one of many possible representations of the operations of boolean algebra. Introduced by the Russian mathematician I.I. Zhegalkin in 1927, they are the polynomials of ordinary high school algebra interpreted over the integers mod 2...
s that lack bilinearBilinearBilinear may refer to:* Bilinear sampling, a method in computer graphics for choosing the color of a texture* Bilinear form* Bilinear interpolation* Bilinear map, a type of mathematical function between vector spaces...
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;
- strictStrict functionA strict function in the denotational semantics of programming languages is a function f where f\left = \perp. The entity \perp, called bottom, denotes an expression which does not return a normal value, either because it loops endlessly or because it aborts due to an error such as division by...
(mapping the all-zeros input to zero); - costrict (mapping all-ones to one).
The NAND
Nand
NAND may stand for:*Nand , an Indian classical raga.*Logical NAND , a binary operation in logic.**NAND gate, an electronic gate that implements a logical NAND....
(dually NOR) operation lacks all these, thus forming a basis by itself.
Truth tables
The finitary operations on {0,1} may be exhibited as truth tableTruth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
s, thinking of 0 and 1 as the truth values false and true. 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 the n-ary operations are binary numbers of 2n bits. There being 22n 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.
These tables continue at higher arities, with 2n rows at arity n, each row giving a valuation or binding of the n variables x0,…xn−1 and each column headed nfi giving the value nfi(x0,…,xn−1) of the i-th n-ary operation at that valuation. The operations include the variables, for example 1f2 is x0 while 2f10 is x0 (as two copies of its unary counterpart) and 2f12 is x1 (with no unary counterpart). Negation or complement ¬x0 appears as 1f1 and again as 2f5, along with 2f3 (¬x1, which did not appear at arity 1), disjunction or union x0∨x1 as 2f14, conjunction or intersection x0∧x1 as 2f8, implication x0→x1 as 2f13, exclusive-or symmetric difference x0⊕x1 as 2f6, set difference x0−x1 as 2f2, 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 clone 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.
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
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
, so it would not be unreasonable to call it Turing order).
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 number
Gödel number
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...
ing 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.
Bit vectors
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 4 formed by oring the three bits in each of the four bit positions, thus 0100∨1000∨1001 = 1101. Another example is the truth tables above for the n-ary operations, whose columns are all the bit vectors of length 2n and which therefore can be combined pointwise whence the n-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.
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.
Power set algebra
Example 3. The power set algebra, the set 2W of all subsets of a given set W. 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 set 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
Direct product
In mathematics, one can often define a direct product of objectsalready known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set....
, applicable not just to Boolean algebras but all kinds of algebra including groups, rings, etc. The direct product of any family Bi 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 (…xi,…) whose i-th element is taken from Bi. The operations of a direct product are the corresponding operations of the constituent algebras acting within their respective coordinates; in particular operation nfj of the product operates on n I-tuples by applying operation nfj of Bi 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 set algebra of a 32-element set, denoted 232. The Boolean algebra of all sets of integers is 2Z. 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 is isomorphic to some power set algebra. Hence the cardinality (number of elements) of a finite Boolean algebra is a power of 2, namely one of 1,2,4,8,…,2n,… 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 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 no countably infinite power set algebras (the smallest infinite power set algebra is the power set algebra 2N of sets of natural numbers, shown by Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
to be uncountable), there exist various countably infinite Boolean algebras.
To go beyond power set algebras we need another construct. A subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
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
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
of a power set algebra is called a field of sets; equivalently a field of sets is a set of subsets of some set W including the empty set and W and closed under finite union and complement with respect to W (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. Now Birkhoff's HSP theorem
Variety (universal algebra)
In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
for varieties can be stated as, every class of models of the equational theory of a class C of algebras is the Homomorphic image of a Subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
of a direct Product
Direct product
In mathematics, one can often define a direct product of objectsalready known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set....
of algebras of C. 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 algebras Homomorphism
Homomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
can be replaced by Isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
. Birkhoff's HSP theorem for varieties in general therefore becomes Birkhoff's ISP theorem for the variety
Variety (universal algebra)
In mathematics, specifically universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. Equivalently, a variety is a class of algebraic structures of the same signature which is closed under the taking of homomorphic...
of Boolean algebras.
Other examples
It is convenient when talking about a set X of natural numbers to view it as a sequence x0,x1,x2,… of bits, with xi = 1 if and only if i ∈ X. This viewpoint will make it easier to talk about subalgebraSubalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
s of the power set algebra 2N, 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 (bit 0 of the sequence being the low-order bit) and the ultimately-one sequences as negative binary numerals (think two's complement
Two's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
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 sequence. A sequence is called periodic when there exists some number n > 0, called a witness to periodicity, such that xi = xi+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. Periodic sequence with period a power of two. This is a proper subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
of 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 of x0 in the table of binary operations, namely 2f10, 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 2n 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. 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 proper subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
of 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 atomless subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
, namely Example 5, and so is not isomorphic to Example 4, every subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
of 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. The direct product
Direct product
In mathematics, one can often define a direct product of objectsalready known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set....
of 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 atomless subalgebra
Subalgebra
In mathematics, the word "algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operation. Algebras in universal algebra are far more general: they are a common generalisation of all algebraic structures...
, 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
The n-ary Boolean operations themselves constitute a power set algebra 2W, namely when W is taken to be the set of 2n valuations of the n inputs. In terms of the naming system of operations nfi 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
- (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 [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).
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 systemAxiomatic system
In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A mathematical theory consists of an axiomatic system and all its derived theorems...
for, the equational laws of Boolean logic
Boolean logic
Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
. 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
Axiom schema
In mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
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 x0 through xn-1. An n-ary term is either an atom or an application. An application mfi(t0,…,tm-1) is a pair consisting of an m-ary operation mfi and a list or m-tuple (t0,…,tm-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 xi where 0 ≤ i < n. For the proof technique here it is convenient to define atoms instead to be n-ary operations nfi, which although treated here as atoms nevertheless mean the same as ordinary terms of the exact form nfi(x0,…,xn-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 nf0 and nf−1 for each n (abbreviating 22n−1 to −1), and the variables x0,…,xn-1 as can be seen from the truth tables where x0 appears as both the unary operation 1f2 and the binary operation 2f10 while x1 appears as 2f12.
The following axiom schema and three inference rules axiomatize the Boolean algebra of n-ary terms.
- A1. mfi(nfj0,…,nfjm-1) = nfioĵ where (ioĵ)v = iĵv, with ĵ being j transpose, defined by (ĵv)u = (ju)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 s0 = t0,…,sm-1 = tm-1 infer mfi(s0,…,sm-1) = mfi(t0,…,tm-1), where all terms si, ti are n-ary.
The meaning of the side condition on A1 is that ioĵ is that 2n-bit number whose v-th bit is the ĵv-th bit of i, where the ranges of each quantity are u: m, v: 2n, ju: 22n, and ĵv: 2m. (So j is an m-tuple of 2n-bit numbers while ĵ as the transpose of j is a 2n-tuple of m-bit numbers. Both j and ĵ therefore contain m2n bits.)
A1 is an axiom schema rather than an axiom by virtue of containing metavariables, namely m, i, n, and j0 through jm-1. The actual axioms of the axiomatization are obtained by setting the metavariables to specific values. For example if we take m = n = i = j0 = 1, we can compute the two bits of ioĵ from i1 = 0 and i0 = 1, so ioĵ = 2 (or 10 when written as a two-bit number). The resulting instance, namely 1f1(1f1) = 1f2, expresses the familiar axiom ¬¬x = x of double negation. Rule R3 then allows us to infer ¬¬¬x = ¬x by taking s0 to be 1f1(1f1) or ¬¬x0, t0 to be 1f2 or x0, and mfi to be 1f1 or ¬.
For each m and n there are only finitely many axioms instantiating A1, namely 22m × (22n)m. Each instance is specified by 2m+m2n 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 nm as the function type m→n, and mn 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 lattice structure
Underlying every Boolean algebra B is a partially ordered setPartially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
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
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
) 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
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
) 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
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
. 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 homomorphismHomomorphism
In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures . The word homomorphism comes from the Greek language: ὁμός meaning "same" and μορφή meaning "shape".- Definition :The definition of homomorphism depends on the type of algebraic structure under...
is a function h: A→B between Boolean algebras A, B such that for every Boolean operation mfi,
- h(mfi(x0,…,xm−1)) = mfi(h(x0),…,h(xm−1)).
The category
Category (mathematics)
In mathematics, a category is an algebraic structure that comprises "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose...
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
Ultrafilter
In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
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 or equal than 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.
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 algebraComplete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
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
Free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....
complete Boolean algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
s 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
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
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
Generating set
In mathematics, the expressions generator, generate, generated by and generating set can have several closely related technical meanings:...
, namely the power set algebra 22V, 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
Free
Free may refer to:* Free will* Political freedom* Economic freedom* Something given or supplied without payment * Gratis versus Libre, the distinction between the two meanings aboveFree may also refer to:- Arts and philosophy :...
complete Boolean algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
s 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
Totally disconnected space
In topology and related branches of mathematics, a totally disconnected space is a topological space that is maximally disconnected, in the sense that it has no non-trivial connected subsets...
compact Hausdorff spaces, subsequently called Stone spaces.
Another infinitary class intermediate between Boolean algebras and complete Boolean algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
s is the notion of a sigma-algebra
Sigma-algebra
In mathematics, a σ-algebra is a technical concept for a collection of sets satisfying certain properties. The main use of σ-algebras is in the definition of measures; specifically, the collection of sets over which a measure is defined is a σ-algebra...
. This is defined analogously to complete Boolean algebras, but with sups
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
and infs
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
limited to countable arity. That is, a sigma-algebra
Sigma-algebra
In mathematics, a σ-algebra is a technical concept for a collection of sets satisfying certain properties. The main use of σ-algebras is in the definition of measures; specifically, the collection of sets over which a measure is defined is a σ-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 algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
s, the Gaifman-Hales result does not apply and free
Free object
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure . It also has a formulation in terms of category theory, although this is in yet more abstract terms....
sigma-algebra
Sigma-algebra
In mathematics, a σ-algebra is a technical concept for a collection of sets satisfying certain properties. The main use of σ-algebras is in the definition of measures; specifically, the collection of sets over which a measure is defined is a σ-algebra...
s do 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 all clopen set
Clopen set
In topology, a clopen set in a topological space is a set which is both open and closed. That this is possible for a set is not as counter-intuitive as it might seem if the terms open and closed were thought of as antonyms; in fact they are not...
s of a topological space
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
. It is no limitation to require the space to be a totally disconnected compact Hausdorff space
Hausdorff space
In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...
, or Stone space, that is, every Boolean algebra arises in this way, up to isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
. 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
Hausdorff space
In topology and related branches of mathematics, a Hausdorff space, separated space or T2 space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most frequently...
, is discrete
Discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...
for inductive objects and compact
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
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.
See also
- Boolean domainBoolean domainIn mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...
- Boolean function
- Boolean-valued functionBoolean-valued functionA boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....
- Boolean-valued modelBoolean-valued modelIn mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory. In a Boolean-valued model, the truth values of propositions are not limited to "true" and "false", but instead take values in some fixed complete Boolean...
- Cartesian closed categoryCartesian closed categoryIn category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in mathematical logic and the theory of programming, in...
- Closed monoidal categoryClosed monoidal categoryIn mathematics, especially in category theory, aclosed monoidal category is a context where we can take tensor products of objects and also form 'mapping objects'. A classic example is the category of sets, Set, where the tensor product of sets A and B is the usual cartesian product A \times B, and...
- Complete Boolean algebraComplete Boolean algebraIn mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
- Elementary topos
- Field of sets
- Filter (mathematics)Filter (mathematics)In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
- Finitary boolean function
- Free Boolean algebraFree Boolean algebraIn abstract algebra, a branch of mathematics, a free Boolean algebra is a Boolean algebra 〈B,F〉, such that the set B has a subset whose elements are called generators...
- Functional completeness
- Ideal (order theory)Ideal (order theory)In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
- Lattice (order)Lattice (order)In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
- Lindenbaum-Tarski algebra
- Minimal negation operator
- Monoidal categoryMonoidal categoryIn mathematics, a monoidal category is a category C equipped with a bifunctorwhich is associative, up to a natural isomorphism, and an object I which is both a left and right identity for ⊗, again up to a natural isomorphism...
- Multigrade operatorMultigrade operatorIn logic and mathematics, a multigrade operator \Omega is a parametric operator with parameter k in the set N of non-negative integers....
- Parametric operator
- Propositional calculusPropositional calculusIn mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...
- Robbins algebraRobbins algebraIn abstract algebra, a Robbins algebra is an algebra containing a single binary operation, usually denoted by \lor, and a single unary operation usually denoted by \neg...
- Truth tableTruth tableA truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
- UltrafilterUltrafilterIn the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
- Universal algebraUniversal algebraUniversal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....