View source for Mired

In [[abstract algebra]], a branch of [[mathematics]], a '''free Boolean algebra''' is a [[Boolean algebra (structure)|Boolean algebra]] 〈''B'',''F''〉, such that the set ''B'' (called the ''carrier'') has a [[subset]] whose elements are called [[generating set|generators]]. The generators satisfy the following properties:
*Each element of ''B'' that is not a generator can be expressed as a [[Finite set|finite]] combination of [[generating set|generators]], using the elements of ''F'', which are [[operation (mathematics)|operations]];
*The generators are as "independent" as possible, in that any equation holding for finite [[term (mathematics)|terms]] formed from the generators using the operations in ''F'', also holds for all elements of all possible Boolean algebras.

==A simple example==
[[File:Hasse2Free.png|right|300px|The [[Hasse diagram]] of the free Boolean algebra on two generators, ''p'' and ''q''. Take ''p (left circle)'' to be "John is tall" and ''q (right circle)''to be "Mary is rich". The atoms are the four elements in the row just above FALSE.]]
The [[generating set|generators]] of a free Boolean algebra can represent independent [[proposition]]s. Consider, for example, the propositions "John is tall" and "Mary is rich". These generate a Boolean algebra with four [[atomic (order theory)|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]]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<sup>''n''</sup>  [[atomic (order theory)|atoms]], and therefore <math>2^{2^n}</math> elements.

If there are [[infinite set|infinitely]] many [[generating set|generators]], a similar situation prevails except that now there are no [[atomic (order theory)|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 [[logical equivalence|logically equivalent]].

==Category-theoretic definition==
In the language of [[category theory]], free Boolean algebras can be defined simply in terms of an [[adjunction]]{{dn|date=December 2013}} 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]].

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''&prime; : ''FX'' → ''B'' that extends ''f''. [[Commutative diagram|Diagrammatically]],
[[File:Free-Boolean-algebra-unit-sloppy.png|center]]
where ''i''<sub>''X''</sub> is the inclusion, and the dashed arrow denotes uniqueness. The idea is that once one chooses where to send the elements of ''X'', the [[Boolean_algebra_(structure)#Homomorphisms_and_isomorphisms|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''&prime; wouldn't be unique, and if the elements of ''X'' weren't sufficiently independent, then ''f''&prime; wouldn't be well defined! It's easily shown that ''FX'' is unique (up to isomorphism), so this definition makes sense. It's 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''&prime; is a homomorphism; since it's 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]] ''U'' : '''BA''' → '''Set''' that "[[Forgetful functor|forgets]]" the algebraic structure, mapping algebras and homomorphisms to their underlying sets and functions.
[[File:Free-Boolean-algebra-unit.png|center]]
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'' → ''B'' extends to a unique Boolean algebra homomorphism ''f''&prime; : ''FX'' → ''B''. The functor ''U'' can be thought of as a device to pull the homomorphism ''f''&prime; 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 functors|adjoint]]. 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]] ''F''.

==Topological realization==
The free Boolean algebra with κ [[generating set|generators]], where κ is a finite or infinite [[cardinal number]], may be realized as the collection of all [[clopen set|clopen]] [[subset]]s of {0,1}<sup>κ</sup>, given the [[product topology]] assuming that {0,1} has the [[discrete topology]]. For each α&lt;κ, the α''th'' generator is the set of all elements of {0,1}<sup>κ</sup> whose α''th'' coordinate is 1. In particular, the free Boolean algebra with <math>\aleph_0</math> generators is the collection of all [[clopen set|clopen subsets]] of a [[Cantor space]]. Surprisingly, this collection is [[countable set|countable]]. In fact, while the free Boolean algebra with ''n'' generators, ''n'' finite, has [[cardinality]] <math>2^{2^n}</math>, the free Boolean algebra with <math>\aleph_0</math> generators has cardinality <math>\aleph_0</math>.

For more on this [[topology|topological]] approach to free Boolean algebra, see [[Stone's representation theorem for Boolean algebras]].

==See also==
* [[Boolean algebra (structure)]]
* [[Generating set]]

==References==
* Steve Awodey (2006) ''Category Theory'' (Oxford Logic Guides 49). Oxford University Press.
* [[Paul Halmos]] and Steven Givant (1998) ''Logic as Algebra''. [[Mathematical Association of America]].
* [[Saunders Mac Lane]] (1998) ''[[Categories for the Working Mathematician]]''. 2nd ed. (Graduate Texts in Mathematics 5). Springer-Verlag.
* [[Saunders Mac Lane]] (1999) ''Algebra'', 3d. ed. [[American Mathematical Society]]. ISBN 0-8218-1646-2.
* Robert R. Stoll, 1963. ''Set Theory and Logic'', chpt. 6.7. Dover reprint 1979.

[[Category:Boolean algebra]]
[[Category:Free algebraic structures]]