Enumerating the rationals

Over on Unity Of Truth my friend Electroblogster asked about Cantor, a 19th century mathematician, and his demonstrations regarding "infinity". I do not have the books with me, and I only have a short between steps of my current work project, so I cannot talk about this at my usual length.

But first I must quote Chesterton, because once we start talking about infinity, there is a certain quote which we must always recall, whether we are mathematicians, computer scientists, theologians, philosophers, or just simple students:

Poetry is sane because it floats easily in an infinite sea; reason seeks to cross the infinite sea, and so make it finite. ... To accept everything is an exercise, to understand everything a strain. The poet only desires exaltation and expansion, a world to stretch himself in. The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits.
[GKC, Orthodoxy CW1:220]

So, perhaps I should write a poem, rather than explaining! (Maybe over the weekend.)

OK, the question (as I understood Electroblogster to ask) is: Are there as many RATIONAL numbers as integers?

Note: this is NOT the famous question answered by Cantor, but it leads up to that one, and if this seems hard to understand, the other one will be somewhat harder.

Second note: I must remind you that this is NOT a matter of "belief" - it is just a bit of mathematics. You can probably find it explained better by somebody who does this for real, no pun intended!

Remember, a rational number is just what some of us call a fraction - you know, we say "something over something" - but we don't mind whether it might also be a WHOLE number, too: like say "six over two" which is really three. We just need the idea that there are two whole numbers, and neither one is zero (positive, nonzero integers).

Now, if we want to show that two things are the same size, we have to show that they are in one-to-one correspondence. A nice way is to make a list of the pairs of things. So that is what we'll do. We'll make a list of all the INFINITE rationals, and show that it's just as long as the INFINITE list of whole numbers!

Do you think God will mind us borrowing eternity just to do this? No, we don't need that long. And you won't have to buy a bigger disk drive, either!

Here's how we make the list. You can do this on your own piece of paper at home. (No, not an INFINITE piece of paper, silly!) Let's just go up to six for now, and you will understand the rest. Make a kind of big tic-tac-toe diagram, but with six columns and six rows. Then across the top, put 1,2,3,4,5 and down the side put 1,2,3,4,5. Hopefully you will have something like this:

row/col	1	2	3	4	5	6
1	_	_	_	_	_	_
2	_	_	_	_	_	_
3	_	_	_	_	_	_
4	_	_	_	_	_	_
5	_	_	_	_	_	_
6	_	_	_	_	_	_

Now, each of those boxes stands for a RATIONAL NUMBER - because there is JUST ONE pair of numbers, the row (on the left) and the column (on the top) which means that rational number for that box is (row over column). Here, I will fill part of it in, so you can see:

row/col	1	2	3	4	5	6
1	1/1	1/2	1/3	1/4	1/5	1/6
2	2/1	2/2	2/3	2/4	2/5	2/6
3	3/1	3/2	3/3	3/4	3/5	3/6
4	4/1	4/2	4/3	4/4	4/5	4/6
5	5/1	5/2	5/3	5/4	5/5	5/6
6	6/1	6/2	6/3	6/4	6/5	6/6

OK! so there we have our rational numbers. Now if we had that infinite paper, and God let us use eternity to fill it in, we would have them all listed. (But we don't have to bother. There is a good math reason for this, too, which is called "mathematical induction" and someday I will talk about that too. But again it is NOT about "faith" it is mathematics. You can trust me on this. ... wait, maybe it is about faith! So Chestertonian!!!)

OK, now we need to see that there are just as many boxes with all the RATIONAL numbers as there are integers.

And you throw up your hands and say HOW CAN THAT BE? There are LOTS more boxes than integers - if there are "infinite" boxes in one row, there must be "infinity squared" in the whole table!

And I say, no, there are just as many - because I can give you a list which links EACH box to JUST ONE integer, and none left over!!!

You get one chance to think it out for yourselves... and then I will tell you how to do it.

While I wait for you to try to get the answer, I'll just quote a relevant Chesterton poem, which is one of my very favourites:

"Eternities"

I cannot count the pebbles in the brook.
Well hath He spoken: 'Swear not by thy head,
Thou knowest not the hairs,' though He, we read,
Writes that wild number in His own strange book.

I cannot count the sands or search the seas,
Death cometh, and I leave so much untrod.
Grant my immortal aureole, O my God,
And I will name the leaves upon the trees.

In heaven I shall stand on gold and glass,
Still brooding earth's arithmetic to spell;
Or see the fading of the fires of hell
Ere I have thanked my God for all the grass.
[GKC, CW10:209]

OK, here's the answer:

You start in the upper left with one. Then to its right put two. Go down one, and left one, and put three. Then, go back to the top row, and put four; then left-down, five; left-down, six. Back to the top: seven; left-down, eight; and so forth. Got it? OK, here is what the table looks like when you fill it in that way:

row/col	1	2	3	4	5	6
1	1	2	4	7	11	16
2	3	5	8	12	17	23
3	6	9	13	18	24	31
4	10	14	19	25	32	40
5	15	20	26	33	41	50
6	21	27	34	42	51	61

So! you see there is just ONE box related to every integer - OH! but that means "infinity squared" is NO BIGGER than infinity!!

Exactly. You need to do something a little more tricking if you want "a bigger infinity"!

Yes, this is funny to think about when one knows God - because He is real, and has all these other amazing properties, like love, and kindness, and justice and mercy, which no conceivable set of numbers can ever have.

So we have seen that the RATIONALS are "enumerable" - there are "as many" fractions are there are "whole numbers" - even if that sounds kind of funny. But there are lots of other numbers besides fractions, though some are very hard to talk about. But that's enough for today.