In his 1891 proof that the cardinality of the power set exceeds the cardinality
ID: 3122776 • Letter: I
Question
In his 1891 proof that the cardinality of the power set exceeds the cardinality of the set itself, Cantor began with any matching between elements of the set A and elements of its power set and had to come up with an element of the power set that could not be on the proposed list. The fact that he figured out how to find such a set in general is a clear testimony to his remarkable genius. Just to see how his insight works in a specific case or two, work on the examples below: (a) Suppose we match all of A = {a, b, c, d, e, f, g} with some of the elements of its power set P(A) as follows: a rightarrow {b, c, g] b rightarrow {b, c, e, g} c rightarrow {b, c) d rightarrow {d} e rightarrow A f rightarrow {a, b, c} g rightarrow {} (empty set) Find the set B from Cantor's proof. Is it an element of P(A)? Is it matched with anything in the matching above? (b) Do the same thing for the matching between N and its power set P(N) given by n rightarrow {n-1, n, n+1} if n is even n rightarrow {n^2, n^2 + 2, n^2 + 4, ...} if n is odd. For this matching, explicitly find the subset B of N and explain why it is or isn't matched with any element n under this matching.Explanation / Answer
162
a) Cantor defined the set B as
B ={ x is an element in A : x does not belong to the set it is matched to }
In the given problem, the numbers a, f and g are paired with subsets in which they are not an element.
Hence B = { a, f, g}.
B is an element of P(A).
It is not matched with any of the elements given in the problem because, we cannot find an element which is matched with {a,f,g}.
b) Given that n -> {n-1, n, n+1}, when n is even
Hence 2 is matched with the set { 1,2,3},
4 is matched with {3, 4, 5} and so on .
It is also given that n -> { n2 , n2 +2, n2 +4, .......}, for n is odd number
Hence, when n = 1, 1 is matched with the set { 1,3,5,7,.....}
when n =3, 3 is matched with { 9,11,13,15,........}
when n= 5, 5 is matched with {25,27,29,....} and so on.
The subset B of N is
B= { 3, 5, 7, 9, ......}
The set B is not matched with any of the elements in the above matching. Because we cannot identify a number which is matched to the set {3, 5, 7, 9,....} under the given matching.