1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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)?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Show there exists a one to one function from N to S iff function f exists
  1. There Exists Only One (Replies: 5)

Loading...