# free Boolean algebra

Let $A$ be a Boolean algebra and $X\subseteq A$ such that $\langle X\rangle=A$. In other words, $X$ is a set of generators of $A$. $A$ is said to be freely generated by $X$, or that $X$ is a free set of generators of $A$, if $\langle X\rangle=A$, and every function $f$ from $X$ to some Boolean algebra $B$ can be extended to a Boolean algebra homomorphism $g$ from $A$ to $B$, as illustrated by the commutative diagram below:

$\xymatrix@R-=2pt{X\ar[dr]^{f}\ar[dd]_{i}\inner@par&B\inner@par A\ar[ur]_{g}}$

where $i:X\to A$ is the inclusion map. By extension of $f$ to $g$ we mean that $g(x)=f(x)$ for every $x\in X$. Any subset $X\subseteq A$ containing $0$ (or $1$) can never be a free generating set for any subalgebra of $A$, for any function $f:X\to B$ such that $f(0)\neq 0$ can never be extended to a Boolean homomorphism.

A Boolean algebra is said to be free if it has a free set of generators. If $A$ has $X$ as a free set of generators, $A$ is said to be free on $X$. If $A$ and $B$ are both free on $X$, then $A$ and $B$ are isomorphic. This means that free algebras are uniquely determined by its free generating set, up to isomorphisms.

A simple example of a free Boolean algebra is the one freely generated by one element. Let $X$ be a singleton consisting of $a$. Then the set $A=\{0,a,a^{\prime},1\}$ is a Boolean algebra, with the obvious Boolean operations identified. Every function from $X$ to a Boolean algebra $B$ singles out an element $b\in B$ corresponding to $a$. Then the function $g:A\to B$ given by $g(a)=b$, $g(a^{\prime})=b^{\prime}$, $g(0)=0$, and $g(1)=1$ is clearly Boolean.

The two-element algebra $\{0,1\}$ is also free, its free generating set being $\varnothing$, the empty set, since the only function on $\varnothing$ is $\varnothing$, and thus can be extended to any function.

In general, if $X$ is finite, then the Boolean algebra freely generated by $X$ has cardinality $2^{2^{|X|}}$, where $|X|$ is the cardinality of $X$. If $X$ is infinite, then the cardinality of the Boolean algebra freely generated by $X$ is $|X|$.

Title free Boolean algebra FreeBooleanAlgebra 2013-03-22 18:01:23 2013-03-22 18:01:23 CWoo (3771) CWoo (3771) 12 CWoo (3771) Definition msc 06E05 msc 03G05 msc 06B20 msc 03G10