FreeBooleanAlgebra 2008-04-24 12:02:53 2008-04-28 23:20:58 Definition Boolean lattice \usepackage{amssymb,amscd} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{mathrsfs} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions \usepackage{amsthm} % making logically defined graphics \usepackage{xypic} \usepackage{pst-plot} % define commands here \newcommand*{\abs}[1]{\left\lvert #1\right\rvert} \newtheorem{prop}{Proposition} \newtheorem{thm}{Theorem} \newtheorem{ex}{Example} \newcommand{\real}{\mathbb{R}} \newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}} 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 \emph{freely generated by $X$}, or that $X$ is a \emph{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: \begin{center} $ \xymatrix@R-=2pt{ X\ar[dr]^f\ar[dd]_i\\ &B\\ A\ar[ur]_g } $ \end{center} 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)\ne 0$ can never be extended to a Boolean homomorphism. A Boolean algebra is said to be \emph{free} if it has a free set of generators. If $A$ has $X$ as a free set of generators, $A$ is said to be \emph{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=\lbrace 0,a,a',1\rbrace$ 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')=b'$, $g(0)=0$, and $g(1)=1$ is clearly Boolean. The two-element algebra $\lbrace 0,1\rbrace$ 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$.