\documentclass{article}
\input{preamble.tex}
\title{Day 17}
\date{Thursday June 14, 2012}
\newcommand{\df}{\textbf}
\usepackage{enumerate}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else {\color{blue} #2} \fi }
\newcommand{\cod}{\opname{cod}}
\newcommand{\id}{\mbox{id}}
\newcommand{\fin}{f^{-1}}
\begin{document}
\maketitle
\section{Cardinality}
\begin{thm}
$\N\times\N$ is countable
\end{thm}
\begin{proof}
\Hide{3in}{
This proof can be done in several ways. If you look back to the notes a few days ago, we actually already proved this by proving that the function $f:\N\times\N$ defined by
\[
f(a,b) = 2^a(2b+1)-1
\]
Was injective and surjective.
Another way to do this proof is by a technique called \df{dovetailing}. From this method, we read off the following bijection:
\begin{align*}
g(a,b) &= a+\sum_{i=1}^{a+b} i \\
&= a + \frac{ (a+b)(a+b+1) } {2}
\end{align*}
}
\end{proof}
This is actually incredibly strong; it says that the natural numbers can code themselves...times themeselves! That is, they can code an entirely new copy of the natural numbers for each natural number. This allows for easy corollaries like:
\begin{thm}
$\Q$ is countable
\end{thm}
\begin{proof}
\Hide{2in}{
We will be a little handwavy with this result. Now, it suffices to get a bijection from $\N\times\N$ and $\Q^+$, since we can always do the thing we did between $\N$ and $\Z$ to add more. Morally speaking, $\Z\times\Z$ is cannot be smaller than $\Q$, since every rational is coded by two integers. That coding is not 1-1 however, but that seems to mean that $\Q$ can only be smaller.
To construct a bijection, one views the lattice not as $\N\times \N$ but as $\Q^+$ reading $(a,b)$ as $\frac{a}{b}$. To figure out what to send $n$ to, one does the dovetailing process and pages all the rationals it has hit. Then, if it ever encounters a point $(a,b)$ which represents the same rational as it hit, then it skips it. In this way, the function is actually well-defined; you can code it yourself!
}
\end{proof}
\begin{thm}
The set of all finite sequences from $\N$ is countable.
\end{thm}
\begin{proof}
\Hide{2in}{
There are multiple ways to prove this. We we handwave a bijection. Firstly, it suffices to biject it with $\N\times\N$, by the first theorem.
\begin{quote}
\begin{lem}
For any $n\in \N$, $\N\times\N\times \cdot \times \N$ is countable
\end{lem}
\begin{proof}
Exercise; it is an easy induction on $n\in \N$ and using the last result.
\end{proof}
\end{quote}
So, for any fixed $n$, we get a bijection between $\N$ and the set of sequences of length $\N$. Call this bijection $f_n$. Therefore, making our bijection from $\N\times\N$ to the set of all finite sequences simply by making the first coordinate specify the length of the sequence, and the second give the number of that sequence in the above specified bijection. That is, define $g$ from $\N\times \N$ to the set of all finite sequences by
\[
g(a,b) = f_a(b)
\]
}
\end{proof}
This allows us enormous flexibility. Here's the following theorem:
\begin{thm}
The countable union of countable sets is countable.
\end{thm}
\begin{proof}
\Hide{2in}{
We might as well suppose that each of the sets is infinite, and there is an infinite number. Otherwise, there's no point. Enumerate the sets $A_\alpha$ for $\alpha\in \N$.
Then, we want to prove that $\bigcup_{\alpha\in \N} A_\alpha$ is countable. We just do our dovedailing procedure as in $\Q$, where we list all the $A_i$'s on the $i$th column. We make sure we skip repeats (the sets need not be disjoint).
}
\end{proof}
\subsection{Other Bijections}
We have now that $|\N| = |\Z| = |\Q|$, among other stuff. $\R$ has not yet been in the mix. Let's do some bijections involving $\R$.
\begin{thm}
$|(0,1)| = |\R|$
\end{thm}
\begin{proof}
\Hide{2in}{
There are a few bijections that we can use.
One is tangent. The tangent is a function which given an angle returns the ratio of the $y$-coordinate of the unit circle corresponding to that angle over the $x$-coordinate. If one considers this geometrically for a moment, one realizes this must be surjective; every real number can certainly get it.
If we restrict the domain to $(-\frac{\pi}{2}, \frac{\pi}{2})$, then tangent is actually bijective. This takes more trig to prove. If you take my word for it however, this gives a bijection from $(-\frac{\pi}{2},\frac{\pi}{2})$ to $\R$. To do $(0,1)$ you do a linear transformation; we will see that later.
}
\end{proof}
\begin{thm}
$|(0,1)| = |(0,1]|$
\end{thm}
\begin{proof}
\Hide{2in}{
Consider $f:(0,1) \to (0,1]$ by
\[
f(x) = \left\{\begin{array}{l l}
\frac{1}{2^{n-1}} & \mbox{ if $x = \frac{1}{2^n}$ for some $n\in \N$} \\
x & \mbox{ otherwise}
\end{array}\right.
\]
One can check this is well defined. As an exercise, verify this is surjective and injective.
}
\end{proof}
\begin{thm}
$\R$ has the same cardinality as the set of infinite sequences of $0$'s and $1$'s
\end{thm}
\begin{proof}
\Hide{1in}{
Suffices to get a bijection from this set to $(0,1)$. Well, one can read an infinite sequence $(a_0,a_1,a_2,a_3,\ldots)$ in binary; that is, write it is
\[
a_0\left(\frac{1}{2}\right) + a_1\left(\frac{1}{4}\right) + a_2\left(\frac{1}{8}\right) + \cdots
\]
This is similar to decimal, but base two instead. One has to know this is well defined; that is it is unambiguous and defined everywhere in the domain and always ends up in $(0,1)$.
All of these things are actually false. This is not well defined. There are things that are hit twice; for instance the sequence $(0,1,1,\ldots)$ maps to the same place as $(1,0,0,\ldots)$. Similarly, the sequences do not stay in $(0,1)$. For instance, $(1,1,1,\ldots)$ goes to $1$, and $(0,0,0,\ldots)$ goes to $0$.
These mistakes, however, can all be fixed to make a bijection. The fix is similar to the last theorem where one bijects $(0,1)$ into $(0,1]$. One needs to add a new points, and then the rest of the objects adjusts. Here however, there are infinitely many ``new objects'' (all the abiguous pairs of binary sequences).
}
\end{proof}
\begin{thm}
$\wp(A)$ has the same cardinality as functions from $A$ to the set $\s{0,1}$.
\end{thm}
\begin{proof}
\Hide{1in}{
Take a subset $A$. One must now come up with a map from $A$ to $\s{0,1}$ which ``represents'' this subset. Well, how about:
\[
f_A(x) = \left\{\begin{array}{l l}
0 & \mbox{ if $x\notin A$ } \\
1 & \mbox{ if $x\in A$ }
\end{array}\right.
\]
This is injective and surjective. To see why, consider the following inverse function:
\[
g( f ) = \set{ x\in A \mid f(x) = 1 }
\]
}
\end{proof}
\begin{thm}
$\wp(\N)$ has the same cardinality as $\R$.
\end{thm}
\begin{proof}
\Hide{1cm}{
The set of infinite binary sequences is the same as functions from $\N$ to $\s{0,1}$. So this is by the previous two results.
}
\end{proof}
\end{document}