Free boolean algebra

Question

Consider the following definition:

Let $X$ be a set and $e : X \mapsto A$ a mapping to a boolean algebra $A.$ We say that $A$ is free over $X$ (with respect to $e$) if for every mapping $f:X \mapsto B$ for a boolean algebra $B$ there is precisely one homomorphism $\overline{f}:A \mapsto B$ such that $\overline{f} \circ e = f.$

I would eventually like to prove some statements involving free boolean algebras but I am stuck in understanding this definition.

I understand it formally but don't see its intuitive meaning. Something simply doesn't click.

How should one think about this definition?

For example, how should one try to prove that if $A$ is free over $X$ with respect to $e:X \mapsto A$ then $e$ is injective? Is it correct to simply say that if $e$ is not injective then so isn't $\overline{f}\circ e$ but since $f$ is arbitrary it can as well be an injective function?

What about the fact that any free algebra over a set of cardinality $n$ has precisely $2^{2^{n}}$ elements? Is there a direct way (without referring to the Lindenbaum algebra) to prove this claim directly from the definition?

(PS. I am no category theorist the arrow notation just scares me :)

Answer 1

This construction is very common all over abstract algebra -- not just for boolean algebras, but also for groups, modules, monoids, and so forth. The technical definition may look forbidding at first sight if one is not used to universal properties, but what it boils down to is very simple. Essentially the free boolean algebra $A$ has three main properties:

1. $A$ contains a copy of $X$, in the sense that each element of $X$ has a unique partner in $A$.

2. $A$ contains no elements that it doesn't have to. More precisely, every element of $A$ can be made by evaluating some finite expression which may contain elements of $X$ in addition to the Boolean algebra operations.

3. $A$ distinguishes between elements as much as possible. Specifically, two different expressions can only evaluate to the same element if it can be proved from the boolean-algebra axioms that they must be the same.

Essentially the free algebra is the set of finite expressions with constants from $X$, modulo those equalities forced by the axioms.

One advantage of the category-theoretic definition (for those of us who don't think that simply being category theoretic is in itself an advantage) is that it allows us to sidestep the issue of precisely what "provable from the axioms" means. It is nice not to depend on proof theory in the technical development.

To see that these properties are implied by the definition:

1. Let $x$ and $y$ be any two different elements of $X$; we want to show that $e(x)\ne e(y)$. Choose $f:X\to\{\mathit{true},\mathit{false}\}$ such that $f(x)=\mathit{true}$ and $f(y)=\mathit{false}$. Then by the definition, there is a homomorphism $\bar f$ such that $\bar f(e(x)=\mathit{true}$ and $\bar f(e(y))=\mathit{false}$. But that is only possible if $e(x)$ and $e(y)$ are different elements.

2. Let $A$ be some free algebra, and let $B$ be the set of elements in it that do arise as the values of finite expressions. Then $B$ is itself a boolean algebra, and $e(x)$ is in $B$ for every $x$. Then the free-algebra property of $A$ gives us $g:A\to B$ such that $g(e(x))=e(x)$ for all $x$. Since $B$ is a subalgebra of $A$, $g$ is also a homomorphism $A\to A$. Using the definition of free algebra again, we learn that there is exactly one homomorphism $g: A\to A$ such that $g(e(x))=e(x)$. But the identity map on $A$ also has this property, so $g$ must be the identity! But that is only possible if $B$ is all of $A$.

3. Let $A$ be an algebra with a map $e_A:X\to A$, and let $B$ be the "set of all expressions modulo consequences of the axioms" I describe above. If there were two expressions that evaluated to the same element in $A$ without having to, they would evaluate to different elements of $B$. But then there can be no homomorphism $A\to B$ that agrees on $e_A$, so $A$ is not a free algebra with respect to $e_A$.