Free Boolean algebra

From Wikipedia, the free encyclopedia

This article or section does not adequately cite its references or sources.
Please help improve this article by adding citations to reliable sources. (help, get involved!)
This article has been tagged since June 2006.

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

[edit] Motivation and example

The Hasse diagram of the free Boolean algebra on two generators, p and q. Take p to be "John is tall" and q 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. For example, we might consider the two 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.

For infinitely many generators the situation is very similar, except that there are no atoms. Each element of the Boolean algebra is a combination of finitely many of the generating propositions; two such elements are considered to be the same if they are logically equivalent.

[edit] Category-theoretic definition

More formally, using concepts from category theory, a free Boolean algebra on a set of generators S is an ordered pair (π,B), where

π: S → B is a mapping,
B is a is a Boolean algebra,

and which is universal with respect to this property. This means that for any Boolean algebra B₁ and mapping π₁: S → B₁, there is a unique homomorphism f: B → B₁ such that

$\pi_1 = f \circ \pi.$

This universality property can also be formulated as an initiality property in so-called comma categories.

The uniqueness up to isomorphism is a property that follows immediately from the universal property. Note that the mapping π can be shown to be injective. Thus any free Boolean algebra B has the property that there is a subset S of B, called the set of generators of B, such that any map from S into a Boolean algebra B₁ extends uniquely to a homomorphism from B into B₁.

[edit] Topological realization

For any desired number κ of generators, finite or infinite, the free Boolean algebra with κ generators 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. The generators may be enumerated as follows: 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 Cantor space. Perhaps surprisingly, there are only countably many of these. In fact, while for finite n the free Boolean algebra with n generators has cardinality $2^{2^n}$ , for infinite κ the corresponding cardinality is just κ.