In
mathematics, a free Boolean algebra is a
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 ...
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 operations, and
#The generators are as ''independent'' as possible, in the sense that there are no relationships among them (again in terms of finite expressions using the Boolean operations) that do not hold in ''every'' Boolean algebra no matter ''which'' elements are chosen.
A simple example
![Free-boolean-algebra-hasse-diagram](https://upload.wikimedia.org/wikipedia/commons/7/72/Free-boolean-algebra-hasse-diagram.svg)
The
generators of a free Boolean algebra can represent independent
proposition
In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, " meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same meaning. Equivalently, a proposition is the no ...
s. Consider, for example, the propositions "John is tall" and "Mary is rich". These generate a Boolean algebra with four
atoms, namely:
*John is tall, and Mary is rich;
*John is tall, and Mary is not rich;
*John is not tall, and Mary is rich;
*John is not tall, and Mary is not rich.
Other elements of the Boolean algebra are then
logical 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 of the atoms, such as "John is tall and Mary is not rich, or John is not tall and Mary is rich". In addition there is one more element, FALSE, which can be thought of as the empty disjunction; that is, the disjunction of no atoms.
This example yields a Boolean algebra with 16 elements; in general, for finite ''n'', the free Boolean algebra with ''n'' generators has 2
''n'' atoms, and therefore
elements.
If there are
infinitely
Infinity is that which is boundless, endless, or larger than any natural number. It is often denoted by the infinity symbol .
Since the time of the ancient Greeks, the philosophical nature of infinity was the subject of many discussions amo ...
many
generators, a similar situation prevails except that now there are no
atoms. Each element of the Boolean algebra is a combination of finitely many of the generating propositions, with two such elements deemed identical if they 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 ...
.
Another way to see why the free Boolean algebra on an n-element set has
elements is to note that each element is a function from n bits to one. There are
possible inputs to such a function and the function will choose 0 or 1 to output for each input, so there are
possible functions.
Category-theoretic definition
In the language of
category theory, free Boolean algebras can be defined simply in terms of an
adjunction between the category of sets and functions, Set, and the category of Boolean algebras and Boolean algebra homomorphisms, BA. In fact, this approach generalizes to any algebraic structure definable in the framework of
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 ...
.
Above, we said that a free Boolean algebra is a Boolean algebra with a set of generators that behave a certain way; alternatively, one might start with a set and ask which algebra it generates. Every set ''X'' generates a free Boolean algebra ''FX'' defined as the algebra such that for every algebra ''B'' and function ''f'' : ''X'' → ''B'', there is a unique Boolean algebra homomorphism ''f''′ : ''FX'' → ''B'' that extends ''f''.
Diagrammatically,
![Free-Boolean-algebra-unit-sloppy](https://upload.wikimedia.org/wikipedia/commons/7/7e/Free-Boolean-algebra-unit-sloppy.png)
where ''i''
''X'' is the inclusion, and the dashed arrow denotes uniqueness. The idea is that once one chooses where to send the elements of ''X'', the
laws for Boolean algebra homomorphisms determine where to send everything else in the free algebra ''FX''. If ''FX'' contained elements inexpressible as combinations of elements of ''X'', then ''f''′ wouldn't be unique, and if the elements of ''X'' weren't sufficiently independent, then ''f''′ wouldn't be well defined! It is easily shown that ''FX'' is unique (up to isomorphism), so this definition makes sense. It is also easily shown that a free Boolean algebra with generating set X, as defined originally, is isomorphic to ''FX'', so the two definitions agree.
One shortcoming of the above definition is that the diagram doesn't capture that ''f''′ is a homomorphism; since it is a diagram in Set each arrow denotes a mere function. We can fix this by separating it into two diagrams, one in BA and one in Set. To relate the two, we introduce a
functor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
''U'' : BA → Set that "
forgets" the algebraic structure, mapping algebras and homomorphisms to their underlying sets and functions.
![Free-Boolean-algebra-unit](https://upload.wikimedia.org/wikipedia/commons/5/5c/Free-Boolean-algebra-unit.png)
If we interpret the top arrow as a diagram in BA and the bottom triangle as a diagram in Set, then this diagram properly expresses that every function ''f'' : ''X'' → ''UB'' extends to a unique Boolean algebra homomorphism ''f''′ : ''FX'' → ''B''. The functor ''U'' can be thought of as a device to pull the homomorphism ''f''′ back into Set so it can be related to ''f''.
The remarkable aspect of this is that the latter diagram is one of the various (equivalent) definitions of when two functors are
adjoint
In mathematics, the term ''adjoint'' applies in several situations. Several of these share a similar formalism: if ''A'' is adjoint to ''B'', then there is typically some formula of the type
:(''Ax'', ''y'') = (''x'', ''By'').
Specifically, adjoin ...
. Our ''F'' easily extends to a functor Set → BA, and our definition of ''X'' generating a free Boolean algebra ''FX'' is precisely that ''U'' has a
left adjoint
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
''F''.
Topological realization
The free Boolean algebra with κ
generators, where κ is a finite or infinite
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...
, may be realized as the collection 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 ...
subsets of
κ, given the
product topology
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-s ...
assuming that has the
discrete topology
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest top ...
. For each α<κ, the α''th'' generator is the set of all elements of
κ whose α''th'' coordinate is 1. In particular, the free Boolean algebra with
generators is the collection of all clopen subsets of a
Cantor space In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2ω is called "the ...
, sometimes called the
Cantor algebra
In mathematics, a Cantor algebra, named after Georg Cantor, is one of two closely related Boolean algebras, one countable and one complete.
The countable Cantor algebra is the Boolean algebra of all clopen subsets of the Cantor set. This is th ...
. This collection is
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
. In fact, while the free Boolean algebra with ''n'' generators, ''n'' finite, has
cardinality , the free Boolean algebra with
generators, as for any free algebra with
generators and countably many finitary operations, has cardinality
.
For more on this
topological
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
approach to free Boolean algebra, see
Stone's representation theorem for Boolean algebras.
See also
*
Boolean algebra (structure)
*
Generating set
In mathematics and physics, the term generator or generating set may refer to any of a number of related concepts. The underlying concept in each case is that of a smaller set of objects, together with a set of operations that can be applied to ...
References
* Steve Awodey (2006) ''Category Theory'' (Oxford Logic Guides 49). Oxford University Press.
*
Paul Halmos
Paul Richard Halmos ( hu, Halmos Pál; March 3, 1916 – October 2, 2006) was a Hungarian-born American mathematician and statistician who made fundamental advances in the areas of mathematical logic, probability theory, statistics, operator ...
and Steven Givant (1998) ''Logic as Algebra''.
Mathematical Association of America.
*
Saunders Mac Lane
Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg.
Early life and education
Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftville ...
(1998) ''
Categories for the Working Mathematician
''Categories for the Working Mathematician'' (''CWM'') is a textbook in category theory written by American mathematician Saunders Mac Lane, who cofounded the subject together with Samuel Eilenberg. It was first published in 1971, and is based on ...
''. 2nd ed. (Graduate Texts in Mathematics 5). Springer-Verlag.
*
Saunders Mac Lane
Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg.
Early life and education
Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftville ...
(1999) ''Algebra'', 3d. ed.
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
. {{ISBN, 0-8218-1646-2.
* Robert R. Stoll, 1963. ''Set Theory and Logic'', chpt. 6.7. Dover reprint 1979.
Boolean algebra
Free algebraic structures