Free Boolean algebra

From Wikipedia, the free encyclopedia

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.

1 A simple example
2 Category-theoretic definition
3 Topological realization
4 See also
5 References

[edit] 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.

[edit] Category-theoretic definition

Using category theory, a free Boolean algebra on a set of generators S is the ordered pair (π,B) such that:

π is the mapping S → B;
B is a Boolean algebra,

and which is universal with respect to this property. This means that for any Boolean algebra B₁ and for any 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 comma categories.

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

[edit] 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$ .