# Free boolean algebra

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.

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 :)

-
This just means that: (1) $X$ generates $A$, and (2) there are no non-trivial relations between the generators. Think free groups, vector spaces spanned by a set etc. –  Alexei Averchenko Jun 17 '12 at 11:41
Yeah I was able to infer that from the wikipedia page. How do you see that from the definitions though? –  Jernej Jun 17 '12 at 11:43
Think about $e$ as a way to mark a few elements. The universal property means that knowing where the marks go under a morphism is enough to reconstruct that morphism. Now denote $A'$ the subalgebra of $A$ generated by $X$. I don't really know how to prove that $A = A'$ :( My best guess is that if $A \coprod_{A'} A$ exists, you can construct two different morphisms that reduce to the identity on $A'$, but I don't know if the category of boolean algebras has pushforwards or if there is a more general way of proving this. –  Alexei Averchenko Jun 17 '12 at 11:55
I'm not knowledgeable about boolean algebras, but isn't the power set of $X$ one? Couldn't you consider the map $$X\rightarrow \mathscr{P}(X),x\mapsto \lbrace x\rbrace$$ –  Olivier Bégassat Jun 17 '12 at 12:03
Notation: What one writes an arrow between two sets to denote "functions from this set to that set", one usually use a plain arrow "$\to$" (\to in TeX). The "$\mapsto$" arrow \mapsto is for "the function we're speaking of maps this particular element to that one". –  Henning Makholm Jun 17 '12 at 14:15

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

-