\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}

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

\begin{document}

\tutn{8}{4/2/99}{April 3, 1999}

\section{Dovetailing}

\begin{lemma}
Union of a countable number of countable sets is countable.
\end{lemma}

This lemma is just the more general formulation of the result proved in
lecture that the set of all positive rational numbers, and the set of all
pairs of natural numbers, is countable, as illustrated in
Figure~\ref{fig:rationals}.  When ``counting'' the positive rationals, we
let the element in row $i$ column $j$ be the rational number $i/j$ for
$i,j >0$.  When counting $\naturals \times \naturals$, the pairs of
natural numbers, we start the numbering of rows and columns at zero
instead of one and let the element in row $i$, column $j$ be the pair
$(i,j)$.  Finally, if $A_0,A_1,\dots,A_n,\dots$ is a countable sequence of
countable sets, and the elements of $A_i$ are counted by the sequence
$a_{i0}, a_{i1}, \dots, a_{in},\dots$, then we let the element in row $i$,
column $j$ be $a_{ij}$.

\begin{figure}[htbp]
\centerline{\psfig{figure=/figures/rationals.eps,height=2.5in}}
\caption{\em The ordering of rationals used to prove countability.
This ordering technique is called ``dovetailing''.}
\label{fig:rationals}
\end{figure}

\emph{Quibbles}:
\begin{itemize}
\item If the set $A_i$ is finite, then $a_{ik}$ is undefined for $k\geq
      \card{A_i}$.

\item If some element occurs in more than one of the $A_i$'s, then
 elements will be repeated on the path, so the sequence of elements on the
 path will only define a \emph{surjection} from $\naturals$ to $\bigcup_i
 A_i$ rather than a bijection.
\end{itemize}

\textbf{Class Exercise}:  Resolve the quibbles.

\solution{(1) If $a_{ik}$ is undefined, skip it.  (2) Similarly, skip any
element on the path which has appeared before.}


\section{Schr\"{o}der-Bernstein Theorem}
\textbf{This section is largely taken verbatim from Handout 40: Notes on
Cardinality.}

\begin{defin}
We write $A \inj B$ to indicate that there is an injection from $A$ to
$B$.  Similarly, we write $A \sur B$ iff there is a surjection from $A$ to
$B$.  Finally, we write $A \bij B$ to indicate that there is a bijection
from $A$ to $B$.
\end{defin}

Some elementary, but important properties of these relations are:
\begin{lemma}

\begin{enumerate}

\item The relation, $\bij$, is an equivalence relation on sets.

\item The relations $\inj$ and $\sur$ are transitive.

\item If $A$ is nonempty, then $A \inj B$ iff $B \sur A$.

\end{enumerate}
\end{lemma}

We've been interpreting $A \inj B$ as ``$A$ is smaller than $B$''.  On
finite sets this definition behaves as expected -- namely $A \inj B$ iff
$\card{A} \leq \card{B}$.  In the Fall 97 Lecture 13 Notes, the
notation $\card{A} \leq \card{B}$ was extended to infinite sets to mean
precisely that $A \inj B$.  The $\inj$ notation is preferable since we
have not---and will not---define $\card{A}$ for infinite sets\footnote{It
is possible to give a technical definition of $\card{A}$ for infinite
sets, but we don't need it in 6.042.}.

Now if two \emph{finite} sets are each ``smaller than'' the other, then
indeed the sets are the same size.  In other words, the ``smaller than''
relation is \emph{symmetric} on \emph{finite} sizes of sets.  We wouldn't
be very happy with our interpretation of ``smaller than'' unless it was
symmetric on infinite sets as well.  Since our notion of ``same size'' for
infinite sets is based on bijections, we can formulate the desired
Symmetry property precisely as follows:
\begin{theorem}
(Schr\"{o}der-Bernstein) [$A \inj B$ and $B \inj A$] iff $A \bij B$.
\end{theorem}

\begin{proof}
($\Leftarrow$) If $A \bij B$ then $A \inj B$ and $A \sur B$ by
definition.  But $A \sur B$ iff $B \inj A$.

($\Rightarrow$) Suppose there is an injection $f:A \to B$ and an injection
$g:B \to A$.  We show how to piece together portions of $f$ and $g$ into a
bijection $h:A \to B$.

We'll assume for convenience that $A$ and $B$ are disjoint (see the
Exercise below).  Now we treat the elements of $A$ and $B$ as the vertices
of a bipartite digraph.  (The graphs we've considered up to now have been
finite.  This one will be infinite whenever $A$ or $B$ is infinite.)  The
edges are
\[E ::= \set{(a,f(a)) : a \in A} \union \set{(b,g(b)) : b \in B}.\]
The graph is illustrated in Figure~\ref{fig:SB}.  Two connected elements
are pictured in Figure~\ref{fig:SB} as having a zig-zag path between them.

\begin{figure}[htbp]
\centerline{\psfig{figure=/figures/sb1.eps,height=2.5in}}
\caption{\em
Sets $A$ and $B$ with injections $f:A \to B$ and $g:B \to A$.}
\label{fig:SB}
\end{figure}

Notice that because $f$ and $g$ are functions, each vertex has out-degree
one.  This implies there is a unique infinite path starting at each
vertex.  Also, a vertex has in-degree one iff it is in the range of $f$ or
$g$; otherwise it has in-degree zero.  This implies there is a unique
maximal path, which may be finite or infinite, into each vertex.  So we
can partition the vertices into four kinds of components, with no edges
between distinct components:
\begin{enumerate}
\item\label{startA} a one-way infinite simple path starting at a vertex in
$A$,

\item\label{startB} a one-way infinite simple path starting at a vertex in
$B$,

\item\label{simcyc} a simple cycle,

\item\label{2way} a simple path which is infinite in both directions (all
its vertices are degree two).

\end{enumerate}
These four possibilities are illustrated in Figure~\ref{fig:4components}.

\begin{figure}[htbp]
\centerline{\psfig{figure=/figures/sb2.eps,width=\textwidth,angle=-90}}
\caption{\em The four kinds of connected components.}
\label{fig:4components}
\end{figure} 

In case~\ref{startA} of a one-way path starting in $A$, the function $f$
defines a bijection from the $A$-vertices on the path to the $B$-vertices
on the path.  Similarly, in case~\ref{startB} of a one-way path starting
in $B$, the function $g$ defines a bijection from the $B$-vertices to the
$A$-vertices on the path.  In cases~\ref{simcyc} and~\ref{2way} of a
finite cycle or two-way infinite path, both $f$ and $g$ define bijections
between the $A$-vertices and the $B$-vertices on the path.

So we simply define $h$ component by component.  Except for
case~\ref{startB}, the function $f$ defines on bijection from $A$-vertices
to $B$-vertices in a component, so define $h(a) ::= f(a)$ when $a$ is not
in a component with a start vertex in $B$.  In case~\ref{startB}, $g$
defines a bijection from the $B$-vertices to the $A$-vertices on the path,
so its inverse $g^{-1}$ is a uniquely defined
bijection from the $A$
vertices to the $B$-vertices.  So we simply define $h(a) ::= g^{-1}(a)$
when $a$ is in a component with a start vertex in $B$.

Since $h$ is a bijection from the $A$-vertices to the $B$-vertices in each
component, and the components are disjoint, $h$ is the desired bijection
from $A$ from to $B$.
\end{proof}

\section{Cantor's Theorem}
\textbf{This section is largely taken verbatim from Handout 40: Notes on
Cardinality.}

There is a nonpictorial version of the diagonal argument from lecture
which is both simpler and more general, although maybe not as intuitive.

\begin{lemma}
For any set $S$ and function $f: S \to P(S)$, let 
\[\mbox{Diag}(f) ::= \set{s\in S: s \not\in f(s)}.\]
Then $\mbox{Diag}(f) \not \in \ran{f}$.
\end{lemma}
\begin{proof}
By contradiction.  Suppose that $\mbox{Diag}(f) \in \ran{f}$, i.e., $\mbox{Diag}(f) = f(s_0)$
for some $s_0 \in S$.  Then by definition of $\mbox{Diag}(f)$,
\[s \in f(s_0) \iff s \in \mbox{Diag}(f) \iff s \not\in f(s)\]
for all $s \in S$.  So letting $s = s_0$, we conclude
\[s_0 \in f(s_0) \iff s_0 \not\in f(s_0),\]
a contradiction.
\end{proof}

\begin{corollary}\label{nosur}
There is no surjection from $S$ to $P(S)$ for any set $S$.
\end{corollary}

\begin{defin}
A set $A$ is \emph{strictly smaller} than a set $B$, in symbols,
\[A \ll B,\]
iff $A \inj B$ and not $B \inj A$
\end{defin}

\begin{theorem}(Cantor)
For every set $S$,
\[S \ll P(S).\]
\end{theorem}
\begin{proof}
The singleton function $g: S \to P(S)$ where $g(s) ::= \set{s}$, is an
injection, so $S \inj P(S)$.  By the preceding Corollary, it is not the
case that $S \sur P(S)$, so it must not be the case that $P(S) \inj S$.
\end{proof}

For example, since $\nats \ll P(\nats) \bij \reals$, we can conclude that
$P(\nats)$ and $\reals$ are both uncountable sets.

\section{Inclusion-exclusion}

\begin {theorem}[Inclusion-Exclusion]\footnote{
By standard mathematical convention,
\[
\bigcap_{i \in \emptyset} A_i = \mbox{the universe}.
\]
So if we let the universe of discourse be
$\bigcup_i A_i$, we could reformulate the theorem in a slightly slicker
form as
\[
0 = \sum_{S \subseteq \set{1,\dots,n}}(-1)^{\card{S}+1} \card{\bigcap_{i
\in S} A_i}.
\]

\noindent Why is $\bigcap_{i \in \emptyset} A_i = \mbox{the universe}$?  Well,
remember that the assertion $\forall i \in S : P(i)$ is shorthand for
$\forall i : i\in S \Rightarrow P(i)$.  But if $S$ is empty, then the
antecedent $i\in S$ is false, so the implication is true.  That is,
$\forall i : i\in \emptyset \Rightarrow P(i)$ is true no matter what the
predicate $P$ may be.  Now by definition $\bigcap_{i \in S} A_i = \set{x
\mid \forall i \in S\, :\, x \in A_i}$.  So for $S = \emptyset$, we have
$\bigcap_{i \in \emptyset} A_i = \set{x \mid \forall i \in \emptyset\, :\, x
\in A_i} = \set{x \mid true} = \mbox{the universe}.$}

\begin{eqnarray*}
\card{\bigcup_{i=1}^n A_i} & = & \sum_{k=1}^{n} (-1)^{k+1}  \sum_{S \subseteq
    \{1,\ldots,n\}, \card{S} = k} \card{\bigcap_{i \in S} A_i}\\
   &=& \sum_{\emptyset \neq S \subseteq
\set{1,\dots,n}}(-1)^{\card{S}+1} \card{\bigcap_{i \in S} A_i}
\end{eqnarray*}
\end {theorem}


\textbf{Example}: Rosen (4th ed.), \S5.5, Example 4.

\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$.  This follows because
these polynomials can be represented as $d+1$-tuples of integers, and by
obvious dovetailing, there are only countably many such tuples.  So the
union over $d \in \naturals$ of these sets is a countable union of
countable sets, and hence there are only a countable number of such
polynomials of any degrees at all.  Now each polynomial has a finite
number of roots, so the set of algebraic numbers is a countable union
(over all the polynomials with integer coefficients) of finite sets (their
roots) and hence is also 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| \ . \]


\solution{\begin {proof}

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

\emph{Inductive Step.}  Assume that
\[
\card{A_1 \cup \ldots \cup A_{n-1}} =
\sum_{k=1}^{n-1} (-1)^{k+1} \sum_{S \subseteq \{1,\ldots,n-1\}, \card{S} = k} 
\card{\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}
