[general_re]

Some infinities are larger than other infinities. The set of all integers is provably larger than the set of all even integers, even though both sets have an infinite number of elements.

Deep, huh? ;-)

[AndrewC]

The set of all integers is provably larger than the set of all even integers, even though both sets have an infinite number of elements.

I believe this is wrong.

I'm infinity, you're infinity. Are we the same infinity?

Let us return to our question: Are there as many even integers as integers? Since we can match every integer n to a single even integer 2n, we must concede that there are the same number of each. The matching is called a one-to-one correspondence. Infinite sets can have one-to-one correspondences with "smaller-looking" subsets of themselves. Of course, this can never happen with finite sets--one will never match 14 objects one for one with any 9 of them. This difference is in fact a fundamental difference between finite sets and infinite sets. We may rest assured that our two questions:

• How many positive integers are there?
• How many even positive integers are there?

do indeed have the same answer, which we've called .

There are, however, different infinities.

[The_Reader_David]

Actually, the set of even natural numbers and the set of natural numbers are the same size of infinite set: the match up 1-1 (doubling natural numbers matches them to even natural numbers, halving even natural numbers matches them to all natural numbers). It is the defining property of an infinite set that it can be matched up with a proper subset of itself, i.e. you can throw some away and still have just as many.

There are, however, different sizes of infinite sets. The simplest example is to consider the set of natural numbers, {0,1,2,3,...} (I follow the example of mathematical logicians rather than grade school teachers in calling 0 a natural number).

Now consider also the set of all subsets of the natural numbers. I claim that we cannot match these sets up 1-1, because any attempt to do so misses some subset:

Suppose we've tried, we match every number n with a subset of the natural numbers S(n). No matter how this was done, we have missed a subset:

Let M(S) (for missed by the list S) be the set of all natural numbers n such that n is not an element of S(n).

Now, M(S) can't be any set in the list S(n), since if we think it's the kth set S(k), there's a problem: if k is in M(S), that means it's not in S(k), so they aren't the same set--one contains k the other doesn't. On the other hand if k is not in M(S), that means it's in S(k), so they aren't the same set--again one contains k the other doesn't.

This annoying fact was discovered by Georg Cantor, whose proof I just presented. A similar proof shows that there are more real numbers than natural numbers (though the rational numbers--ones which can be written as fractions--match up with the natural numbers), and that the set of subsets of any set always has more elements than the orginal set.