\problemdata     
{S01-PS3-3}           
{induction, logic}              
{}              
{S01-PS3} 		
{S01 Karger}        	

\newcommand{\F}{\mathcal{F}}
\newcommand{\G}{\mathcal{G}}
\renewcommand{\H}{\mathcal{H}}
\renewcommand{\power}{\mathcal{P}}
\newcommand{\I}{\mathcal{I}}
\begin{problem} 

 Suppose that $\Omega$~is a finite set. A collection $\F \subseteq
\power(\Omega)$ is called an \emph{algebra} if
\begin{enumerate}
\item $\Omega \in \F$,\label{algebra:non-empty}
\item $\omega \in \F \implies \overline{\omega} \in \F$,\label{algebra:complement}
\item $\omega_1 \in \F \land \omega_2 \in \F \implies \omega_1 \union
  \omega_2 \in \F$.\label{algebra:union}
\end{enumerate}
(The complement in item~\ref{algebra:complement} above is with respect
the universe~$\Omega$.)


For instance, if $\Omega = \{1,2,3\}$, the collection
$\{\{1,3\},\{2\}\}$ is \emph{not} an algebra, but the collection
$\{\emptyset,\{1,3\},\{2\},\{1,2,3\}\}$ is.

\solution{
\begin{quote}\small
  A special type of algebras---so called $\sigma$-algebras---is the
  foundation of axiomatic probability theory. They are defined by
  basically the same axioms as above, but $\Omega$~does not have to be
  a finite set and the algebra has to be closed under the union of a
  countably infinite number of sets instead of the union of just two
  sets. The elements of~$\F$ are the possible \emph{events}, i.e., the
  information we can get about the outcome of the random experiment.
  Then a positive number $P(\omega)$ is assigned to every element
  of~$\F$ in such a way that $P(\Omega) = 1$ and $P(\omega_1 \union
  \omega_2) = P(\omega_1) + P(\omega_2)$ for disjoint
  $\omega_1,\omega_2 \in \F$. This number is the \emph{probability} of
  the events in~$\F$. The triple $(\Omega, P, \F)$ is usually called a
  \emph{probability space}. For the example above, with $\Omega =
  \{1,2,3\}$ and the algebra $\F =
  \{\emptyset,\{1,3\},\{2\},\{1,2,3\}\}$, we could for instance set
  $P(\{1,3\}) = 2/3$ and $P(\{2\}) = 1/3$. That would model the
  situation ``choose a number in $\{1,2,3\}$ uniformly'' where the
  only information we can observe about the outcome is if the number
  is odd or not.
\end{quote}
}

\begin{problemparts}
  \problempart Prove that if $\F$~is an algebra, $\omega_1 \in \F
  \land \omega_2 \in \F \implies \omega_1 \intersect \omega_2 \in \F$.

  \solution{
    \begin{proof}
      By property~\ref{algebra:complement}, $\overline{\omega_1} \in
      \F$ and $\overline{\omega_2} \in \F$.  By the
      property~\ref{algebra:union}, this implies that
      $\overline{\omega_1} \union \overline{\omega_2} \in \F$. By
      property~\ref{algebra:complement}, this inplies that
      $\overline{\overline{\omega_1} \union \overline{\omega_2}} \in
      \F$. By DeMorgan, this implies that $\omega_1 \intersect
      \omega_2 \in F$.
    \end{proof}
    }

  \problempart Prove that if $\F_1 \subseteq \power(\Omega)$ and $\F_2
  \subseteq \power(\Omega)$ are algebras, then $\F_1 \intersect \F_2$ is
  also an algebra.

  \solution{
    \begin{proof}
      Let $\F_1$ and~$\F_2$ be algebras. We now show that $\F_1
      \intersect \F_2$ satisfies the definition of an algebra.
      
      Since $\F_1$ is an algebra $\Omega \in \F_1$; since $\F_2$ is an
      algebra $\Omega \in \F_2$. Thus $\Omega \in \F_1 \intersect
      \F_2$ by the definition of intersection.
      
      Suppose that $\omega \in \F_1 \intersect \F_2$. Then $\omega \in
      \F_1 \land \omega \in \F_2$. If $\omega \in F_1$, then
      $\overline{\omega} \in \F_1$ since $\F_1$~is an algebra. If
      $\omega \in F_2$, then $\overline{\omega} \in \F_2$ since
      $\F_2$~is an algebra. Thus $\overline{\omega} \in \F_1
      \intersect \F_2$.
      
      Suppose that $\omega_1 \in \F_1 \intersect \F_2$ and that
      $\omega_2 \in \F_1 \intersect \F_2$. This implies that both
      $\omega_1$ and~$\omega_2$ are in~$\F_1$; and that both
      $\omega_1$ and~$\omega_2$ are in~$\F_2$.  Since both $\omega_1$
      and~$\omega_2$ are in~$\F_1$ and $\F_1$ is an algebra, $\omega_1
      \union \omega_2$ is also in~$\F_1$.  Since both $\omega_1$
      and~$\omega_2$ are in~$\F_2$ and $\F_2$ is an algebra, $\omega_1
      \union \omega_2$ is also in~$\F_2$. Thus $\omega_1 \union
      \omega_2$ is both in $\F_1$ and in~$\F_2$, which is the same
      thing as saying that $\omega_1 \union \omega_2 \in \F_1
      \intersect \F_2$.
    \end{proof}
    }
  
  \problempart Prove that if $\F_i \subseteq \power(\Omega)$ are algebras
  for $i = 1,\ldots,n$, then $\bigcap_{i=1}^n \F_i$ is also an
  algebra.
  
  \solution{
    \begin{proof}
      We prove the claim by induction on~$n$. The base case ($n=1$) is
      clear. We now assume that $\bigcap_{i=1}^n \F_i$ is an
      algebra and rewrite
      \begin{displaymath}
        \bigcap_{i=1}^{n+1} \F_i = 
        \biggl(\bigcap_{i=1}^n \F_i\biggr) \intersect \F_{n+1}
      \end{displaymath}
      Thus, $\bigcap_{i=1}^{n+1} \F_i$ is---by the assumption---the
      intersection of two algebras. Since we proved above that the
      intersection of two algebras is also an algebra, we have thus
      proven that $\bigcap_{i=1}^{n+1} \F_i$ is an algebra.
    \end{proof}
    }
  
% \ignore'd by Lars 2/20
% \ignore{
%   \problempart Consider a collection $\G \subseteq \power(\Omega)$ that
%   might not be an algebra. Consider the set
%   \begin{displaymath}
%     \I = \{\F_i \suchthat
%     \mbox{$\G \subseteq \F_i$ and $\F_i$ is an algebra}\bigr\}
%   \end{displaymath}
%   of all algebras containing~$\G$. Note, that since $\power(\Omega)$ is
%   itself an algebra, $\power(\Omega) \in \I$, and thus $\I$~is non-empty.
%   By the result you proved above, $\F = \bigcap \I$ is an algebra.
%   Moreover, $\G \subseteq \F$ since $\G \subseteq \F_i$ for all $\F_i
%   \in \I$. Prove that $\F$~is the smallest algebra containing~$\G$. In
%   other words, prove that there cannot exist any $\H \subseteq
%   \power(\Omega)$ such that $\H$~is an algebra and $\G \subseteq \H \subset
%   \F$.

%   \Solution{
%     \begin{proof}
%       Suppose that there exists an $\H \subseteq \power(\Omega)$ such that
%       $\H$~is an algebra and $\G \subseteq \H \subset \F$. Since $\H$
%       is an algebra that contains~$\G$, $\H \in \I$. Thus, by the
%       definition of~$\F$, $\F \subseteq \H$, which is a contradicion.
%     \end{proof}
%     }
  
  \problempart Consider an algebra $\F \subseteq \Omega$. The members
  of~$\F$ form a partial order with respect to the subset operation,
  i.e., $(\F,\subseteq)$ is a partial order. Since $\Omega \in \F$ by
  the definition of an algebra, we also have $\F \ni \bar{\Omega} =
  \emptyset$, which implies that the partial order $(\F,\subseteq)$
  has one unique minimal element, $\emptyset$. Now consider the set
  \begin{displaymath}
    \G = \bigl\{\omega \in \F \bigm| (\forall \omega' \in \F)
    (\omega' \subset \omega \implies \omega' = \emptyset\bigr\},
  \end{displaymath}
  i.e., the family of sets in~$\F$ that are immediately
  above~$\emptyset$ in the partial order. Prove that the elements
  of~$\G$ form a partition of~$\Omega$.

  \solution{
    \begin{proof}
      We first prove that there are no two sets in~$\G$ that
      intersect. Suppose that there are two such sets~$G_1$ and~$G_2$
      such that $G_1 \neq G_2$ and $G_1 \intersect G_2 \neq
      \emptyset$. Since $\F$~is an algebra, $G_1 \intersect G_2 \in
      \F$. Moreover, either $G_1 \intersect G_2 \subset G_1$ or $G_1
      \intersect G_2 \subset G_2$ since $G_1 \neq \G_2$. This
      contradicts the fact that both $G_1$ and~$G_2$ are members
      of~$\G$.
      
      Fix some $a \in \Omega$. We now show that $a$~occurs in exactly
      one member of~$\G$. Assume the contrary, i.e., that $a$~does not
      occur in any member of~$\G$---we now by the above reasoning that
      no sets in~$\G$ intersect, so this is the only remaining
      possibility. Since $\Omega \in \F$, there exists at least one
      set in~$\F$ containing~$a$. Let $\omega$~be the smallest such
      set---by well-ordering, such an~$\omega$ always exists. By our
      assumption, $\omega \notin \G$. Consider the case $|\omega| =
      1$. Then the only proper subset of~$\omega$ is~$\emptyset$,
      which implies that $\omega \in \G$---a contradiction.
      
      Now assume that $|\omega| > 1$. Since $\omega \notin \G$, there
      must exist some~$\omega' \in \F$ satisfying $\emptyset \subset
      \omega' \subset \omega$. Moreover, since $\omega$~is the
      smallest set in~$\F$ that contains~$a$, $a \notin \omega'$. But
      since $\omega,\omega' \in \F$, the set $\omega - \omega'$, which
      contains~$a$, is also in~$\F$ and has a size smaller
      than~$|\omega|$. This is a contradiction.
    \end{proof}
    }

\end{problemparts}  

\end{problem}
