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.
2. Suppose that a nonempty set T has a function f from T to T which lacks fixed points (i.e. f(x)≠x for all x∈T). Convince yourself that there is no surjection from S to S→T, for any nonempty S. (We will write the set of functions from A to B either as A→B or BA; these are the same.)
Solution:
Suppose that g were such a surjection. Then we may define a function h:S→T by h(s)=(g(s))(s). Now, since g is surjective, there
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.
2. Suppose that a nonempty set T has a function f from T to T which lacks fixed points (i.e. f(x)≠x for all x∈T). Convince yourself that there is no surjection from S to S→T, for any nonempty S. (We will write the set of functions from A to B either as A→B or BA; these are the same.)
Solution:
Suppose that g were such a surjection. Then we may define a function h:S→T by h(s)=(g(s))(s). Now, since g is surjective, there