Cantor Can!

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\celsius }[0]{} \newcommand {\degree }[0]{} \newcommand {\ohm }[0]{} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\tri }[0]{\triangle } \newcommand {\l }[0]{\ell } \newcommand {\P }[0]{\mathcal {P}} \newcommand {\R }[0]{\mathbb {R}} \newcommand {\Q }[0]{\mathbb {Q}} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\N }[0]{\mathbb N} \newcommand {\ph }[0]{\varphi } \newcommand {\vec }[0]{\mathbf } \newcommand {\d }[0]{\,d} \newcommand {\egmil }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_person.pdf}\hspace {0.5mm}}} \newcommand {\eghuntho }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_fish.pdf}\hspace {0.5mm}}} \newcommand {\egtentho }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_finger.pdf}\hspace {0.5mm}}} \newcommand {\egtho }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_lotus.pdf}\hspace {0.5mm}}} \newcommand {\eghun }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_scroll.pdf}\hspace {0.5mm}}} \newcommand {\egten }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_heel.pdf}\hspace {0.5mm}}} \newcommand {\egone }[1]{\multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_stroke.pdf}\hspace {0.5mm}}} \newcommand {\egyptify }[7]{ \multido {\i =1+1}{#1}{\includegraphics [scale=.1]{egyptian/egypt_person.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#2}{\includegraphics [scale=.1]{egyptian/egypt_fish.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#3}{\includegraphics [scale=.1]{egyptian/egypt_finger.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#4}{\includegraphics [scale=.1]{egyptian/egypt_lotus.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#5}{\includegraphics [scale=.1]{egyptian/egypt_scroll.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#6}{\includegraphics [scale=.1]{egyptian/egypt_heel.pdf}\hspace {0.5mm}} \multido {\i =1+1}{#7}{\includegraphics [scale=.1]{egyptian/egypt_stroke.pdf}\hspace {0.5mm}} \hspace {.5mm} } \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\degree }[0]{\ensuremath {^\circ }} \newcommand {\celsius }[0]{\ifmmode ^\circ \mathrm {C}\else $^\circ $C\fi } \newcommand {\ohm }[0]{\ifmmode \Omega \else $\Omega $\fi } \newcommand {\arraystretch }[0]{3}$

In this activity we look at Cantor’s diagonal argument.

It took until the 1700’s to get algebra and number systems in place in a workable way. But there was still trouble understanding what infinity was. Was the set of counting numbers really infinite, or was it only as big as the highest number that anyone had ever counted, or as big as the number of atoms in the universe, or…? But even if the set of counting numbers was infinite, then the set of real numbers was also infinite. But then again, were they the same infinity? Some math grad student in Germany around 1850 shocked the math world by saying ‘no.’

Here is a table of rational numbers: ${\renewcommand {\arraystretch }{3} \begin {array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \cdots & -5 & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & \cdots \\\hline \cdots &\frac {-5}{2} & & \frac {-3}{2} & & \frac {-1}{2} & & \frac {1}{2} & & \frac {3}{2} & & \frac {5}{2} & \cdots \\\hline \cdots & \frac {-5}{3} & \frac {-4}{3} & & \frac {-2}{3} & \frac {-1}{3} & & \frac {1}{3} & \frac {2}{3} & & \frac {4}{3} & \frac {5}{3} & \cdots \\\hline \cdots & \frac {-5}{4} & & \frac {-3}{4} & & \frac {-1}{4} & & \frac {1}{4} & & \frac {3}{4} & & \frac {5}{4} & \cdots \\\hline \cdots & & \frac {-4}{5} & \frac {-3}{5} & \frac {-2}{5} & \frac {-1}{5} & & \frac {1}{5} & \frac {2}{5} & \frac {3}{5} & \frac {4}{5} & & \cdots \\\hline & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\\hline \end {array}}$

(a): What does the 12th row of the table look like?
(b): Name three different rational numbers. Will they (eventually) appear on the table?
(c): Will every rational number eventually appear in the table above?
(d): Can you figure out how to “enumerate” the rationals?

The question: Are the set of counting numbers and the set of real numbers between $0$ and $1$ the same size?

Cantor’s answer: Suppose they were, then you could make a one-to-one, onto match-up:

$\begin{align*} 1 &:0\,.\,2\,2\,3\,4\,3\,7\,9\,8\,7\,8\,4\,\dots\\ 2 &:0\,.\,8\,5\,9\,8\,4\,7\,5\,9\,3\,4\,8\,\dots\\ 3 &:0\,.\,1\,1\,2\,9\,0\,2\,9\,3\,9\,8\,0\,\dots\\ 4 &:0\,.\,0\,3\,4\,3\,2\,3\,4\,0\,5\,6\,3\,\dots\\ 5 &:0\,.\,9\,3\,9\,2\,8\,4\,9\,8\,2\,3\,9\,\dots\\ 6 &:0\,.\,7\,9\,7\,8\,8\,9\,3\,7\,8\,3\,3\,\dots\\ &\;\vdots \end{align*}$ So, you think you did it, eh? I will find a real number between zero and one that is not on your list. How will I do it?

Explain why the same argument does not show that the rationals cannot be enumerated.

Is the cardinality of $\mathbb {R}$ equal to the cardinality of $\mathcal {P}(\mathbb {Q})$ ?