\problemdata       % Takes 5 *mandatory* arguments
  {set-size-induction}     % latex-friendly label for the prob.
  {Induction}              % The topic(s) of the problem content.
  {}                       % Source (if known)
  {S02 cp2W-3}             % Usage (list ones you are aware of).
  {Nick Matsakis, S02}     % Last revision info (author, date).
\begin{problem}

Prove by induction on the size of finite sets, $A,B$, that
\begin{equation}\label{IE2}
\card{A \union B} = \card{A} + \card{B} - \card{A \intersect B}
\end{equation}

\solution{Equation~(\ref{IE2}) makes no mention of an induction variable
$n$, so to apply induction, we have to reformulate it in terms of $n$.
There are several reasonable ways to do this.  We'll choose
\[
P(n) \eqdef\quad \forall A\ \card{A} = n \implies \forall B\ \card{A
\union B} = \card{A} + \card{B} - \card{A \intersect B}.
\]
Now the conclusion of an induction proof will be $\forall n\ P(n)$.  This
is not quite the same as~(\ref{IE2})---it mentions $n$---but is obviously
equivalent to~(\ref{IE2}).  In other words, all we have to do is prove
$\forall n\ P(n)$.

\begin{proof}(by Induction).   The induction hypothesis, $P(n)$, was
defined above.

We first establish:
\begin{lemma*}
If $A \subseteq B$, then~(\ref{IE2}) holds.
\end{lemma*}
\begin{proof}(of Lemma).  In this case, $A \union B = B$, $A \intersect B =
A$, so equation~(\ref{IE2})
reduces to 
\[
\card{B} = \card{A} + \card{B} - \card{A},
\]
which holds trivially.
\end{proof}

We now proceed with the induction proof.

\textbf{Base case}: $n=0$.  This means $A = \emptyset$.  So surely, $A
\subseteq B$, and equation~(\ref{IE2}) holds by the Lemma.  So $P(0)$ is
true.

\textbf{Induction step}: Assume the induction hypothesis, $P(n)$, holds in
order to prove $P(n+1)$.

So suppose $\card{A} = n+1$.  We want to prove that~(\ref{IE2}) holds for
all finite sets $B$.  To do this we proceed by cases.  Let $B$ be any
given finite set.

Case 1: $A \subseteq B$.  Then~(\ref{IE2}) holds by the Lemma.  (Note: we
didn't even need to assume $P(n)$.)

Case 2: $A \not\subseteq B$.  In this case, there is an $a \in A - B$.  Let
$A' \eqdef A - \set{a}$.  So $\card{A'} = n$, and from $P(n)$, we have
\begin{equation}\label{A'}
\card{A' \union B} = \card{A'} + \card{B} - \card{A' \intersect B}
\end{equation}
Now
\[
A \union B = (A' \union \set{a}) \union  B =  \set{a} \union (A' \union
B),
\]
and since $a \notin (A' \union B)$, we have
\begin{equation}\label{1a}
\card{A \union B} = \card{\set{a} \union (A' \union B)} = 1 + \card{(A' \union B)}.
\end{equation}
Also, $A \intersect B = A' \intersect B$, so from~(\ref{A'}) we have
\begin{equation}\label{A'B}
\card{A' \union B} = n + \card{B} - \card{A \intersect B}.
\end{equation}
Now from~(\ref{1a}),
\begin{eqnarray*}
\card{A \union B} & = & 1 + \card{A' \union B}\\
& = & 1 + n + \card{B} - \card{A \intersect B}\\
& = & \card{A} + \card{B} - \card{A \intersect B}.
\end{eqnarray*}
So we have proved~(\ref{IE2}) in this case also.

Hence~(\ref{IE2}) holds for all $B$, and we have completed the proof of
$P(n+1)$.
\end{proof}
}
\end{problem}
