Well, you're both right. Yes, surprisingly, the set of all ordered pairs of integers can be placed into one-to-one correspondence with the set of all integers. But that has little to do with steveb's assertion, also correct, that the members of the set of all subsets of a given set cannot be placed into one-to-one correspondence with the members of that set.

I'll use the set of all integers as a demonstration, but it works for any set. The proof is a reductio ad absurdium.

Suppose there is a one-to-one correspondence between the members of a set, and all possible subsets of that set. For example,

0 -> {}
1 -> {0}
2 -> {all integers}
3 -> {all odd integers}
etc.

Now, for some numbers, the number will also appear in the set with which it is paired. (This is true of 2 and 3 in my example above). Call these members of the set "blue". For others (0 and 1 in my example above), the number does not appear in the set with which it is paired. Call these "red".

Now, consider the set of all red numbers. What number is associated with that set? It cannot be a red number, since red numbers do not appear in the set they are associated with, and this is the set of all red numbers. And it cannot be a blue number, since blue numbers do appear in the set they are associated with, and this is the set of all red numbers! Since our initial premise--that there is a one-to-one mapping between members of a set and all subsets of that set--leads to a logical contradiction, that premise must be false.


©2000 Charles Carroll. Anyone besides Derek Balling may copy this post or parts of it freely.