Free Boolean algebra

In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called generators, such that: The generators of a free Boolean algebra can represent independent propositions.

These generate a Boolean algebra with four atoms, namely: 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".

If there are infinitely many generators, a similar situation prevails except that now there are no atoms.

Another way to see why the free Boolean algebra on an n-element set has

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.

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.

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.

To relate the two, we introduce a functor U : BA → Set that "forgets" the algebraic structure, mapping algebras and homomorphisms to their underlying sets and functions.

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.

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. 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.

In fact, while the free Boolean algebra with n generators, n finite, has cardinality

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 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.