A recent conversation reminded me that many of my lawyer friends don't know these really cool mathematical items, but enjoy them when they learn about them. I thought, then, that I'd quickly go through them; I'm no math maven these days, but I think I can get them right, substantively even if not with the level of formal precision that hard-core math people might prefer.

Here's the first question: Are there more positive integers (1, 2, 3, 4, 5, ...) or more integer squares (1, 4, 9, 16, 25, ...)? The answer: The two sets are of the same size.

Counterintuitive, some may say: After all, positive integers include all the squares, plus all the nonsquares, as well. In any interval from 1 to n, when n>1, there are more integers than squares; what's more, the ratio increases as n grows. In 1 to a million, for instance, there are a thousand times more integers than squares.

Yet this is quite true, under the standard mathematical definition of equal size. Let's define two sets as equal if there's a one-to-one mapping between them, so that each number in one set corresponds to precisely one number in the other. The mapping here is simple: Map any integer n to n squared, which is to say 1 to 1, 2 to 4, 3 to 9, 4 to 16, 5 to 25, and so on. Every number in the positive integers maps to precisely one square, and vice versa. The two sets are equal.

In fact, as one can easily prove through a similar approach, any two infinite subsets of the positive integers are equal. In fact, this may lead you to replace your old intuition (lots more integers than squares) with a new one (hey, both sets are infinite, and infinity = infinity). But not so fast! Two questions for you: Are there more positive integers or positive rational numbers (numbers that are the ratio of two integers, such as 2/7 or 549/100)? And are there more positive integers or real numbers? More on that soon.

I asked that near the end of my previous post; and the answer, counterintuitively, is that these two sets are also equally big. Remember that the standard definition we're working with is that two sets are equally big if there's a way of mapping each element of the first to precisely one element of the second. So here's the mapping, with the unbracketed item in each cell being a rational number (e.g., 2/3), and the bracketed item being the positive integer to which the mapping is being done. (To make it simple, I'll ignore the double counting that happens when some fractions equal some others that came before, for instance when we get to 2/2 and 3/3, which equal 1/1; to make it more precise, we can just skip over them.

As you can see, if the rational numbers in the form p/q are organized in an infinite matrix, we can start counting by diagonals, and eventually get to any p/q you care to mention. So every positive rational number has precisely one positive integer to which it's mapped. And therefore the sets are equal in size.

If you want another mapping, try mapping any p/q (where p and q are relatively prime) to 2^p x 3^q; that maps the positive rationals to a subset of the positive integers. Of course, if you grasp why that works, you've probably learned the diagonals proof already.

So we've seen that there are as many squares as there are positive integers, and as many rational numbers as there are positive integers. That's because infinity is infinity, right? All infinite sets are infinite and therefore equal in size?

The answer, it turns out, is no. Georg Cantor, in fact, provided a simple and elegant proof that there are more real numbers even just between 0 and 1 (not counting 1) than there are integers, which is to say that there's no one-to-one mapping of real numbers and integers, though there is of rational numbers and integers.

Here's the proof. Let's assume that there is such a mapping, so that, for instance,

1 maps to 0.62584146011243...
2 maps to 0.43256984161433...
3 maps to 0.46543618463411...
4 maps to 0.68905671314112...
5 maps to 0.23348521001518...
...

Then let's construct a number based on the digits along the diagonal, with its first digit after the decimal point being 1 more than the first digit of the first number, the second digit being 1 more than the second digit of the second number, and so on (those are the underlined digits); but if some digit in the original mapping is an 8 or 9, we change it to a 0 instead of adding 1. The diagonal number for the mapping above, for instance, is 0.63508..., and the constructed number is 0.74610....

This constructed number is not within the mapping; it can't correspond to any integer n, because the nth digit of the constructed number is guaranteed to differ from the nth digit of the nth number in the mapping.

What's more, this is true of any mapping you can come up with. No matter how you try to map the real numbers between 0 and 1 to the positive integers, there will always be a real number between 0 and 1 that one can construct using Cantor's algorithm that will be guaranteed to be outside the mapping. Therefore, no such mapping can exist: It's not possible to map the real numbers between 0 and 1 to the positive integers. Cool, no? All infinite numbers are infinite, but some are more infinite than others.