Some Infinities Are Bigger Than Others

This post is dedicated to RA and this meme he sent me. This post is a little longer than usual, but hopefully it seems small in proportion to its topic.
 

In The Fault In Our Stars, Hazel-Grace boldy proclaims that "some infinities are bigger than others" citing the fact that there are more numbers between 0 and 10 than between 0 and 1. If I were marking her work then she would get a drawing of a donut because, although her conclusion is correct, she used woefully misinformed reasoning to reach it. Let's dig in.

We first need to understand how we might establish that 2 sets have the same size without being able to count them. I'm going to refer to it as labelling: if I can label every number in my set with a positive whole (i.e. natural) number and every label gets used then I can conclude that there my set of numbers has the same size as the set of natural numbers. [strictly speaking I want a bijection]. The first example which suggests that we must abandon intuition is the fact that there are the same number of even numbers as whole numbers. Firstly it really feels like there are more whole numbers than even numbers. But equally there are infinitely many of each and all infinities are the same size, right? To avoid both these blunders we must be more precise: each even number can be labelled with a natural number equal to half of it: 2 is labelled by 1, 4 is labelled by 2 and so on. We need every natural number to finish the labelling so these sets must be the same size! Likewise we can do the same for the square numbers: label 1 with 1, label 4 with 2, label 9 with 3 and so on.

That method allows us to make a definition: a set is countably infinite if it can be labelled using the natural numbers. This is exemplified by Hilbert's paradox of the Grand Hotel. If we have a hotel with rooms number 1, 2, 3,.. and so on ad infinitum then how could we possibly fit more guests? If a finite number of guests, say n, arrive then everyone just shifts up by n rooms, leaving the first n rooms free for occupation. Now if the nextdoor hotel that also has rooms labelled 1,2,3,.. has an ant infestation then our hotel can easily accomodate them: everyone just moves to double their room number, so that each of the infinitely many guests has their neighbouring room unoccupied. We could even accomodate the arrival of a countably infinite number of coaches, each carrying a countably infinite number of guests, but that's covered in the wikipedia article.

I hope that provides a little intuition around countable infinities. We're happy that there's an infinite number of numbers between 0 and 1. But it turns out that there is no way to label all the points between 0 and 1 and so while there is an infinite number, it is called an uncountable infinity. You might like to think of this as meaning there are "no gaps" between the points and I won't stop you doing that. But our labelling method is still valid for uncountable infinities: I can take every number between 0 and 1 and multiply it by 10 to get a number between 0 and 10. Likewise I can take every number between 0 and 10 and divide it by 10 to get a number between 0 and 1. Therefore there must be the same number of numbers in each set. We would say that there is a continuum of points between 0 and 1 and that characterises the uncountability. An interesting open problem in maths is called the Continuum Hypothesis: there is no size of infinity between the countable and the uncountable. I hope that explains the meme. 

[The "no gaps" thing isn't really rigorous but I don't have a better way to provide intuition: the seemingly contradictory fact is that the set of fractions (i.e. the rational numbers) is countable, with the labelling demonstrated in the diagram below. However they are also dense in the reals, meaning that I can find a rational number as close as I like to any real number. The notion of a countable, dense subset is counterintuitive and makes the real numbers separable. But a dense set need not be countable, as there is still some notion of the rational numbers having "gaps": I can take a sequence of rational numbers which tends to an irrational number, meaning the rationals are not complete. I hope this demonstrates that intuition must be abandoned, especially when dealing with beasts such as the middle third Cantor set.]