Further Thoughts on the Mathematical Infinite: The Coincidence of the Naturals and the Rationals

In my previous post, I introduced a meaningful, well-defined way to think the relations of size between “infinitely” large sets.  I put “infinity” in quotation marks here because, as it will be shown in later posts, this inquiry will require us to radically rethink what it is we mean by our intuitive notions of what is and is not “infinite.”  To recap, two sets are said to have the same size or “cardinality” if and only if it is possible to develop a one-to-one correspondence between them.  Furthermore, under this definition of cardinality, it was shown that the set of natural numbers (N) and the set of even numbers (2N) are the some size.

It turns out that there are many subsets of N that share the same cardinality.  There exists one-to-one correspondences between 3N, 10N, 1027N, and in general aN, where a is any natural number.  The same is true of N², the set of all square numbers, as well as Z, the set of all integers, defined as the set of all positive numbers, negative numbers, and 0.  However, a truly surprising result is that, under this definition of cardinality, N has the same cardinality as Q, the set of all rational numbers.

A rational number is any number that can be expressed as a fraction, or a ratio of two integers.  Thus 1/2, 2/3, and -27/29 are all rational numbers.  Rational numbers include the natural numbers (3 can be thought of as the ratio 3:1, or 3/1), the integers, and many numbers beside.  In fact, Q contains so many numbers it is said to be “dense” – between any two numbers in Q there exists another number in Q.  For example, 0 and 1/2 are both in Q.  But between 0 and 1/2 is 1/4, which is also in Q.  Between 0 and 1/4 is 1/8, and between 1/4 and 1/2 is 3/8, both of which are in Q.  This process can be repeated indefinitely.

To see that Q and N have the same cardinality, we can represent all the elements of Q in the following chart:

0	1	2	3	4	…	n
1	1/1	½	1/3	¼	1/…	1/n
2	2/1	2/2	2/3	2/4	2/…	2/n
3	3/1	3/2	3/3	3/4	3/…	3/n
4	4/1	4/2	4/3	4/4	4/…	4/n
…	…/1	…/2	…/3	…/4	…/…	…/n
n	n/1	n/2	n/3	n/4	n/…	n/n

We can prove that this chart contains all the elements of Q: Let x be an element of Q.  Then x = m/n for where m and n are both natural numbers.  But m must appear somewhere in the vertical axis of the chart, and n must appear somewhere in the horizontal axis of the chart.  So m/n will appear at the intersection of the corresponding column and row.  So the chart contains all the elements of Q.  (In fact, the chart contains even more boxes than there are elements in Q; for example, all the elements along the diagonal are equal to 1, and so are considered to be the same element).

Image via Wikipedia

 

Cantor‘s genius in proving that Q and N had the same cardinality was to take this chart, and draw a line that eventually passes through every box.  As in the diagram, starting at 0, go one box down to 1.  Then go diagonally up and to the right to the 1.  Then go one box to the right, to 2, and go diagonally down and to the left, through 1/1, to 2.  Go down to 3, diagonally up and to the right to 3, and so on.  Eventually (admittedly a very long eventually), every element in the chart will have been reached by the line.  If we associate each box that the line crosses through with a natural number (that is, the first box with 1, the second box with 2, the third with 3, and so on), we will have a pairing between every rational number with every natural number.

 

 

 

Frankly, Cantor found this result shocking.  After all, his goal in making a formal study of mathematical infinities in the context of set theory was to prove finitism, that the infinite does not exist and cannot even be made meaningful sense of.  One of the reasons he waited so many years to publish his results was that he didn’t even believe them.  Convinced he must have made a mistake somewhere, he checked and rechecked his work for years, only demonstrating more thoroughly the legitimacy of his work.