Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 30, 2011 #1
    1. The problem statement, all variables and given/known data
    Show that for a set S, there exists an injective function [itex]\Phi[/itex] :
    N [itex]\rightarrow[/itex] S if and only if there exists an injective, but non-surjective
    function f : S [itex]\rightarrow[/itex] 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 [itex]\Phi: N \rightarrow S[/itex] is injective then f: S [itex]\rightarrow[/itex] S is injective but not surjective
    ii)If f: S [itex]\rightarrow[/itex] S is injective but not surjective then [itex]\Phi: N \rightarrow S[/itex] 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. jcsd
  3. Oct 30, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Oct 30, 2011 #3
    yes, well
    n--->2n is injective but not surjective
     
  5. Oct 30, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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)?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook