The Cantor Set
Författare
Andy
Last Updated
för 8 år sedan
Licens
Creative Commons CC BY 4.0
Sammanfattning
An overview of the Cantor Set and its connection to counting.
An overview of the Cantor Set and its connection to counting.
\documentclass{tufte-handout}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{units}
\usepackage{fancyvrb}
\fvset{fontsize=\normalsize}
\usepackage{multicol}
\usepackage{lipsum}
\newcommand{\doccmd}[1]{\texttt{\textbackslash#1}}
\newcommand{\docopt}[1]{\ensuremath{\langle}\textrm{\textit{#1}}\ensuremath{\rangle}}
\newcommand{\docarg}[1]{\textrm{\textit{#1}}}
\newenvironment{docspec}{\begin{quote}\noindent}{\end{quote}}
\newcommand{\docenv}[1]{\textsf{#1}}
\newcommand{\docpkg}[1]{\texttt{#1}}
\newcommand{\doccls}[1]{\texttt{#1}}
\newcommand{\docclsopt}[1]{\texttt{#1}}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{morefloats}
\setkeys{Gin}{width=\linewidth,totalheight=\textheight,keepaspectratio}
\graphicspath{{graphics/}}
\usepackage{hyperref}
\hypersetup{colorlinks=true,urlcolor=ProcessBlue}
\usepackage{parskip}
\title{Day 1: The Cantor Set\thanks{Part of a year-long journey to learn one thing a day.}}
\begin{document}
\maketitle
\setlength{\parindent}{0in}
\section{Introduction}
The Cantor Set is remarkable because it only takes a line and some imagination to create. With simple tools, one can find out whether we can actually count every number from 0 to 1.
The set is formed by repeatedly cutting a line. The name for a process like this is a "finite subdivision rule". The goal of such a rule is to systematically divide a shape into smaller, more interesting pieces. One of my favourite examples of this is the Sierpinski triangle, generated by cutting out triangles from a triangles.
\begin{figure}[!h]
\includegraphics{Sierpinski_triangle_evolution.png}
\caption{Pretty things happen when you remove stuff systematically.}
\label{fig:Sierpinski_triangle_evolution}
\setfloatalignment{b}
\end{figure}
By applying rules, you can generate other amazing fractals, and cool stuff like \href{https://en.wikipedia.org/wiki/Fractal_landscape}{mountains}.
\section{Making the Set}
\begin{enumerate}
\item Take a line from 0 to 1, and split it into thirds\footnote{We don't need to choose thirds, but that is a common choice. We will focus on the points from 0 to 1, but any line works.}.
\item Delete everything in the middle, from 1/3 to 2/3, but keep the ends (just because).
\item Do this again to the remaining pieces, and again, and again.
\end{enumerate}
\begin{figure}[!h]
\includegraphics{Cantor_iterations.jpg}
\caption{A few iterations. Each time you could zoom in and start all over with a smaller line.}
\label{fig:Cantor_iterations}
\setfloatalignment{b}
\end{figure}
That's it.
\section{What's Left?}
We cut a line into smaller lines and those lines into smaller lines. So what? Well, let's start with the fact that after many iterations, there is no length left on the line:
\begin{itemize}
\item We started by cutting out 1/3.
\item Then we cut the two remaining segments by 1/3 of their length. That's two times 1/9.
\item Then we cut the two remaining segments from those two remaining segments by 1/3 of their length, which is four times 1/27.
\end{itemize}
See the pattern? In total we have: Stuff Cut Out \(= \frac{1}{3} + \frac{2}{3^2} + \frac{2^2}{3^3} + ...\)
Which is a geometric series: Stuff Cut Out \(= \frac{1}{3}(1 + \frac{2}{3} + \frac{2^2}{3^2} + ...)\)
So we can use a handy formula: Stuff Cut Out \(= \frac{1}{3}(1 + \frac{1}{1-\frac{2}{3}}) = 1\)
Is there nothing left after infinite iterations? Not quite. Remember we decided to include the end points ("just because"). Take 1/3, for example. Once we cut the line there, there is no way the "middle" of any future line will ever be 1/3. We know 1/3 will always be the end of a line. The same logic applies to other ends.
So we have points. But in fact we have more than just end points. That part isn't easy to see, but we're going to work at it.
\section{Sorcery}
Let's start counting things. What is remarkable about the Cantor Set is that there are as many numbers left behind as there were to begin with.
Does that sound impossible? You might have heard before that the numbers between 0 and 1 are not "countable," but what does that really mean? Hopefully we understand that more tangibly by working with this set.
The plan is to show that any number left over can be mapped back to a number we had to begin with.
If we can always provide a number from the Cantor Set to find a number that we originally had, we must have the same amount of numbers in total. But if that's the case, there is some sort of contradiction in terms of ordinary common-sense counting and the numbers are said to be "uncountable".
\section{Review}
Before we go deeper, you should look up what it means to write a number in a different base.
\section{Number Crunching Time}
We are going to use base 3 notation (ternary) to quickly summarize what gets deleted in an iteration.
Let's start in the first iteration. The end point 1/3 written in ternary is \(0.1_3\) because it is one times the first negative exponent of three. Similarly, 2/3 is twice that: \(0.2_3\).
By removing the middle third in the first iteration, we are removing the numbers between 1/3 and 2/3. In ternary, we are removing numbers that are bigger than \(0.1_3\) and less than \(0.2_3\). In other words, we remove any number that has 1 in its first decimal place in base 3 (except 1/3, which can also be written without a 1 as \(0.0222..._3\)).
Here are some examples of numbers we remove:
\(0.11_3, 0.12_3, 0.121_3, 0.122_3\)
We now have two lines remaining. The lines are a third of the length of the original line. This means any cutting that happens will now occur one decimal down in ternary.
Let's just focus on the first line from 0 to \(0.1_3\). Anything that is true about that line should be true for the other line from \(0.2_3\) to 1, since they are just translations of each other being cut in the exact same way.
The line from 0 to \(0.1_3\) is cut at a third of a third, or \(0.01_3\) in ternary. It is also cut at the point twice that: \(0.02_3\).
Again, by the same way of thinking, the terms with 1, now in the second decimal place, will be removed. We remove anything between \(0.01_3\) and \(0.02_3\).
For the other line from \(0.2_3\) to 1, the same logic applies at the second decimal place. That is, we remove anything between \(0.2 + 0.01_3\) and \(0.2 + 0.02_3\)
This can continue forever. Try it out yourself!
\section{Going Back Up a Level}
We now have a convenient way of describing any number in our set: it must consist entirely of 0s and 2s in ternary (end points can be represented with never-ending 2s if needed).
With only these numbers, we can find any number we originally had in the following way:
\begin{itemize}
\item Take any number between 0 and 1.
\item Its binary representation consists of 0s and 1s.
\item Take any code of 0s and 1s and switch 1s to 2s.
\item Since we have all numbers with 0s and 2s, we have just as many numbers, just coded differently.
\end{itemize}
This shows that there are as many points in the original line as there are in its sliced up set. Since this is not normal, the numbers must be uncountable.
On the other hand, we definitely can count how many end points we had, since it is just the number of iterations we applied times 2. This means that there are far more - in fact an uncountable amount more - numbers in the Cantor Set which are not end points at all!
\section{Conclusion}
The Cantor set has as many points as the interval it was made from, yet it contains no interval with length!
Thanks for joining me for Day 1.
\end{document}