Today’s Monday Morning Math was suggested by Justin, one of our Math Club Officers! He requested a MMM about the fact that there are the same number of rational numbers and integers, because that’s that is really awesome. Great idea Justin!

The idea behind this is that when we talk about infinite sets, we say that they are the same size if there is a bijection between them (a function that is one-to-one and onto – that is, it exactly matches each object in the first set with an object in the second set). This leads to weird things, for example, like that there are the same number of integers as even integers. This is because the function:

f(n)=2n

exactly matches each integer to a unique even integer, so the two sets (integers and even integers) must have the same size. Which is weird, because half the integers are even, so you’d expect there to be twice as many integers as even integers. Infinity is weird.

But finding a map between the integers and the rational numbers is not trivial. One way to think about it is to put the numbers in each set in some sort of order, where if you count them, and you have a lot of time on your hands, you know you’ll reach each number in the set. For the integers it’s not too bad – you could count:

0, 1, -1, 2, -2, 3, -3, …..

but then the rationals are sneaky. How do you even put fractions in order? One way is to look first at the positive fractions and find a way, and there’s a pretty picture here of how to do that

So we could list the numbers as:

1/1, 2/1, 1/2, 1/3, (then skip over 2/2 because that’s the same as 1/1), 3/1, etc. If you look at the way the picture weaves back and forth, you will eventually list every positive rational number.

That gets us the positive rational numbers, and to get the rest we could alternative positive and negative, the way we did with the integers! So our listing would be:

0, 1/1, -1/1, 2/1, -2/1, 1/2, -1/2, etc.

Then, since you can list all the integers in an order, and you can list all of the rational numbers in an order, then you can match the first numbers in each list, the second in each list, etc. and see that there are the same number of integers as rational numbers!

Fun fact – we posted about infinities on our unofficial department blog back in 2008. I notice that a lot of those links are broken, but I’ll quote part that isn’t. Happy infinity!

[Digression: for a cool description of the countability of the rationals, read Recounting the Rationals, part I and Recounting the Rationals, part II (fractions grow on trees!) at The Math Less Traveled, which is an exposition of the paper

Recounting the Rationalsby Neil Calkin and Herbert Wilf.)