A Most Merry and Illustrated Proof of Cantor's Theorem on the Countability of Rational Numbers

A Most Merry and Illustrated Proof of the Unintuitive

(Concise Version)

 

George was not being irrational.

CooperToons has posted samples of proofs for the diagonal argument proving there are more real numbers than counting numbers and also that the number of counting numbers (1, 2, 3, 4, ... ) is the same as the number of integers ( ..., -3, -2, -1, 0, 1, 2, 3, ... ). Both theorems were first proven by the great German mathematician Georg Cantor, who although you really pronounce his first name as "GAY-org", we - being friends - will call him George.

But George didn't stop there. He decided to count how many rational numbers there were. At that time just about everyone thought there had to be a lot more rational numbers than integers. But George wasn't so sure. If you could count the integers, then why couldn't you count the rationals as well?

How George Did It

George was the first mathematician - and philosopher - to put infinity in precise terms which can be used in proofs. We know the counting numbers are infinite, George said, because no matter what number you pick, you can always add one to the number and get another number. This is not just one characteristic of an infinite set, George said. It is the actual definition.

George called this simplest of all infinities - the infinity of the counting numbers - a countable infinity - which he called aleph-null or . So if you were able to prove that a set was of size , you were actually counting an infinite set.

This then was the key to counting infinite sets. As long you can find a function that maps any counting number, no matter how large, to a unique element of another set, then the other set is the same size as - or as George put, has the same cardinality - as the counting numbers. Any such set - one that can be put into a one-to-one correspondence with the counting numbers - is itself countably infinite.

Now with the rules set in place, George decided to tackle the sticky problem of the rational numbers.

The Rationale of the Rationals

Moving beyond counting numbers and integers, eventually someone - particularly the Babylonians and the Egyptians - developed the concept of fractions or more exactly, the rational numbers (1/2, 1/9, 4/33, etc.). Rational numbers are usually represented as ratios of integers (the word rational refers to the ratios, not anyone's ability to reason).

In trying to count the rational numbers, you encounter a property they have that is not shared by integers. Rational numbers are dense. That is, if you pick any two rational numbers, you can find another rational number between them. That also means that if you pick any two rational numbers, you can pack any number of other rational numbers between them.

So it seems there has to be more rational numbers than integers. But that's what people thought abut the integers, too, and when George set out to count the rationals, he was not being irrational.

A Rational Arrangement

Like George's proof about the integers, you can find all sorts "diagrammatic demonstrations" that rational numbers are countably infinite.

This diagram really doesn't prove the case, of course. What we need is a formula which will match every rational number to every counting number. If we can find such a formula, then the two sets must be the same size.

But first, we'll begin at the beginning and decide exactly what rational numbers are - or rather how to best represent them. For our purposes, the best way to represent rationals are as ordered pairs of the integers. Ordered pairs are simply two numbers in a particular order, usually represented in parentheses like, (1 , 2), (1 , 9) or (4 , 33). For these to be rationals, then, the first number is the numerator and the second is the denominator.

The notation fits with the problem which is to find a function that takes an ordered pair, (i , j), and generates a unique counting number.

This type of formula - with some restrictions - will establish the one-to-one correspondence we need.

Now, as the psychiatrist said, we can begin, yes?

Some Definitions

As the diagram above suggested, we need to come up with an arrangement of rationals that can be listed in a sequence. In doing so we will produce a proof in three parts:

1. First, as we said above, the rational numbers are defined as ordered pairs of zero and counting numbers.

Here we note we have to exclude pairs like (1, 0) since 1/0 is not defined as a rational number (you can't divide by zero). That is, no ordered pair has the second digit as zero.

Now we also need to address how distinct we want to be. That is, 1/2 is a rational number. But so are 2/4 and 50/100. But because you can speak of two fourths in certain contexts as distinct form one half, we will treat 1/2 and 2/4 are different rational numbers, although they do have the same value.

Oh, yes. Letting numbers like 1/2 and 2/4 be different rationals simplifies the proof.

2. The second part of the definitions is to define the arrangement of the rationals in a set of rows. This is very simple. For any row n, the k^th ordered pair is (n - k, k) where k is 1 to n.

Which means each row appears as:

In other words, any row, n, starts off by having the first ordered pair as (n - 1, 1). Then we calculate the next ordered pair on the same row by subtracting 1 from the first element and adding 1 to the second. We continue the process until we end up with the last ordered pair on a row as (0, n).

1:	(0, 1)
2:	(1, 1), (0, 2)
3:	(2, 1), (1, 2), (0, 3)
	.
	.
	.
n:	(n-1, 1), (n-2 , 2), (n-3, 3), ... , (0, n)
n+1:	(n, 1), (n-1 , 2), (n-2, 3), ... , (0, n + 1)
	.
	.
	.

There are two properties of our array that we will mention here. First, all ordered pairs in any column have the same value for the second element. That is they have the same j value.

Next, our array generates only the positive rationals and zero. But we will be able to show that it is easy (or relatively easy) to slip in the negative rationals and that the final formula we create will generate all the positive and negative rationals.

That's all there is to our definitions. Now we will start off our proof by pointing out some other properties of the definitions, some of which require a little bit of proof but not too much.

 

Starting the Proof

George's proof has two main parts which we outline briefly.

1. We first prove our definition generates all rational numbers.

2. We then show we can use the array to derive a formula where the ordered pairs generate all the counting numbers.

If we prove both of these points, we have proven what we want to prove - that the counting numbers and rationals have one-to-one correspondence and the two sets are the same size.

Now, to proceed.

From the definition of our array, there are three conclusions we can draw.

1. The number of pairs in a row is equal to the row number.

This follows immediately from the definition. The second element of the pair starts with 1 and increases until it reaches the value n. So there's n elements per row.

n:	(n-1, 1),	(n-2 , 2),	(n-3, 3),	... ,	(0, n)
	1	2	3		n

2. All rational numbers are generated by our definition. Specifically, you will find for any ordered pair, (i, j), on Row i + j and Column j.

People familiar with arrays probably recognize that such a definition necessarily generates all possible ordered pairs. But for those who don't see it right away, you first note that if move down to any row j, the last ordered pair is (0, j). Then stay in the same column and you can eventually find any i value you need. So when you can find any ordered pair is (i, j), you have to be in Column j, and Row i + j

Or in diagrammatic form:

 

For example, you want ordered pair (31415926, 271827)? Easy. Move to row 271827. The last ordered pair is (0, 271827). Count down 31415926 places, and you will be in row 271826 + 31415927 = 31687753. Sure enough, your ordered pair will be (31415926, 271827)

1: (0,1)

2: (1, 1) (0, 2)

3: (2, 1), (1, 2) (0, 3)

.

.

.

31415927: (31415926, 1), (31415925 , 2), ... (0, 31415927)

.

.

.

31867753: (31867753, 1), (31867752 , 2), ..., (31415926, 31415927), ..., (0, 31867753)

 

3. Each ordered pair is unique; no ordered pair is repeated.

Again people who are familiar with arrays say this - quote - "follows immediately from our definition" - unquote. But eins mehr (as George would say), if the conclusion isn't obvious, then consider the following.

From the way we defined our array, we pointed out that the columns share the same j value. So if two ordered pairs are identical, then they must be in the same column.

But that isn't possible. From the way we defined the rows, for Row n, the ordered pair in column j is (n - j, j). Go up or down any row x places and the ordered pair is (n ± x - j, j). So you can't have the same i value if you are in the same column.

n:	(n-1 , 1)	(n-2 , 2)	(n-3, 3)	...	(1, n)
n + 1:	(n , 1)	(n-1 , 2)	(n-2, 3)	...	(1, n + 1)

So by our definition, all ordered pairs are unique, and our array represents all the possible (positive) rational numbers.

Now we can proceed with the Proof Proper.

 

The Proof Proper (or the Proper Proof)

The final steps remain to develop a real algebraic formula relating the counting numbers with the ordered pairs, and hence the rational numbers. There are five steps to this last part of the proof and all are based on how we constructed our array.

1. The total number of ordered pairs up to and including Row n is n(n + 1)/2

The number of ordered pairs in each row is n. So we need to sum up the counting numbers from 1 to n.

Total ordered pairs =	1	+	2	+	3	+	4	+	...	+	n
Up to Row	1		2		3		4		...		n

Our formula, then, follows from the well known formula found in appropriate mathematics reference sources.

1 + 2 + 3 + ... + n = n(n + 1)/2

2. The numbers of ordered pairs up to the row before the row with ordered pair (i, j) is (i + j - 1)(i + j)/2.

From the definition of the rows, for every ordered pair, we know n = i + j. That is, since every ordered pair is (n - k, k) then n - k + k = n. Therefore the previous row is n - 1 which is equal to i + j - 1. Using the formula we just derived, the total number of ordered pairs up to and including row i + j - 1 is

n(n + 1)/2	= (i + j - 1)(i + j - 1 + 1)/2
	= (i + j - 1)(i + j)/2

3. For an ordered pair (i, j), the number of ordered pairs in the same row up to and including pair (i, j) is simply j.

Once more this conclusion is immediate from our definition. You start counting in the first column where j = 1. So regardless of the row when you reach any number, j, it is in place j.

4. The total number of ordered pairs up to any pair (i, j) is (i + j - 1)(i + j)/2 + j

This follows simply by adding the numbers from the previous two steps:

Total pairs = (i + j - 1)(i + j)/2 + j

5. Therefore our function, N(i, j), which relates any ordered pair, (i, j) - that is zero or a positive rational number - to a unique counting number, n, is just that total.

N(i, j) = (i + j - 1)(i + j)/2 + j

and N(i,j) has the values 1, 2, 3, ...

At this point, readers of the previous essay on counting the integers, may wonder if we now have to prove this equation by mathematical induction. The answer is no because we did not get this equation by a mixture of empiricism and guesswork. But here we derived this equation by starting with our definitions, and then by using proper mathematical deductions, we came up with the formula. That process constitutes a proper proof - a constructive proof, in fact - and so we don't need to do any more.

But oh, yes. We've only completed half the proof.

 

Adding the Other Half

Yes, we have derived a formula that relates positive rationals to the counting numbers. At this point we could simply say you can derive an analogous equation using negative j's which would correspond to negative rational numbers. We do this by changing the plus sign before the j's with minus signs, and then the ordered pairs (i, -j) will generate the counting numbers. Then we say that if you combine two countable infinities you still have a countable infinity. So we have proven all rationals are countably infinite.

While correct as far as it goes, the more finicky of theorem provers may want to know whether we can make one formula that fits the bill and generates all rationals - positive, negative, and zero - and matches them with the counting numbers.

The answer is yes or we wouldn't have raised the question.

 

The Big Formula

The trick to making space in the counting numbers for both positive and negative rationals is to realize that if you multiply any counting number by 2, you get an even number. Multiply it by 2 and and subtract one, you get an odd number.

So take our formula (as Henny Youngman might have said, please).

N(i, j) = (i + j - 1)(i + j)/2 + j

Multiply the right hand side by 2 and our array of ordered pairs, (i, j), will generate the even numbers only.

NEven(i, j)	= 2[(i + j - 1)(i + j)/2 + j]
	= (i + j - 1)(i + j) + 2j

To generate the odd numbers, we multiply our original equation by 2 and subtract 1.

NOdd(i, j)	= 2[(i + j - 1)(i + j)/2 + j] - 1
	= (i + j - 1)(i + j) + 2j - 1

Now we have to make one of the equations work for a negative j. We'll use the even numbers as we outlined above - just put a negative sign before j.

NEven(i, j)

= (i - j - 1)(i - j) - 2j

Now we we cannot simply add the two equations, NOdd(i, j) and NEven(i, j). Instead first we need to multiply each one by a mathematical "switch". That is, we multiply NEven(i, j) and NOdd(i,j) by a factor, that that will turn off part of the equation depending on whether j is negative or not. That's really pretty easy.

The formula

(1 - j/|j|)/2

has a value of 1 if j is negative and 0 if j is positive (|j| represents it usual meaning as the absolute value of j).

Similarly, the formula

(1 + j/|j|)/2

gives us a factor of 0 if j is negative and 1 if j is positive.

So now if you multiply the separate equations, NEven(i, j) and NOdd(i, j) by the appropriate factors and then add everything together, you get one equation that really, really works.

N(i,j) = [(i - j - 1)(i - j) - 2j - 1](1 + j/|j|)/2 + [(i + j - 1)(i + j) + 2j](1 - j/|j|)/2

This, equation will indeed produce the counting numbers if you take our original array and insert the ordered pair with the negative j under it's positive counterpart.

 

(0 ,  1):		1
(0 , -1):		2
(1 ,  1):		3
(1 , -1):		4
(0 ,  2):		5
(0 , -2):		6
(i ,  j):		n
(i , -j):		n + 1

Some people,though, still don't like saying the multiple zeros (0/1, 0/2, 0/3, etc) are distinct rational numbers. Yes, you can argue that 2/4 - that is two parts out of four - may in different contexts be distinct from 1/2, 3/6, 50/100, and the like. But zero is zero and we don't want the repetitions.

But there is an alternate formula - whose proof, as the textbooks say, is left for the reader - that omits the repetitions. [The proof, by the way, is based on defining the rows so that Row 1 is (0,1) and starting with Row 2 the rows end with (1, n), not (0, n). That Row 1 and Row 2 both have one ordered pair complicates the algebra, but not all that much.]

N(i,j)	= [(i + j - 1)(i + j - 2) + 2j + 2δ0,i - 2](1 + j/|j|)/2
	+ [(i - j - 1)(i - j - 2) - 2j + 2δ0,i - 1](1 - j/|j|)/2
	+ 1 - δ0,i

 

where δ_0,i is the famous Kronecker delta where

δ_0,i = 0 if i = 0

and

δ_0,i = 1 if i ≠ 0

This formula, then, will map all the rational numbers to a unique counting number. Exactly what we wanted.

 

The Integers and Counting Numbers

 

In other words, there sure enough is a one-to-one correspondence with the rational numbers and counting numbers. The two sets must be the same size.

Once more we have to tip our hats to George.

 

A Point of Clarification

At this point, some people remain unconvinced. After all, they say they can match the rationals 1/1, 2/1, 3/1, 4/1, with the counting numbers and have an infinite number of rationals left over. Therefore there must be more rationals than counting numbers. You can make the same argument for the number of integers being more than the counting numbers. You can match the positive integers, 1, 2, 3, ..., etc., with counting numbers and so have the negative integers (and zero) left over. So how can integers, rationals, and counting numbers be the same size?

Not so fast, there, Pilgrim. Yes what you say is true, but completely irrelevant. When you say 1/1, 2/1, 3/1, 4/1, etc,. can be matched with counting numbers that is certainly the case - because 1/1, 2/1, 3/1, 4/1, etc. are indeed the counting numbers. So all you are saying is the counting numbers can be matched with the counting numbers. Or in other words, when you do your one-to-one correspondence, you are simply omitting to match up all the members of your set with the other set.

On the other hand, if you want to say the set of rationals is not the same size as the counting numbers, you must prove that no function will give us a one-to-one correspondence to rationals and counting numbers. Only if you can prove no such pairing exists, then can you correctly claim the sets are not the same size.

But what we just proven, both for the rational numbers and as we did earlier for the integers, that there are indeed such functions. So the sets of rationals, integers, and counting numbers must be the same size.

Q. E. D.

George and the Rationals: Mission Accomplished!

References

Schaum's Outline of Boolean Algebra and Switching Circuits, Elliott Mendelson, McGraw-Hill, (1970). Problem 2.18 on page 46, is a worked example which gives the formula to formula relating positive rationals to the counting numbers. As usual, if you want information about a particular topic, it's hard to beat a Schaum's Outline.

Georg Cantor: His Mathematics and Philosophy of the Infinite, Joseph Warren Dauben, Princeton University Press (1990). Not really a biography and not something for the general reader (knowledge of fairly advanced math expected). You'd think by now George would have a real biography. True many mathematicians don't leave incredibly exciting lives, but you'd think someone like George deserves better.

Return to CooperToons Department of Education

Return to CooperToons Homepage