Show there exists a one to one function from N to S iff function f exists

[h.shin]

Homework Statement

Show that for a set S, there exists an injective function \Phi :
N \rightarrow S if and only if there exists an injective, but non-surjective
function f : S \rightarrow S. (Sets S satisfying this condition are called
innite sets.)

Homework Equations

The Attempt at a Solution

Since this is a if and only if (biconditional) statement.
I can prove this statement if i can prove the two conditional statements:
i) If \Phi: N \rightarrow S is injective then f: S \rightarrow S is injective but not surjective
ii)If f: S \rightarrow S is injective but not surjective then \Phi: N \rightarrow S is injective.

I realize that this is the step that i should take, but i just don't know how to prove these two statements..
Any help?

 

[Dick]

Take them one at a time. If you have phi:N->S is injective, you want to prove there is a function f:S->S that's injective but not surjective. You probably want to define f in terms of phi. Can you think of a function from N->N that's injective but not surjective?

 

[h.shin]

Take them one at a time. If you have phi:N->S is injective, you want to prove there is a function f:S->S that's injective but not surjective. You probably want to define f in terms of phi. Can you think of a function from N->N that's injective but not surjective?

yes, well
n--->2n is injective but not surjective

 

[Dick]

yes, well
n--->2n is injective but not surjective

Ok, so phi(n) is an element of S for all n in N. Define f(s)=phi(2n) for all of those elements of S. What's an easy way to define f(s) if s isn't in phi(N)?