I have two set theory questions I'm stuck on:
1) Prove that the following properties of a set are equivalent:
i) There exists an injective function f : N → X (N is the set of natural numbers (sometimes called omega))
ii) there exists a function g : X → X which is injective but not surjective.
Now, I think I can show that ii) implies i) by using the recursion theorem to construct a function, and showing that it is 1-1. (Define f:N → X by recursion:
f(0)=c, (c in X/ran(f))
f is one-one. Does this look right?)
However, I'm struggling to show that i) implies ii).
2) Let A, X and Y be sets such that X≤A. Prove that Y ^X≤Y ^A. Deduce that, for cardinals κ, λ and μ, if κ ≤ λ, then κμ ≤ λμ. (Y^X is the set of functions from Y into X). Now, clearly I have to define some function from Y ^X into Y ^A, but I don't know how to go about this, particularly since the members of Y ^X and Y ^A are themselves functions...
Any help greatly appreciated.