Ramble, Part 66: No Ceiling
Jan. 31st, 2009 01:14 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowThere is no largest cardinality; no matter how large a set is, there is a larger one. The proof of this, which is an adaptation of Cantor diagonalization, is under the cut.
Let A and B be two sets. We will use |A| and |B| to represent their cardinalities; they may be numbers, or they may be transfinite. We say that |A|=|B| if the two sets can be paired off; that |A|≥|B| if B can be paired off with some subset of |A|; and that |A|>|B| if B can be paired off with a subset of A, but not with A itself.
Let's think about Cantor's original argument again. Instead of using the decimal representation of real numbers between 0 and 1, let's use binary representations. These look like infinite strings .a1a2a3a4..., where each ai is a single bit, 0 or 1. Some real numbers have more than one binary representation; for example, 1/2 is .1000... and also .0111.... Let's ignore this; instead of thinking about the set of numbers themselves, let's think of the set of all binary representations. (1/2 and some other numbers get counted twice, but this turns out not to affect the cardinality.)
Each of these strings can be made to correspond to a subset of the positive integers, in a natural way: if the nth bit of the string is 1, then n is in the subset, and otherwise not. So the string .0000... corresponds to the empty set, .1111... to the set of all of the positive integers, and .1010... to the set of odd positive integers. That is, if N is the set of positive integers, the set of strings corresponds to P(N), the power set of N - the set of all subsets of N.
Now, suppose we have a list of bit strings - or, equivalently, a list of subsets of N. Let's call the first subset S1, the second S2, and so on. Cantor's diagonalization argument constructs a new bit string - or subset of N, which we'll call S - as follows. If the nth bit of the nth string is 1 - that is, if n is an element of Sn - then the nth bit of the new string is 0 - that is, n is not an element of S. Conversely, if n is not an element of Sn, then n is an element of S.
Can S be one of the Sn? Suppose S is Sm. Is m in S? If m is in S, then m is in Sm - but that disqualifies it from being in S. On the other hand, if m is not in S, then m is not in Sm - but that's precisely the qualification to be in S! Either way, we get a contradiction; therefore S cannot be one of the Sn. That is, |P(N)|>|N|.
But now we can show that, for any set A, |P(A)|>|A|, using essentially the same argument. Suppose we pair off each element x of A with some subset Ax of A. Then we can define another subset B of A, whose elements are precisely those x which are not contained in Ax. If B, so defined, were one of the sets Ax - say, Ay - the question whether y is in B again has no consistent answer. That is, if we pair off the elements of A with subsets of A, there is at least one subset of A which doesn't get paired off: |P(A)|>|A|.
There is no largest cardinality. The consequences of this are momentous; among other things, this fact exposes a flaw in set theory as Cantor conceived it. That's a story for another day, though.
Previous Next
Ramble Contents
Let A and B be two sets. We will use |A| and |B| to represent their cardinalities; they may be numbers, or they may be transfinite. We say that |A|=|B| if the two sets can be paired off; that |A|≥|B| if B can be paired off with some subset of |A|; and that |A|>|B| if B can be paired off with a subset of A, but not with A itself.
Let's think about Cantor's original argument again. Instead of using the decimal representation of real numbers between 0 and 1, let's use binary representations. These look like infinite strings .a1a2a3a4..., where each ai is a single bit, 0 or 1. Some real numbers have more than one binary representation; for example, 1/2 is .1000... and also .0111.... Let's ignore this; instead of thinking about the set of numbers themselves, let's think of the set of all binary representations. (1/2 and some other numbers get counted twice, but this turns out not to affect the cardinality.)
Each of these strings can be made to correspond to a subset of the positive integers, in a natural way: if the nth bit of the string is 1, then n is in the subset, and otherwise not. So the string .0000... corresponds to the empty set, .1111... to the set of all of the positive integers, and .1010... to the set of odd positive integers. That is, if N is the set of positive integers, the set of strings corresponds to P(N), the power set of N - the set of all subsets of N.
Now, suppose we have a list of bit strings - or, equivalently, a list of subsets of N. Let's call the first subset S1, the second S2, and so on. Cantor's diagonalization argument constructs a new bit string - or subset of N, which we'll call S - as follows. If the nth bit of the nth string is 1 - that is, if n is an element of Sn - then the nth bit of the new string is 0 - that is, n is not an element of S. Conversely, if n is not an element of Sn, then n is an element of S.
Can S be one of the Sn? Suppose S is Sm. Is m in S? If m is in S, then m is in Sm - but that disqualifies it from being in S. On the other hand, if m is not in S, then m is not in Sm - but that's precisely the qualification to be in S! Either way, we get a contradiction; therefore S cannot be one of the Sn. That is, |P(N)|>|N|.
But now we can show that, for any set A, |P(A)|>|A|, using essentially the same argument. Suppose we pair off each element x of A with some subset Ax of A. Then we can define another subset B of A, whose elements are precisely those x which are not contained in Ax. If B, so defined, were one of the sets Ax - say, Ay - the question whether y is in B again has no consistent answer. That is, if we pair off the elements of A with subsets of A, there is at least one subset of A which doesn't get paired off: |P(A)|>|A|.
There is no largest cardinality. The consequences of this are momentous; among other things, this fact exposes a flaw in set theory as Cantor conceived it. That's a story for another day, though.
Previous Next
Ramble Contents
