Set theory help
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.
Take the fibers of each element of under and generated the obvious bijection...can you see where to go from there?
Originally Posted by KSM08