Now consider power sets. A set S's power set P(S) is the set of all subsets of it. Georg Cantor showed that P(S) has a higher cardinality than S. He did so by showing that if it did not, then one gets a contradiction.
So element a of S would be mapped onto subset A of S. Let's consider the set of all a's that are not members of their corresponding A's, a set that I'll call N.
Let's suppose some n corresponds to N, then since n is not in n, then n must belong in N. But if that is the case, then n violates the definition of N, and n cannot be in N.
Thus, card(P(S)) > card(S), or |P(S)| > |S|.
One can construct a sequence of power sets starting with the smallest infinite cardinality, aleph-0. This sequence is sometimes called the beth numbers. Thus,
- beth-0 = aleph-0
- beth-1 = C, the continuum cardinality, that of the real numbers
- beth-2 = cardinality of all functions from real numbers to real numbers
We don't have identifications for any higher beth numbers.
-
It's easy to prove that |(countable set) - (finite subset)| = |countable set| = aleph-0 (A0).
From
hw8ans.pdf is a rather simple proof of something a bit more difficult:
|(real numbers) - (countable subset of them)| = |real numbers| = C
For the real numbers R, consider a countable subset of them, S, and find a countable subset T of (R - S), all elements of R not in S. Now define a bijection f between R and (R - S):
f(x in (R - (S union T))) = x
f(s(n)) = t(2n)
f(t(n)) = t(2n-1)
where n = 1, 2, 3, ..., all s(n) are in S, and all t(n) are in T. This bijection thus pushes the elements of S into (R - S), moving elements of T out of the way for them.
Thus, |R - S| = |R| = C