Previously, I discussed how the algebraic numbers are countable, meaning there are equally as many of them as natural numbers, in the technical sense that you can define a bijection between the two. (In the sense that the natural numbers are a proper subset of the algebraic numbers, there are fewer of them, but mathematicians rarely use this criterion as a method of counting the size of infinite sets).
It is common knowledge (at least in certain circles) that the real numbers are uncountable, and this is commonly explained using Cantor’s diagonal argument(Wikipedia). In this post, I’d like to get a better idea of how many real numbers there are, other than “uncountably many”.
Let’s begin by thinking about real numbers as decimal expansions. We’ll agree to write the real number in scientific notation. That way, we represent it by an ordered pair of an integer (for its exponent) and an infinite list of digits (for the digits of the decimal expansion). So, for example, the real number could be represented by . This is the representation of real numbers I want to begin with.
The goal is to form a bijection between these real numbers and something easier to understand. That thing will be an infinite list of bits.
We’ll begin by making a bijection between infinite lists of digits and infinite lists of bits. By this I mean that we want to turn an infinite list like into a list of ones and zeroes, like .
For this step, we make the following correspondence:
To turn a list of digits into bits, simply find the corresponding sequence of bits for the first digit and write them out as the first three or four entries, and repeat for the second, third, etc. digits. To turn a list of bits into digits, take the first three or four bits (whichever appears on the list) and write down the corresponding digit. Then take the next three or four bits, etc. For example, the list becomes , and the list becomes . This defines a bijection between lists of digits and list of bits.
What I actually wanted, though, was a bijection between lists of bits and real numbers. Lists of bits are very simple, so it would be nice to study them rather than lists of digits with an integer stuck on. We have the digits nailed down, but left out the integer. There is a standard bijection between lists of digits and integers, called the binary representation of the integer. For example, in binary . Working from right to left and adding infinitely-many leading zeroes (which, when working from right to left, come at the end), we could write where all the rest are zeroes. This forms a bijection from integers to lists of digits.
So a real number is an integer plus a list of digits. We have a bijection from lists of digits to lists of bits, and one from integers to lists of bits. So, if we can just find a bijection from two lists of bits to lists of bits, we’ll have (by composition of functions) a bijection from lists of bits to real numbers. But this bijection is trivial – all the odd numbered entries in the list correspond to one infinite list of bits, and all the even entries correspond to another. Therefore, we can make a bijection from the real numbers to infinite lists of bits.
So how many infinite lists of bits are there? For a finite list length , there are possible lists of bits, corresponding to the numbers that can be represented by that many digits in binary. So for a list of digits of infinite length, we could write the size as .
One thing to note is that this is the same as , or any other base to an infinite exponent, since we could equally well have used lists with more digits than just one and zero, so for natural numbers .
The lists of bits are nice because there is a simple way to view them in terms of the natural numbers. For a given infinite list of bits, each entry on the list corresponds to a certain natural number – there is a first entry, a second entry, a 9831st entry, etc. Then we get one bit of information about each natural number. One way to interpret a bit is: Do you get to play on the team (yes or no)?
Each infinite list of bits (and hence each real number) can correspond to a possible team of natural numbers. The list with all zeroes is the team with nobody on it. The list with all the rest zeroes is the team with two and five and nobody else. The list with all ones is the team where everyone gets to play. These teams are mathematically subsets. All the possible teams are there in the set of all lists of bits, so we’re looking at the set of all subsets of the integers. This is called the power set. What we’ve done is create a bijection between the real numbers and the power set of the integers, and we’ve said they both have a size .
Because the real numbers are uncountable, so is the power set of integers. The cardinality of these sets is represented by , while the cardinality of the integers is represented by , so we have the strange-looking equation .
Interestingly, the cardinality of the plane, or by induction higher-dimensional spaces, is the same as that of the reals. So you can form a bijection between the two (an easy way to do it is by alternating decimals, similarly to the way we used one list of digits to represent two lists of digits). However, that doesn’t mean you can think of space as one-dimensional, because these bijections don’t preserve topology. Points that are next to each other in the plane won’t be next to each other when you’ve mapped them on the line (more technically, open balls don’t map to open balls, but again I don’t know a proof of why this is impossible).
One further fact, which I also do not understand, but which I get from the reputable source of books and things, is that there are no possible in-between cardinalities. That means any set is either smaller than the integers (in which case it will be countable – there are no infinities smaller than the integers), the same size as them, larger than them but the same size as the reals, or larger than the reals. You can’t find an infinity bigger than the integers and smaller than the reals. Drop me a line if you understand that one.
Note: one small technical difficulty is that the mapping from real numbers to decimal expansions is itself not a true bijection, because for example . It’s not going to keep me up at night though. A deadly fear of snakes crawling through my window already does that.