View source for Boolean algebras canonically defined

MyWikiBiz, Author Your Legacy — Thursday December 26, 2024

← Boolean algebras canonically defined

You do not have permission to edit this page, for the following reasons:

• The action you have requested is limited to users in one of the groups: Users, vuser.
• You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

---

You can view and copy the source of this page.

:''Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the equivalence of both the lattice and ring definitions to this more elementary one.'' '''Boolean algebra''' is a branch of [[abstract algebra]] closely related to other branches such as [[group theory]] and [[linear algebra]]. Common to these subjects is the notion of an [[algebra]] as a set together with a family of operations on that set satisfying certain equations. Just as group theory deals with [[Group (mathematics)|groups]], and linear algebra with [[vector spaces]], so does Boolean algebra treat [[Boolean algebras]] as the models of the equational theory of two values. Just as there are basic examples of groups such as the group '''Z''' of integers and the group ''S''_''n'' of permutations of ''n'' objects, so does Boolean algebra have its basic examples, in particular the Boolean algebra of binary digits or bits 0 and 1 under the logical operations including disjunction, conjunction, and negation, and the [[algebra of sets]] under the set operations including union, intersection, and complement. The former example finds applications to both [[propositional calculus]] and [[digital circuits]], the latter to any area of mathematics for which sets form a natural foundation. Boolean algebra thus permits the general methodology of [[abstract algebra]] to be applied to mathematical logic, digital logic, and the set-theoretic foundations of mathematics, among other applications. Boolean algebra has a rich mathematical theory, though unlike group theory which exhibits complex diversity in its finite models, the finite Boolean algebras are trivial, with the subject's intricacies divided between the structure of infinite algebras and the algorithmic complexity of its syntactic structure. __TOC__ ==Definition== A '''Boolean algebra''' is any model of the finitary equational theory of two values. That is, it is a set together with operations on that set corresponding in arity and equational properties to the finitary operations on the set {0,1}. It is not necessary to furnish all such operations explicitly. Any set from which the remaining operations can be obtained by composition, called a ''basis'', will suffice for the purpose of fully defining "Boolean algebra." Boolean algebras are customarily defined on a finite basis, most commonly either the lattice basis or the ring basis. These bases impart respectively a logical and an arithmetic character to the subject. The lattice basis originated in the 19th century with the work of [[Boole]], [[Peirce]], and others seeking a logical analogue to algebra. The ring basis emerged in the 20th century with the work of [[Ivan Ivanovich Zhegalkin|Zhegalkin]] and [[Marshall Stone|Stone]] and became the basis of choice for algebraists coming to the subject from a ring-theoretic background. Many other bases have been considered for various purposes, such as the basis consisting solely of the [[Sheffer stroke]] or NOR (not-or) operation, whose economy has made it and its dual NAND the operations of choice for [[gate array]]s in [[digital electronics]]. The common elements of the lattice and ring bases are two constants 0 and 1 and an [[associative]] [[commutative]] [[binary operation]], conventionally called [[conjunction]] ''x''&and;''y'' in the lattice basis and [[multiplication]] ''xy'' in the ring basis, differing only in name. The lattice basis further has the logical operations ''x''&or;''y'' of [[disjunction]] and &not;''x'' of [[negation]] or [[complement]]. The ring basis has instead the arithmetic operation ''x''&oplus;''y'' of [[addition]] (the symbol &oplus; is used in preference to + because the latter is sometimes interpreted in Boolean algebra as disjunction). To be a basis is to yield all other operations by composition, whence any two bases must be intertranslatable. The lattice basis translates ''x''&or;''y'' to the ring basis as ''x''&oplus;''y''&oplus;''xy'', and &not;''x'' as ''x''&oplus;1. Conversely the ring basis translates ''x''&oplus;''y'' to the lattice basis as (''x''&or;''y'')&and;&not;(''x''&and;''y''). Both of these bases allow Boolean algebras to be defined via a finite selection of all the equational properties of the Boolean operations. For the lattice basis, it suffices to define a Boolean algebra as a [[distributive lattice]] satisfying ''x''&and;&not;''x'' = 0 and ''x''&or;&not;''x'' = 1, called a [[Complemented lattice|complemented]] distributive lattice. The ring basis makes a Boolean algebra a [[ring]] satisfying ''x''² = ''x'', called a [[Boolean ring]]. [[Emil Post]] gave a necessary and sufficient condition for a set of operations to be a basis. Define a property of operations to be ''nontrivial'' when some operations have the property and some don't. Post listed five nontrivial properties of operations, 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 of a candidate for basis-hood 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 [[Monotonic function|monotone]] (no 0-1 input transition can cause a 1-0 output transition), [[affine]] (representable with [[Zhegalkin polynomials]] that lack bilinear or higher terms, e.g. ''x''&oplus;''y''&oplus;1 but not ''xy''), [[De Morgan's laws|self-dual]] (complementing all inputs complements the output, as with ''x'', or the [[median operator]] ''xy''&oplus;''yz''&oplus;''zx'', or their negations), [[Strict function|strict]] (mapping the all-zeros input to zero), and costrict (mapping all-ones to one). The NAND operation lacks all these and so can form a basis all by itself. ==The prototypical Boolean algebra== With the concept of basis clarified we can now develop the subject independently of choice of basis. Just as linear algebra treats the whole vector space while keeping in mind the option of using this or that basis as convenient, so is it preferable to treat the whole ''clone'' (for "closed nest") of Boolean operations, namely the common closure under composition of every basis, without the appearance of dependence on or bias towards a particular choice of basis. This is easily accomplished with the representation of the clone as simply the finitary operations on {0,1}, which we take to be the ''prototypical Boolean algebra''. There being ''k''^{''k''<span>^''n''</span>} ''n''-ary operations ''f'':&nbsp;''X''^''n''&rarr;''X'' on a ''k''-element set ''X'', there are therefore 2^{2<span>^''n''</span>} ''n''-ary operations on {0,1}. It follows that every Boolean algebra, however small or large, has two constants or "nullary" operations, four unary operations, 16 binary operations, 256 ternary, etc., called the '''[[Boolean operation]]s''' of the given Boolean algebra. With the exception of the degenerate or one-element Boolean algebra (proscribed by a few of the earlier authors), all operations of a Boolean algebra can be shown to be distinct. (In the degenerate case all operations of a given arity must be the same operation since all return the same result on all inputs.) The operations on {0,1} may be exhibited as ''[[truth table]]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 2^''n'' bits. There being 2^{2<span>^''n''</span>} such operations, one cannot ask for a more succinct nomenclature! This layout and associated naming of operations is illustrated here in full for arities from 0 to 2. <div> <center> ::{| border="0" style="border:4px" |+ '''Truth tables for the Boolean operations of arity up to 2''' |- valign="top" | {| border="1" cellspacing="0" cellpadding="0" style="text-align:center;border:2px" |+ Constants |- | style="width:1px" | | style="width:2em" | ⁰''f''₀ | style="width:2em" | ⁰''f''₁ |- | || 0 || 1 |} | {| border="1" cellspacing="0" cellpadding="0" style="text-align:center;border:2px" |+ Unary Operations |- ! style="width:2em" | ''x''₀ | style="width:1px" | | style="width:2em" | ¹''f''₀ | style="width:2em" | ¹''f''₁ | style="width:2em" | ¹''f''₂ | style="width:2em" | ¹''f''₃ |- | 0 || || 0 || 1 || 0 || 1 |- | 1 || || 0 || 0 || 1 || 1 |} |- | colspan="5" | {| border="1" cellspacing="0" cellpadding="0" style="text-align:center;border:2px" |+ Binary Operations |- ! style="width:2em" | ''x''₀ ! style="width:2em" | ''x''₁ | style="width:1px" | | style="width:2em" | ²''f''₀ | style="width:2em" | ²''f''₁ | style="width:2em" | ²''f''₂ | style="width:2em" | ²''f''₃ | style="width:2em" | ²''f''₄ | style="width:2em" | ²''f''₅ | style="width:2em" | ²''f''₆ | style="width:2em" | ²''f''₇ | style="width:2em" | ²''f''₈ | style="width:2em" | ²''f''₉ | style="width:2em" | ²''f''₁₀ | style="width:2em" | ²''f''₁₁ | style="width:2em" | ²''f''₁₂ | style="width:2em" | ²''f''₁₃ | style="width:2em" | ²''f''₁₄ | style="width:2em" | ²''f''₁₅ |- | 0 || 0 || || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 |- | 1 || 0 || || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 |- | 0 || 1 || || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 |- | 1 || 1 || || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1 |} |} </center> </div> These tables continue at higher arities, with 2^''n'' rows at arity ''n'', each row giving a valuation or binding of the ''n'' variables ''x''₀,&hellip;''x''_''n''−1 and each column headed ^''n''''f''_''i'' giving the value ^''n''''f''_''i''(''x''₀,&hellip;,''x''_''n''−1) of the ''i''-th ''n''-ary operation at that valuation. The operations include the variables, for example ¹''f''₂ is ''x''₀ while ²''f''₁₀ is ''x''₀ (as two copies of its unary counterpart) and ²''f''₁₂ is ''x''₁ (with no unary counterpart). Negation or complement &not;''x''₀ appears as ¹''f''₁ and again as ²''f''₅, along with ²''f''₃ (&not;''x''₁, which did not appear at arity 1), disjunction or union ''x''₀&or;''x''₁ as ²''f''₁₄, conjunction or intersection ''x''₀&and;''x''₁ as ²''f''₈, implication ''x''₀&rarr;''x''₁ as ²''f''₁₃, exclusive-or or symmetric difference ''x''₀&oplus;''x''₁ as ²''f''₆, set difference ''x''₀&minus;''x''₁ as ²''f''₂, and so on. As a minor detail important more for its form than its content, the operations of an algebra are traditionally organized as a list. Although we are here indexing the operations of a Boolean algebra by the finitary operations on {0,1}, the truth-table presentation above serendipitously orders the operations first by arity and second by the layout of the tables for each arity. This permits organizing the 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. :(i) The ''i''-th row in the left half of the table is the binary representation of ''i'' with its least significant or 0-th bit on the left ("little-endian" order, originally proposed by [[Alan Turing]], so it would not be unreasonable to call it Turing order). :(ii) The ''j''-th column in the right half of the table is the binary representation of ''j'', again in little-endian order. In effect the subscript of the operation ''is'' the truth table of that operation. By analogy with [[Gödel 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 <tt>''x''|''y''</tt>, conjunction <tt>''x''&''y''</tt>, and negation <tt>~''x''</tt>. A program can therefore represent for example the operation ''x''&and;(''y''&or;''z'') in these languages as <tt>''x''&(''y''|''z'')</tt>, having previously set <tt>''x''&nbsp;= 0xaa</tt>, <tt>''y''&nbsp;= 0xcc</tt>, and <tt>''z''&nbsp;= 0xf0</tt> (the "<tt>0x</tt>" indicates that the following constant is to be read in hexadecimal or base 16), either by assignment to variables or defined as macros. These one-byte (eight-bit) constants correspond to the columns for the input variables in the extension of the above tables to three variables. This technique is almost universally used in raster graphics hardware to provide a flexible variety of ways of combining and masking images, the typical operations being ternary and acting simultaneously on source, destination, and mask bits. ==Examples: the power set algebras== '''Example 1'''. The set {0,1} with all finitary operations (indexed by themselves) constitutes the prototypical example of a Boolean algebra. It is prototypical in that all other Boolean algebras model the arities and equational properties of their operations on those of the prototype. '''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&or;1000&or;1001&nbsp;= 1101. This works equally well for bit vectors of finite and infinite length, the only rule being that the bit positions all be indexed by the same set in order that "corresponding position" be well defined. The '''atoms''' of such an algebra are the bit vectors containing exactly one 1. In general the atoms of a Boolean algebra are those elements ''x'' such that ''x''&and;''y'' has only two possible values, ''x'' or 0. '''Example 3'''. The set 2^''W'' of all subsets of a given set ''W'', called the power set algebra. This is just Example 2 in disguise, with ''W'' serving to index the bit positions. Any subset ''X'' of ''W'' can be viewed as the bit vector having 1's in just those bit positions indexed by elements of ''X''. Thus the all-zero vector is the empty subset of ''W'' while the all-ones vector is ''W'' itself, these being the constants 0 and 1 respectively of the power set algebra. The counterpart of disjunction ''x''&or;''y'' is union ''X''&cup;''Y'', while that of conjunction ''x''&and;''y'' is intersection ''X''&cap;''Y''. Negation &not;''x'' becomes ~''X'', complement relative to ''W''. There is also set difference ''X''∖''Y''&nbsp;= ''X''&cap;~''Y'', symmetric difference (''X''∖''Y'')&cup;(''Y''∖''X''), ternary union ''X''&cup;''Y''&cup;''Z'', and so on. The atoms here are the singletons, those subsets with exactly one element. Examples 2 and 3 are special cases of a general construct of algebra called [[direct product]], applicable not just to Boolean algebras but all kinds of algebra including groups, rings, etc. The direct product of any family ''B''_i of Boolean algebras where ''i'' ranges over some index set ''I'' (not necessarily finite or even countable) is a Boolean algebra consisting of all ''I''-tuples (&hellip;''x''_i,&hellip;) whose ''i''-th element is taken from ''B''_''i''. The operations of a direct product are the corresponding operations of the constituent algebras acting within their respective coordinates; in particular operation ^''n''''f''_''j'' of the product operates on ''n'' ''I''-tuples by applying operation ^''n''''f''_''j'' of ''B''_''i'' to the ''n'' elements in the ''i''-th coordinate of the ''n'' tuples, for all ''i'' in ''I''. When all the algebras being multiplied together in this way are the same algebra ''A'' we call the direct product a ''direct power'' of ''A''. The Boolean algebra of all 32-bit bit vectors is the two-element Boolean algebra raised to the 32nd power, or power set algebra of a 32-element set, denoted 2³². The Boolean algebra of all sets of integers is 2^'''Z'''. All Boolean algebras we have exhibited thus far have been direct powers of the two-element Boolean algebra, justifying the name "power set algebra". ==Other examples== 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,&hellip;,2^''n'',&hellip; 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 2^''N'' of sets of natural numbers, shown by [[Georg Cantor|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 [[variety (universal algebra)|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. It is convenient when talking about a set ''X'' of natural numbers to view it as a sequence ''x''₀,''x''₁,''x''₂,&hellip; of bits, with ''x''_''i''&nbsp;= 1 if and only if ''i'' &isin; ''X''. This viewpoint will make it easier to talk about subalgebras of the power set algebra 2^''N'', which this viewpoint makes the Boolean algebra of all sequences of bits. It also fits well with the columns of a truth table: when a column is read from top to bottom it constitutes a sequence of bits, but at the same time it can be viewed as the set of those valuations (assignments to variables in the left half of the table) at which the function represented by that column evaluates to 1. '''Example 4'''. Ultimately constant sequences. Any Boolean combination of ultimately constant sequences is ultimately constant, whence these form a Boolean algebra. We can identify these with the integers by viewing the ultimately-zero sequences as nonnegative binary numerals (bit 0 of the sequence being the low-order bit) and the ultimately-one sequences as negative binary numerals (think [[two's complement]] arithmetic with the all-ones sequence being −1). This makes the integers a Boolean algebra, with union being bit-wise OR and complement being ''−x−1''. There are only countably many integers, so this infinite Boolean algebra is countable. The atoms are the powers of two, namely 1,2,4,&hellip;. Another way of describing this algebra is as the set of all finite and cofinite sets of natural numbers, with the ultimately all-ones sequences corresponding to the cofinite sets, those sets omitting only finitely many natural numbers. '''Example 5'''. Periodic sequences. A sequence is called ''periodic'' when there exists some number ''n'' &gt; 0, called a witness to periodicity, such that ''x''_''i''&nbsp;= ''x''_''i''+''n'' for all ''i'' &ge; 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 sequences with period a power of two. This is a proper subalgebra of Example 5 ("proper" meaning that at least one element has been omitted). These can be understood as the finitary operations, with the first period of such a sequence giving the truth table of the operation it represents. For example the truth table of ''x''₀ in the table of binary operations, namely ²''f''₁₀, has period 2 (and so can be recognized as using only the first variable) even though 12 of the binary operations have period 4. When the period is 2^''n'' 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. These are 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 Example 5 with a finite Boolean algebra (other than the degenerate one-element Boolean algebra, which is the unique finite atomless Boolean algebra). This resembles Example 7 in having both atoms and an atomless subalgebra, but differs in 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 2^''W'', namely when ''W'' is taken to be the set of 2^''n'' valuations of the ''n'' inputs. In terms of the naming system of operations ^''n''''f''_''i'' where ''i'' in binary is a column of a truth table, the columns can be combined with Boolean operations of any arity to produce other columns present in the table. That is, we can apply any Boolean operation of arity ''m'' to ''m'' Boolean operations of arity ''n'' to yield a Boolean operation of arity ''n'', for any ''m'' and ''n''. The practical significance of this convention for both software and hardware is that ''n''-ary Boolean operations can be represented as words of the appropriate length. For example each of the 256 ternary Boolean operations can be represented as an unsigned byte. The available logical operations such as AND and OR can then be used to form new operations. If we take ''x'', ''y'', and ''z'' (dispensing with subscripted variables for now) to be 10101010, 11001100, and 11110000 respectively (170, 204, and 240 in decimal, 0xaa, 0xcc, and 0xf0 in hexadecimal), their pairwise conjunctions are ''x''&and;''y''&nbsp;= 10001000, ''y''&and;''z''&nbsp;= 11000000, and ''z''&and;''x''&nbsp;= 10100000, while their pairwise disjunctions are ''x''&or;''y''&nbsp;= 11101110, ''y''&or;''z''&nbsp;= 11111100, and ''z''&or;''x''&nbsp;= 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''&and;''y'')&or;(''y''&and;''z'')&or;(''z''&and;''x'') and : (''x''&or;''y'')&and;(''y''&or;''z'')&and;(''z''&or;''x'') are actually the same operation. That is, we have proved the equational identity : (''x''&and;''y'')&or;(''y''&and;''z'')&or;(''z''&and;''x'')&nbsp;= (''x''&or;''y'')&and;(''y''&or;''z'')&and;(''z''&or;''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!&nbsp;= 6 permutations of its arguments. The two halves of its truth table 11101000 are the truth tables for &or;, 1110, and &and;, 1000, so the operation can be phrased as '''if''' ''z'' '''then''' ''x''&or;''y'' '''else''' ''x''&and;''y''. Since it is symmetric it can equally well be phrased as either of '''if''' ''x'' '''then''' ''y''&or;''z'' '''else''' ''y''&and;''z'', or '''if''' ''y'' '''then''' ''z''&or;''x'' '''else''' ''z''&and;''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). ==Underlying lattice structure== Underlying every Boolean algebra ''B'' is a [[partially ordered set]] or '''poset''' (''B'',&le;). The '''partial order''' relation is defined by ''x'' &le; ''y'' just when ''x''&nbsp;= ''x''&and;''y'', or equivalently when ''y''&nbsp;= ''x''&or;''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'' &le; ''y'', while a lower bound on ''X'' is an element ''y'' such that for every element ''x'' of ''X'', ''y'' &le; ''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''&or;''y'', and likewise their inf exists, namely ''x''&and;''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'',&le;) such that every pair ''x'',''y'' of elements has both a sup and an inf is called a '''[[lattice (order)|lattice]]'''. We write ''x''&and;''y'' for the sup and ''x''&and;''y'' for the inf. The underlying poset of a Boolean algebra always forms a lattice. The lattice is said to be '''distributive''' when ''x''&and;(''y''&or;''z'')&nbsp;= (''x''&and;''y'')&or;(''x''&and;''z''), or equivalently when ''x''&or;(''y''&and;''z'')&nbsp;= (''x''&or;''y'')&and;(''x''&or;''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''&and;''y''&nbsp;= 0 and ''x''&or;''y''&nbsp;= 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''&nbsp;= ''y'', and is therefore sometimes referred to as the inconsistent Boolean algebra. ==Boolean homomorphisms== A Boolean [[homomorphism]] is a function ''h'': ''A''&rarr;''B'' between Boolean algebras ''A'', ''B'' such that for every Boolean operation ^''m''''f''_''i'', : ''h''(^''m''''f''_''i''(''x''₀,&hellip;,''x''_''m''−1))&nbsp;= ^''m''''f''_''i''(''h''(''x''₀),&hellip;,''h''(''x''_''m''−1)). The [[category]] '''Bool''' of Boolean algebras has as objects all Boolean algebras and as morphisms the Boolean homomorphisms between them. There exists a unique homomorphism from the two-element Boolean algebra '''2''' to every Boolean algebra, since homomorphisms must preserve the two constants and those are the only elements of '''2'''. A Boolean algebra with this property is called an '''initial''' Boolean algebra. It can be shown that any two initial Boolean algebras are isomorphic, so up to isomorphism '''2''' is ''the'' initial Boolean algebra. In the other direction, there may exist many homomorphisms from a Boolean algebra ''B'' to '''2'''. Any such homomorphism partitions ''B'' into those elements mapped to 1 and those to 0. The subset of ''B'' consisting of the former is called an '''ultrafilter''' of ''B''. When ''B'' is finite its ultrafilters pair up with its atoms; one atom is mapped to 1 and the rest to 0. Each ultrafilter of ''B'' thus consists of an atom of ''B'' and all the elements above it; hence exactly half the elements of ''B'' are in the ultrafilter, and there as many ultrafilters as atoms. For infinite Boolean algebras the notion of ultrafilter becomes considerably more delicate. 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 algebra is one every subset of which has both a sup and an inf, even the infinite subsets. Gaifman [1964] and Hales [1964] independently showed that infinite free complete Boolean algebras do not exist. This suggests that it is impossible to have an infinitary Boolean logic for lack of terms. There is however another approach to introducing infinitary Boolean operations: simply drop "finitary" from the definition of Boolean algebra. A model of the equational theory of the algebra of ''all'' operations on {0,1} of arity up to the cardinality of the model is called a complete atomic Boolean algebra, or ''CABA''. (In place of this awkward restriction on arity we could allow any arity, leading to a different awkwardness, that the signature would then be larger than any set, that is, a proper class. One benefit of the latter approach is that it simplifies the definition of homomorphism between CABAs of different cardinality.) Such an algebra can be defined equivalently as a complete Boolean algebra that is '''atomic''', meaning that every element is a sup of some set of atoms. Free CABAs exist for all cardinalities of a set ''V'' of generators, namely the power set algebra 2^{2<span>^''V''</span>}, this being the obvious generalization of the finite free Boolean algebras. This neatly rescues infinitary Boolean logic from the fate the Gaifman–Hales result seemed to consign it to. The nonexistence of complete Boolean algebras can be traced to failure to extend the equations of Boolean logic suitably to all laws that should hold for infinitary conjunction and disjunction, in particular the neglect of distributivity in the definition of complete Boolean algebra. A complete Boolean algebra is called '''completely distributive''' when arbitrary conjunctions distribute over arbitrary disjunctions and vice versa. A Boolean algebra is a CABA if and only if it is complete and completely distributive, giving a third definition of CABA. A fourth definition is as any Boolean algebra isomorphic to a power 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 space]]s, subsequently called [[Stone space]]s. Another infinitary class intermediate between Boolean algebras and complete Boolean algebras is the notion of a [[sigma-algebra]]. This is defined analogously to complete Boolean algebras, but with sups and infs limited to countable arity. That is, a [[sigma-algebra]] is a Boolean algebra with all countable sups and infs. Because the sups and infs are of bounded cardinality, unlike the situation with complete Boolean algebras, the Gaifman-Hales result does not apply and free sigma-algebras do exist. However the situation parallels that with complete Boolean algebras vs. CABAs to a limited extent. We can define a countably distributive sigma-algebra to be one that satisfies distributivity of countable sups over countable infs and vice versa, or equivalently as a model of the equational theory of the algebra of all operations on {0,1} of countable arity. The free countably generated countably distributive sigma-algebra has the same nice structure as free CABAs, being the power set algebra 2^{2<span>^'''N'''</span>}. The free countably generated sigma algebra on the other hand is not a power set algebra, and neither are the free uncountably generated countably distributive sigma-algebras, just as the free countably generated Boolean algebras are not power set algebras. ==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 (Stone), and as a product-preserving functor from a certain category (Lawvere). Two more definitions worth mentioning are as follows. ; ([[Marshall Stone|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 power set algebras. 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 to make it [[Hausdorff space|Hausdorff]] is [[discrete space|discrete]] for inductive objects and [[compact space|compact]] for profinite objects. The topology of finite Hausdorff spaces is always both discrete and compact, whereas for infinite spaces ''discrete'' and ''compact'' are mutually exclusive. Thus when generalizing finite algebras (of any kind, not just Boolean) to infinite ones, ''discrete'' and ''compact'' part ways, and one must decide which to follow. The general rules, for both finite and infinite algebras, are that finitary algebras are discrete, whereas for their duals, compactness and infinitary operations come with the territory. These are only the two extremes, there are many infinite Boolean algebras in between whose topology is neither discrete nor compact. ==References== <!-- Use [[WP:CITET|templates]] for consistency --> * {{cite journal | last = Birkhoff | first = Garrett | authorlink = Garrett Birkhoff | title = On the structure of abstract algebras | journal = Proc. Camb. Phil. Soc. | volume = 31 | pages = 433–454 | date = 1935 | id = {{ISSN|0008-1981}} }} * {{cite book | last = Boole | first = George | authorlink = George Boole | title = An Investigation of the Laws of Thought | publisher = Prometheus Books | origyear = 1854 | date = 2003 | id = ISBN 978-1-59102-089-9 }} * {{cite book | last = Dwinger | first = Philip | title = Introduction to Boolean algebras | publisher = Physica Verlag | location = Würzburg | date = 1971 }} * {{cite journal | last = Gaifman | first = Haim | title = Infinite Boolean Polynomials, I | journal = Fundamenta Mathematicae | volume = 54 | pages = 229–250 | date = 1964 | id = {{ISSN|0016-2736}} }} * {{cite journal | last = Grau | first = A.A. | title = Ternary Boolean algebra | journal = Bull: Am. Math. Soc. | volume = 33 | pages = 567–572 | date = 1947 }} * {{cite journal | last = Hales | first = Alfred W. | title = On the Non-Existence of Free Complete Boolean Algebras | journal = Fundamenta Mathematicae | volume = 54 | pages = 45–66 | date = 1964 | id = {{ISSN|0016-2736}} }} * {{cite book | last = Halmos | first = Paul | title = Lectures on Boolean Algebras | publisher = van Nostrand | date = 1963 }} * {{cite book | last = Johnstone | first = Peter T. | title = Stone Spaces | publisher = Cambridge University Press | date = 1982 | location = Cambridge, UK | id = ISBN 978-0-521-33779-3 }} * {{cite journal | last = Ketonen | first = Jussi | title = The structure of countable Boolean algebras | journal = Annals of Mathematics | volume = 108 | pages = 41–89 | date = 1978 | id = }} * {{cite book | last = Koppelberg | first = Sabine | chapter = General Theory of Boolean Algebras | title = Handbook of Boolean Algebras, Vol. 1 (ed. J. Donald Monk with Robert Bonnet) | publisher = North Holland | date = 1989 | location = Amsterdam | id = ISBN 978-0-444-70261-6 <!--0-444-70261-X--> }} <!-- This doesn't work well either; still searching for good template * {{cite conference | first = Koppelberg | last = Sabine | year = 1989 | title = General Theory of Boolean Algebras | booktitle = Handbook of Boolean Algebras, Vol. 1 | editor = J. Donald Monk with Robert Bonnet | publisher = North Holland | location = Amsterdam | pages = | id = ISBN 978-0-444-70261-6 }}--> * {{cite book | last = Peirce | first = Charles S. | title = Writings of Charles S. Peirce: A Chronological Edition: 1879–1884 (ed. Christian J. W. Kloesel) | publisher = Indiana University Press | date = 1989 | location = Bloomington, IN | id = ISBN 978-0-253-37204-8 }} * {{cite journal | last = Lawvere | first = F. William | authorlink = William Lawvere | title = Functorial semantics of algebraic theories | journal = Proceedings of the National Academy of Sciences | volume = 50 | issue = 5 | pages = 869–873 | date = 1963 | url = http://www.tac.mta.ca/tac/reprints/articles/5/tr5abs.html }} * {{cite book | last = Schröder | first = Ernst | authorlink = Ernst Schröder | title = Vorlesungen über die Algebra der Logik (exakte Logik), I–III<!--, III.1--> | publisher = B.G. Teubner | location = Leipzig | date = 1890–1910<!--1895--> | id = }} * {{cite book | last = Sikorski | first = Roman | authorlink = Roman Sikorski | title = Boolean Algebras | publisher = Springer-Verlag | location = Berlin | edition = 3/e | date = 1969 | id = ISBN 978-0-387-04469-9 }} * {{cite journal | last = Stone | first = Marshall | authorlink = Marshall Harvey Stone | title = The Theory of Representations for Boolean Algebras | journal = Transactions of the American Mathematical Society | volume = 40 | pages = 37–111 | date = 1936 | id = {{ISSN|0002-9947}} }} * {{cite journal | last = Tarski | first = Alfred | authorlink = Alfred Tarski | title = Sur les classes closes par rapport à certaines opérations élémentaires | journal = Fundamenta Mathematicae | volume = 16 | pages = 195–197 | date = 1929 | id = {{ISSN|0016-2736}} }} * {{cite journal | last = Tarski | first = Alfred | authorlink = Alfred Tarski | title = Zur Grundlegung der Booleschen Algebra, I | journal = Fundamenta Mathematicae | volume = 24 | pages = 177–198 | date = 1935 | id = {{ISSN|0016-2736}} }} * {{ cite book | last = Vladimirov | first = D.A. | title = булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974) | publisher = Nauka (German translation Akademie-Verlag) | year = 1969 }} ==See also== {{col-begin}} {{col-break}} * [[Boolean domain]] * [[Boolean function]] * [[Boolean-valued function]] * [[Cartesian closed category]] * [[Closed monoidal category]] * [[Topos#Elementary topoi (topoi in logic)|Elementary topos]] {{col-break}} * [[Finitary boolean function]] * [[Lattice (order)]] * [[Minimal negation operator]] * [[Monoidal category]] * [[Multigrade operator]] {{col-break}} * [[Parametric operator]] * [[Propositional calculus]] * [[Truth table]] * [[Universal algebra]] * [[Zeroth order logic]] {{col-end}} [[Category:Boolean algebra]]

Return to Boolean algebras canonically defined.