\documentstyle[11pt,twoside,amsfonts,amstex,psfig]{article}
%\usepackage{amsmath}
%\usepackage{graphics}
\input{macros-course}

\newcommand{\bij}{\mathop{\mbox{\rm bij}}}
\newcommand{\inj}{\mathop{\mbox{\rm inj}}}
\newcommand{\sur}{\mathop{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\iden}[1]{\text{id}_{#1}}
\newcommand{\clop}[1]{\mbox{{\rm \texttt{[}$0,#1$\texttt{)}}}}
\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}

\makeatletter
\newcommand{\solution}[1]{\@bsphack\@esphack}
\makeatother

%%  \newcommand{\solution}[1]{\textbf{Solution}: \bigskip #1}

\begin{document}

\tutprobn{8}{4/2/99}{April 1, 1999}

\section*{Team Problems}

\begin{problems}

\problem 

A real number is {\em algebraic} if it is the root of a polynomial with
rational number coefficients.
Algebraic numbers form an important part in
the study of (what else?) modern algebra.  A number that is not algebraic
is called {\em transcendental}.

\bparts

\ppart Explain why a number is algebraic iff it is the root of a
polynomial with integer coefficients.

\solution{$p(\alpha)=0$ where $p$ has rational coefficients iff $c\cdot
p(\alpha)$ where $c$ is the product of the denominators of the
coefficients of $p$.}

\ppart Prove that the set of algebraic numbers is countable.

\solution{There are only a countable number of polynomials with integer
coefficients of any given degree $d \in \naturals$, hence (by countable
union of countable sets) only a countable number of such polynomials of
any degrees at all.  Each polynommial has a finite number of roots, so the
algebraic numbers are a countable union (over all the polynomials with
integer coefficients) of finite sets (their roots) and hence is
countable.}


\ppart Conclude that there is a transcendental number.  \solution{We know
the reals are not countable, so $\reals$ must \emph{properly} contain the
set of algebraic numbers.  So there is a real which is not algebraic.}

\eparts

\problem Prove the Inclusion-Exclusion Theorem by induction on the number
of sets.  You may assume the case we have proved in lecture:
\[ |A \cup B| = |A| + |B| - |A \cap B| \ . \]

\end{problems}

\end{document}

\solution{\begin {proof}

{\em Base Case.} For $n=1$ the Inclusion-Exclusion formula
is just $|A_1| = |A_1|$.

{\em Inductive Step.} Assume that 

\[ |A_1 \cup \ldots \cup A_{n-1}| = \sum_{k=1}^{n-1} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S} A_i | \ . \]
and consider an $n$-th set $A_{n}$. Using
Inclusion-Exclusion for two sets,  we
have
\begin{eqnarray*} |A_1 \cup \cdots \cup A_n | &= &
| (A_1 \cup \ldots \cup A_{n-1}) \cup A_n | \\
&= & |A_1 \cup \ldots \cup A_{n-1}| + |A_n| -
|(A_1 \cup \ldots \cup A_{n-1}) \cap A_n |\\
&= & |A_1 \cup \ldots \cup A_{n-1}| + |A_n| -
|(A_1 \cap A_n) \cup  \ldots \cup (A_{n-1} \cap A_n) |
\end {eqnarray*}

Using the inductive hypothesis we can compute
unions of $n-1$ sets.
\begin{eqnarray*} |A_1 \cup \ldots \cup A_{n-1}|
&=& \sum_{k=1}^{n-1} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S} A_i | \\
& = & \sum_{k=1}^{n-1} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n \not\in S} 
| \bigcap_{i \in S} A_i |
\end {eqnarray*}
\begin{eqnarray*}
 |(A_1 \cap A_n) \cup  \ldots \cup (A_{n-1} \cap A_n) |
& =& \sum_{k=1}^{n-1} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S} (A_i\cap A_n) | \\
&=& \sum_{k=1}^{n-1} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n-1\}, |S| = k} 
| \bigcap_{i \in S\cup \{n \}} A_i | \\
& = & - \sum_{k=2}^{n} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n\in S} 
| \bigcap_{i \in S} A_i |
\end {eqnarray*}

Putting the pieces together, we have that
\begin{eqnarray*} |A_1 \cup \cdots \cup A_n | &= &
\sum_{k=1}^{n-1} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n \not\in S} 
| \bigcap_{i \in S} A_i |\\
&&+ |A_n|\\
&&+ \sum_{k=2}^{n} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k, n \in S} 
| \bigcap_{i \in S} A_i | \\
& = & \sum_{k=1}^{n} (-1)^{k+1} 
\sum_{S \subseteq \{1,\ldots,n\}, |S| = k}
 | \bigcap_{i \in S} A_i |\\
\end {eqnarray*}

\end {proof}}


\end{problems}

\end{document}
