:''Boolean algebras are models of the equational theory of two values; this definition is equivalent to the lattice and ring definitions.''
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
is a mathematically rich branch of
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 ...
. ''Stanford Encyclopaedia of Philosophy'' defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
deals with
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
, and
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
with
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
s,
Boolean algebras are models of the
equational theory
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of stud ...
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
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
closed under some
operations satisfying certain equations.
Just as there are basic examples of groups, such as the group
of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s and the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group ...
of
permutations of objects, there are also basic examples of Boolean algebras such as the following.
* The algebra of
binary digit
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
s or bits 0 and 1 under the logical operations including disjunction, conjunction, and negation. Applications include 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 ...
and the theory of digital circuits.
* The
algebra of sets under the set operations including
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
,
intersection, and
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
. Applications are far-reaching because
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
is the standard
foundations of mathematics
Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathe ...
.
Boolean algebra thus permits applying the methods of
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 ...
to
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
digital logic
A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gate ...
.
Unlike groups of finite
order, which exhibit complexity and diversity and whose
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
ic complexity of their
syntactic structure.
Definition
Boolean algebra treats the
equational theory
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of stud ...
of the maximal two-element
finitary
In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values.
In standard mathematics, an operation ...
algebra, called the Boolean prototype, and the models of that theory, called Boolean algebras. These terms are defined as follows.
An
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
is a
family
Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Idea ...
of operations on a set, called the underlying set of the algebra. We take the underlying set of the Boolean prototype to be .
An algebra is
finitary
In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values.
In standard mathematics, an operation ...
when each of its operations takes only finitely many arguments. For the prototype each argument of an operation is either or , as is the result of the operation. The maximal such algebra consists of all finitary operations on .
The number of arguments taken by each operation is called the
arity of the operation. An operation on of arity , or -ary operation, can be applied to any of possible values for its arguments. For each choice of arguments, the operation may return or , whence there are -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
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 ...
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: if , if . It has sixteen
binary operations; 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 -ary operations in the prototype is the square of the number of -ary operations, so there are ternary operations, quaternary operations, and so on.
A
family
Family (from la, familia) is a group of people related either by consanguinity (by recognized birth) or affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its members and of society. Idea ...
is indexed by an
index set
In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consists ...
. 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 -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 -th -ary symbol to be as done below in the section on
truth tables
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argume ...
.
An
equational theory
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of stud ...
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 , , , and .
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 .
The
equational theory
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of stud ...
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 of several different bases. Three bases for Boolean algebra are in common use, the lattice basis, the ring basis, and the
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both". It is also called nand ("not and") ...
or NAND basis. These bases impart respectively a logical, an arithmetical, and a parsimonious character to the subject.
* The
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
basis originated in the 19th century with the work of
Boole,
Peirce, and others seeking an algebraic formalization of logical thought processes.
* The
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 ...
basis emerged in the 20th century with the work of
Zhegalkin and
Stone
In geology, rock (or stone) is any naturally occurring solid mass or aggregate of minerals or mineraloid matter. It is categorized by the minerals included, its Chemical compound, chemical composition, and the way in which it is formed. Rocks ...
and became the basis of choice for algebraists coming to the subject from a background 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 ...
. Most treatments of Boolean algebra assume the lattice basis, a notable exception being
Halmos963
Year 963 ( CMLXIII) was a common year starting on Thursday (link will display the full calendar) of the Julian calendar.
Events
By place
Byzantine Empire
* March 15 – Emperor Romanos II dies at age 25, probably of poison admini ...
whose linear algebra background evidently endeared the ring basis to him.
* Since all finitary operations on can be defined in terms of the
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both". It is also called nand ("not and") ...
NAND (or its dual NOR), the resulting economical basis has become the basis of choice for analyzing
digital circuits, in particular
gate array
A gate array is an approach to the design and manufacture of application-specific integrated circuits (ASICs) using a prefabricated chip with components that are later interconnected into logic devices (e.g. NAND gates, flip-flops, etc.) according ...
s in
digital electronics
Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.
Digital electronic circuits are usual ...
.
The common elements of the lattice and ring bases are the constants 0 and 1, and an
associative commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
binary operation, called
meet
Meet may refer to:
People with the name
* Janek Meet (born 1974), Estonian footballer
* Meet Mukhi (born 2005), Indian child actor
Arts, entertainment, and media
* ''Meet'' (TV series), an early Australian television series which aired on ABC du ...
in the lattice basis, and
multiplication in the ring basis. The distinction is only terminological. The lattice basis has the further operations of
join Join may refer to:
* Join (law), to include additional counts or additional defendants on an indictment
*In mathematics:
** Join (mathematics), a least upper bound of sets orders in lattice theory
** Join (topology), an operation combining two top ...
, , and
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
, . The ring basis has instead the arithmetic operation 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 to the ring basis as , and as . Conversely the ring basis translates to the lattice basis as .
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
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 ...
satisfying and , called a
complemented distributive lattice. The ring basis turns a Boolean algebra into 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 ...
, namely a ring satisfying .
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Gove ...
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
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is b ...
," is the easy observation that a property from among these five holding of every operation in a candidate basis will also hold of every operation formed by composition from that candidate, whence by nontriviality of that property the candidate will fail to be a basis.) Post's five properties are:
*
monotone
Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony.
Monotone or monotonicity may also refer to:
In economics
*Monotone preferences, a property of a consumer's preference ordering.
*Monotonic ...
, no 0-1 input transition can cause a 1-0 output transition;
*
affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a relative by marriage in law and anthropology
* Affine cipher, a special case of the more general substitution cipher
* Affine comb ...
, representable with
Zhegalkin polynomials that lack bilinear or higher terms, e.g. but not ;
*
self-dual
In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a Injective function, one-to-one fashion, often (but not always) by means of an Involution (mathematics), involutio ...
, so that complementing all inputs complements the output, as with , or the
median operator , or their negations;
*
strict (mapping the all-zeros input to zero);
* costrict (mapping all-ones to one).
The
NAND (dually NOR) operation lacks all these, thus forming a basis by itself.
Truth tables
The finitary operations on may be exhibited as
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
s, thinking of 0 and 1 as the
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 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 -ary operations are binary numbers of bits. There being 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 rows at arity , each row giving a valuation or binding of the variables and each column headed giving the value of the -th -ary operation at that valuation. The operations include the variables, for example is while is (as two copies of its unary counterpart) and is (with no unary counterpart). Negation or complement appears as and again as , along with (, which did not appear at arity 1), disjunction or union as , conjunction or intersection as , implication , exclusive-or symmetric difference as , set difference as , 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 , the truth-table presentation above serendipitously orders the operations first by arity and second by the layout of the tables for each arity. This permits organizing the set of all Boolean operations in the traditional list format. The list order for the operations of a given arity is determined by the following two rules.
: (i) The -th row in the left half of the table is the binary representation of with its least significant or -th bit on the left ("little-endian" order, originally proposed by
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical co ...
, so it would not be unreasonable to call it Turing order).
: (ii) The -th column in the right half of the table is the binary representation of , again in little-endian order. In effect the subscript of the operation ''is'' the truth table of that operation. By analogy with
Gödel numbering of computable functions one might call this numbering of the Boolean operations the Boole numbering.
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 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.
Examples
Bit vectors
Example 2. All
bit vector
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...
s of a given length form a Boolean algebra "pointwise", meaning that any -ary Boolean operation can be applied to 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 . Another example is the truth tables above for the -ary operations, whose columns are all the bit vectors of length and which therefore can be combined pointwise whence the -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 such that has only two possible values, or .
Power set algebra
Example 3. The power set algebra, the set of all subsets of a given set . This is just Example 2 in disguise, with serving to index the bit positions. Any subset of can be viewed as the bit vector having 1's in just those bit positions indexed by elements of . Thus the all-zero vector is the empty subset of while the all-ones vector is itself, these being the constants 0 and 1 respectively of the power set algebra. The counterpart of disjunction is union , while that of conjunction is intersection . Negation becomes , complement relative to . There is also set difference , symmetric difference , ternary union , 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 of Boolean algebras where ranges over some index set (not necessarily finite or even countable) is a Boolean algebra consisting of all -tuples whose -th element is taken from . The operations of a direct product are the corresponding operations of the constituent algebras acting within their respective coordinates; in particular operation of the product operates on -tuples by applying operation of to the elements in the -th coordinate of the tuples, for all in .
When all the algebras being multiplied together in this way are the same algebra we call the direct product a ''direct power'' of . 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 . The Boolean algebra of all sets of integers is . 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 , namely one of 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 of sets of natural numbers,
shown by
Cantor
A cantor or chanter is a person who leads people in singing or sometimes in prayer. In formal Jewish worship, a cantor is a person who sings solo verses or passages to which the choir or congregation responds.
In Judaism, a cantor sings and lead ...
to be
uncountable
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...
), there exist various countably infinite Boolean algebras.
To go beyond power set algebras we need another construct. A
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
of an algebra is any subset of closed under the operations of . Every subalgebra of a Boolean algebra must still satisfy the equations holding of , since any violation would constitute a violation for itself. Hence every subalgebra of a Boolean algebra is a Boolean algebra.
A
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
of a power set algebra is called 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 ...
; equivalently a field of sets is a set of subsets of some set including the empty set and and closed under finite union and complement with respect to (and hence also under finite intersection). Birkhoff's
935
Year 935 ( CMXXXV) was a common year starting on Thursday (link will display the full calendar) of the Julian calendar.
Events
By place
Europe
* Spring – Arnulf I ("the Bad") of Bavaria invades Italy, crossing through the Upper ...
representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. Now
Birkhoff's HSP theorem
In universal algebra, a variety of algebras or equational class is the class of all algebraic structures of a given signature satisfying a given set of identities. For example, the groups form a variety of algebras, as do the abelian groups, the ...
for varieties can be stated as, every class of models of the equational theory of a class of algebras is the Homomorphic image of a
Subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
of a
direct Product of algebras of . 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
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" ...
can be replaced by
Isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
. Birkhoff's HSP theorem for varieties in general therefore becomes Birkhoff's ISP theorem for the
variety
Variety may refer to:
Arts and entertainment Entertainment formats
* Variety (radio)
* Variety show, in theater and television
Films
* ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont
* ''Variety'' (1935 film), ...
of Boolean algebras.
Other examples
It is convenient when talking about a set ''X'' of natural numbers to view it as a sequence of bits, with if and only if . This viewpoint will make it easier to talk about
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
s of the power set algebra , which this viewpoint makes the Boolean algebra of all sequences of bits.
[http://diposit.ub.edu/dspace/bitstream/2445/127682/2/memoria.pdf ] 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 of the sequence being the low-order bit) and the ultimately-one sequences as negative binary numerals (think
two's complement
Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent (but negative) value, using the binary digit with the greatest place value (the leftmost bit in big- endian ...
arithmetic with the all-ones sequence being ). This makes the integers a Boolean algebra, with union being bit-wise OR and complement being . 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 , called a witness to periodicity, such that for all . 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 , 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 with a sequence of greater period is neither nor . 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 In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
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 in the table of binary operations, namely , has period (and so can be recognized as using only the first variable) even though 12 of the binary operations have period . When the period is the operation only depends on the first 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 In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
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 In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
, namely Example 5, and so is not isomorphic to Example 4, every
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
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 In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations.
"Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear operat ...
, 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
978
Year 978 ( CMLXXVIII) was a common year starting on Tuesday (link will display the full calendar) of the Julian calendar.
Events
By place
Byzantine Empire
* Battle of Pankaleia: Rebel forces under General Bardas Skleros are defeated ...
classified completely in terms of invariants representable by certain hereditarily countable sets.
Boolean algebras of Boolean operations
The -ary Boolean operations themselves constitute a power set algebra , namely when is taken to be the set of valuations of the inputs. In terms of the naming system of operations where 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 to Boolean operations of arity to yield a Boolean operation of arity , for any and .
The practical significance of this convention for both software and hardware is that -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 , , and (dispensing with subscripted variables for now) to be , , and respectively (170, 204, and 240 in decimal, , , and in hexadecimal), their pairwise conjunctions are , , and , while their pairwise disjunctions are , , and . The disjunction of the three conjunctions is , 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
947
Year 947 ( CMXLVII) was a common year starting on Friday (link will display the full calendar) of the Julian calendar.
Events
By place
Europe
* Summer – A Hungarian army led by Grand Prince Taksony campaigns in Italy, heading ...
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 permutations of its arguments. The two halves of its truth table are the truth tables for , , and , , so the operation can be phrased as if then else . Since it is symmetric it can equally well be phrased as either of if then else , or if then else . 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 system
In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contains ...
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 In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom.
Formal definition
An axiom schema is a formula in the metalanguage of an axiomatic system, in which one or more schematic variables ap ...
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 where and are -ary terms, by which we shall mean here terms whose variables are limited to through . An -ary term is either an atom or an application. An application is a pair consisting of an -ary operation and a list or -tuple of -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 where . For the proof technique here it is convenient to define atoms instead to be -ary operations , which although treated here as atoms nevertheless mean the same as ordinary terms of the exact form (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 -ary operations and for each (abbreviating to ), and the variables as can be seen from the truth tables where appears as both the unary operation and the binary operation while appears as .
The following axiom schema and three inference rules axiomatize the Boolean algebra of ''n''-ary terms.
: A1. where , with being transpose, defined by .
: R1. With no premises infer .
: R2. From and infer where , , and are -ary terms.
: R3. From infer , where all terms are -ary.
The meaning of the side condition on A1 is that is that -bit number whose -th bit is the -th bit of , where the ranges of each quantity are , , , and . (So is an -tuple of -bit numbers while as the transpose of is a -tuple of -bit numbers. Both and therefore contain bits.)
A1 is an axiom schema rather than an axiom by virtue of containing metavariables, namely , , , and through . The actual axioms of the axiomatization are obtained by setting the metavariables to specific values. For example, if we take , we can compute the two bits of from and , so (or when written as a two-bit number). The resulting instance, namely , expresses the familiar axiom of double negation. Rule R3 then allows us to infer by taking to be or , to be or , and to be or .
For each and there are only finitely many axioms instantiating A1, namely . Each instance is specified by 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 is provable in this system. One first shows by induction on the height of that every Boolean law for which is atomic is provable, using R1 for the base case (since distinct atoms are never equal) and A1 and R3 for the induction step ( an application). This proof strategy amounts to a recursive procedure for evaluating to yield an atom. Then to prove in the general case when may be an application, use the fact that if is an identity then and must evaluate to the same atom, call it . So first prove and as above, that is, evaluate and using A1, R1, and R3, and then invoke R2 to infer .
In A1, if we view the number as the function type , and as the application , we can reinterpret the numbers , , , and as functions of type , , , and . The definition in A1 then translates to , that is, is defined to be composition of and understood as functions. So the content of A1 amounts to defining term application to be essentially composition, modulo the need to transpose the -tuple 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 is a
partially ordered set
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 ...
or poset . The partial order relation is defined by just when , or equivalently when . Given a set of elements of a Boolean algebra, an upper bound on is an element such that for every element of , , while a lower bound on is an element such that for every element ' of ', .
A
sup of ' is a least upper bound on ', namely an upper bound on ' that is less or equal to every upper bound on '. Dually an (
inf) of ' is a greatest lower bound on '. The sup of and always exists in the underlying poset of a Boolean algebra, being , and likewise their inf exists, namely . 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 such that every pair of elements has both a sup and an inf is called a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
. We write for the sup and for the inf. The underlying poset of a Boolean algebra always forms a lattice. The lattice is said to be distributive when , or equivalently when , 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 of elements is called complementary when and , and we then say that is a complement of and vice versa. Any element 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 , and is therefore sometimes referred to as the inconsistent Boolean algebra.
Boolean homomorphisms
A Boolean
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" ...
is a function between Boolean algebras such that for every Boolean operation :
:
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) ...
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 ' to 2. Any such homomorphism partitions ' into those elements mapped to 1 and those to 0. The subset of ' consisting of the former is called an
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 ...
of '. When ' is finite its ultrafilters pair up with its atoms; one atom is mapped to 1 and the rest to 0. Each ultrafilter of ' thus consists of an atom of ' and all the elements above it; hence exactly half the elements of ' 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
The history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers. The standard way to resolve these debates is to define the operations of calculus using (ε, δ)-definitio ...
, 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
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
is one every subset of which has both a sup and an inf, even the infinite subsets. Gaifman
964and
Hales
Hales is a small village in Norfolk, England. It covers an area of and had a population of 479 in 192 households as of the 2001 census, which had reduced to 469 at the 2011 census.
History
The villages name means 'Nooks of land'.
The manor ...
964independently showed that infinite
free complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
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 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
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
that is atomic, meaning that every element is a sup of some set of atoms. Free CABAs exist for all cardinalities of a set of
generators, namely 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 ...
algebra , 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
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
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
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 ...
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
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) ...
compact Hausdorff space
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i. ...
s, subsequently called
Stone space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in ...
s.
Another infinitary class intermediate between Boolean algebras and
complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
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
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
s, the Gaifman-Hales result does not apply and
free sigma-algebras 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
In geology, rock (or stone) is any naturally occurring solid mass or aggregate of minerals or mineraloid matter. It is categorized by the minerals included, its Chemical compound, chemical composition, and the way in which it is formed. Rocks ...
(1936): A Boolean algebra is the set of all
clopen set
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 ...
s of a
topological space
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 po ...
. It is no limitation to require the space to be a totally disconnected compact
Hausdorff space
In topology and related branches of mathematics, a Hausdorff space ( , ), separated space or T2 space is a topological space where, for any two distinct points, there exist neighbourhoods of each which are disjoint from each other. Of the m ...
, or
Stone space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in ...
, that is, every Boolean algebra arises in this way, up to
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
. 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 space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in ...
s. This definition is fleshed out by the next definition.
; Johnstone (1982): A Boolean algebra is a
filtered colimit In category theory, filtered categories generalize the notion of directed set understood as a category (hence called a directed category; while some use directed category as a synonym for a filtered category). There is a dual notion of cofiltered ...
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 space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in ...
s 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
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
*Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
*Discrete group, a g ...
for inductive objects and
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 ...
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 domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
*
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
*
Boolean-valued function
A Boolean-valued function (sometimes called 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, i.e. a generic two-element set, (for example B = ), whose elements are i ...
*
Boolean-valued model
In 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 v ...
*
Cartesian closed category
In 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 math ...
*
Closed monoidal category
In mathematics, especially in category theory, a closed monoidal category (or a ''monoidal closed category'') is a category that is both a monoidal category and a closed category in such a way that the structures are compatible.
A classic exa ...
*
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolea ...
*
Elementary topos
In mathematics, a topos (, ; plural topoi or , or toposes) is a category that behaves like the category of sheaves of sets on a topological space (or more generally: on a site). Topoi behave much like the category of sets and possess a notion ...
*
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 ...
*
Filter (mathematics)
In mathematics, a filter or order filter is a special subset of a partially ordered set (poset). Filters appear in order and lattice theory, but can also be found in topology, from which they originate. The dual notion of a filter is an orde ...
*
Finitary boolean function
In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values.
In standard mathematics, an operatio ...
*
Free Boolean algebra In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called ''generators'', such that:
#Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean opera ...
*
Functional completeness In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. ( ...
*
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different noti ...
*
Lattice (order)
*
Lindenbaum–Tarski algebra
In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a logical theory ''T'' consists of the equivalence classes of sentences of the theory (i.e., the quotient, under the equivalence relation ~ defined such that ''p'' ...
*
List of Boolean algebra topics
This is a list of topics around Boolean algebra and propositional logic.
Articles with a wide scope and introductions
* Algebra of sets
* Boolean algebra (structure)
* Boolean algebra
* Field of sets
* Logical connective
* Prop ...
*
Monoidal category
In mathematics, a monoidal category (or tensor category) is a category \mathbf C equipped with a bifunctor
:\otimes : \mathbf \times \mathbf \to \mathbf
that is associative up to a natural isomorphism, and an object ''I'' that is both a left a ...
*
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 ...
*
Robbins algebra
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'', ...
*
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
*
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 ...
*
Universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of stu ...
References
*
*
*
*
*
*
*
*
*
*
*
* Koppelberg, Sabine (1989) "General Theory of Boolean Algebras" in Monk, J. Donald, and Bonnet, Robert, eds., ''Handbook of Boolean Algebras, Vol. 1''. North Holland. .
* Charles Sanders Peirce, Peirce, C. S. (1989) ''Writings of Charles S. Peirce: A Chronological Edition: 1879–1884''. Kloesel, C. J. W., ed. Indianapolis: Indiana University Press. {{ISBN, 978-0-253-37204-8.
* {{cite journal
, last = Lawvere
, first = F. William
, author-link = William Lawvere
, title = Functorial semantics of algebraic theories
, journal = Proceedings of the National Academy of Sciences
, volume = 50
, issue = 5
, pages = 869–873
, year = 1963
, url = http://www.tac.mta.ca/tac/reprints/articles/5/tr5abs.html
, doi = 10.1073/pnas.50.5.869 , pmc = 221940
, pmid=16591125
, bibcode = 1963PNAS...50..869L
, doi-access = free
* {{cite book
, last = Schröder
, first = Ernst
, author-link = Ernst Schröder (mathematician)
, title = Vorlesungen über die Algebra der Logik (exakte Logik), I–III
, publisher = B.G. Teubner
, location = Leipzig
, date = 1890–1910
* {{cite book
, last = Sikorski
, first = Roman
, author-link = Roman Sikorski
, title = Boolean Algebras
, publisher = Springer-Verlag
, location = Berlin
, edition = 3rd.
, year = 1969
, isbn = 978-0-387-04469-9
* {{cite journal
, author-link = Marshall Harvey Stone
, journal = Transactions of the American Mathematical Society
, volume = 40
, issue = 1
, pages = 37–111
, jstor = 1989664
, issn = 0002-9947
, doi = 10.2307/1989664
, title = The Theory of Representation for Boolean Algebras
, year = 1936
, author = Stone, M. H.
* Alfred Tarski, Tarski, Alfred (1983). ''Logic, Semantics, Metamathematics'', Corcoran, J., ed. Hackett. 1956 1st edition edited and translated by J. H. Woodger, Oxford Uni. Press. Includes English translations of the following two articles:
** {{cite journal
, last = Tarski
, first = Alfred
, author-link = Alfred Tarski
, title = Sur les classes closes par rapport à certaines opérations élémentaires
, journal = Fundamenta Mathematicae
, volume = 16
, pages = 195–97
, year = 1929
, issn = 0016-2736
** {{cite journal
, last = Tarski
, first = Alfred
, author-link = Alfred Tarski
, title = Zur Grundlegung der Booleschen Algebra, I
, journal = Fundamenta Mathematicae
, volume = 24
, pages = 177–98
, year = 1935
, doi = 10.4064/fm-24-1-177-198
, issn = 0016-2736 , doi-access = free
* {{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
References
{{Reflist
Boolean algebra