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

1. Oct 30, 2011

### h.shin

1. The problem statement, all variables and given/known data
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.)

2. Relevant equations

3. 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?

2. Oct 30, 2011

### 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?

3. Oct 30, 2011

### h.shin

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

4. Oct 30, 2011

### Dick

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)?