Originally Posted by

**KSM08** Hi,

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(n+)= g(f(n))

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.