1. Recall Cantor’s diagonal argument for the uncountability of the real numbers. Apply the same technique to convince yourself than for any set S, the cardinality of S is less than the cardinality of the power set P(S) (i.e. there is no surjection from S to P(S)).
Solution:
Suppose that f:S→P(S) is surjective. Then take A={s∣s∉f(s)}. Since f is surjective, there existst∈S such that f(t)=A. But then t∈f(t)⇔t∈A⇔t∉f(t), a contradiction
Here are my solutions to the first six problems:
1. Recall Cantor’s diagonal argument for the uncountability of the real numbers. Apply the same technique to convince yourself than for any set S, the cardinality of S is less than the cardinality of the power set P(S) (i.e. there is no surjection from S to P(S)).
Solution:
Suppose that f:S→P(S) is surjective. Then take A={s∣s∉f(s)}. Since f is surjective, there existst∈S such that f(t)=A. But then t∈f(t)⇔t∈A⇔t∉f(t), a contradiction