Exercise 1: Let f:S↦P(S) and let A={x∈S|x∉f(x)}. Suppose that A∈f(S), then let x∈S be an element such that f(x)=A. Then x∉f(x)=A⟹x∈A by definition, and x∈A=f(x)⟹x∉A. So x∉A⟺x∈A, a contradiction. Hence A∉f(S), so that f is not surjective.
Ex 2
Exercise 2: Since T is nonempty, it contains at least one element t0. Let h:T↦T be a function without a fixed point, then t0≠h(t0)=:t1, so that t0 and t1 are two different elements in T (this is the only thing we shall use the function h for).
Let Ψ:S↦TS for S nonempty. Suppose by contradiction that Ψ is surjective. Define a map f:S↦P(S) by the rule f(x)={s∈S|Ψ(x)(s)=t0}. Given any subset U⊂S, let g:S↦T be given by g:x↦{t0x∈Ut1x∉U Since Ψ is surjective, we find a s∗∈S such that Ψ(s∗)=g. Then f(s∗)=U. This proves that f is surjective, which contradicts the result from (a).
Ex 3
Exercise 3: By (2) we know that T={x}, and so f={(x,x)} and g={(s,h)|s∈S} where h={(s,x)|s∈S}. That means x=g(s)(s′)=fn(g(s)(s′)) for any s,s′∈S. and n∈N.
Ex 1
Exercise 1: Let f:S↦P(S) and let A={x∈S|x∉f(x)}. Suppose that A∈f(S), then let x∈S be an element such that f(x)=A. Then x∉f(x)=A⟹x∈A by definition, and x∈A=f(x)⟹x∉A. So x∉A⟺x∈A, a contradiction. Hence A∉f(S), so that f is not surjective.
Ex 2
Exercise 2: Since T is nonempty, it contains at least one element t0. Let h:T↦T be a function without a fixed point, then t0≠h(t0)=:t1, so that t0 and t1 are two different elements in T (this is the only thing we shall use the function h for).
Let Ψ:S↦TS for S nonempty. Suppose by contradiction that Ψ is surjective. Define a map f:S↦P(S) by the rule f(x)={s∈S|Ψ(x)(s)=t0}. Given any subset U⊂S, let g:S↦T be given by g:x↦{t0x∈Ut1x∉U Since Ψ is surjective, we find a s∗∈S such that Ψ(s∗)=g. Then f(s∗)=U. This proves that f is surjective, which contradicts the result from (a).
Ex 3
Exercise 3: By (2) we know that T={x}, and so f={(x,x)} and g={(s,h)|s∈S} where h={(s,x)|s∈S}. That means x=g(s)(s′)=fn(g(s)(s′)) for any s,s′∈S. and n∈N.