TheInfoList

OR:

In
abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathematics), fields, module (mathe ...
, a Boolean algebra or Boolean lattice is a complemented
distributive lattice In mathematics, a distributive lattice is a lattice in 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 ...
. This type of algebraic structure captures essential properties of both set operations and
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
operations. A Boolean algebra can be seen as a generalization of a
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
algebra or a
field of sets In mathematics, a field of sets is a mathematical structure consisting of a pair ( X, \mathcal ) consisting of a set X and a family \mathcal of subsets of X called an algebra over X that contains the empty set as an element, and is closed un ...
, or its elements can be viewed as generalized
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false''). Computing In some pro ...
s. It is also a special case of a
De Morgan algebra __NOTOC__ In mathematics, a De Morgan algebra (named after Augustus De Morgan, a British mathematician and logician) is a structure ''A'' = (A, ∨, ∧, 0, 1, ¬) such that: * (''A'', ∨, ∧, 0,&nbs ...
and a Kleene algebra (with involution). Every Boolean algebra gives rise to a
Boolean ring In mathematics, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean al ...
, and vice versa, with
ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
multiplication corresponding to
conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...
or meet ∧, and ring addition to exclusive disjunction or
symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...
(not
disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
∨). However, the theory of Boolean rings has an inherent asymmetry between the two operators, while the axioms and theorems of Boolean algebra express the symmetry of the theory described by the duality principle. __TOC__

# History

The term "Boolean algebra" honors
George Boole George Boole (; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher, and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in ...
(1815–1864), a self-educated English mathematician. He introduced the
algebraic system In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
initially in a small pamphlet, ''The Mathematical Analysis of Logic'', published in 1847 in response to an ongoing public controversy between Augustus De Morgan and William Hamilton, and later as a more substantial book, ''
The Laws of Thought ''An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities'' by George Boole, published in 1854, is the second of Boole's two monographs on algebraic logic. Boole was a professor of mathem ...
'', published in 1854. Boole's formulation differs from that described above in some important respects. For example, conjunction and disjunction in Boole were not a dual pair of operations. Boolean algebra emerged in the 1860s, in papers written by
William Jevons William Stanley Jevons (; 1 September 183513 August 1882) was an English economist and logician. Irving Fisher described Jevons's book ''A General Mathematical Theory of Political Economy'' (1862) as the start of the mathematical method in eco ...
and
Charles Sanders Peirce Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism". Educated as a chemist and employed as a scientist for t ...
. The first systematic presentation of Boolean algebra and
distributive lattice In mathematics, a distributive lattice is a lattice in 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 ...
s is owed to the 1890 ''Vorlesungen'' of Ernst Schröder. The first extensive treatment of Boolean algebra in English is A. N. Whitehead's 1898 ''Universal Algebra''. Boolean algebra as an axiomatic algebraic structure in the modern axiomatic sense begins with a 1904 paper by Edward V. Huntington. Boolean algebra came of age as serious mathematics with the work of
Marshall Stone Marshall Harvey Stone (April 8, 1903 – January 9, 1989) was an American mathematician who contributed to real analysis, functional analysis, topology and the study of Boolean algebras. Biography Stone was the son of Harlan Fiske Stone, who wa ...
in the 1930s, and with
Garrett Birkhoff Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory. The mathematician George Birkhoff (1884–1944) was his father. Life The son of the mathematician Ge ...
's 1940 ''Lattice Theory''. In the 1960s,
Paul Cohen Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician. He is best known for his proofs that the continuum hypothesis and the axiom of choice are independent from Zermelo–Fraenkel set theory, for which he was award ...
,
Dana Scott Dana Stewart Scott (born October 11, 1932) is an American logician who is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, Ca ...
, and others found deep new results in
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
and axiomatic set theory using offshoots of Boolean algebra, namely forcing and Boolean-valued models.

# Definition

A Boolean algebra is a six-
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
consisting of a set ''A'', equipped with two binary operations ∧ (called "meet" or "and"), ∨ (called "join" or "or"), a
unary operation In mathematics, an unary operation is an operation with only one operand, i.e. a single input. This is in contrast to binary operations, which use two operands. An example is any function , where is a set. The function is a unary operation o ...
¬ (called "complement" or "not") and two elements 0 and 1 in ''A'' (called "bottom" and "top", or "least" and "greatest" element, also denoted by the symbols ⊥ and ⊤, respectively), such that for all elements ''a'', ''b'' and ''c'' of ''A'', the following axioms hold: :: Note, however, that the absorption law and even the associativity law can be excluded from the set of axioms as they can be derived from the other axioms (see Proven properties). A Boolean algebra with only one element is called a trivial Boolean algebra or a degenerate Boolean algebra. (In older works, some authors required 0 and 1 to be ''distinct'' elements in order to exclude this case.) It follows from the last three pairs of axioms above (identity, distributivity and complements), or from the absorption axiom, that ::''a'' = ''b'' ∧ ''a''     if and only if     ''a'' ∨ ''b'' = ''b''. The relation ≤ defined by ''a'' ≤ ''b'' if these equivalent conditions hold, is a
partial order In mathematics, especially order theory, a partially ordered set (also poset) 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 bina ...
with least element 0 and greatest element 1. The meet ''a'' ∧ ''b'' and the join ''a'' ∨ ''b'' of two elements coincide with their
infimum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
and supremum, respectively, with respect to ≤. The first four pairs of axioms constitute a definition of a
bounded lattice A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper boun ...
. It follows from the first five pairs of axioms that any complement is unique. The set of axioms is self-dual in the sense that if one exchanges ∨ with ∧ and 0 with 1 in an axiom, the result is again an axiom. Therefore, by applying this operation to a Boolean algebra (or Boolean lattice), one obtains another Boolean algebra with the same elements; it is called its dual.

# Examples

* The simplest non-trivial Boolean algebra, the
two-element Boolean algebra In mathematics and abstract algebra, the two-element Boolean algebra is the Boolean algebra whose ''underlying set'' (or universe or ''carrier'') ''B'' is the Boolean domain. The elements of the Boolean domain are 1 and 0 by convention, so that ''B ...
, has only two elements, 0 and 1, and is defined by the rules: :* It has applications in
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
, interpreting 0 as ''false'', 1 as ''true'', ∧ as ''and'', ∨ as ''or'', and ¬ as ''not''. Expressions involving variables and the Boolean operations represent statement forms, and two such expressions can be shown to be equal using the above axioms if and only if the corresponding statement forms are
logically equivalent Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
. :* The two-element Boolean algebra is also used for circuit design in electrical engineering; here 0 and 1 represent the two different states of one
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
in a digital circuit, typically high and low
voltage Voltage, also known as electric pressure, electric tension, or (electric) potential difference, is the difference in electric potential between two points. In a static electric field, it corresponds to the work needed per unit of charge to ...
. Circuits are described by expressions containing variables, and two such expressions are equal for all values of the variables if and only if the corresponding circuits have the same input-output behavior. Furthermore, every possible input-output behavior can be modeled by a suitable Boolean expression. :* The two-element Boolean algebra is also important in the general theory of Boolean algebras, because an equation involving several variables is generally true in all Boolean algebras if and only if it is true in the two-element Boolean algebra (which can be checked by a trivial brute force algorithm for small numbers of variables). This can for example be used to show that the following laws (''
Consensus theorem In Boolean algebra, the consensus theorem or rule of consensus is the identity: :xy \vee \barz \vee yz = xy \vee \barz The consensus or resolvent of the terms xy and \barz is yz. It is the conjunction of all the unique literals of the terms, ...
s'') are generally valid in all Boolean algebras: :** (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'') ∧ (''b'' ∨ ''c'') ≡ (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'') :** (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'') ∨ (''b'' ∧ ''c'') ≡ (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'') * The
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
(set of all subsets) of any given nonempty set ''S'' forms a Boolean algebra, an algebra of sets, with the two operations ∨ := ∪ (union) and ∧ := ∩ (intersection). The smallest element 0 is the empty set and the largest element 1 is the set ''S'' itself. :* After the two-element Boolean algebra, the simplest Boolean algebra is that defined by the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
of two atoms: * The set $A$ of all subsets of $S$ that are either finite or cofinite is a Boolean algebra and an algebra of sets called the finite–cofinite algebra. If $S$ is infinite then the set of all cofinite subsets of $S,$ which is called the
Fréchet filter In mathematics, the Fréchet filter, also called the cofinite filter, on a set X is a certain collection of subsets of X (that is, it is a particular subset of the power set of X). A subset F of X belongs to the Fréchet filter if and only if the c ...
, is a free
ultrafilter In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter o ...
on $A.$ However, the Fréchet filter is not an ultrafilter on the power set of $S.$ * Starting with the
propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...
with κ sentence symbols, form the Lindenbaum algebra (that is, the set of sentences in the propositional calculus modulo
logical equivalence In logic and mathematics, statements p and q are said to be logically equivalent if they have the same truth value in every model. The logical equivalence of p and q is sometimes expressed as p \equiv q, p :: q, \textsfpq, or p \iff q, depending o ...
). This construction yields a Boolean algebra. It is in fact the free Boolean algebra on κ generators. A truth assignment in propositional calculus is then a Boolean algebra homomorphism from this algebra to the two-element Boolean algebra. * Given any
linearly ordered In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
set ''L'' with a least element, the interval algebra is the smallest algebra of subsets of ''L'' containing all of the half-open intervals 'a'', ''b'') such that ''a'' is in ''L'' and ''b'' is either in ''L'' or equal to ∞. Interval algebras are useful in the study of Lindenbaum–Tarski algebras; every countable Boolean algebra is isomorphic to an interval algebra. * For any natural number ''n'', the set of all positive divisors of ''n'', defining $a \leq b$ if ''a'' divides ''b'', forms a
distributive lattice In mathematics, a distributive lattice is a lattice in 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 ...
. This lattice is a Boolean algebra if and only if ''n'' is
square-free {{no footnotes, date=December 2015 In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''. A ...
. The bottom and the top element of this Boolean algebra is the natural number 1 and ''n'', respectively. The complement of ''a'' is given by ''n''/''a''. The meet and the join of ''a'' and ''b'' is given by the
greatest common divisor In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
(gcd) and the
least common multiple In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers ''a'' and ''b'', usually denoted by lcm(''a'', ''b''), is the smallest positive integer that is divisible by bo ...
(lcm) of ''a'' and ''b'', respectively. The ring addition ''a''+''b'' is given by lcm(''a'',''b'')/gcd(''a'',''b''). The picture shows an example for ''n'' = 30. As a counter-example, considering the non-square-free ''n''=60, the greatest common divisor of 30 and its complement 2 would be 2, while it should be the bottom element 1. * Other examples of Boolean algebras arise from
topological spaces In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called point ...
: if ''X'' is a topological space, then the collection of all subsets of ''X'' which are both open and closed forms a Boolean algebra with the operations ∨ := ∪ (union) and ∧ := ∩ (intersection). * If $R$ is an arbitrary ring then its set of '' central idempotents'', which is the set $A = \left\,$ becomes a Boolean algebra when its operations are defined by $e \vee f := e + f - e f$ and $e \wedge f := e f.$

# Homomorphisms and isomorphisms

A ''
homomorphism In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
'' between two Boolean algebras ''A'' and ''B'' is a
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
''f'' : ''A'' → ''B'' such that for all ''a'', ''b'' in ''A'': : ''f''(''a'' ∨ ''b'') = ''f''(''a'') ∨ ''f''(''b''), : ''f''(''a'' ∧ ''b'') = ''f''(''a'') ∧ ''f''(''b''), : ''f''(0) = 0, : ''f''(1) = 1. It then follows that ''f''(¬''a'') = ¬''f''(''a'') for all ''a'' in ''A''. The class of all Boolean algebras, together with this notion of morphism, forms a
full subcategory In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitive ...
of the
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
of lattices. An ''isomorphism'' between two Boolean algebras ''A'' and ''B'' is a homomorphism ''f'' : ''A'' → ''B'' with an inverse homomorphism, that is, a homomorphism ''g'' : ''B'' → ''A'' such that the
composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography *Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
''g'' ∘ ''f'': ''A'' → ''A'' is the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
on ''A'', and the composition ''f'' ∘ ''g'': ''B'' → ''B'' is the identity function on ''B''. A homomorphism of Boolean algebras is an isomorphism if and only if it is
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
.

# Boolean rings

Every Boolean algebra (''A'', ∧, ∨) gives rise to a
ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...
(''A'', +, ·) by defining ''a'' + ''b'' := (''a'' ∧ ¬''b'') ∨ (''b'' ∧ ¬''a'') = (''a'' ∨ ''b'') ∧ ¬(''a'' ∧ ''b'') (this operation is called
symmetric difference In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...
in the case of sets and XOR in the case of logic) and ''a'' · ''b'' := ''a'' ∧ ''b''. The zero element of this ring coincides with the 0 of the Boolean algebra; the multiplicative identity element of the ring is the 1 of the Boolean algebra. This ring has the property that ''a'' · ''a'' = ''a'' for all ''a'' in ''A''; rings with this property are called
Boolean ring In mathematics, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2. Every Boolean ring gives rise to a Boolean al ...
s. Conversely, if a Boolean ring ''A'' is given, we can turn it into a Boolean algebra by defining ''x'' ∨ ''y'' := ''x'' + ''y'' + (''x'' · ''y'') and ''x'' ∧ ''y'' := ''x'' · ''y''. Since these two constructions are inverses of each other, we can say that every Boolean ring arises from a Boolean algebra, and vice versa. Furthermore, a map ''f'' : ''A'' → ''B'' is a homomorphism of Boolean algebras if and only if it is a homomorphism of Boolean rings. The
categories Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) * Categories (Peirce) * ...
of Boolean rings and Boolean algebras are equivalent. Hsiang (1985) gave a rule-based algorithm to
check Check or cheque, may refer to: Places * Check, Virginia Arts, entertainment, and media * ''Check'' (film), a 2021 Indian Telugu-language film * ''The Checks'' (episode), a 1996 TV episode of ''Seinfeld'' Games and sports * Check (chess), a thr ...
whether two arbitrary expressions denote the same value in every Boolean ring. More generally, Boudet, Jouannaud, and Schmidt-Schauß (1989) gave an algorithm to solve equations between arbitrary Boolean-ring expressions. Employing the similarity of Boolean rings and Boolean algebras, both algorithms have applications in
automated theorem proving Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs. Automated reasoning over mathematical proof was a ma ...
.

# Ideals and filters

An ''ideal'' of the Boolean algebra ''A'' is a subset ''I'' such that for all ''x'', ''y'' in ''I'' we have ''x'' ∨ ''y'' in ''I'' and for all ''a'' in ''A'' we have ''a'' ∧ ''x'' in ''I''. This notion of ideal coincides with the notion of
ring ideal In ring theory, a branch of abstract algebra, an ideal of a ring is a special subset of its elements. Ideals generalize certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers p ...
in the Boolean ring ''A''. An ideal ''I'' of ''A'' is called ''prime'' if ''I'' ≠ ''A'' and if ''a'' ∧ ''b'' in ''I'' always implies ''a'' in ''I'' or ''b'' in ''I''. Furthermore, for every ''a'' ∈ ''A'' we have that ''a'' ∧ ''-a'' = 0 ∈ ''I'' and then ''a'' ∈ ''I'' or ''-a'' ∈ ''I'' for every ''a'' ∈ ''A'', if ''I'' is prime. An ideal ''I'' of ''A'' is called ''maximal'' if ''I'' ≠ ''A'' and if the only ideal properly containing ''I'' is ''A'' itself. For an ideal ''I'', if ''a'' ∉ ''I'' and ''-a'' ∉ ''I'', then ''I'' ∪ or ''I'' ∪ is properly contained in another ideal ''J''. Hence, that an ''I'' is not maximal and therefore the notions of prime ideal and maximal ideal are equivalent in Boolean algebras. Moreover, these notions coincide with ring theoretic ones of prime ideal and
maximal ideal In mathematics, more specifically in ring theory, a maximal ideal is an ideal that is maximal (with respect to set inclusion) amongst all ''proper'' ideals. In other words, ''I'' is a maximal ideal of a ring ''R'' if there are no other ideals c ...
in the Boolean ring ''A''. The dual of an ''ideal'' is a ''filter''. A ''filter'' of the Boolean algebra ''A'' is a subset ''p'' such that for all ''x'', ''y'' in ''p'' we have ''x'' ∧ ''y'' in ''p'' and for all ''a'' in ''A'' we have ''a'' ∨ ''x'' in ''p''. The dual of a ''maximal'' (or ''prime'') ''ideal'' in a Boolean algebra is ''
ultrafilter In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter o ...
''. Ultrafilters can alternatively be described as
2-valued morphism In mathematics, a 2-valued morphism. is a homomorphism that sends a Boolean algebra ''B'' onto the two-element Boolean algebra 2 = . It is essentially the same thing as an ultrafilter on ''B'', and, in a different way, also the same things as a max ...
s from ''A'' to the two-element Boolean algebra. The statement ''every filter in a Boolean algebra can be extended to an ultrafilter'' is called the '' Ultrafilter Theorem'' and cannot be proven in ZF, if ZF is
consistent In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
. Within ZF, it is strictly weaker than the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
. The Ultrafilter Theorem has many equivalent formulations: ''every Boolean algebra has an ultrafilter'', ''every ideal in a Boolean algebra can be extended to a prime ideal'', etc.

# Representations

It can be shown that every ''finite'' Boolean algebra is isomorphic to the Boolean algebra of all subsets of a finite set. Therefore, the number of elements of every finite Boolean algebra is a
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negativ ...
. Stone's celebrated '' representation theorem for Boolean algebras'' states that ''every'' Boolean algebra ''A'' is isomorphic to the Boolean algebra of all
clopen In topology, a clopen set (a portmanteau of closed-open set) in a topological space is a set which is both open and closed. That this is possible may seem counter-intuitive, as the common meanings of and are antonyms, but their mathematical de ...
sets in some (
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in British ...
totally disconnected In topology and related branches of mathematics, a totally disconnected space is a topological space that has only singletons as connected subsets. In every topological space, the singletons (and, when it is considered connected, the empty set) ...
Hausdorff) topological space.

# Axiomatics

The first axiomatization of Boolean lattices/algebras in general was given by the English philosopher and mathematician Alfred North Whitehead in 1898. It included the above axioms and additionally ''x''∨1=1 and ''x''∧0=0. In 1904, the American mathematician Edward V. Huntington (1874–1952) gave probably the most parsimonious axiomatization based on ∧, ∨, ¬, even proving the associativity laws (see box). He also proved that these axioms are
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s * Independ ...
of each other. In 1933, Huntington set out the following elegant axiomatization for Boolean algebra. It requires just one binary operation + and a unary functional symbol ''n'', to be read as 'complement', which satisfy the following laws: # ''Commutativity'': ''x'' + ''y'' = ''y'' + ''x''. # ''Associativity'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z''). # ''Huntington equation'': ''n''(''n''(''x'') + ''y'') + ''n''(''n''(''x'') + ''n''(''y'')) = ''x''.
Herbert Robbins Herbert Ellis Robbins (January 12, 1915 – February 12, 2001) was an American mathematician and statistician. He did research in topology, measure theory, statistics, and a variety of other fields. He was the co-author, with Richard Co ...
immediately asked: If the Huntington equation is replaced with its dual, to wit: :4. ''Robbins Equation'': ''n''(''n''(''x'' + ''y'') + ''n''(''x'' + ''n''(''y''))) = ''x'', do (1), (2), and (4) form a basis for Boolean algebra? Calling (1), (2), and (4) a ''Robbins algebra'', the question then becomes: Is every Robbins algebra a Boolean algebra? This question (which came to be known as the
Robbins conjecture In 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. These operations satisfy the following axioms: For all elements ''a'', ''b'', ...
) remained open for decades, and became a favorite question of
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
and his students. In 1996,
William McCune William Walker McCune (December 17, 1953 – May 2, 2011) was an American computer scientist and logician working in the fields of automated reasoning, algebra, logic, and formal methods. He was best known for the development of the Otter, Prover ...
at Argonne National Laboratory, building on earlier work by Larry Wos, Steve Winker, and Bob Veroff, answered Robbins's question in the affirmative: Every Robbins algebra is a Boolean algebra. Crucial to McCune's proof was the computer program EQP he designed. For a simplification of McCune's proof, see Dahn (1998). Further work has been done for reducing the number of axioms; see
Minimal axioms for Boolean algebra In mathematical logic, minimal axioms for Boolean algebra are assumptions which are equivalent to the axioms of Boolean algebra (or propositional calculus), chosen to be as short as possible. For example, if one chooses to take commutativity for gra ...
.

# Generalizations

Removing the requirement of existence of a unit from the axioms of Boolean algebra yields "generalized Boolean algebras". Formally, a
distributive lattice In mathematics, a distributive lattice is a lattice in 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 ...
''B'' is a generalized Boolean lattice, if it has a smallest element 0 and for any elements ''a'' and ''b'' in ''B'' such that ''a'' ≤ ''b'', there exists an element ''x'' such that a ∧ x = 0 and a ∨ x = b. Defining a ∖ b as the unique ''x'' such that (a ∧ b) ∨ x = a and (a ∧ b) ∧ x = 0, we say that the structure (B,∧,∨,∖,0) is a ''generalized Boolean algebra'', while (B,∨,0) is a ''generalized Boolean
semilattice In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a ...
''. Generalized Boolean lattices are exactly the ideals of Boolean lattices. A structure that satisfies all axioms for Boolean algebras except the two distributivity axioms is called an
orthocomplemented lattice In the mathematical discipline of order theory, a complemented lattice is a bounded lattice (with least element 0 and greatest element 1), in which every element ''a'' has a complement, i.e. an element ''b'' satisfying ''a'' ∨ ''b''&nbs ...
. Orthocomplemented lattices arise naturally in
quantum logic In the mathematical study of logic and the physical analysis of quantum foundations, quantum logic is a set of rules for manipulation of propositions inspired by the structure of quantum theory. The field takes as its starting point an observ ...
as lattices of closed subspaces for separable Hilbert spaces.

# References

## Works cited

* * *. * * * *. * *

## General references

*. See Section 2.5. * *. See Chapter 2. *. *. *. *. * * *. In 3 volumes. (Vol.1:, Vol.2:, Vol.3:) *. *. Reprinted by
Dover Publications Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward and Blanche Cirker. It primarily reissues books that are out of print from their original publishers. These are often, but not always, book ...
, 1979.