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 F is Injective & Cardinality of Domain

  1. May 18, 2014 #1
    1. The problem statement, all variables and given/known data
    Let ## S = \{ (m,n) : m,n \in \mathbb{N} \} \\ ##
    a.) Show function ## f: S -> \mathbb{N} ## defined by ## f(m,n) = 2^m 3^n ## is injective
    b.) Use part a.) to show cardinality of S.

    3. The attempt at a solution
    a.) ## f(a,b) = f(c, d ) ; a,b,c,d \in \mathbb{N} \\\\ 2^a 3^b = 2^c 3^d, ## then ## a =c \\ b=d\\ ##
    Therefore, f is injective.

    b.) Since (m,n) belong to the naturals. Their cardinality is equal to them ##\equiv \aleph_0##

    Am I right?
     
  2. jcsd
  3. May 18, 2014 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You are given ##2^a3^b=2^c3^d##. What is your argument to show a=c and b=d?

    (m,n) is not a natural. What is the "their" and "them"?
     
  4. May 18, 2014 #3
    I could state in another way, but I still have no argument as to why they are equal.
    I was thinking that I could say
    ## 2^{a-c} = 3^{ d-b} ## and somehow since there is not a power other than 0 that satisfies then
    a =c and d =b. But, I am not sure what is this "somehow" or if it is even truth. :/
    "Their" in my little head means the set S and "them" means the Natural numbers. Since the set S is denumerable, their cardinality is equal to the natural numbers.
    I am not sure, if I am right :/
     
  5. May 19, 2014 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That is a correct argument.

    Isn't S being denumerable what you are trying to prove? From part (a) you have found an injection from S to N. That isn't enough to show they have the same cardinality. What else do you need to show?
     
  6. May 19, 2014 #5
    I have to show an injective relation from N into S. Can I say that g(x,y) = (x,y), where x and y ## \in \mathbb{N} ##

    Therefore, by Cantor, Schroder, Bernstein's theorem ## \mathbb{N} \wedge S ## have the same cardinality.
     
  7. May 19, 2014 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The domain of a function from N to S is the positive integers. g can not be a function of two variables. You need g(n) = something in S.
     
  8. May 19, 2014 #7
    You are right. Just to make this clear to myself, I will define g as strictly injective and very non-surjective.
    g(n) = (n, 1), where ( n,1) ## \in S ##
     
  9. May 19, 2014 #8

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Good. Now you are getting somewhere. It's trivial, but you need to write down the steps to show g is injective. Then you can apply Shroeder-Bernstein.

    Earlier when you had the equation ##2^{a-c}=3^{d-b}## the reason that the exponents must both be zero is the unique factorization theorem for natural numbers. A number with only factors of 2 can't equal a number with only factors of 3.
     
  10. May 20, 2014 #9
    To show that ## g## is injective:
    ## g(a) = g(b ) \\ (a,1 ) = (b ,1 )##


    Then, ##a## must be equal to ## b## and ## g ## is injective.

    Thank you for the unique factorization explanation.
     
  11. May 20, 2014 #10
    Now, I am wondering... do they have to be equal? a =2 and b =3. If the only restriction is that a,b ## \in \mathbb{N}##
    What would be an argument against what I just wrote?
     
  12. May 20, 2014 #11

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, your original argument is correct. (a,b) = (c,d) if and only if a=c and b=d. Otherwise they are different points in the plane, no?
     
  13. May 20, 2014 #12
    Thanks.
     
  14. May 20, 2014 #13

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You're welcome. I just want to point out additionally, that when you have two sets like in this problem, where one of the sets seems "larger" than the other (informally, the plane seems larger than the line), the injection one way is usually a lot easier than the other way. So the map ##f(n) = (n,1)## was real easy for you to come up with. The other way ##f(a,b) = 2^a3^b## is much more difficult to dream up and I daresay you might not have ever thought of it. Me neither if I hadn't seen it before. That's why it was given as a hint.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Show F is Injective & Cardinality of Domain
  1. Domain of f o g (Replies: 10)

Loading...