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 exists a u∈S such that g(u)=f∘h. Passing u as an argument to both sides, we have (g(u))(u)=f(h(u)), so h(u)=f(h(u)), contradicting the fact that f has no fixed points.
3. For nonempty S and T, suppose you are given g:S→TS a surjective function from the set S to the set of functions from S to T, and let f be a function from T to itself. The previous result implies that there exists an x in T such that f(x)=x. Can you use your proof to describe x in terms of f and g?
Solution:
Define h:S→T by h(s)=(g(s))(s). Since g is surjective, there exists u∈S such that g(u)=f∘h. Then take x=h(u). From my proof above, x is a fixed point of f.
4. Given sets A and B, let Comp(A,B) denote the space of total computable functions from A to B. We say that a function from C to Comp(A,B) is computable if and only if the corresponding function f′:C×A→B (given by f′(c,a)=f(c)(a)) is computable. Show that there is no surjective computable function from the set S of all strings to Comp(S,{T,F}).
Solution:
Suppose for the sake of contradiction that f:S→Comp(S,{T,F}) is a surjective computable function. Then the following is computable: g(u)=¬f′(u,u). Since f is surjective, there exists v∈S such that f(v)=g, but then f(v)(v)=g(v)=¬f′(v,v)=¬f(v)(v), a contradiction.
5. Show that the previous result implies that there is no computable function halt(x,y) from S×S→{T,F} which outputs T if and only if the first input is a code for a Turing machine that halts when given the second input.
Suppose for the sake of contradiction that there exists such a computable function halt(x,y). Then define a function f:S→Comp(S,{T,F}) as follows: for any string x, if x is not a code for a Turing Machine, let f(x) be the function sending all strings to T. If x is a code for a Turing machine, let f(x) be the function y↦halt(x,y). I claim this is a surjective computable function from S to Comp(S,{T,F}): to show it is surjective, for any computable function g:S→{T,F}, there is a Turing machine which halts precisely when that function returns T. Letting x be the code for that Turing machine, we then have f(x)=g. It’s also computable since we assume halt(x,y) is computable. This contradicts the previous result, so we must have been wrong in our initial assumption.
6. Given topological spaces A and B, let Cont(A,B) be the space with the set of continuous functions from A to B as its underlying set, and with topology such that f:C→Cont(A,B) is continuous if and only if the corresponding function f′:C×A→B (given by f′(c,a)=f(c)(a)) is continuous, assuming such a space exists. Convince yourself that there is no space X which continuously surjects onto Cont(X,S), where S is the circle.
Suppose for the sake of contradiction that for some space X, f:X→Comp(X,S) is a surjective continuous function. Let o:S→S denote the continuous function giving the point on the opposite side of the circle. Then the following is continuous: g(x)=o(f′(x,x)). Since f is surjective, there exists y∈X such that f(y)=g, but then f(y)(y)=g(y)=o(f′(y,y))=o(f(y)(y)), 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.
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 exists a u∈S such that g(u)=f∘h. Passing u as an argument to both sides, we have (g(u))(u)=f(h(u)), so h(u)=f(h(u)), contradicting the fact that f has no fixed points.
3. For nonempty S and T, suppose you are given g:S→TS a surjective function from the set S to the set of functions from S to T, and let f be a function from T to itself. The previous result implies that there exists an x in T such that f(x)=x. Can you use your proof to describe x in terms of f and g?
Solution:
Define h:S→T by h(s)=(g(s))(s). Since g is surjective, there exists u∈S such that g(u)=f∘h. Then take x=h(u). From my proof above, x is a fixed point of f.
4. Given sets A and B, let Comp(A,B) denote the space of total computable functions from A to B. We say that a function from C to Comp(A,B) is computable if and only if the corresponding function f′:C×A→B (given by f′(c,a)=f(c)(a)) is computable. Show that there is no surjective computable function from the set S of all strings to Comp(S,{T,F}).
Solution:
Suppose for the sake of contradiction that f:S→Comp(S,{T,F}) is a surjective computable function. Then the following is computable: g(u)=¬f′(u,u). Since f is surjective, there exists v∈S such that f(v)=g, but then f(v)(v)=g(v)=¬f′(v,v)=¬f(v)(v), a contradiction.
5. Show that the previous result implies that there is no computable function halt(x,y) from S×S→{T,F} which outputs T if and only if the first input is a code for a Turing machine that halts when given the second input.
Suppose for the sake of contradiction that there exists such a computable function halt(x,y). Then define a function f:S→Comp(S,{T,F}) as follows: for any string x, if x is not a code for a Turing Machine, let f(x) be the function sending all strings to T. If x is a code for a Turing machine, let f(x) be the function y↦halt(x,y). I claim this is a surjective computable function from S to Comp(S,{T,F}): to show it is surjective, for any computable function g:S→{T,F}, there is a Turing machine which halts precisely when that function returns T. Letting x be the code for that Turing machine, we then have f(x)=g. It’s also computable since we assume halt(x,y) is computable. This contradicts the previous result, so we must have been wrong in our initial assumption.
6. Given topological spaces A and B, let Cont(A,B) be the space with the set of continuous functions from A to B as its underlying set, and with topology such that f:C→Cont(A,B) is continuous if and only if the corresponding function f′:C×A→B (given by f′(c,a)=f(c)(a)) is continuous, assuming such a space exists. Convince yourself that there is no space X which continuously surjects onto Cont(X,S), where S is the circle.
Suppose for the sake of contradiction that for some space X, f:X→Comp(X,S) is a surjective continuous function. Let o:S→S denote the continuous function giving the point on the opposite side of the circle. Then the following is continuous: g(x)=o(f′(x,x)). Since f is surjective, there exists y∈X such that f(y)=g, but then f(y)(y)=g(y)=o(f′(y,y))=o(f(y)(y)), a contradiction.