Free Boolean algebra

In abstract algebra, a branch of mathematics, a free Boolean algebra is a Boolean algebra 〈B,F〉, such that the set B (called the carrier) has a subset whose elements are called generators. The generators satisfy the following properties:

• Each element of B that is not a generator can be expressed as a finite combination of generators, using the elements of F, which are operations;
• The generators are as "independent" as possible, in that any equation holding for finite terms formed from the generators using the operations in F, also holds for all elements of all possible Boolean algebras.

A simple example

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 generators of a free Boolean algebra can represent independent propositions. 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 disjunctions 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 is not a disjunction of atoms (though it 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ⁿ atoms, and therefore $2^{2^{n}}$ elements.

If there are infinitely 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.

Category-theoretic definition

Using category theory, free Boolean algebras can be defined simply in terms of an adjoint functor pair between the category of sets, Set, and the category of Boolean algebras, BA. Given a Boolean algebra B, let UB denote its underlying set. This extends to a functor U : BA → Set called the forgetful functor – it forgets the structure of Boolean algebras and homomorphisms. It can be shown that U has a left adjoint F : Set → BA, i.e. every function f : X → UB extends to a unique homomorphism f′ : FX → B. Diagramatically,

File:Latex-image-1.png

FX is the free Boolean algebra generated by the set X and i_X is the inclusion.

The idea is that once you choose where to send the elements of X, the requirements on Boolean algebra homomorphisms determine where to send everything else in the free algebra FX. The functor U is just a device to get the function f and the homomorphism f′ in the same category.

Uniqueness up to isomorphism follows immediately from universality of the unit of the adjunction. Moreover, the mapping i can be shown to be injective. Thus given any free Boolean algebra B, there exists a subset X of B, called the generating set of B, such that any map from X into B′ extends uniquely to a homomorphism from B into B′.

Topological realization

The free Boolean algebra with κ generators, where κ is a finite or infinite cardinal number, may be realized as the collection of all clopen subsets of {0,1}^κ, given the product topology assuming that {0,1} has the discrete topology. For each α<κ, the αth generator is the set of all elements of {0,1}^κ whose αth coordinate is 1. In particular, the free Boolean algebra with $\aleph _{0}$ generators is the collection of all clopen subsets of a Cantor space. Surprisingly, this collection is countable. In fact, while the free Boolean algebra with n generators, n finite, has cardinality $2^{2^{n}}$, the free Boolean algebra with $\aleph _{0}$ generators has cardinality $\aleph _{0}$.

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

See also

• Boolean algebra
• Generating set

References

• Paul Halmos and Steven Givant (1998) Logic as Algebra. Mathematical Association of America.
• Saunders Mac Lane (1999) Algebra, 3d. ed. American Mathematical Society. ISBN 0-821-81646-2.
• Stoll, R. R., 1963. Set Theory and Logic, chpt. 6.7. Dover reprint 1979.