Season 2 Episode 10

In this episode, James defines what it means for a set to be countable, and proves that we can't describe most of the numbers.

Squash Function

Sometimes the world of countability can feel quite vague and confusing, so let’s try and make things a bit more precise. Halfway through the livestream, there was an idea for getting all the people from infinitely many coaches (one coach for each positive whole number), where each coach has infinitely many seats (one seat for each positive whole number), into Hilbert’s hotel, which has one room for each positive whole number.

There were at least two suggestions for ways to do this in the livestream, and we can write down formulas for them using algebra; we’ll use the letter $x$ for the seat number and the letter $y$ for the coach number, so that each person arrives at the hotel with a pair of positive whole numbers $(x,y)$. We’re looking for a function (some sort of rule) that takes in both numbers and gives out one number- it would look like $f(x,y)=z$ where $z$ is something complicated to do with $x$ and $y$. The important thing that we want is for nobody to be sent to the same hotel room as anyone else, and we can write that in mathematical terms by saying that we want the following property to hold; \begin{equation*}
\text{If }\quad f(x,y)=f(u,v)\quad\text{then}\quad x=u \quad \text{and} \quad y=v.
\end{equation*}

That might look like a slightly strange way to phrase it, but it does work! Maybe you can think of a different equivalent way to write this.

One of the suggestions from chat was to use the prime numbers. If we take the $x$th prime number to the power of $y$, then we can’t get the same number two different ways, because prime factorisation is unique. We might write that as $f(x,y)=\left(p_x\right) ^y$ where $p_x$ is the $x$th prime number. That works, but I think it made some people nervous because there isn’t a nice neat formula for the $x$th prime number (there definitely is a millionth prime number, but it’s complicated to work out exactly what it is).

Another suggestion was to draw diagonal lines on the grid of people, and work along the diagonal lines giving each person a number as we go along. This is a nice description, and it does work, but I thought it might be useful here to turn that into a tidy formula. I can use what I know about triangle numbers to work out what number will be given to each person, and I get \begin{equation*}
f(x,y)=\frac{(x+y-1)(x+y-2)}{2}+x
\end{equation*}(if you want to try and re-create this formula, note that I’m working along the diagonal lines with $x+y$ constant, using a formula for the triangle number of people in the previous diagonal lines, and I’m working along each line in the same direction because it makes the formula nicer).

That formula also has “if $f(x,y)=f(u,v)$ then $x=u$ and $y=v$", but that’s much harder to check if you don’t know where the formula came from.

You might like to try and invent your own function here, perhaps using a different argument, or perhaps inspired by the relatively nice property that we want $f(x,y)$ to have.

More dimensions

On the livestream, I tried to talk about a 3D version of this problem where people arrive on coaches in a multi-storey carpark, so they have coordinates $(x,y,z)$ and we’re looking for a new function that takes all three coordiantes and returns a single number. People suggested some clever things with primes or spirals, but here’s a different approach – the squashing that I tried to describe. If we start with a 3D grid of people with coordinates $(x,y,z)$, then we can give each person the room number $ f(f(x,y),z)$ where $f(x,y)$ is any function that we used in the previous 2D problem! Once we’ve had this idea, it’s not too hard to do the 4D version of the problem with $f(f(f(x,y),z),w)$ and the 5D version of the problem and so on. Mathematicians love finding this sort of way to recycle content by reducing the problem to something we've done before.

Infinity is weird

Someone asked a really good question; can we do infinity dimensions? The answer is actually “no, that’s uncountable”, which might be a bit surprising; after all, I just said that we can do the 4D version, the 5D version, “and so on”. Doesn’t that mean we can do “infinity”-D? The difference is very subtle here (it’s to do with whether the coordinates to specify where someone is “end” or not – whether they’re like words or like snakes). In general, you should watch out for the difference between “true for any large number $N$” and “true when $N$ is infinitely large”. Consider the problem of organising a tennis tournament where one game is played at a time and one player is knocked out of the tournament in every game. Now for any large number $N$, I can organise a tournament which will end in finite time with a winner. But if $N$ is infinitely large, then I cannot organise a tournament which will end in finite time (I’ve got Wimbledon on the mind, sorry).

Books

Lots of books have been written about infinity – you might like Ian Stewart’s “Taming the Infinite” or John D Barrow’s “The Infinite Book: A Short Guide to the Boundless, Timeless and Endless”.

Curve sketching

The floor function $[x]$ is defined as the largest whole number that’s less than or equal to $x$, so $[3.2]=3$ and $[-4]=-4$. Sketch
\begin{equation*}
y=[x],\quad\text{and}\quad y=[10 x] /10 , \quad\text{and}\quad y=[100 x]/100.
\end{equation*}

If you draw in little vertical lines where the function jumps up in value, then you get little pictures of staircases, and you’ve drawn a line from $(0,0)$ to $(1,1)$. What’s the length of the line in each case? What if I change the number 100 to one thousand or to one million? Comment on the difference between “true for any large number $N$” and “true when $N$ is infinitely large”.

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.