## Sunday, June 4, 2017

### A tale of a tangle

At the early stages of mathematics, things are all very satisfying. At first you don't understand something, then you think about it, and solve problems, and think about the problems (rinse and repeat), and after a while you do understand it. But as you progress, you realise that you often go back to these things that you already understood and find that there's a whole new layer of understanding that you didn't previously realize you lacked, and a whole new bunch of thinking and understanding to do.

In a previous blog, I argued that the lack of a clear agree notion of the real numbers is one of the problems in providing a convincing argument that $$0.\dot{9}=1$$. This time I want to present some evidence that even after we agree on what the real numbers are, there are still some surprises in store, even (or especially) regarding some quite fundamental properties.

How the rational and irrational numbers fit together is something which gives me the feeling that the harder I think about it, the less I understand it.

# Rational and irrational

For many, one of the first big mathematical surprises we meet as students is that there is the same number of rational numbers in the interval $$[0,1]$$ as there are positive integers (so we call that set countable), but that there are more real numbers (and therefore more irrational numbers) then there are rational numbers (so we call that set uncountable).

Both arguments are very familiar, but each is interesting in itself, so let's recall them briefly.

First, we can explicitly list the rational numbers in $$[0,1]$$, as follows: for each denominator $$n \geq 1$$, list the rational numbers $$0/n,1/n\ldots n/n$$, and build a list of each such group, in order of increasing $$n$$. Then remove from the list any fraction which reduces to an earlier one in the list. We now have a list which contains all the rational numbers in $$[0,1]$$, and so a bijection between $$\mathbb{N}$$ and this set. So there are the same number of rationals in $$[0,1]$$ as there are natural numbers.

On the other hand, it is impossible for a list of real numbers to include all of them.

The proof of this relies on Cantor's wonderful diagonalization argument. First, we have to get a slightly awkward detail out of the way: any number whose decimal expansion eventually terminates can also be represented by a decimal which ends in an infinite string of 9's. We agree to use the version which terminates whenever this choice arises, and now there is a unique decimal representation for every real number.

Now suppose we have an infinite list of real numbers in $$[0,1]$$ (or rather, their decimal representations). We build a real number by looking at the $$n$$th decimal digit of the $$n$$th number in the list: if it is anything but a $$1$$, we replace it by a $$1$$, and if it is a $$1$$, we replace it by a $$0$$. This real number cannot be the first number in the list, because the first digits are different; it cannot be the second, because the second digits are different; and so on. Obviously, this real number cannot be any number in the list.

This tells us that whatever infinite list of real numbers we consider, it cannot include all the real numbers in $$[0,1]$$. So there are more real numbers in $$[0,1]$$ than there are rational numbers, even though both sets are infinite. This has been known to cause an unpleasant reaction in some people, but there really isn't any avoiding it without performing some fairly radical surgery on the basic ideas of mathematics. (To be fair, that's just the route that some people have gone down, including perfectly respectable mathematicians. You can reject the notions of infinite sets and irrational numbers entirely, and work with what's left. But let's stick with normal mathematics here.)

It doesn't quite get us what I claimed though: I claimed that there were more irrationals than rationals. All I know so far is that by taking the total collection of rationals and irrationals, I get a collection with more numbers than just the rationals. But that last step's not hard to see. If the irrationals were in fact countable, we could just make a list of all the real numbers by interleaving the rational and irrational numbers, and that would mean the set of real numbers was countable after all.

So there's no doubt: the irrational numbers are uncountable, and therefore there are definitely more irrational numbers than rational numbers.

# A complicated arrangement

The arguments above, though they're commonplace and almost universally accepted now, caused quite a stir to begin with, and a certain amount of mathematical feuding. But interesting though it is to see that infinite sets aren't necessarily the same size, it only scratches the surface of some stuff that I find pretty mysterious.

Bizarrely, not only are there more irrationals than there are rationals, but the rationals don't take up any room.

That's worth thinking about. We know that no matter how small a subinterval of $$[0,1]$$ we choose, there are infinitely many rational numbers in there; and likewise, there are infinitely many irrational numbers in there. Both sets of numbers are dense in $$[0,1]$$. So how can the rational numbers not be taking up any space?

It has to do with the mysterious way that the rational numbers and the irrational numbers are arranged to make the real line.

We can see that the rational numbers take up no space by showing that no matter how small a positive number, $$\epsilon$$, we choose, we can fit all the rational numbers into a region of size less than $$\epsilon$$. So, back to our list of rational numbers. Around the $$n$$th rational number in the list, we put an interval of width $$\epsilon/2^{n}$$. Call this collection of intervals an $$\epsilon$$-covering of the rationals. Every rational number is in at least one of the intervals, and since every interval contains infinitely many rational numbers there will be lots of overlaps. Therefore the total amount of space required to put all the rational numbers into these intervals is less than $\epsilon\sum_{n=1}^\infty \frac{1}{2^n} = \epsilon.$

It follows that the rationals can't actually take up any space at all. Those intervals, of total size less than $$\epsilon$$, include all the rational numbers, but miss out at least $$1-\epsilon$$ of the stuff in $$[0,1]$$, and we can choose $$\epsilon$$ as small as we like.

So how does that work?

I can't see it. The rationals are dense, so there's a finite interval around every one of a dense set of points. And yet the total amount of space taken up by these can be made smaller than any positive number you choose. What's missed out of the intervals? It's a set of irrational numbers that can't include any intervals at all, because any interval would contain a rational number. And yet the set of irrational numbers that's omitted by an $$\epsilon$$-covering of the rationals takes up at least $$1-\epsilon$$ of the space in $$[0,1]$$.

It is tempting to think that this is because there are so many more irrationals than there are rationals: naturally they take up much more of the space. But this isn't it. There are uncountable subsets of of reals that also take up no space. The Cantor set (yes, same Cantor) is probably the best-known example.

I don't have any kind of handle on how this all fits together. I have no feel for how what's left behind when you remove countably many intervals can be uncountable many irrationals, all separated by what has been removed, but nevertheless occupying almost all the space. I think it's saying something quite deep about the structure of the real line, but I don't know what.

Yet.