At his blog, Joe G. has worked himself into a lather over the cardinality (or roughly speaking, the size) of infinite sets (h/t Neil Rickert):

Of Sets, Supersets and Subsets
Oleg the Asshole, Still Choking on Sets
Of Sets and EvoTARDS
Subsets and Supersets, Revisted [sic]

In particular, Joe is convinced that the sets {0,1,2,3,…} and {1,2,3,4,…} have different cardinalities:

…the first set has at least one element that the second set does not, ie they are not equal.

So if two sets are not equal, then they cannot have the same cardinality.

As a public service, let me see if I can explain Joe’s errors to him, step by step.

First of all, Joe, sets do not have to be equal in order to have the same cardinality, as Neil showed succinctly:

I give you two sets. The first is a knife and fork. The second is a cup and saucer. Those two sets are not equal. Yet both have cardinality two.

Two sets have the same cardinality if their elements can be placed into a one-to-one correspondence. That’s the only requirement. Here is a one-to-one correspondence (or “bijection”) for Neil’s sets:

knife <–> cup
fork <–> saucer

Note that there is nothing special about that one-to-one correspondence. This one works just as well:

fork <–> cup
knife <–> saucer

It makes no difference if the elements are numbers. The same rule applies: two sets have the same cardinality if their elements can be placed into a one-to-one correspondence. Consider the sets {0,1,2} and {4,5,6}. They can be placed into the following correspondence:

0 <–> 4
1 <–> 5
2 <–> 6

As before, there is nothing special about that correspondence. This one also works:

1 <–> 4
0 <–> 5
2 <–> 6

There are six distinct one-to-one correspondences for these sets, and any one of them, by itself, is enough to demonstrate that the sets have the same cardinality.

Now take the sets {1,2,3} and {2,4,6}.  They can be placed into this one-to-one correspondence:

2 <–> 2
1 <–> 4
3 <–> 6

However, note that it’s not required that the 2 in the first set be mapped to the 2 in the second set. This one-to-one correspondence also works:

1 <–> 2
2 <–> 4
3 <–> 6

As in the previous example, there are six distinct one-to-one correspondences, and any one of them is sufficient to demonstrate that the cardinalities are the same.

Now consider the sets that are befuddling you: the infinite sets {0,1,2,3,…} and {1,2,3,4,…}. They can be placed into a one-to-one correspondence:

0 <–> 1
1 <–> 2
2 <–> 3
3 <–> 4
…and so on.

A one-to-one correspondence exists. Therefore the cardinalities are the same.

Here’s what I think is confusing you, Joe: there is a different mapping from the first set to the second that looks like this:

0 doesn’t map to anything
1 <–> 1
2 <–> 2
3 <–> 3
… and so on.

You observe that all of the elements of the second set are “used up”, while the first set still has an “unused” element — 0. You comment:

They both go to infinity but the first one starts one number before the second. That means that the first one will always have one element more than the second which means they are NOT the same size, by set standards.

But that’s silly, because you could just as easily choose a different mapping, such as:

0 doesn’t map to anything
1 doesn’t map to anything
2 doesn’t map to anything
3 <–> 1
4 <–> 2
5 <–> 3
… and so on.

Now there are three unused elements in the first set. We can also arrange for the “unused” elements to be in the second set:

nothing maps to 1
nothing maps to 2
nothing maps to 3
0 <–> 4
1 <–> 5
2 <–> 6
… and so on.

There are now three unused elements in the second set. By your logic, that would mean that the second set has a greater cardinality. It clearly doesn’t, so your logic is wrong.

You can even arrange for an infinite number of unused elements:

0 <–> 2
1 <–> 4
2 <–> 6
3 <–> 8
… and so on.

Now the odd integers are unused in the second set. Since there are now infinitely many “unused” elements in the second set, then by your logic the second set is infinitely larger than the first. Your logic is wrong, and the mathematicians are right.

Two sets have the same cardinality if they can be placed into a one-to-one correspondence. The sets {0,1,2,3,…} and {1,2,3,4,…} can be placed into such a correspondence, so they have the same cardinality.

END (Hi, KF!)