%!TEX root = proofs+concepts.tex


 
 \chapter{Cardinality} \label{CardinalityChap}
 
\begin{quote}
\it Our knowledge can only be finite, 
\\ while our ignorance must necessarily be infinite.
\par\raggedleft \small\rm\sf
Karl Popper (1902--1994), Austrian-born British philosopher
\\ \emph{Conjectures and Refutations: The Growth of Scientific Knowledge}
\end{quote}

\section{Definition and basic properties} \label{BasicCardinalitySect}
 
Informally, the \emph{cardinality} of a set is the number of elements that it contains. (This was mentioned in \cref{InformalCardinalityDefn}.)
 
 \begin{exers} \label{WhatCardinalityEx}
 What is the cardinality of each of these sets?
\\ (\!\emph{You do \emph{not} need to show your work or justify your answers.})
\begin{tasks}(2)
\task\fixtask \label{WhatCardinalityEx-1234}%
$\#\{1,2,3,4\} =$
\task\fixtask \label{WhatCardinalityEx-aeiou}%
$\#\{\var{a},\var{e},\var{i},\var{o},\var{u}\} =$
\task\fixtask \label{WhatCardinalityEx-alberta}%
$\#\{\var{a},\var{l},\var{b},\var{e},\var{r},\var{t},\var{a}\} =$
\task\fixtask \label{WhatCardinalityEx-empty}%
$\#\emptyset=$
\task\fixtask \label{WhatCardinalityEx-(empty)}%
$\#\{\emptyset\} =$
\task\fixtask \label{WhatCardinalityEx-not7}%
 $\#\bigl\{ k \in \{\, 1,2,\ldots,10 \} \mathrel{\big|} k \neq 7 \,\bigr\} =$
%\task\fixtask $\#\bigl\{ k \in \{\, 1,2,\ldots,10 \} \mathrel{\big|} \mbox{$k$ is even} \,\bigr\} =$
\end{tasks}
\end{exers}

An informal understanding of cardinality is not sufficient in advanced mathematics courses, so we need to study this idea more thoroughly.

\begin{eg}
The cardinality of $\{\var{a}, \var{b}, \var{c}\}$ is~$3$.
 Children learn to verify this by counting: 
 	$$ \text{$1$ (for~$\var{a}$), \quad $2$ (for $\var{b}$), \quad  $3$ (for~$\var{c}$).} $$
 They are taught to assign exactly one number to each element of the set (and not skip any numbers as they count up).
 Mathematicians express this idea in a more sophisticated way: if we define a function $f \colon \{\var{a},\var{b},\var{c}\} \to \{1,2,3\}$ by
 	$$ f(\var{a}) = 1, \ f(\var{b}) = 2, \ f(\var{c}) = 3 ,$$
then $f$ is a bijection. 
\end{eg}

In general, if a set~$A$ has $n$ elements, then counting the elements one-by-one defines a bijection from~$A$ to $\{1,2,3,\ldots,n\}$. 
This observation leads to the following official definition.
 
 \begin{defn} \label{CardDefn} \ 
 \begin{enumerate}
 \item \label{CardDefn-defn}
 Let $A$ be a set and $n$~be a natural number. We say that the \define{cardinality} of~$A$ is~$n$ (and write $\# A = n$)%
 \nindex{$\#$}
 iff there is a bijection from~$A$ to $\{1,2,3,\ldots,n\}$.
 \item A set~$A$ is \define[finite set]{finite} iff there is some $n \in \natural$, such that $\# A = n$. 
 \item A set~$A$ is \define[infinite set]{infinite} iff it is \emph{not} finite.
  \end{enumerate}
 \end{defn}

\begin{rems} \label{FiniteRem} \ 
\noprelistbreak
	\begin{enumerate}
	\item  \label{FiniteRem-N}
	Not all sets are finite. For example, $\natural$ is infinite (see \fullcref{FinalCardEx}{NInfinite}).
	\item \label{FiniteRem-subset}
	We will see in \cref{SubsetOfFiniteIsFinite} that every subset of a finite set is finite.
	\end{enumerate}
\end{rems}

Since the definition of $\#A$ is based on bijections, every proof about cardinality will rely on facts about bijections.

\begin{eg} \label{Card(1..n)}
Show $\#\{1,2,3,\ldots,n\} = n$, for every $n \in \natural$.
\end{eg}

\begin{scratchwork}
The definition of cardinality tells us that if $A$ is any set, and we need to show $\#A = n$, then we need to find a bijection from~$A$ to $\{1,2,3,\ldots,n\}$. In this problem, we have $A = \{1,2,3,\ldots,n\}$. Therefore, we need to find a bijection from $\{1,2,3,\ldots,n\}$ to $\{1,2,3,\ldots,n\}$. Thus, we need to find a bijection from a set to itself. \Cref{IdIsBij} tells us that the identity map is such a function.
\end{scratchwork}

\begin{proof}
From \cref{IdIsBij}, we know that the identity map $\Id_{\{1,2,\ldots,n\}}$ is a bijection from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n\}$, so $\#\{1,2,\ldots,n\} = n$. 
\end{proof}

\begin{proof}[Alternate proof]
Define $f \colon \{1,2,3,\ldots,n\} \to \{1,2,3,\ldots,n\}$ by $f(k) = k$. 

We claim that $f$~is a bijection. In other words, we claim that $f$~is one-to-one and onto.

\begin{itemize} \leftskip=0.75in 
\item[\hskip-0.5in(one-to-one)] Given $i_1,i_2 \in \{1,2,3,\ldots,n\}$, such that $f(i_1) = f(i_2)$, we have $i_1 = i_2$. So $f$ is one-to-one.
\item[(onto)] Given $j \in \{1,2,3,\ldots,n\}$, let $i = j$. Then $f(i) = i = j$. So $f$ is onto.
\end{itemize}
Since $f$ is both one-to-one and onto, it is a bijection. This completes the proof of the claim.

Therefore, there is a bijection (namely,~$f$) from $\{1,2,3,\ldots,n\}$ to $\{1,2,3,\ldots,n\}$. Hence, $\# \{1,2,3,\ldots,n\} = n$.
\end{proof}

\begin{rem} \label{Card(empty)}
Since the empty set has no elements, its cardinality should be~$0$. Although it may not be obvious, \cref{CardDefn} does agree with this observation. To verify this, it is important to realize that, for any $n \in \natural$, the notation $\{1,2,\ldots,n\}$ is just another name for the set $\{\, i \in \natural \mid 1 \le i \le n \,\}$. In particular, if $n = 0$, then
	\begin{align*}
	\{1,2,\ldots,n\} 
	= \{\, i \in \natural \mid 1 \le i \le n \,\} 
	=  \{\, i \in \natural \mid 1 \le i \le 0 \,\} 
	= \emptyset
	. \end{align*}
Therefore, letting $n = 0$ in \cref{Card(1..n)} tells us that $\#\emptyset = 0$, as expected.
\end{rem}

The definition of $\#A$ specifies that there is a bijection from $A$ to $\{1,2,3,\ldots,n\}$. The following exercise shows there is no harm if you choose to have the bijection go the other way.
  
\begin{exer} \label{CardInverseEx}
Let $A$ be a set. For $n \in \natural$, show $\#A = n$ iff there is a bijection from $\{1,2,3,\ldots,n\}$ to~$A$.
 \hint{Use \fullcref{InverseUniqueExers}{bij}.}
\end{exer}

Bijections can be used to show that two sets have the same cardinality, without knowing how many elements they have.

 \begin{eg}
 In the society \var{Married} of \cref{MarriedEg} (where every man is married to a woman, and vice-versa), it is clear that there must be exactly the same number of men and women. (If there were more women than men, then either some woman would be unmarried, or more than one woman would have to be married to the same man. Similarly, if there were more men than women.) This is true, even though we have no idea how many women or men there are in the society. All we know is that however many women there are is exactly the same as the number of men.
\end{eg}

This observation is formalized in the following \namecref{CardA=CardBbijection}.

\begin{prop} \label{CardA=CardBbijection}
Suppose $A$ and $B$ are finite sets.
Then $\#A = \#B$ if and only if there is a bijection from~$A$ to~$B$.
\end{prop}

\begin{proof}
($\Rightarrow$) Let $n$ be the cardinality of~$A$. By definition, this means 
	$$ \text{there is a bijection $f \colon A \to \{1,2,\ldots,n\}$} .$$
By assumption, $n$~is also the cardinality of~$B$, so 
	$$ \text{there is also a bijection $g \colon B \to  \{1,2,\ldots,n\} $} .$$
The inverse of a bijection is a bijection (see \fullcref{InverseUniqueExers}{bij}), and the composition of bijections is a bijection (see \fullcref{BijectionComposeExer}{gf}), so $g^{-1} \compose f$ is a bijection from~$A$ to~$B$.

\smallskip

($\Leftarrow$) We leave this as an exercise. 
\end{proof}

\begin{exer} \label{Prove CardA=CardBbijectionEx}
Prove \cref{CardA=CardBbijection}($\Leftarrow$).
\hint{Use \fullcref{BijectionComposeExer}{gf}.}
\end{exer}

\begin{exers} \label{Card(AxB)Ex}
\ %Assume $B$ is a finite set.
\noprelistbreak
\begin{problist}
\item \label{Card(AxB)Ex-A1=A2}
 Show that if $\# A_1 = \#A_2$, then $\#(A_1 \times B) = \#(A_2 \times B)$.
\\ \hint{If $f \colon A_1 \to A_2$ is a bijection, define $g \colon A_1 \times B \to A_2 \times B$ by $g(a_1,b) = \bigl( f(a_1),b \bigr)$.}
 \item \label{Card(AxB)Ex-single}
 Show that if $\{a_0\}$ is any set with only one element, then $\#\bigl(\{a_0\} \times B \bigr) = \#B$.
\\ \hint{Define $f \colon B \to \{a_0\} \times B$ by $f(b) = (a_0,b)$.}
\item \label{Card(AxB)Ex-image}
Suppose $f \colon A \to B$ is one-to-one, and $X \subset A$. Show $\#f(X) = \#X$.
 \end{problist}
\end{exers}

\begin{eg}
In elementary school, we learn that if Alice has $m$~apples and Bob has $n$~apples, then the sum $m + n$ is the total number of apples that the two of them have. However, this simple example assumes that Alice and Bob are not {sharing} any of the apples; the set of Alice's apples must be \emph{disjoint} from the set of Bob's apples.
\end{eg}

The following result generalizes this example.

\begin{prop} \label{|AcupB|}
If $A$ and~$B$ are disjoint finite sets, then 
	$$ \# (A \cup B) = \#A + \# B .$$
\end{prop}

\begin{proof}
Let $m = \#A$ and $n = \# B$. Then there exist bijections
	$$ \text{$f \colon \{1,2,\ldots,m\} \to A$ \quad and \quad $g \colon \{1,2,\ldots,n\} \to B$.} $$
Define a function $h \colon \{1,2,\ldots,m+n\} \to (A \cup B)$ by
	$$ h(k) = \begin{cases}
	\hfil f(k) & \text{if $k \le m$} \\
	g(k-m) & \text{if $k > m$}
	\end{cases} $$
(Notice that if $k \in \{1,2,\ldots,m+n\}$, and $k > m$, then $m + 1 \le k \le m+n$, so $1 \le k - m \le n$; therefore, $k -m$ is in the domain of~$g$, so the expression $g(k-m)$ makes sense.)

To complete the proof, it suffices to show that $h$~is a bijection; thus, we we need only show that $h$ is one-to-one and onto.

(onto) Given $y \in A \cup B$, we have either $y \in A$ or $y \in B$, and we consider these two possibilities as separate cases.
	\begin{enumerate}
	\item Suppose $y \in A$. Since $f$ is onto, there is some $k \in \{1,2,\ldots,m\}$ with $f(k) = y$. Then, because $k \le m$, we have
		$$ h(k) = f(k) = y .$$
	\item Suppose $y \in B$. Since $g$ is onto, there is some $k \in \{1,2,\ldots,n\}$ with $g(k) = y$. Then $k + m \in \{1,2,\ldots,m+n\}$ and $k+m > m$, so
		$$ h(k+m) = g \bigl( (k+m) - m \bigr) = g(k) = y .$$
	\end{enumerate}
Since $y$ is an arbitrary element of $A \cup B$, we conclude that $h$~is onto.

(one-to-one) We leave this as an exercise.
\end{proof}

\begin{exer} \label{|AcupB|hEx}
Show that the function $h$ defined in the proof of \cref{|AcupB|} is one-to-one.
\end{exer}

\begin{exers} \label{CardinalitySubsetExers}
Assume $B$ is a finite set.
\begin{enumerate}
\item \label{CardinalitySubsetExers-B/b}
For all $b \in B$, show that $\# \bigl( B \sm \{b\} \bigr) = \#B - 1$.
\item \label{CardinalitySubsetExers-subset}
 Show that if $A \subset B$, then $\#A \le \#B$.
 \hint{$\#B = \#A + \#(B \sm A) \ge \#A$.}
 \item  \label{CardinalitySubsetExers-disjoint}
Show that if $A_1$ and~$A_2$ are disjoint subsets of~$B$, then $\#A_1 + \#A_2 \le \#B$.
 \item (harder)  \label{CardinalitySubsetExers-harder}
Assume $B \neq \emptyset$. Show that if $S \subset \power(B)$, and no two elements of~$S$ are disjoint, then $\#S \le \frac{1}{2} \, \#\power(B)$.
 \\ \hint{You may assume (without proof) that $\power(B)$ is finite. If $X \in S$, then $\comp{X} \notin S$.}
 \item \label{CardinalitySubsetExers-empty}
Show $\#B = 0$ if and only if $B = \emptyset$.
 \end{enumerate}
\end{exers}

The following generalization of \cref{|AcupB|} applies to the union of any number of sets, not just two. 

\begin{exer} \label{|DisjUnion|}
 If $A_1,A_2,\ldots,A_n$ are pairwise-disjoint finite sets, then 
	$$ \#(A_1 \cup A_2 \cup \cdots \cup A_n) = \#A_1 + \#A_2 + \cdots + \#A_n .$$
\hint{Induct on~$n$, using \cref{|AcupB|,PairDisjUnionEx}.}
\end{exer}

It was pointed out in \cref{Card(AxB)Rem} that if $A$ and~$B$ are finite sets, then $\#(A \times B) = \#A \cdot \#B$. We can now prove this, after using \cref{|DisjUnion|} to solve the following exercise:

\begin{exer}   \label{Card(AxB)disjoint}
 Suppose $A_1,A_2,\ldots,A_m$ are pairwise-disjoint finite sets. Show that if $A = A_1 \cup \cdots \cup A_m$, then 
 	$$\#( A \times B) = \#(A_1 \times B) +  \#(A_2 \times B) + \cdots +  \#(A_m \times B)  .$$
\hint{The sets $A_i \times B$ are pairwise-disjoint, and their union is $A \times B$.}
\end{exer} 

\begin{thm} \label{Card(AxB)Thm}
For any finite sets $A$ and~$B$, we have 
	$$\#(A \times B) = \#A \cdot \#B .$$
\end{thm}

\begin{proof}
Let $m = \#A$. Then there is no harm in assuming $A = \{1,2,\ldots,m\}$ (see \fullcref{Card(AxB)Ex}{A1=A2}). Therefore
	$$ A = \{1\} \cup \{2\} \cup \cdots \cup \{m\} ,$$
and the sets $\{1\} , \{2\} , \cdots , \{m\}$ are pairwise-disjoint, so
	\begin{align*}
	\#(A \times B)
	&= \#\bigl( \{1\} \times B\bigr) +  \#\bigl( \{2\} \times B \bigr) + \cdots +  \#\bigl( \{m\} \times B \bigr) 
	&& \text{(\cref{Card(AxB)disjoint})}
	\\&= \#B +   \#B + \cdots +   \#B \qquad \text{($m$ summands)}
	&& \text{(\fullcref{Card(AxB)Ex}{single})}
	\\&= m \cdot \#B
	\\& = \#A \cdot \#B
	. \qedhere \end{align*}
\end{proof}

\begin{exers} \label{CardinalityExers} 
Suppose $A$ and $B$ are finite sets, and $m,n \in \natural$. Prove:
\begin{enumerate}
\item \label{CardinalityExers-onetooneN} 
If $m \le n$, then there exists a one-to-one function $f \colon \{1,2,\ldots,m\} \to \{1,2,\ldots,n\}$.
\item \label{CardinalityExers-onetoone} 
 If $\#A \le \#B$, then there exists a one-to-one function $f \colon A \to B$.
\\ \hint{Use the preceding exercise.}
\item \label{CardinalityExers-ontoN} 
If $m \ge n > 0$, then there exists an onto function $f \colon \{1,2,\ldots,m\}  \to \{1,2,\ldots,n\}$.
 \item \label{CardinalityExers-onto} 
 If $A$ and~$B$ are nonempty, and $\#A \ge \#B$, then there exists an onto function $f \colon A \to B$.
\hint{Use the preceding exercise.}
\end{enumerate}
\end{exers}

The converses of the exercises in~\pref{CardinalityExers} are true, and important. They will be discussed in \cref{PigeonholeSect}.

We end % !!!
the \lcnamecref{BasicCardinalitySect} with a basic fact that may seem to be obvious (and was mentioned in \fullcref{FiniteRem}{subset}), but that would be difficult or impossible to prove without using induction.

\begin{thm} \label{SubsetOfFiniteIsFinite}
Every subset of any finite set is finite.
\end{thm}

\begin{proof}
Define $P(n)$ to be the assertion
	$$ \text{If $A$ is any set with $\#A = n$, then every subset of~$A$ is finite.} $$

\smallskip
 (i) \emph{Base case.} Assume $n = 0$, and let $B$ be any subset of~$A$. Now $\#A = n = 0$, so $A = \emptyset$. Since the only subset of the empty set is the empty set, we have $B = \emptyset$. Hence $\#B = 0$, so $B$ is finite.
 
 \smallskip

 (ii) \emph{Induction step.} Assume $n \ge 1$, and that $P(n-1)$ is true, and let $B$ be any subset of~$A$. We may assume $B$ is a proper subset of~$A$. (Otherwise, we have $B = A$, so $\#B = \#A = n$, which means that $B$ is finite.) Thus, there exists $a \in A$, such that $a \notin B$. Let $A' = A \sm \{a\}$. Then $\#A' = n - 1$, so the induction hypothesis tells us that every subset of~$A'$ is finite. Since $B \subset A'$, we conclude that $B$ is finite.
\end{proof}




\section{The Pigeonhole Principle} \label{PigeonholeSect}

If a mail carrier has $m$~letters to distribute among $n$~mailboxes (or ``pigeonholes''), and $m > n$, then it is clear that at least one of the mailboxes will have to get more than one letter. This important observation is known as the ``Pigeonhole Principle\rlap.''  (See \cref{PigeonholePfEx} for the proof.) In the language of sets, it can be stated as follows.

\begin{prop}[(Pigeonhole Principle)] \label{PigeonholePrinciple}  \index{Pigeonhole Principle}
Let $B$ and $A_1,A_2,\ldots,A_n$ be finite sets. If
	$$ B \subset A_1 \cup A_2 \cup \ldots \cup A_n ,$$
and $\#B > n$, then $\#A_i \ge 2$, for some~$i$.
\end{prop}

 Here are a few of the many applications of the Pigeonhole Principle. In these real-world examples, our explanations will be a bit informal.
 
 \begin{eg} \label{socks4colours}
 Bob's sock drawer has many, many socks in it, and they come in 4 colours. Unfortunately, the light in his room has burned out, so he cannot see anything.  How many socks should he grab from the drawer, so that he can be sure at least two of them are of the same colour?
 \end{eg}
 
 \begin{solution}
 Bob should grab 5 (or more) socks.
 
To see this, note, first, that taking 4 socks may not be enough: If Bob grabs only 4 socks, it is possible that he has one sock of each of the 4 different colours. Then he would not have two socks of the same colour.
 
 Now suppose Bob grabs (at least) 5~socks. He can sort them into $4$~piles, by colour. Since $5 > 4$, one of the piles must have more than one sock. So there are (at least) $2$ socks of the same colour.
% Now suppose Bob grabs (at least) 5~socks. We can define a function
% 	$$ f \colon \{\, \text{socks Bob grabbed} \,\} \to \{\, \text{colours of Bob's socks} \,\} $$
%by letting $f(s)$ be the colour of sock~$s$. Since the number of socks that Bob grabbed is greater than the number of colours of socks, the Pigeonhole Principle tells us that $f$ is not one-to-one. This means there are two different socks $s_1$ and~$s_2$, such that $f(s_1) = f(s_2)$. In other words, the socks $s_1$ and~$s_2$ have the same colour. Thus, two (or more) of the socks that Bob grabbed are of the same colour. 
 \end{solution}
 
\begin{eg}
If you pick $50$ numbers from $1$ to~$98$, then it is guaranteed that two of them will add up to exactly $99$.
\end{eg}

\begin{solution}
The numbers from $1$ to~$98$ can be divided into $49$ pigeonholes:
	$$ \{1,98\}, \  \{2,97\}, \ \{3,96\}, \ \ldots, \ \{49,50\} . $$
(So two different numbers $x$ and~$y$ are in the same pigeonhole iff $x + y = 99$.) Since $50 > 49$, two of the numbers we chose must be in the same pigeonhole.
Then the sum of these two numbers is exactly $99$.
\end{solution}

\begin{eg}
If you pick $5$ points on the surface of a (spherical) orange, then there is always a way to cut the orange exactly in half, such that at least $4$~of your points are in the same half. (We assume any point that is exactly on the cut is considered to belong to both halves.)
\end{eg}

\begin{solution}
Any two of the points will lie on a great circle of the sphere, so we can cut the orange so that $2$ of the points are exactly on the cut.  The other $3$ points are distributed in some way among the two halves of the orange. By the Pigeonhole Principle, at least two of those three points are in the same half. Then that half contains the $2$~points on the cut, plus these additional $2$~points, for a total of (at least) $4$ of the points you picked.
\end{solution}

\begin{exers} \label{PigeonholeRealWorld} \ 
\begin{problist} 

\item  \label{PigeonholeRealWorld-hockey}
There are ten people in a skating rink, playing hockey. Explain how you know that two of them were born on the same day of the week.

 \item \label{PigeonholeRealWorld-Bday}
 If there are $400$ students in an elementary school, explain how you know that (at least) two of them have the same birthday.

 \item  \label{PigeonholeRealWorld-initials}
If there are $700$ employees at a company, explain how you know that there are two of them with the same initials. (That is, their first names start with the same letter, and their last names start with the same letter.)

\item  \label{PigeonholeRealWorld-hair}
It is known that:
	\begin{itemize}
	\item No one has more than $300,000$ hairs on their head.
	\item More than a million people live in Calgary.
	\end{itemize}
Show that there are two people in Calgary who have exactly the same number of hairs on their heads.

\end{problist}
\end{exers}

In addition to the above real-world examples, the Pigeonhole Principle has important applications in theoretical mathematics. % (and other areas of science).

\begin{cor} \label{Cardinality:OneToOneVsOntoThm}
Suppose $A$ and~$B$ are finite sets. %% don't assume $A$ is finite? !!!
\begin{enumerate}
\item \label{Cardinality:OneToOneVsOntoThm-11} 
If there exists a one-to-one function $f \colon A \to B$, then $\#A \le \#B$.
\item \label{Cardinality:OneToOneVsOntoThm-onto} 
If there exists an onto function $f \colon A \to B$, then $\#A \ge \#B$.
\end{enumerate}
\end{cor}

\begin{proof}
Let $m = \#A$ and $n = \#B$.

\pref{Cardinality:OneToOneVsOntoThm-11}
Suppose $f \colon A \to B$ is one-to-one, and $m > n$. Assume without loss of generality that $B = \{1,2,\ldots,n\}$, so we may let
	$$ \text{$A_i = f^{-1}(i)$ \ for $i = 1,2,\ldots,n$} . $$
For any $a \in A$, we have $a \in f^{-1} \bigl( f(a) \bigr) = A_{f(a)}$, so $a \in A_1 \cup A_2 \cup \cdots \cup A_n$. Since $a$ is an arbitrary element of~$A$, this implies $A \subset A_1 \cup A_2 \cup \ldots \cup A_n$. Because $\#A = m > n$, we conclude that $\#A_i \ge 2$ for some~$i$. This means $\#f^{-1}(i) > 1$, which contradicts the fact that $f$~is one-to-one.

\pref{Cardinality:OneToOneVsOntoThm-onto} Suppose $f\colon A \to B$ is onto, and $m < n$.
There is no harm in assuming $A = \{1,2,\ldots,m\}$, and then we may let
	$$B_i = \{f(i)\} $$
for $i = 1,2,\ldots,m$. Since $f$~is onto, we know, for any $b \in B$, there is some $i \in A$, such that $f(i) = b$. This means $b \in B_i$; hence,  $b \in B_1 \cup B_2 \cup \cdots \cup B_m$. Since $b$ is an arbitrary element of~$B$, this implies $B \subset B_1 \cup B_2 \cup \ldots \cup B_m$. Because $\#B = n > m$, we conclude that $\#B_i \ge 2$ for some~$i$. This contradicts the fact that $\#B_i = 1$ (because $B_i =  \{f(i)\}$ has only one element).
\end{proof}

\begin{rem}
Instead of \cref{PigeonholePrinciple}, many mathematicians consider the contrapositive of \fullcref{Cardinality:OneToOneVsOntoThm}{11} to be the Pigeonhole Principle:
	\begin{quotation}
	\em If $\#A > \#B$, then there does not exist a one-to-one function from~$A$ to~$B$.
	\end{quotation}
\end{rem}

\begin{exers} \label{FinalCardEx} \ 
\begin{enumerate}
 
 \item  \label{FinalCardEx-samesum}
Suppose $A$ is a set of $10$ natural numbers between $1$ and~$100$ (inclusive). Show that two different subsets of~$A$ have the same sum. For example, if 
 	$$ A = \{ 2, 6, 13, 30, 45, 59, 65, 82, 88, 97 \} ,$$
then the subsets $\{ 6, 13, 45, 65\}$ and $\{ 2, 30, 97\}$ both add up to $129$.
\hint{Compare the answers to two questions: How many subsets of~$A$ are there? Since there are only $10$ elements of~$A$, and all of them are $\le 100$, how many different possible sums are there?}

\item  \label{FinalCardEx-triangle}
Show that if you put 5 points into an equilateral triangle of side length 2~cm, then there are two of the points that are no more than 1~cm apart.
\\ \hint{Divide the triangle into $4$ equilateral triangle of side length 1~cm.}

\item \label{FinalCardEx-repunit}
The numbers $1$, $11$, $111$, $1111$, etc. are called \define[repunit]{repunits}. (Their decimal representation consists entirely of~$1$'s.)
Show that some repunit is divisible by $2017$.
\\ \hint{If $n \times 10^k$ is divisible by $2017$, for some $k \in \natural$, then $n$~is divisible by $2017$. \emph{Why?}}

 \item \label{FinalCardEx-well}
 Show that $\# A$ is well-defined. That is, if $\#A = m$ and $\#A = n$, for some $m,n \in \natural$, then $m = n$.
 \hint{Apply \cref{Cardinality:OneToOneVsOntoThm} with $B = A$.}
 
\item \label{FinalCardEx-NInfinite} 
Show $\natural$ is infinite.
 \hint{Proof by contradiction. Apply \fullcref{Cardinality:OneToOneVsOntoThm}{11}.}

\end{enumerate}
\end{exers}
 
 \begin{rem} \label{GeneralPigeon}
 Here are two generalizations of the Pigeonhole Principle that are often useful.
 	\begin{enumerate}
	\item \label{GeneralPigeon-k}
	If a mail carrier has $m$~letters to distribute among $n$~mailboxes, and $m > kn$, then at least one of the mailboxes has to get more than $k$~letters. 
	\item \label{GeneralPigeon-ki}
	Suppose a mail carrier has $m$~letters to distribute among $n$~mailboxes. If 
		$$ \text{$k_1,k_2,\ldots,k_n \in \natural$ \ and \ $m > k_1 + k_2 + \cdots + k_n$} ,$$
	then there must be some~$i$, such that the $i$th mailbox gets more than $k_i$~letters. 
	\end{enumerate}
\end{rem}

\begin{exer} \label{StateGeneralPigeon}
State \pref{GeneralPigeon-k} and \pref{GeneralPigeon-ki} of \cref{GeneralPigeon} analogously to:
\noprelistbreak
	\begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}
	\item \label{StateGeneralPigeon-set}
	\cref{PigeonholePrinciple} (that is, in terms of a set~$B$ contained in $A_1 \cup A_2 \cup \cdots \cup A_n$),
	and
	\item \label{StateGeneralPigeon-func}
	\fullcref{Cardinality:OneToOneVsOntoThm}{11} (that is, in terms of a function $f \colon A \to B$).
	\end{enumerate}
\end{exer}

\begin{exer} \label{MorePigeonholeEx}
	\begin{enumerate}
	
	\item \label{MorePigeonholeEx-hair}
Strengthen the conclusion of \fullcref{PigeonholeRealWorld}{hair}: show there is a collection of 4~people in Calgary who all have exactly the same number of hairs on their head.
	
	\item \label{MorePigeonholeEx-Bobsocks}
As in \cref{socks4colours}, Bob's sock drawer has many, many socks in it, and they come in 4~colours. How many socks should he grab from the drawer, so that he can be sure at least~12 of them are of the same colour?
	
	\item \label{MorePigeonholeEx-Bettysocks}
Betty's sock drawer has 6~blue socks, 10~red socks, 14~white socks, and 18~black socks. How many socks should she grab from the drawer, so that she can be sure at least~12 of them are of the same colour?

	\end{enumerate}
 \end{exer}





\section{Cardinality of a union} \label{|Union|Sect}
\nobreak % (shouldn't need to say this) !!!
We know that if $A$ and~$B$ are disjoint, then the cardinality of $A \cup B$ is $\#A + \#B$. Here is a formula that works even when the sets are not disjoint:

\begin{prop} \label{card(AcupB)}
For any finite sets $A$ and~$B$, we have
	$$ \#(A \cup B) = \#A + \#B - \#(A \cap B) .$$
\end{prop}

\begin{proof}
From \cref{Venn3parts}, we know that $A \sm B$, $B \sm A$, and $A \cap B$ are pairwise-disjoint, and that their union is $A\cup B$, so
	$$ \#(A \sm B) + \#(B \sm A) + \# (A \cap B)
	= \# \bigl( (A \sm B) \cup (B \sm A) \cup (A \cap B)  \bigr)
	= \# (A \cup B) .$$
Also, we have
	\begin{align*}
	\#A
	 &= \# \bigl( (A \sm B) \cup (A \cap B) \bigr)   && \text{(\fullcref{DeMorganSetEx}{partition})}
	 \\&= 	 \#(A \sm B) + \# (A \cap B) && \text{(\fullcref{DisjointEx}{AsmBvsAcapB})}
	 . \end{align*}
Similarly, we have
	$$  \# B = \#(B \sm A) + \# (A \cap B) .$$
Therefore
	\begin{align*}
	\#A + \#B
	&= \bigl( \#(A \sm B) + \# (A \cap B)  \bigr) + \bigl(  \#(B \sm A) + \# (A \cap B) \bigr)
	\\&=  \#(A \sm B) + \#(B \sm A) + 2\# (A \cap B)
	\\&=  \#(A \cup B) + \# (A \cap B)
	.  \end{align*}
%	\begin{align*}
%	\#A + \#B - \#(A \cap B)
%	&= \bigl( \#(A \sm B) + \# (A \cap B)  \bigr) + \bigl(  \#(B \sm A) + \# (A \cap B) \bigr) - \#(A \cap B)
%	\\&=  \#(A \sm B) + \#(B \sm A) + \# (A \cap B)
%	\\&= \#(A \cup B) 
%	. \qedhere \end{align*}
The desired conclusion is obtained by subtracting $\# (A \cap B)$ from both sides.
\end{proof}

\begin{figure}[h]
\begin{center}
\includegraphics{PDF/InclExcl2.pdf}
\end{center}
\caption{The sum $\#A + \#B$ includes all the elements of $A \cup B$, but counts the elements of $A \cap B$ twice, so $\#A + \#B = \#(A \cup B) + \# (A \cap B)$.
Therefore $\#(A \cup B) = \#A + \#B - \# (A \cap B)$.}
\end{figure}
%texpreamble
%("  \usepackage{amsmath, amssymb}");
%defaultpen(  fontcommand("\normalfont") + fontsize(11) ); 
%
%from graph access *;
%unitsize(1.25cm);
%
%real linethick = 1.5;
%real dotthick = 12;
%dotfactor=12;
%
%real a = 0, b = 1, r = 1;
%
%draw( circle( (a,0),r ), linewidth(2) );
%draw( circle( (b,0),r ), linewidth(2) );
%
%label( "$A \cap B$", ((a+b)/2,0) );
%label( "$A {\smallsetminus} B$", (a-0.4*r,-0.4*r) );
%label( "$B {\smallsetminus} A$", (b+0.375*r,-0.4*r) );
%label( "$A$", (-r,r), 0.1*SE );
%label( "$B$", (b+r,r), 0.1*SW );

\begin{eg}
Let $A = \{\var{p},\var{r},\var{o},\var{n},\var{g}\}$ and $B = \{\var{h},\var{o},\var{r}, \var{n}, \var{s}\}$. Then
$$ \text{$\#A = 5$, $\#B = 5$, and $\#(A \cap B) = \#\{\var{r},\var{o},\var{n}\} = 3$,} $$
so \cref{card(AcupB)} tells us that 
	$$ \#(A \cup B) = \#A + \#B - \#(A \cap B) = 5 + 5 - 3 = 7 .$$
This is correct, since
	$$ \#(A \cup B) = \#\{\var{p},\var{r},\var{o},\var{n},\var{g}, \var{h}, \var{s} \} = 7 .$$
\end{eg}


\begin{eg}
Every one of the 4000 students at Modern~U owns either a cell phone or an iPod (or both). Surveys show that:
\begin{itemize}
\item  3500 students own a cell phone,
and
\item 1000 students own an iPod.
\end{itemize}
How many students own \emph{both} a cell phone and an iPod?

\begin{solution}
Let 
\begin{itemize}
\item $S$ be the set of all students at Modern~$U$,
\item $C$ be the set of students who own a cell phone,
and
\item $I$ be the set of students who own an iPod.
\end{itemize}
Then, by assumption,
	$$ 
	\#S = 4000, \qquad
	\#C = 3500, \qquad
	\#I = 1000 .
	$$
Since every student owns either a cell phone or an iPod, we have $S = C \cup I$. Therefore, \cref{card(AcupB)} tells us that
	$$ \#S = \#(C \cup I) = \#C + \#I - \#(C \cap I) ,$$
so
	$$ \#(C \cap I) =  \#C + \#I - \#S = 3500 + 1000 -4000 = 500 .$$
Hence, there are exactly 500 students who own both a cell phone and an iPod.
\end{solution}
\end{eg}
\begin{exers} \label{CardUnionEx} \ 
\begin{enumerate}
\item Assume $\#U = 15$, $\#V = 12$, and $\#(U \cap V) = 4$. Find $\#(U \cup V)$.
\item Assume $\#R = 13$, $\#S = 17$, and $\#(R \cup S) = 25$. Find $\#(R \cap S)$.
\item Assume $\#J = 300$, $\#(J \cup L) = 500$, and $\#(J \cap L) = 150$. Find~$\#L$.
\item \label{CardUnionEx-university}
 At a small university, there are 90 students that are taking either Calculus \emph{or} Linear Algebra (or both).
If the Calculus class has 70 students, and the Linear Algebra class has 35 students, then how many students are taking both Calculus \emph{and} Linear Algebra?
%\item Surveys of the residents of Vegland show that:
%\begin{enumerate}
%\item 425 residents like either broccoli \emph{or} squash (or both).
%\item 250 of the residents like broccoli (an,
%and
%\item 300 of the residents like squash,
%and
%\end{enumerate}
%How many of the residents like {both} broccoli \emph{and} squash?
\item \label{CardUnionEx-InclExcl3}
(\emph{harder}) Suppose $A$, $B$, and~$C$ are finite sets. Show
	\begin{align*}
		 \#(A \cup B \cup C) &= \#A + \#B + \#C 
		 	\\&\qquad \quad  {} - \#(A \cap B) - \#(A \cap C) - \#(B \cap C) 
			\\&\qquad \quad \qquad \quad {}+ \#(A \cap B \cap C) 
	. \end{align*}
\hint{We have formulas for $\#\bigl( (A \cup B) \cup C \bigr)$ and  $\#(A \cup B)$. Another useful formula comes from the equality $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$.}
\end{enumerate}
\end{exers}

The following exercises are examples of another type of application of the formula for the cardinality of a union.

\begin{exers} \label{|A|+|B|>|C|Ex} \ 
\begin{problist}
\item \label{|A|+|B|>|C|Ex->C}
Suppose $A$ and~$B$ are subsets of a finite set~$C$. Show that if $\# A + \# B > \# C$, then $A \cap B \neq \emptyset$.
\hint{Use \cref{card(AcupB)} to show that $\#(A \cap B) \neq 0$.}
\item \label{|A|+|B|>|C|Ex-600of1000}
Show that if $A$ is a set of at least 600 natural numbers that are less than 1000, then two of the numbers in~$A$ differ by exactly 100.
\hint{Let $B = \{\, a + 100 \mid a \in A \,\}$, and use the preceding exercise to show that $A \cap B \neq \emptyset$.}
\end{problist}
\end{exers}

%\begin{solution}
%Let 
%	$$ B = \{\, a + 100 \mid a \in A \,\} ,$$
%and note that $\# B = \# A$.
%By assumption, we know that 
%	$$ \text{$a \le 1000$, for every $a \in A$}. $$
%Therefore, the definition of~$B$ implies that
%	$$ \text{$b < 1100$, for every $b \in B$}. $$
%Hence
%	$$ A \cup B \subset \{0,1,2,3,\ldots, 1100 \} ,$$
%so
%	$$ \# (A \cup B) \le \# \{0,1,2,3,\ldots, 1100 \} = 1101 . $$
%On the other hand, we know that
%	$$ \# B = \# A \ge 600 .$$
%Therefore
%	$$ 1101 
%	\ge  \# (A \cup B) 
%	= \#A + \# B - \# (A \cap B)
%	\ge 600 + 600 - \# (A \cap B)
%	= 1200 - \# (A \cap B),
%	$$
%so 
%	$$  \# (A \cap B) \ge 1200 - 1101 = 99 > 0.$$
%This implies $A \cap B \neq \emptyset$, so there exists $a \in A$, such that $a \in B$. By definition of~$B$, this means there exists $a' \in A$, such that $a = a' + 100$. So $a$ and~$a'$ differ by exactly $100$.
%\end{solution}

\begin{exers} \ \label{PigeonholePfEx} 
\begin{problist}
\item Suppose $A_1,A_2,\ldots,A_n$ are finite sets. Show
	$$ \#(A_1 \cup A_2 \cup \cdots \cup A_n) \le \#A_1 + \#A_2 + \cdots + \#A_n .$$
\hint{The induction step uses \cref{card(AcupB)}.}
\item Prove the Pigeonhole Principle \pref{PigeonholePrinciple}.
\\ \hint{The contrapositive states that if $\#A_i \le 1$ for every~$i$, then $\#(A_1 \cup A_2 \cup \cdots \cup A_n) \le n$.}
\end{problist}
\end{exers}



\begin{rem}
Generalizing \fullcref{CardUnionEx}{InclExcl3}, the \define{Inclusion-Exclusion} formula calculates the cardinality of the union of any number of sets:
$$|A_1 \cup \cdots \cup A_n|
	= \sum_{i=1}^n |A_i| 
	- \hskip-10pt \sum_{1 \le i<j\le n} \hskip-8pt |A_i \cap A_j| 
	+ \hskip-14pt \sum_{1 \le i<j<k\le n} \hskip-12pt |A_i\cap A_j\cap A_k|
	- \cdots 
	+ (-1)^{n+1}|A_1\cap \cdots \cap A_n| .$$
(The sign ${+}/{-}$ depends on the number of sets being intersected: odd intersections are added, and even intersections are subtracted, which agrees with both \cref{{card(AcupB)}} and \fullcref{CardUnionEx}{InclExcl3}.)
We do not need this formula, but you can read about it in a Combinatorics textbook (or on \href{https://en.wikipedia.org/wiki/Inclusion–exclusion_principle}{\emph{Wikipedia}}).
\end{rem}










\section{Hotel Infinity and the cardinality of infinite sets} \label{HotelInfinitySect}

The above discussion of cardinality included the following important fact that appeared in  \cref{CardA=CardBbijection}:
\factoidbox{Two finite sets $A$ and~$B$ have the same cardinality 
\\ if and only if  there is a bijection from~$A$ to~$B$.}%
Extending this property to all sets (not just the finite ones) is the \emph{definition} of cardinality for infinite sets:

\begin{defn}
Two sets $A$ and~$B$ have the \define[cardinality!same]{same cardinality} iff there exists a bijection from~$A$ to~$B$.
\end{defn}

Two main ideas will be developed in the remainder of this chapter:
	\begin{enumerate}
	\item Many sets have the same cardinality as~$\natural^+$. These are the smallest infinite sets, and they are said to be \define[countably infinite]{countably} infinite.
	\item Not all sets are countably infinite:  some sets are more infinite than others! These sets are said to be \define[uncountable set]{uncountable}.
	\end{enumerate}

Let us begin with an informal discussion of some of the ideas that are involved in countability, rather than looking at the official definition right away. First, a simple example involving finite sets.

\begin{eg}
 Suppose a hotel has $n$~rooms, numbered $1,2,3,\ldots,n$.
\begin{enumerate}
\item If $A$ is a tour group of~$n$ people $a_1,a_2,\ldots,a_n$, then the hotel clerk will obviously have no trouble assigning each of the people a room: $a_i$ can be put in room~$i$. There will be no empty rooms left.
$$\begin{array}{ c |c|c|c|ccc|c|}
\text{room \#} &
{\quad 1 \quad}  &
{\quad 2 \quad}  &
{\quad 3 \quad}&
&\cdots &&
{\quad n \quad} \\
\hhline{-----~--}
\vphantom{\Big|} 
\text{occupant} &
a_1&
a_2&
a_3&&
\cdots &&
a_n\\
\hhline{~----~--}
\end{array}$$

\item Now, if another person~$b$ arrives who wants a room, then the situation is hopeless.  There is no way to give each of these $n+1$ people a room, without making two of them share a room. In general:
\factoidbox{If there are more guests than hotel rooms,
\\ then not everyone can have a room.}
This is a restatement of the Pigeonhole Principle \pref{PigeonholePrinciple}.
\end{enumerate}
\end{eg}

\begin{eg}[(\define{Hotel Infinity})] \label{HotelInfinityEg}
Now consider a hotel with infinitely many rooms, numbered $1,2,3,\ldots$. (There is one room for each $i \in \natural^+$.)
\begin{enumerate}
\item If $A$ is a tour group of~$n$ people $a_1,a_2,\ldots,a_n$, then the hotel clerk will obviously have no trouble giving each of the people a room: $a_i$ can be put in room~$i$. There will be lots of empty rooms left over.
$$\begin{array}{|c|c|c|ccc|c|c|c|cc}
{\quad 1 \quad} &
{\quad 2 \quad} &
{\quad 3 \quad} &
&\cdots&&
{\quad n \quad}  &
n+1 &
n+2 &
& {\cdots} 
\\
\hhline{----~-----}
\vphantom{\Big|} a_1&
a_2&
a_3&&
 \cdots &&
a_n &
&
&
&
{\cdots} 
\\
\hhline{----~-----}
\end{array}$$

\item Even if $A$ is infinite, rather than finite, with people $a_1,a_2,\ldots$, the hotel clerk can accommodate all of them, by putting $a_i$ in room~$i$. There will be no empty rooms left.
$$\begin{array}{|c|c|c|c|cc}
{\quad 1 \quad} &
{\quad 2 \quad} &
{\quad 3 \quad} &
{\quad 4 \quad} &
& {\cdots}
\\
\hhline{-----~}
\vphantom{\Big|} a_1&
a_2&
a_3&
a_4&
&
 \cdots 
\\
\hhline{-----~}
\end{array}$$
%$$\begin{array}{|c|c|c|ccc|c|c|c|cc}
%{\quad 1 \quad} &
%{\quad 2 \quad} &
%{\quad 3 \quad} &
%&&&
%{\quad n \quad}  &
%n+1 &
%n+2
%\\
%\hhline{----~-----}
%\vphantom{\Big|} a_1&
%a_2&
%a_3&&
% \cdots &&
%a_n &
%a_{n+1} &
%a_{n+2} &
%&
%{\cdots} 
%\\
%\hhline{----~-----}
%\end{array}$$

\item Now suppose that, in addition to this tour group, there is another person~$b$ who also wants a room. Even though the hotel is already full, the hotel clerk can handle this situation quite easily, by shifting everyone to the next room, to make space for~$b$. That is, the clerk can put 
	$$\text{ 
	$b$ into room~$1$
	\quad
	and 
	\quad
	 $a_i$ in room~$i+1$. }
	$$
Everyone will have his or her own room.
$$\begin{array}{|c|c|c|c|cc}
{\quad 1 \quad} &
{\quad 2 \quad} &
{\quad 3 \quad} &
{\quad 4 \quad} &
& {\cdots}
\\
\hhline{-----~}
\vphantom{\Big|} b&
a_1&
a_2&
a_3&
&
 \cdots 
\\
\hhline{-----~}
\end{array}$$
%$$\begin{array}{|c|c|c|ccc|c|c|c|cc}
%{\quad 1 \quad} &
%{\quad 2 \quad} &
%{\quad 3 \quad} &
%&&&
%{\quad n \quad}  &
%n+1 &
%n+2
%\\
%\hhline{----~-----}
%\vphantom{\Bigg|} b &
%a_1&
%a_2&&
% \cdots &&
%a_{n-1} &
%a_n &
%a_{n+1} &
%&
%{\cdots} 
%\\
%\hhline{----~-----}
%\end{array}$$

\item The same idea works, even if, instead of just one person, there is a whole group~$B$ of $n$~people $b_1,b_2,\ldots,b_n$ that want rooms. The clerk can put 
	$$\text{ 
	 $b_j$ in room~$j$, 
	\quad
	and 
	\quad
	$a_i$ in room $i+n$.
	} $$
$$\begin{array}{|c|c|c|ccc|c|c|c|c|cc}
{\quad 1 \quad} &
{\quad 2 \quad} &
{\quad 3 \quad} &
&\cdots&&
{\quad n \quad}  &
n+1 &
n+2 &
n+3 &
& \cdots
\\
\hhline{----~------}
\vphantom{\Big|} b_1&
b_2&
b_3&&
 \cdots &&
b_n &
a_1 &
a_2 &
a_3 &
&
{\cdots} 
\\
\hhline{----~------}
\end{array}$$

\item It may seem that there would be a problem if the second group~$B$ consists of infinitely many people $b_1,b_2,b_3,\ldots$, but a clever hotel clerk can accommodate even this situation. Note that there are infinitely many odd-numbered rooms, so all of~$A$ can be put in those rooms, and there are also infinitely many even-numbered rooms, so all of~$B$ can be put in there. More precisely, the clerk can put
	$$\text{ 
	 $a_i$ in room $2i-1$,
	\quad
	and 
	\quad
	 $b_j$ in room $2j$.
	} $$
$$\begin{array}{|c|c|c|c|ccc|c|c|c|c|cc}
{\quad 1 \quad} &
{\quad 2 \quad} &
{\quad 3 \quad} &
{\quad 4 \quad} &
&\cdots&&
 2n-1   &
{\ \ \ 2n\ \ \ } &
2n+1 &
2n+2 &
& \cdots
\\
\hhline{-----~------}
\vphantom{\Big|} a_1&
b_1&
a_2&
b_2&&
 \cdots &&
a_n &
b_n &
a_{n+1} &
b_{n+1} &
&
{\cdots} 
\\
\hhline{-----~------}
\end{array}$$

\item  \label{HotelInfinityEg-FiniteUnion}
Even if there are several of these countably infinite tour groups, not just~$2$ of them, they can all be accommodated. Namely, suppose there are $n$ tour groups $A_1,A_2,A_3,\ldots,A_n$, and make a table (or matrix) with $n$ infinitely long rows that lists the elements of $A_i$ in the $i$th row. That is, if $a_{i,1}, a_{i,2},a_{i,3},\ldots$ is a list of the people in~$A_i$, then the table looks like:
$$\begin{matrix}
A_1: & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & \cdots \\
A_2: & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} & \cdots \\
A_3: & a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
A_n: & a_{n,1} & a_{n,2} & a_{n,3} & a_{n,4} & a_{n,5} & \cdots \\
\end{matrix}$$
We can assign rooms $1,2,3,\ldots$ to the entries of this table by counting down the 1st column (from~$1$ to~$n$), then the 2nd column (starting at $n+1$), then the 3rd column (continuing from where we left off after the 2nd column), etc., as indicated here:
\newcommand{\nnn}[2]{\genfrac{}{}{0pt}{0}{\color{blue}\lower 10pt\hbox{$#1$}}{#2}}
\newcommand{\bluearrowdown}{\lower 5pt \hbox{\color{blue} \rotatebox{90}{\ $\leftarrow$\ }}}
\newcommand{\bluearrowsdown}{\bluearrowdown & \bluearrowdown & \bluearrowdown & \bluearrowdown & \bluearrowdown & {\color{blue} \raise3pt\hbox{$\cdots$}}}
$$\begin{matrix}
 \nnn{1}{a_{1,1}} &  \nnn{n+1}{a_{1,2}} &  \nnn{2n+1}{a_{1,3}} &  \nnn{3n+1}{a_{1,4}} &  \nnn{4n+1}{a_{1,5}} & \cdots  \\
\bluearrowsdown \\
 \nnn{2}{a_{2,1}} &  \nnn{n+2}{a_{2,2}} &  \nnn{2n+2}{a_{2,3}} &  \nnn{3n+2}{a_{2,4}} &  \nnn{4n+2}{a_{2,5}}  & \cdots  \\
\bluearrowsdown \\
 \nnn{3}{a_{3,1}} &  \nnn{n+3}{a_{3,2}} &  \nnn{2n+3}{a_{3,3}} &  \nnn{3n+3}{a_{3,4}} &  \nnn{4n+3}{a_{3,5}}  & \cdots  \\
\bluearrowsdown  \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots  \\
\bluearrowsdown \\
 \nnn{n}{a_{n,1}} &  \nnn{2n}{a_{n,2}} &  \nnn{3n}{a_{n,3}} &  \nnn{4n}{a_{n,4}} &  \nnn{5n}{a_{n,5}}  & \cdots  \\
\end{matrix}$$
This assigns a different room number to each of the people, so everyone has their own room.

\begin{remnonums} \ 
	\begin{enumerate}
	\item Another way for the hotel clerk to find this solution is to note that there are infinitely many numbers that are congruent to~$i$ modulo~$n$, so all of~$A_i$ can be put in those rooms. 
	\item  It can be seen that guest $a_{i,j}$ is assigned to room $i + (j-1)n$, but we have no need for this formula.
	\end{enumerate}
\end{remnonums}

%\begin{exers*} \ 
%\begin{enumerate}
%	\item  \label{HotelInfinityEg-FiniteUnion-Distinct}
%Show that the clerk has not put two guests in the same room. That is, show, for all $k_1,k_2 \in \{1,2,\ldots,n\}$ and $i_1,i_2 \in \natural^+$, such that $k_1 + i_1 n = k_2 + i_2 n$, we have $k_1 = k_2$ and $i_1 = i_2$. 
%	\item   \label{HotelInfinityEg-FiniteUnion-efficient}
%The clerk has left some rooms empty, which is wasteful. (For example, it is not difficult to see that no guest has been put in room~$1$.) Modify the clerk's formula to obtain a method that does not leave any empty rooms (and, of course, does not put two guests in the same room.)
%\end{enumerate}
%\end{exers*}

\item  \label{HotelInfinityEg-hardest}
Going further, even if there were infinitely many infinite tour groups $A_1,A_2,\ldots$, they could all be accommodated. (We assume that each tour group is countably infinite, and that the number of groups is countably infinite.) To see this, start by considering an infinitely large table (or matrix) that lists the elements of~$A_i$ in the $i$th row:
$$\begin{matrix}
A_1: & a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & \cdots \\
A_2: & a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} & \cdots \\
A_3: & a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} & \cdots \\
A_4: & a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} & \cdots \\
A_5: & a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{matrix}$$
We can assign rooms $1,2,3,\ldots$ to the entries of this table as follows:
\smallskip
\begin{multicols}{2}
\begin{itemize}
\item Begin with $1$ in the top left corner. 
\item Then place $2$ at the top of the second column and move diagonally (down and to the left) to place~$3$.
\item Then place $4$ at the top of the third column, and move diagonally (down and to the left) to place~$5$ and~$6$.
\item Then place the next number (namely, $7$) at the first open spot in the top row (namely, at the top of the fourth column), and move diagonally (down and to the left) to place the following numbers (namely, $8$, $9$, and~$10$), until a number (namely,~$10$) is placed in the first column.
\item Continue by moving to the first open spot in the top row, and repeating infinitely.
\end{itemize}
\renewcommand{\nnn}[2]{\genfrac{}{}{0pt}{0}{\vphantom{\biggl|} \color{blue}\lower 10pt\hbox{$#1$}}{#2}}
\newcommand{\nnna}[2]{\nnn{#1}{#2}\vbox to 0pt{\vskip 14pt\hbox to 0pt{\color{blue}\hskip-34pt\rotatebox{52}{$\longleftarrow$}\hss}\vss}}
$$ \begin{matrix}
 \nnn{1}{a_{1,1}} &  \nnna{2}{a_{1,2}} &  \nnna{4}{a_{1,3}} &  \nnna{7}{a_{1,4}} &  \nnna{11}{a_{1,5}} &  \nnna{16}{a_{1,6}} \\
 \nnn{3}{a_{2,1}} &  \nnna{5}{a_{2,2}} &  \nnna{8}{a_{2,3}} &  \nnna{12}{a_{2,4}} &  \nnna{17}{a_{2,5}}  & \ddots \\
 \nnn{6}{a_{3,1}} &  \nnna{9}{a_{3,2}} &  \nnna{13}{a_{3,3}} &  \nnna{18}{a_{3,4}} & \ddots  \\
 \nnn{10}{a_{4,1}} &  \nnna{14}{a_{4,2}} &  \nnna{19}{a_{4,3}} & \ddots   \\
 \nnn{15}{a_{5,1}} &  \nnna{20}{a_{5,2}} & \ddots   \\
 \nnn{21}{a_{6,1}}  & \ddots \\
 \\
\end{matrix}$$
\end{multicols}
\smallskip\noindent
No entries of the table are omitted from the numbering, and no room numbers are repeated, so each guest has his or her own room.
\begin{remnonum}
It can be shown that guest $a_{i,j}$ is put into room 
	$ \binom{i+j-1}{2} + i$,
but we have no need for this formula.
\end{remnonum}
\end{enumerate}
\end{eg}






It might seem that Hotel Infinity could accommodate every set of tourists, but that is not the case. For example, we will see in \cref{UncountableSect} that if all of the real numbers want rooms at the hotel, then some of them will have to share. In other words, \emph{the set\/~$\real$ of real numbers is uncountable}.

\begin{otherterm}
Hotel Infinity is often called ``Hilbert's Hotel\rlap,'' in honour of the German mathematician David Hilbert (1862--1943), who was apparently the first to talk about such a hotel (in lectures in Germany in 1924).
\end{otherterm}




\section{Countable sets} \label{CountableSect}
For use in proving theorems, the ideas encountered in the discussion of Hotel Infinity need to be stated more formally. Let us begin with the definitions that form the foundation of the subject.

\begin{defn}
Suppose $A$ and~$B$ are sets.
\begin{enumerate}
\item $A$ and~$B$ \define[cardinality!same]{have the same cardinality} iff there is a bijection from~$A$ to~$B$.
\item $A$ is \define{countably infinite} iff it has the same cardinality as~$\natural^+$.
\item $A$ is \define{countable} iff either $A$ is finite or $A$ is countably infinite.
\item $A$ is \define[uncountable set]{uncountable} iff $A$ is \emph{not} countable.
\end{enumerate}
\end{defn}


\begin{rems} \ 
\begin{enumerate}
\item In the terminology of the preceding section, a set is countable if and only if all of its elements can be given rooms in Hotel Infinity (see \fullcref{CountIffEx}{11ToN}). 
\item If you are told to show that $A$~is countably infinite, directly from the definition, then you should find a bijection from~$A$ to~$\natural^+$. However, because it is so well known that the inverse of a bijection is a bijection, it is acceptable to find a bijection from~$\natural^+$ to~$A$, instead. 
\end{enumerate}
\end{rems}


\begin{rems}
One can (and should) think of countable sets as the sets whose elements can be listed in a sequence. The sequence may have only finitely many terms, or may continue forever:
\begin{enumerate}
\item A set~$A$ is finite iff its elements can be listed in a sequence $a_1,a_2,\ldots,a_n$, for some~$n$.
\item If the elements of~$A$ can be listed in an infinite sequence $a_1,a_2,a_3,\ldots$, then we may define a bijection $f \colon \natural^+ \to A$ by $f(i) = a_i$. Therefore, $A$~is countably infinite. 
\item Conversely, if~$A$ is countably infinite, then there is a bijection $f \colon \natural^+ \to A$, so letting $a_i = f(i)$ yields an infinite sequence $a_1,a_2,a_3,\ldots$ that lists the elements of~$A$.
\end{enumerate}
\end{rems}

\begin{exer} \label{cardinality-equivrel}
Define a binary relation $\approx$ on the collection of all sets by
	$$ \text{$A \approx B$ \quad iff \quad $A$ and~$B$ have the same cardinality.} $$
\begin{multicols}{2}
\begin{problist}
\item  \label{cardinality-equivrel-equiv}
Show that $\approx$ is an \hbox to 0pt{equivalence relation.\hss} % !!!
\item  \label{cardinality-equivrel-class}
What is the equivalence class of~$\natural^+$?
\end{problist}
\end{multicols}
\end{exer}


The following fundamental result shows that the smallest infinite sets are the countable ones:

\begin{thm} \label{CountableSmall} \ 
\begin{enumerate}
\item \label{CountableSmall-HasSubset} 
Every infinite set contains a countably infinite subset.
\item  \label{CountableSmall-subset} 
Every subset of a countable set is countable.
\end{enumerate}
\end{thm}

%
\begin{proof}
\pref{CountableSmall-HasSubset} Given an infinite set~$A$, it suffices to construct an infinite sequence $a_1,a_2,a_2,\ldots$ of distinct elements of~$A$, for then $\{a_1,a_2,a_3,\ldots\}$ is a countably infinite subset of~$A$.
	\begin{enumerate}
	\item Since $A$ is infinite, it is certainly not empty, so it has some elements. Let $a_1$ be any of these elements of~$A$.
	\item Since $A$ is infinite, we know that $a_1$ is not its only element. Let $a_2$ be any element of~$A$ other than~$a_1$. Then $a_1$ and $a_2$ are distinct elements of~$A$.
	\item Since $A$ is infinite, we know that $a_1$ and~$a_2$ are not its only elements. Let $a_3$ be any element of~$A$ other than~$a_1$ and~$a_2$. Then $a_1$, $a_2$, and~$a_3$ are distinct elements of~$A$. 
	\\ \hbox{\hskip 1in} $\vdots$
	\item[($i$)] Since $A$ is infinite, we know that $a_1,a_2,a_3,\ldots,a_{i-1}$ are not its only elements. Let $a_i$ be any element of~$A$ other than $a_1,a_2,a_3,\ldots,a_{i-1}$. Then the elements $a_1,a_2,a_3,\ldots,a_i$ are distinct.
	\\ \hbox{\hskip 1in} $\vdots$
	\end{enumerate}
Continuing this inductive process yields the desired infinite sequence $a_1,a_2,a_3,\ldots$ of distinct elements of~$A$.


\pref{CountableSmall-subset} Given a subset~$M$ of a countable set~$A$, we wish to show that $M$ is countable. We may assume $M$ is infinite, for otherwise it is obviously countable. 
So we wish to show there is a sequence $m_1,m_2,m_3,\ldots$ that lists all the elements of~$M$. 

To simplify the notation, let us first consider the case where $A = \natural^+$.

\setcounter{case}{0}
\begin{case} \label{CountableSmallPf-N}
Assume $A = \natural^+$. 
\end{case}
Let 
\begin{enumerate}
\item $m_1$ be the smallest element of~$M$,
\item $m_2$ be the smallest element of~$M \smallsetminus \{m_1\}$,
\item $m_3$ be the smallest element of~$M \smallsetminus \{m_1,m_2\}$,
\item $m_4$ be the smallest element of~$M \smallsetminus \{m_1,m_2,m_3\}$,
\\ \hbox{\hskip 1in} $\vdots$
\item[($i$)] $m_i$ be the smallest element of~$M \smallsetminus \{m_1,m_2, \ldots,m_{i-1}\}$.
\\(In other words, $m_i$ is the smallest element of~$M$ that is not in $\{m_1,m_2, \ldots,m_{i-1}\}$.)
\\ \hbox{\hskip 1in} $\vdots$
\end{enumerate}
For each $m \in M$, notice that if we let $k$ be the number of elements of~$M$ that are less than~$m$, then $m_{k+1} = m$. Therefore, every element~$m$ of~$M$ appears in the sequence $m_1,m_2,m_3,\ldots$. 

%for each $i \in \natural^+$, that $m_{i+1} > m_i$. Using this, it is easy to show (by induction) that $m_i \ge i$ for every $i \in \natural^+$. In particular, 
%	$$m_{k+1} \ge k+1 > k .$$
%Since, by definition, $m_{k+1}$ is the \emph{smallest} element of~$M$ that is not in $\{m_1,m_2, \ldots,m_k\}$, we conclude that $k \in \{m_1,m_2, \ldots,m_k\}$. So $k$ is one of the terms in the sequence, as desired.


\begin{case} \label{CountableSmallPf-general}
The general case.
\end{case}
This is left as an exercise. 
\end{proof}


\begin{exers} \label{CountIffEx} \ 
\begin{enumerate}
\item \label{CountIffEx-CompleteSmall} 
Complete \cref{CountableSmallPf-general} in the proof of \cref{CountableSmall}.
\\ \hint{If $M$ is infinite, then $A$ must be infinite (why?). List the elements of~$A$ in a sequence $a_1,a_2,a_3,\ldots$, and apply the argument of \cref{CountableSmallPf-N}.}
\item \label{CountIffEx-11ToAny}
Suppose that $f \colon A \to B$, that $f$~is one-to-one, and that $B$ is countable. Show that $A$ is countable.
\\ \hint{If~$f$ is not onto, you will want to use the fact that every subset of a countable set is countable.}
\item \label{CountIffEx-11ToN}
Show that a set~$A$ is countable iff there exists a one-to-one function $f \colon A \to \natural^+$.
\end{enumerate}
\end{exers}


\begin{rem}
Mathematicians think of countable sets as being small --- even though they may be infinite, they are almost like finite sets. Consider the following basic properties of finite sets:
\begin{enumerate}
\item Any subset of a finite set is finite.
\item The union of two finite sets is finite.
\item More generally, the union of finitely many finite sets is finite.
\item If you have two finite sets, then you can make only finitely many ordered pairs from them. (That is, the Cartesian product of two finite sets is finite.)
\item If you have only finitely many darts to throw, then you can hit only finitely many things with them. That is, if $f \colon A \to B$, and $A$ is finite, then the image $f(A)$ is finite.
%\item If a hotel has only a few rooms, then it can have only a few guests. That is, if $f \colon A \to B$, $f$~is one-to-one, and $B$ has only a few elements, then $A$ has only a few elements.
\end{enumerate}
All of the above assertions remain true when the word ``finite'' is replaced with ``countable\rlap.'' The first assertion was established in Thm.~\fullref{CountableSmall}{subset}; the others are contained in the following important theorem:
\end{rem}

\begin{thm} \label{CtblUnion} \ 
\begin{enumerate}
\item  \label{CtblUnion-union}
A countable union of countable sets is countable. 
\item  \label{CtblUnion-product}
The cartesian product of two countable sets is countable.
\item  \label{CtblUnion-image}
The image of a countable set is countable.
\end{enumerate}
\end{thm}


\begin{rem}
Here are more precise statements of the assertions of \cref{CtblUnion}:
\begin{enumerate}
\item If $A_1,A_2,A_3,\ldots$ is any sequence of countable sets, then the union
	$$ \bigcup_{i=1}^\infty A_i = A_1 \cup A_2 \cup A_3 \cup \cdots $$
is countable. Also, if $A_1,A_2,A_3,\ldots,A_n$ is any finite sequence of countable sets, then the union 
	$$ \bigcup_{i=1}^n A_i = A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_n$$
is countable.
\item If $A$ and~$B$ are any countable sets, then $A \times B$ is countable.
\item If $f \colon A \to B$, and $A$ is countable, then $f(A)$ is countable.
\end{enumerate}
\end{rem}

%% want reference to appear in correct style, but \MakeUppercase makes the reference unusable !!!
\setbox0\hbox{\proofnamestyle \ref{CtblUnion}} 
\begin{proof}[Proof of Theorem~\copy0] %% Is this a theorem? !!!
\pref{CtblUnion-union} Given either an infinite sequence $A_1,A_2,A_3,\ldots$ of countable sets, or a finite sequence $A_1,A_2,A_3,\ldots,A_n$ of countable sets, we wish to show that the the union of the sets is countable. Subsets of a countable set are countable, so there is no harm in assuming:
	\begin{itemize}
	\item the sequence is infinite (because adding additional terms to the sequence will make the union larger),
	and 
	\item each of the sets is infinite (because replacing $A_i$ with an infinite superset will make the union larger).
	\end{itemize}
Now, the numbering method of Eg.~\fullref{HotelInfinityEg}{hardest} shows there is an onto function $g \colon \natural^+ \to \bigcup_{i=1}^\infty A_i$. So, from~\pref{CtblUnion-image}, we conclude that $\bigcup_{i=1}^\infty A_i$ is countable.

\medskip

\pref{CtblUnion-product} Given countable sets $A$ and~$B$, we wish to show that $A \times B$ is countable. Subsets of a countable set are countable, so there is no harm in assuming that $A$ and~$B$ are infinite (because replacing $A$ and~$B$ with infinite supersets will make the cartesian product larger). Let
\begin{itemize}
\item $a_1,a_2,a_3,\ldots$ be a list of the elements of~$A$,
and
\item $b_1,b_2,b_3,\ldots$ be a list of the elements of~$B$,
\end{itemize}
Then the elements of $A \times B$ are listed in the following table (or matrix):
$$\begin{matrix}
(a_1,b_1) & (a_1,b_2) & (a_1,b_3) & (a_1,b_4) & (a_1,b_5) & \cdots \\
(a_2,b_1) & (a_2,b_2) & (a_2,b_3) & (a_2,b_4) & (a_2,b_5) & \cdots \\
(a_3,b_1) & (a_3,b_2) & (a_3,b_3) & (a_3,b_4) & (a_3,b_5) & \cdots \\
(a_4,b_1) & (a_4,b_2) & (a_4,b_3) & (a_4,b_4) & (a_4,b_5) & \cdots \\
(a_5,b_1) & (a_5,b_2) & (a_5,b_3) & (a_5,b_4) & (a_5,b_5) & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{matrix}$$
The numbering method of Eg.~\fullref{HotelInfinityEg}{hardest} defines a bijection from $A \times B$ to~$\natural^+$. So $A \times B$ is countable.

\medskip
\pref{CtblUnion-image} Suppose $f \colon A \to B$, and $A$~is countable. By replacing~$B$ with~$f(A)$, we may assume $f$~is onto; then we wish to show that $B$ is countable. 

By \fullcref{CountIffEx}{11ToAny}, it suffices to define a one-to-one function $g \colon B \to A$. The function~$f$ is onto, so, for each $b \in B$, there is some $a \in A$, such that $f(a) = b$; thus, for each $b \in B$, we may choose $g(b)$ to be an element of~$A$ such that 
	$$ f \bigl( g(b) \bigr) = b .$$
Then $g \colon B \to A$, and all that remains is to show that $g$ is one-to-one. Given $b_1,b_2 \in B$, such that $g(b_1) = g(b_2)$, we have $f \bigl( g(b_1) \bigr) = b_1$ and $f \bigl( g(b_2) \bigr) = b_2$. Therefore
	$$ b_1 = f \bigl( g(b_1) \bigr) = f \bigl( g(b_2) \bigr) = b_2 .$$
So $g$~is one-to-one, as desired.
\end{proof} 


The theorems of this section make it easy to show that many sets are countable. Here are a few important examples:

\begin{exer} \label{NZQCountableEx}
Show that each of the following sets is countable.
\begin{enumerate}

\item \label{NZQCountableEx-N+}
$\natural^+$.

\item \label{NZQCountableEx-N}
$\natural$.
\hint{$\natural = \natural^+ \cup \{0\}$.}

\item \label{NZQCountableEx-Z}
$\integer$.
\hint{Let $\integer^- = \{\, n \in \integer \mid n < 0 \,\}$, so $\integer = \natural \cup \integer^-$. The set~$\integer^-$ is the image of~$\natural^+$ under a function.}

\item \label{NZQCountableEx-Q}
$\rational$.
\hint{Let $\integer^+$ be the set of positive integers, so $\rational$~is the image of $\integer \times \integer^\times$ under the function $f(a,b) = a/b$.}
\end{enumerate}
\end{exer}

\factoidbox{%
It is very important to remember that~$\rational$ is countable. 
\\
Since $\natural$ and~$\integer$ are subsets of~$\rational$, this implies that $\natural$ and~$\integer$ are also countable.%
}


\begin{exers} \label{InfCardEx} \ 
%\emphit{Do not assume sets in these exercises are countable.}
\begin{problist}
\item  \label{InfCardEx-AddOne}
Suppose $A$ is countably infinite, and $b \notin A$. Show, directly from the definition, that $A \cup \{b\}$ is countably infinite.
\item  \label{InfCardEx-TakeOne}
Suppose $A$ is countably infinite, and $a \in A$. Show, directly from the definition, that $A \smallsetminus \{a\}$ is countably infinite.
\item  \label{InfCardEx-union}
Suppose $A$ and~$B$ are countably infinite and disjoint. Show, directly from the definition, that $A \cup B$ is countably infinite.
\item  \label{InfCardEx-DisjointUnion}
Suppose 
	$$ \begin{matrix}
	\text{$A_1$ is disjoint from~$B_1$,} 
	& & 
	\text{$A_1$ and $A_2$ have the same cardinality,}
	\\
	\text{$A_2$ is disjoint from~$B_2$,}
	& \text{and} &
	\text{$B_1$ and $B_2$ have the same cardinality.}
	\end{matrix} $$
Show that $(A_1 \cup B_1)$ has the same cardinality as $(A_2 \cup B_2)$.
\item  \label{InfCardEx-ProperSame}
Suppose $A$ is infinite. Show there is a \emph{proper} subset~$B$ of~$A$, such that $B$ has the same cardinality as~$A$.
 \hint{Combine \fullcref{CountableSmall}{HasSubset} with Exercises % !!!
 \pref{InfCardEx-TakeOne} and~\pref{InfCardEx-DisjointUnion}.}
\end{problist}
\end{exers}

\begin{otherterm}
Some mathematicians do not consider finite sets to be ``countable\rlap,'' so the terms ``countable'' and ``countably infinite'' are synonymous to them. Then, a set that is either finite or countably infinite is said to be ``at most countable\rlap.'' Other mathematicians say that a countably infinite set is ``denumerable\rlap.''
\end{otherterm}






\section{Uncountable sets} \label{UncountableSect}
The preceding % !!!
section showed that many sets (including $\natural$, $\integer$, and~$\rational$) are countable. We will now see that some sets are \emph{not} countable. 

\subsection{The reals are uncountable} 
Here is perhaps the most important example of an uncountable set:

\begin{thm} \label{RealUncountable}
The set\/~$\real$ of real numbers is uncountable.
\end{thm}

If $\real$ were countable, then all of its subsets would be countable. Thus, in order to establish \cref{RealUncountable}, it suffices to find an uncountable subset of~$\real$. Here are some well-known examples of subsets:

\begin{notation}
For $a,b \in \real$ with $a < b$:
	\begin{itemize}
	\item \define[interval!open]{open interval}\nindex{$(a,b)$}:
	$(a,b) = \{\, x \in \real \mid a < x < b \,\}$.
	\item \define[interval!closed]{closed interval}\nindex{$[a,b]$}:
	$[a,b] = \{\, x \in \real \mid a \le x \le b \,\}$. 
	\item \define[interval!half-open]{half-open interval}\nindex{$[a,b)$}\nindex{$(a,b]$}:
	$[a,b) = \{\, x \in \real \mid a \le x < b \,\}$
	or $(a,b] = \{\, x \in \real \mid a < x \le b \,\}$.
	
	\end{itemize}
\end{notation}

We will see that all of these intervals are uncountable. Here is one example:

\begin{thm} \label{IUncountable}
The interval $[0,1)$ is uncountable.
\end{thm}

\begin{proof}[Proof  by contradiction]
Suppose $[0,1)$ is countable. (This will lead to a contradiction.) This means there is a list $x_1,x_2,x_3,\ldots$ of all the numbers in~$[0,1)$. 
%We will show that there is an element of $[0,1)$ that is missing from this list, contradicting the fact that the list was suppose to include all the elements of $[0,1)$.
To obtain a contradiction, we will use a method called the \emph{Cantor Diagonalization Argument}. It was discovered by the mathematician Georg Cantor in the 19th century.

Each number in $[0,1)$ can be written as a decimal of the form $0.d_1d_2d_3\ldots$, where each $d_k$ is a digit ($0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, or~$9$). In particular, we can write each $x_i$ in this form:
	$$ x_i = 0. x_{i,1} x_{i,2} x_{i,3} x_{i,4} x_{i,5} \ldots $$
 Then we can make a list of all of these decimals (omitting the leading~$0$ in each one):
	$$\begin{matrix}
	x_1= & . x_{1,1} x_{1,2} x_{1,3} x_{1,4} x_{1,5} \ldots \\
	x_2= & . x_{2,1} x_{2,2} x_{2,3} x_{2,4} x_{2,5} \ldots \\
	x_3= & . x_{3,1} x_{3,2} x_{3,3} x_{3,4} x_{3,5} \ldots \\
	x_4= & . x_{4,1} x_{4,2} x_{4,3} x_{4,4} x_{4,5} \ldots \\
	x_5= & . x_{5,1} x_{5,2} x_{5,3} x_{5,4} x_{5,5} \ldots \\
	\vdots & \vdots 
	\end{matrix} $$
The right-hand side can be thought of as an array of digits, and we now focus on the diagonal entries $x_{i,i}$ of this array, which are circled in the following picture:
\def\circleit{\vbox to 0pt{\vss\hbox to 0pt{\hskip-4pt\color{blue}\Huge$\bigcirc$\hss}\vskip-9pt}}
	$$\begin{matrix}
	x_1= & . \circleit x_{1,1} x_{1,2} x_{1,3} x_{1,4} x_{1,5} \ldots \\
	x_2= & . x_{2,1} \circleit x_{2,2} x_{2,3} x_{2,4} x_{2,5} \ldots \\
	x_3= & . x_{3,1} x_{3,2} \circleit x_{3,3} x_{3,4} x_{3,5} \ldots \\
	x_4= & . x_{4,1} x_{4,2} x_{4,3} \circleit x_{4,4} x_{4,5} \ldots \\
	x_5= & . x_{5,1} x_{5,2} x_{5,3} x_{5,4} \circleit x_{5,5} \ldots \\
	\vdots & \vdots 
	\end{matrix} $$
They form a sequence $x_{1,1}, x_{2,2}, x_{3,3}, \ldots$. 

The key to the proof is to make a new sequence $d_1,d_2,d_3,\ldots$ of digits, such that 
	$$ \text{$d_1 \neq x_{1,1}$, \ $d_2 \neq x_{2,2}$, \ $d_3 \neq x_{3,3}$, \ etc.} $$
This means that every term of the new sequence is different from the corresponding term of the diagonal sequence. (This idea of choosing a sequence that is completely different from the diagonal is called \define{Cantor diagonalization}, because it was invented by the mathematician Georg Cantor.) Also, to avoid problems coming from the fact that $.999\cdots = 1.000\cdots$, you should not use the digits $0$ and~$9$. The sequence $\{d_i\}$ can be constructed in many ways: just be sure to choose each~$d_i$ to be a digit that is not $x_{i,i}$ (and is not $0$ or~$9$).  For example, we could let
	$$ d_i = \begin{cases} 1 & \text{if $x_{i,i} \neq 1$} \\ 5 & \text{if $x_{i,i} = 1$} . \end{cases} $$

Now, let 
	$$d = 0.d_1d_2d_3\ldots \in [0,1) .$$
For each~$i$, we made sure that $d_i \neq x_{i,i}$, which means that the $i$th digit of~$d$ is different from the $i$th digit of~$x_i$. Therefore, for each~$i$, we have $d \neq x_i$\rlap.\footnote{The digits of~$d$ are only $1$'s and~$5$'s, so it is not a problem that numbers ending $000\ldots$ can also be expressed as a different decimal that ends $999\ldots$.} So $d$ is an element of~$[0,1)$ that is not in the list $x_1,x_2,x_3,\ldots$. This contradicts the fact that $x_1,x_2,x_3,\ldots$ is a list of \emph{all} the numbers in~$[0,1)$.
\end{proof}

\begin{exers} \label{UncountEx} \ 
\begin{problist}
\item \label{UncountEx-(0,1)}
Show that the interval $(0,1)$ is uncountable.
 \hint{$[0,1) = (0,1) \cup \{0\}$ is uncountable.}
\item  \label{UncountEx-(a,b)}
Suppose $a,b \in \real$. Show that if $a < b$, then the interval $(a,b)$ has the same cardinality as $(0,1)$. %Therefore, $(a,b)$ is uncountable.
\hint{Define $f \colon (0,1) \to (a,b)$ by $f(x) = a + (b-a) x$.}
\item  \label{UncountEx-(a,infty)}
Suppose $a \in \real$. Show that the interval $(a,\infty)$ has the same cardinality as $(0,1)$.
\\ \hint{Define $f \colon (0,1) \to (a,\infty)$ by $f(x) = (1/x) + a - 1$.}
\end{problist}
\end{exers}

\begin{cor}
If $a,b \in \real$ and $a < b$, then the intervals $(a,b)$, $[a,b]$, $[a,b)$, and $(a,b]$ are uncountable.
\end{cor}

\begin{exers} \label{WhichUncount}
Decide which of the following sets are countable, and which are uncountable.
(\!\emph{You do not need to justify your answers.})
\begin{tasks}(2)
\task\fixtask \label{WhichUncount-[3,3.1]}%
The closed interval $[3,3.1]$
\task\fixtask \label{WhichUncount-1to1000}%
 $\{1,2,3,\ldots,1000\}$
\task\fixtask \label{WhichUncount-ZxZ}%
$\integer \times \integer$
\task\fixtask \label{WhichUncount-ZxQ}%
$\integer \times \rational$
\task\fixtask \label{WhichUncount-RxN}%
$\real \times \natural$
\task\fixtask \label{WhichUncount-RminQ}%
$\real \smallsetminus \rational$
\task\fixtask \label{WhichUncount-QminR}%
$\rational \smallsetminus \real$
\task\fixtask \label{WhichUncount-RxQminQxR}%
$(\real \smallsetminus \rational) \cap (\rational \smallsetminus \real)$
\task\fixtask \label{WhichUncount-RminQcupQminR}%
$(\real \smallsetminus \rational) \cup (\rational \smallsetminus \real)$
\task\fixtask \label{WhichUncount-RminQxQminR}%
$(\real \smallsetminus \rational) \times (\rational \smallsetminus \real)$
\task\fixtask \label{WhichUncount-2<x<3}%
$\{\, x \in \real \mid 2 < x < 3 \,\}$
\task\fixtask \label{WhichUncount-x2=3}%
$\{\, x \in \real \mid x^2 = 3 \,\}$
\task\fixtask \label{WhichUncount-x2+12<3}%
$\{\, x \in \real  \mid x^2 + 12 < 3 \,\}$
\task\fixtask \label{WhichUncount-x2+3<12}%
$\{\, x \in \real  \mid x^2 + 3 < 12 \,\}$
\task\fixtask \label{WhichUncount-x2+3<12Q}%
$\{\, x \in \rational  \mid x^2 + 3 < 12 \,\}$
\task\fixtask \label{WhichUncount-xminy=1}%
$\{\, (x,y) \in \real \times \real \mid  x - y = 1 \,\}$
\task\fixtask \label{WhichUncount-xminyinZ}%
$\{\, (x,y) \in \real \times \real \mid  x - y \in \integer \,\}$
\task\fixtask \label{WhichUncount-xminyinQ(ZxR)}%
$\{\, (x,y) \in \integer \times \real \mid  x - y \in \rational \,\}$
\task\fixtask \label{WhichUncount-circle}%
$\{\, (x,y) \in \real^2 \mid x^2 + y^2 = 1 \,\}$
\task\fixtask \label{WhichUncount-emptycircle}%
$\{\, (x,y) \in \real^2 \mid x^2 + y^2 = -1 \,\}$
\end{tasks}
\end{exers}

%\vskip-\baselineskip

\subsection{The cardinality of power sets}
If $A$ is a finite set, then the set $\power(A)$ of all subsets of~$A$ is also finite. (Indeed, $\#\power(A) = 2^{\#A}$.) However, this assertion does \emph{not} remain true when the word ``finite'' is replaced with ``countable'':

\begin{exer} \label{P(N)UncountEx}
 Show that $\power(\natural^+)$ is uncountable.
\\ \hint{For any $f \colon \natural^+ \to \power(\natural^+)$, the set $\bigset{i \in \natural^+}{ i \notin f(i)}$ is not in the image of~$f$.}
\end{exer}

For every set~$A$, not just the countable ones, the same argument shows that the cardinality of $\power(A)$ is greater than the cardinality of~$A$. Thus, there is no ``largest'' infinite set. For every set, there is always some set that has \emph{much} larger cardinality.

\begin{exer} \label{P(A)UncountEx}
For every set~$A$, show there does not exist an onto function $f \colon A \to \power(A)$.
\hint{The set $\bigset{a \in A}{ a \notin f(a)}$ is not in the image of~$f$.}
\end{exer}

The preceding exercises are very closely related to a classical paradox:

\begin{eg}[(``Barber Paradox'')]
Suppose there is a town with only one barber, and that barber is a man. Furthermore, assume the barber shaves precisely those men in the town who do not shave themselves. More precisely, if $B$ is the Barber, and $M$ is any man in the town, then
	$$ \text{$B$ shaves $M$  \qquad iff \qquad $M$ does not shave $M$.} $$
Now, we ask:
	$$ \text{\emph{Does the barber shave himself?}} $$
This question is a paradox:
	\begin{itemize}
	\item If the answer is \textsf{yes}, then the barber shaves himself. But the barber does \emph{not} shave men who shave themselves, so this means that the barber does not shave himself. But we already said that the barber does shave himself, so this is nonsense.
	\item If the answer is \textsf{no}, then the barber does not shave himself. But the barber \emph{does} shave any man who does not shave himself, so this means that the barber does  shave himself. But we already said that the barber does not shave himself, so this is nonsense.
	\end{itemize}
The upshot of this discussion is that the hypothesized situation leads to a contradiction, so it is impossible.
\end{eg}


The same reasoning shows there is no set that contains precisely the sets that do not contain themselves. (Otherwise, the question ``\emph{Does the set contain itself?}'' would be a paradox. Do you see why?) The solutions of \cref{P(N)UncountEx,P(A)UncountEx} are based on the same idea.






\begin{summary}
\item Important definitions:
\begin{itemize}
\item cardinality
\item finite, infinite
\item countable, countably infinite
\item uncountable
\end{itemize}
\item $A$ and $B$ have the same cardinality iff there is a bijection from~$A$ to~$B$.
\item Pigeonhole Principle
\item For finite sets $A$ and~$B$, we have $\#(A \times B) = \#A \cdot \#B$.
\item Inclusion-Exclusion: $A \cup B = \#A + \#B - \#(A \cap B)$.
\item Properties of countable sets, including:
\begin{itemize} 
\item a countable union of countable sets is countable; and
\item  the cartesian product of two countable sets is countable.
\end{itemize}
\item $\natural$, $\integer$, and $\rational$ are countable, but $\real$ is uncountable.
\item The power set $\power(A)$ has larger cardinality than $A$, for any set $A$.
\item Notation:
\begin{itemize}
\item $\# A$
\item intervals $(a,b)$, $[a,b]$, $[a,b)$, $(a,b]$
\item power set $\power(A)$
\end{itemize}
\end{summary}



 