\documentclass[12pt]{article}
\usepackage{graphicx,geometry,amsfonts,wrapfig}
\geometry{paperheight=11in,paperwidth=8.5in,tmargin=1in,
bmargin=1in,inner=1in,outer=1in}

\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\nat}{\field{N}}
\newcommand{\real}{\field{R}}
\newcommand{\rat}{\field{Q}}
\newcommand{\cpl}{\field{C}}
\newcommand{\capt}[1]{\centering{\scriptsize{\textsc{#1}}}}
\newcommand{\size}{1.35in}

\newcommand{\pset}[1]{{\cal P}(#1)}
\newcommand{\atom}{\alpha}

\renewcommand{\refname}{\normalsize{References:}}

\newtheorem{prob}{Problem}
\newenvironment{pro}{\begin{prob}\em }{\end{prob}}


\begin{document}
\thispagestyle{empty}
\noindent{\large{\bf Boolean Algebra Theorem Sequence}}\vspace{.3in}\\
\textsc{Helmut Knaust}\medskip\\
\footnotesize{Department of Mathematical Sciences\\The University of Texas at El Paso\\El Paso TX 79968-0514}\vspace{.6in}\\
%%
\section{Beginning}
\emph{Statements and their logic connectives on the one hand, and sets and set connectives on the other hand behave somewhat analogously. The English mathematician \textsc{George Boole} (1815--1864) made this idea precise by describing what he called ``algebra of logic''\cite{bl}. Today we use the name ``Boolean Algebra'' in his honor instead. The axioms below were first formulated~\cite{ht}\ by the American mathematician \textsc{Edward V.~Huntington} (1874--1952).}\bigskip
 
\section{Boole}
A \emph{Boolean Algebra} is a set ${\cal B}$ together with two ``connectives'' $\sqcap$ and $\sqcup$ satisfying the following properties:
\begin{enumerate}
\item \textbf{Closure Laws}: 
\begin{enumerate} 
\item If A and B are two elements in ${\cal B}$, then $A\sqcap B$ is also an element in ${\cal B}$.
\item If A and B are two elements in ${\cal B}$, then $A\sqcup B$ is also an element in ${\cal B}$.
\end{enumerate}
\item \textbf{Commutative Laws}:
\begin{enumerate}
\item $A\sqcap B=B\sqcap A$\quad for all elements $A$ and $B$ in $\cal B$.
\item $A\sqcup B=B\sqcup A$\quad for all elements $A$ and $B$ in $\cal B$.
\end{enumerate}
\item \textbf{Distributive Laws}:
\begin{enumerate}
\item $A\sqcap (B\sqcup C)=(A\sqcap B)\sqcup (A\sqcap C)$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\item $A\sqcup (B\sqcap C)=(A\sqcup B)\sqcap (A\sqcup C)$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\end{enumerate}
\item\label{no} \textbf{Identity Laws}:\medskip\\
There are elements $N\in{\cal B}$ (called the \emph{null-element}) and $O\in{\cal B}$ (the \emph{one-element}) such that
\begin{enumerate}
\item $A\sqcap N=N$ and $A\sqcap O=A$\quad for all elements $A$ in $\cal B$.
\item $A\sqcup O=O$ and $A\sqcup N=A$\quad for all elements $A$ in $\cal B$.
\end{enumerate}
\item\label{comp} \textbf{Complement Law}:\medskip\\
For every element $A$ in $\cal B$ there is an element $B$ in $\cal B$ such that $A\sqcap B=N$ and $A\sqcup B=O$.
\item \textbf{Associative Laws}:\footnote{The Associative Laws can be deduced from the other five Boolean Algebra Laws.}
\begin{enumerate}
\item $A\sqcap (B\sqcap C)=(A\sqcap B)\sqcap C$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\item $A\sqcup (B\sqcup C)=(A\sqcup B)\sqcup C$\quad for all elements $A$, $B$ and $C$ in $\cal B$.
\end{enumerate}
\end{enumerate}
\bigskip

\emph{Let $X$ be an arbitrary set. Note that 
\[{\cal P}(X)=\{A\ |\ A\subseteq X\},\]
the power set of $X$, with the connectives $\cap$ (in the role of $\sqcap$) and $\cup$ (in the role of $\sqcup$) forms a Boolean Algebra. }

\begin{wrapfigure}[14]{r}{\size}
\includegraphics[width=\size]{Boole.jpg}\\\capt{G.~Boole}
\end{wrapfigure}
\begin{pro}
Let $X$ be an arbitrary set.
Let $A$ and $B$ be elements in ${\cal P}(X)$. Show the following
\[A\cap (A\cup B)=A.\] (Similarly one obtains that 
$A\cup (A\cap B)=A$.)
\end{pro}

\begin{pro}
Let $A$ and $B$ be elements in a Boolean Algebra ${\cal B}$. Show:
\[A\sqcap (A\sqcup B)=A.\] 
\end{pro}
\emph{Analogously one can obtain $A\sqcup (A\sqcap B)=A$. }

\begin{pro}
Let $A$ be an element in a Boolean Algebra ${\cal B}$ with null-element $N$ and one-element $O$. Furthermore let $B,C \in {\cal B}$ such that \[A\sqcap B=N \mbox{ and } A\sqcup B=O,\]
\[A\sqcap C=N \mbox{ and } A\sqcup C=O.\]
Show that $B=C$.
\end{pro}

\emph{Certain sets of statements with connectives $\wedge$ (in the role of $\sqcap$) and $\vee$ (in the role of $\sqcup$) also form Boolean Algebras.}

\emph{What is meant by ``certain'' sets of statements? Our task at hand is to identify what sets of statements correspond to power sets.} 

\emph{Let us consider an example and start with one ``generic'' statement $P$. How many distinct propositional forms can we form involving this statement? A little bit of reflection will lead us on the following path: Every propositional form has a truth table, so the number of distinct propositional forms is limited by the number of distinct truth tables. Since a truth table involving the statement $P$ has two rows, and since we have two choices for each row entry (T or F), there are at most 4~distinct truth tables, and therefore there are at most 4~distinct propositional forms. On the other hand it is easy to see that $P$, $\neg P$, $P\vee \neg P$ and $P\wedge \neg P$ are 4~distinct propositional forms contained in each Boolean Algebra containing $P$.}

\emph{It is now boring to check that the following 4-element set indeed forms a Boolean Algebra:
\[{\cal S}_1=\{P\wedge\neg P;\ P,\ \neg P;\ P\vee \neg P\}\]
${\cal S}_1$ is called the ``Boolean Algebra generated by the free statement $P$''.}

\begin{pro}
Find the Boolean Algebra ${\cal S}_2$ generated by two free statements $P$ and $Q$. How many elements does ${\cal S}_2$ have?
\end{pro}
\bigskip

%hw5
\emph{For a natural number $n$, let ${\cal D}_n$ denote the set of the divisors of $n$. For example, ${\cal D}_{42}=\{1,2,3,6,7,14,21,42\}$ and ${\cal D}_{12}=\{1,2,3,4,6,12\}$. For $m,n\in\nat$ let $m\sqcap n$ denote the greatest common divisor of $n$ and $m$, and $m\sqcup n$ their least common multiple. For instance $6\sqcap 4=2$ and $6\sqcup 4=12$. It turns out that ${\cal D}_{42}$ with these two operations $\sqcap$ and $\sqcup$ forms a Boolean Algebra, while ${\cal D}_{12}$ does \textbf{not}.}

\begin{pro}  
Verify Boolean Algebra Laws 3, 4 and 5 for ${\cal D}_{42}$. 
\end{pro}

\begin{pro}
\begin{enumerate}
\item Show that ${\cal D}_{12}$ does not form a Boolean Algebra.
\item Conjecture for which values of $n$ the set ${\cal D}_{n}$ forms a Boolean Algebra.  
\end{enumerate}
\end{pro}
\bigskip

\emph{Every Boolean Algebra is endowed with a partial order:}

\begin{pro}
Consider the relation ``$\preceq$'' on a Boolean Algebra ${\cal B}$ defined by 
\[A\preceq B \quad \Leftrightarrow\quad A\sqcup B=B\] for $A,B\in{\cal B}$. Prove that $\preceq$ is reflexive, anti-symmetric and transitive. 
\end{pro}

\begin{wrapfigure}[15]{r}{\size}
\includegraphics[width=\size]{Huntington.jpg}
\\\capt{E.V.~Huntington}
\end{wrapfigure}
\begin{pro}
Show: $A\preceq B \ \Leftrightarrow\ A\sqcap B=A$ for $A,B\in{\cal B}$.
\end{pro}

\begin{pro}
Draw  \emph{Hasse diagrams} for the Boolean Algebras ${\cal S}_1$, and ${\cal S}_2$, respectively, endowed with the partial order~$\preceq$.
\end{pro}

\emph{Let $X$ be a set, partially ordered by $\preceq$. We say that $x\in X$ is an \textsc{immediate predecessor} of $y\in X$ if\newline (1) $x\preceq y$, and (2) for all $z\in X$ with $x\preceq z\preceq y$, it follows that $z=x$ or $z=y$.}

\begin{pro}\label{atom}
Let ${\cal B}$ be a Boolean Algebra with null-element $N$, partially ordered by $\preceq$. We say that $A\in{\cal B}$ is an \textsc{atom} of ${\cal B}$ if $N$ is an immediate predecessor of $A$.
\begin{enumerate}
\item Find all atoms of ${\cal P}(\{1,2,3,4\})$.
\item Find all atoms of ${\cal D}_{42}$.
\end{enumerate}
\end{pro}

\begin{pro}
Find a Boolean Algebra with 8~elements that is a subset of ${\cal P}(\{1,2,3,4\})$, but \textbf{not} the power set of a three-element subset of $\{1,2,3,4\}$, then find its atoms and draw its Hasse diagram.
\end{pro}

\begin{pro}\label{atom3} 
Assume that ${\cal B}$ is a Boolean Algebra with finitely many elements. Show that for every $B\in{\cal B}$ with $B\neq N$ there is an atom $A$ such that $A\preceq B$.
\end{pro}

\begin{pro}
Let $A,B$ be two elements in a Boolean Algebra. Show the following: 
If $A\sqcap B=N$ and $A\preceq B$, then $A=N$. 
\end{pro}


\begin{pro}\label{atomm}
Let $A_1,A_2$ be two atoms in a finite Boolean Algebra. Show the following: 
\begin{enumerate}
\item The least upper bound of the set $\{A_1,A_2\}$ is the element $A_1 \sqcup A_2$.
\item If $A_1\neq A_2$, then $A_1\sqcap A_2=N$.
\end{enumerate}  
\end{pro}

\begin{pro}\label{aatom}
Given an element $B$ in a finite Boolean Algebra ${\cal B}$, we let \[\atom(B)=\{A\in{\cal B}\ |\ A\preceq B \mbox{ and } A \mbox{ is an atom of } {\cal B}\}.\]  Let $A_1\neq A_2$ be two atoms in ${\cal B}$. Show that $\atom(A_1\sqcup A_2)=\{A_1,A_2\}$.
\end{pro}

\emph{In the sequel, you may assume that results corresponding to those proved for two atoms in Problems~\ref{atomm} and \ref{aatom} also hold for finitely many atoms.}

\begin{pro}
Let $B\neq N$ be an element in a finite Boolean Algebra ${\cal B}$, and suppose $\atom(B)=\{A_1, A_2, A_3,\dots, A_k$\} for some $k\in\nat$ and some atoms $A_1, A_2, A_3,\dots, A_k$ of ${\cal B}$. Show:\footnote{\emph{Hint:} Expect to use Boolean Algebra Law 5 along the way.}
\[B=A_1\sqcup A_2\sqcup A_3\sqcup\ldots\sqcup A_k.\]
\end{pro}

\begin{wrapfigure}[10]{l}{\size}
\includegraphics[width=\size]{Stone.jpg}
\\\capt{M.H.~Stone}
\end{wrapfigure}
\emph{The next problem is the finite version of a general representation theorem for Boolean Algebras~\cite{stone}, proved by the American mathematician \textsc{Marshall H.~Stone} (1903--1989).}

\begin{pro}\label{mstone}
Let ${\cal B}$ be a finite Boolean Algebra with $k$ atoms for some $k\in\nat$, and let ${\cal P}(A)$ denote the power set of the set $A$ of all atoms  of ${\cal B}$.
\begin{enumerate}
\item Show that the function $\atom:{\cal B}\to{\cal P}(A)$, defined in Problem~\ref{aatom}, is a bijection. Thus ${\cal B}$ has $2^k$ elements.
\item Show that the identities $\atom(B\sqcup B')=\atom(B)\cup \atom(B')$ and  $\atom(B\sqcap B')=\atom(B)\cap \atom(B')$ hold for all $B,B'\in{\cal B}$.

Additionally, show that $\atom(N)=\emptyset$ and $\atom(O)=A$.
\end{enumerate}
\end{pro}


\emph{The result in Problem~\ref{mstone} is no longer true for infinite Boolean Algebras:}

\begin{pro}
\begin{enumerate}
\item Let ${\cal B}=\{B\in\pset{\nat}\ |\ (B \mbox{ is finite) or (} \nat\setminus B \mbox{ is finite)}\}$. Show that ${\cal B}$ is a Boolean Algebra (with $\cup$ and $\cap$).
\item Let ${\cal A}$ denote the power set of all atoms of ${\cal B}.$  Show that ${\cal B}$ is countably infinite, while ${\cal A}$ is uncountable. Therefore the function $\atom:{\cal B}\to{\cal A}$, defined in Problem~\ref{aatom}, is \textbf{not} a bijection.
\end{enumerate}
\end{pro}\vspace{1cm}

\begin{thebibliography}{9}
\bibitem{bl} George Boole: \emph{An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities} (1854).
\bibitem{ht} Edward V. Huntington: \emph{Sets of Independent Postulates for the Algebra of Logic}. Transactions of the American Mathematical Society 5 (1904), pp. 288-309.
\bibitem{stone} Marshall H.~Stone: \emph{The Theory of Representation for Boolean Algebras}. Transactions of the American Mathematical Society 40 (1936), pp. 37-111.
\end{thebibliography}
\vfill

\flushright \tiny Last edit: \today
\end{document}
