\documentclass{article}
\input{preamble.tex}
\title{Day 16}
\date{Wednesday June 13, 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}
\subsection{Bijections and Results}
\begin{dfn}
A function $f:D \to C$ is a \df{bijection} if and only if it is both injective and surjective.
\end{dfn}
One may question why a bijection is important. The following should give us an idea why.
\begin{dfn}
If $A$ is a nonempty set, the \df{identity function on $A$}, written $\id_A$, is the function from $A\to A$ with $\id_A(x) = x$ for all $x\in A$.
We say a function $f:D\to C$ is \df{invertible} if and only if there is some function $g:C\to D$ such that
\begin{itemize*}
\item $f\circ g = \id_C$\\
\item $g\circ f = \id_D$
\end{itemize*}
In which, we call $g$ the \df{inverse} of $f$
\end{dfn}
\begin{lem}
If $f:D\to C$ is invertible then $f$ is injective
\end{lem}
\begin{proof}
\Hide{1in}{
Let $f:D\to C$ be invertible, and take $a,b\in D$, supposing that $f(a)=f(b)$. We want to show $a=b$. Well, as $g$ is a function, it must take $f(a)$ and $f(b)$ to the same place. Therefore, $g(f(a)) = g(f(b))$. But, as $g$ is the inverse of $f$, $g(f(a))=a$ and $g(f(b))=b$, so $a=b$.
}
\end{proof}
\begin{lem}
If $f:D\to C$ is invertible then $f$ is surjective.
\end{lem}
\begin{proof}
\Hide{1in}{
Let $f:D\to C$ be invertible, and let $a\in C$. Let $g$ be in the inverse of $f$. Then for every $x\in C$ we must have $f(g(x)) = x$. In particular, $f(g(a)) = a$. Therefore, $a$ is attained by $f$. Therefore $f$ is surjective.
}
\end{proof}
The more surprsing result perhaps:
\begin{lem}
If $f:D\to C$ is bijective, then $f$ is invertible.
\end{lem}
\begin{proof}
\Hide{1in}{
Take $f:D\to C$ bijective. We want to construct an inverse, $g:C\to D$. Well, define $g$ as:
\[
g(x) = y \mbox{ for } y\in f^{-1}[\s{x}]
\]
That is to say, define $g(x)$ by looking at the preimage of $\s{x}$, and then mapping it to an element in this. We need to show this is a well-defined rule. Firstly, does this rule map every element of the domain $C$? Well, if $a\in C$ then $\fin[\s{a}]\neq\emptyset$ since $f$ is surjective (ie. $a$ gets hit by at least one value). Therefore, $g(a)$ is defined for every $a$.
Next we ask does everything land in the codomain. The answer is yes since for any $C'\sbs C$ we have $\fin[C']\sbs D$.
Finally we ask: is it ambiguous? Well, suppose that $g(x) = a$ and $g(x) = b$. We want to show that $a$ and $b$ are equal. As $g(x) = a$ we must have that $a\in \fin[\s{x}]$. Similarly, as $g(x) = b$ we must have $b\in \fin[\s{x}]$. Therefore, we know $f(a) = x$ and $f(b) = x$ by definition. But, by injectivity, $a=b$.
}
\end{proof}
\begin{thm}
Let $f:D\to C$. Then the following are equivalent:
\begin{enumerate}[(a)]
\item $f$ is a bijection.
\item $f$ is invertible.
\end{enumerate}
\end{thm}
\begin{proof}
The first two lemmas above give us $(b)\to(a)$. The last gives us $(a)\to (b)$.
\end{proof}
\begin{lem}
The inverse of a bijection is unique, and a bijection itself.
\end{lem}
\begin{proof}
Exercise; For the first, consider there being two inverses, and show they must be equal (similar to the proof that inverses are unique mod $p$). The second is a straightforward excise.
\end{proof}
\begin{dfn}
If $f$ is invertible, by the last lemma, $f$ has a unique inverse. Therefore, we give it a name in general: $f^{-1}$.
\end{dfn}
We also have these two results:
\begin{lem}
Suppose $f:A\to B$ and $g:B\to C$.
\begin{itemize*}
\item If $f$ and $g$ are surjections then $g\circ f$ is a surjection.
\item If $f$ and $g$ are injections then $g\circ f$ is an injections.
\end{itemize*}
\end{lem}
\begin{proof}
I will prove only the first. The second is left as an exercise.
\Hide{1in}{
Well $g\circ f : A \to C$. Take $c\in C$. Want to show that something hits it in $A$. Well, as $c\in C$ and $g$ is a surjection, there is some $b\in B$ such that $g(b) = c$. As $b\in B$, we have since $f$ is a surjection there is some $a\in A$ such that $f(a) = b$. So,
\[
(g\circ f)(a) = g(f(a)) = g(b) = c
\]
}
\end{proof}
\begin{thm}
The compositions of two bijections is a bijection.
\end{thm}
\subsection{Cardinality Definition}
What does the size of a set mean? This is a hard notion to nail down, really. It's quite easy to talk about when we can write down what the set is. For instance the sets $\s{3,4,6}$ and $\s{9,34,1}$ both have the same size.
There are 2 reasons to reasons one could argue this (perhaps more, but 2 I can think of).
\begin{enumerate*}
\item One reason is that we can count the first...1,2,3...and then count the second...1,2,3... and since we counted to the same number in each, they must be the same.
\item Another reason is because we can ``pair off' elements from one set with elements from the other. $3$ gets paired with $9$, $4$ gets paired with $34$ and $6$ gets paired with $1$. There are no elements left of either sets after this process, so they must be the same size.
\end{enumerate*}
Okay, so we want to make a correspondence between one set of objects and another...Oh! That's what a function is. Okay, so we make a set from one set of object to the other, but we want to make sure everything in the other set actually gets matched up (this is surjective) and we want to make sure we don't overcount things by pairing things up twice (this is injective).
\begin{rmk}
We make the following heurestic: Two set $A$ and $B$ have the same size if there is a bijection between $A$ and $B$. Since we already have a notion of size for finite sets, we need to make sure our new heurestic conforms to it. This will come in a bit. First let's finite some notation.
\end{rmk}
\begin{dfn}
We say that two sets $A$ and $B$ are \df{equinumerous} if there is a bijection between $A$ and $B$.
\end{dfn}
\begin{rmk}
Equinumerous is actually a real math word, but I suggest one never says it. It sounds fairly old. We will discover a better phrase later.
\end{rmk}
\begin{thm}
Equinumerousity is an equivalence relation on sets. That is:
\begin{enumerate}
\item For every set $A$, $A$ is equinumerous with itself.
\item For every set $A$ and $B$, if $A$ is equinumerous with $B$ then $B$ is equinumerous with $A$.
\item For every $A$, $B$, and $C$, if $A$ is equinumerous with $B$ and $B$ is equinumerous with $C$, then $A$ is equinumerous with $C$.
\end{enumerate}
\end{thm}
\begin{proof}
\Hide{1in}{
For the first, clearly $\id_A:A\to A$ is a bijection (if it's not clear, check this!).
For the second, if $f:A\to B$ is a bijection, then $f^{-1}:B\to A$ is a bijection, so $B$ is equinumerous with $A$.
For the third, we have already shown the compositions of two bijections is a bijection.
}
\end{proof}
\begin{rmk}
As there is no set of all sets, the last theorem doesn't even make sense. The last theorem is more of a ``morally speaking'' theorem.
\end{rmk}
\begin{dfn}
A set $A$ is \df{finite} if there is a bijection between the set and $[n]$ for some $n\in \Z^+$. Otherwise, a set is \df{infinite}.
\end{dfn}
\begin{dfn}
If $A$ is a set, we write $|A|$ to talk about the equivalence class of $A$ under the equinumerous equivalence relation. Therefore, we say
\[
|A| = |B|
\]
to say that $A$ an $B$ are equinumerous. Given $A$, the equivalence class of $A$ is called the \df{cardinality of $A$}.
Instead of saying $A$ and $B$ are equinumerous, we will instead say $A$ has the same cardinality as $B$.
In the case where $A$ is finite and $|A|=|[n]|$, we normally write $|A|=n$; this is slight abuse of notation, but is suggestive.
\end{dfn}
\begin{thm}
Suppose that $A$ and $B$ are finite sets, where there are exactly $n$ members in both $A$ and $B$. Then there is a bijection between $A$ and $B$.
\end{thm}
\begin{proof}
\Hide{2cm}{
If there is $n$ members of $A$, then there is a bijection $f:[n]\to A$. This is just counting the members of $A$. Similarly, there is a bijection $g:[n]\to B$. Taking the inverse of $f$ and composing, we get a bijection $g\circ f^{-1} : A \to B$.
}
\end{proof}
This justifies our notion of cardinality. The cardinality of finite sets are equal when the have the same number of elements as we'd expect. But, unfortunately, we don't quite have intuition about infinite sets. Are there different ``sizes'' of infinite things? Or, maybe ``infinite'' things are all identified.
\begin{thm}[Cantor 1874]
There are infinite sets which do not have the same size
\end{thm}
This is a theorem which was very revolutionary for the time, and instigated a larger program of Cantor on the infinite sets an sizes (cardinalities). We will, with time, see a proof of this theorem, But first, it will help us greatly to consider infinite sets which do have the same times as each other, to perhaps answer why some infinite sets are different than others.
\subsection{Hilbert Hotels}
We begin with story, that we are managers of the Hotel Hilbert. Over the years there have been a lot of changes in the hotel. There used to just a few rooms here and there, but now we spot an infinite supply of rooms, each numbered with a positive integer $n$.
When we finished construction, it was hard to believe that we would need them all, but there's a pretty big wedding in town, and we just filled up! We turned on the No Vacancy sign. Here at the Hotel Hilbert, however, that sign does not mean that we cannot give you a room.
\begin{question}
A guest comes into our hotel and wants a room. How should we accommodate them?
\end{question}
\begin{ans}
\Hide{1cm}{
Well, we can shift everyone down one room. So move the person in room number $1$ to room number $2$, $2$ to $3$, etc. Then we can put our new guest in room $1$ because it's open!
}
\end{ans}
\begin{question}
Uh-oh. There's another big wedding in town, and another infinite supply of guests is looking for rooms. Each is wearing a shirt with a different natural number on it. Can we accommodate them?
\end{question}
\begin{ans}
\Hide{1cm}{
Of course! We will just have to do some rearranging. We will say that if you are in room $i$, you have to move to room $2i$. This is quite a long walk for some people, but that's okay. They don't mind. After this, we have all the odd rooms completely open as everyone is now staying in an even room!
}
\end{ans}
\begin{question}
Okay, one wedding was fine. Two weddings was manageable. But now there are infinitely many weddings in town! Each wedding is assigned a distinct natural number by the city's wedding planning committee. They all want to stay in our hotel. Can we accommodate them?
\end{question}
\begin{ans}
\Hide{1cm}{
No problem! We'll just put the existing people to rooms numbered with powers of $2$, then the first wedding in rooms with powers of $3$, then the next in rooms with powers of $5$, etc, the $n$th in rooms with powers of $p$ where $p$ is the $n$th prime, and so on. This leaves a lot of rooms empty, but that's okay: infinitely many rooms allows us to be a little less efficient.
}
\end{ans}
\section{Countability}
So, we like counting things using the numbers that, well, we use to count things: $\N$.
\begin{dfn}
A set $A$ is called \df{countable} if and only if it is finite or there is a bijection between the set and $\N$.
\end{dfn}
Some people (like people who index their arrays starting at $1$ for some reason) count things using $\Z^+$. We first show that if you can count a set using one then you can count a set using the other by showing that you can count one using the other.
\begin{thm}
\[|\Z^+| = |\N|\]
\end{thm}
\begin{proof}
Simply define $f:\N \to \Z^+$ by
\[
f(x) = x+1
\]
This is clearly surjective; if $y\in \Z^+$, then $y$ is a positive natural, so $y-1$ is certainly a natural and $f(y-1) = y$. Similarly, if $x+1 = y+1$ then $x=y$.
\end{proof}
This really corresponds to our first Hilbert Hotel Problem. We shift all the guests up by one, and then add the new one in the room get gets emptied.
\begin{thm}
\[
|\Z| = |\N|
\]
\end{thm}
\begin{proof}
We define $g:\Z \to \N$ by
\[
g(n) = \left\{\begin{array}{l l}
-2n & \mbox{if } n\leq 0 \\
2n-1 & \mbox{if } n > 0
\end{array}\right.
\]
Clearly $g$ is bijection. For surjective, if you wanted to hit $m$, if $m$ is even then $m=2k$ for some $k$, and $g(-k) = -2k = m$. If $m$ is odd then $m=2k-1$ for some $k\in \N$, and $g(k) = 2k-1$.
For injective, let $a,b\in \Z$ and suppose $g(a) = g(b)$. Clearly if $a,b\leq 0$ or $a,b>0$. then $a=b$. So, suffices to only check when they're different. WLOG, $a\leq 0$ and $b > 0$. But then $g(a)$ is even and $g(b)$ is odd, which contradicts $g(a)=g(b)$.
\end{proof}
This corresponds to the second hotel problem; I have the people who were already there (the non-negatives) and the new people (the negatives) and somehow I have to fit them in their rooms!
\begin{thm}
\[
|\N\times\N| = |\N|
\]
\end{thm}
\begin{proof}
This one is tricky. What should we do?
\end{proof}
\end{document}