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!

Bijective Function Proof

  1. Nov 10, 2012 #1
    1. The problem statement, all variables and given/known data

    Let f : Z² to Z² be defined as f(m, n) = (m − n, n) . Is f a properly defined
    function? Is f a bijection? If yes then give a proof and derive a formula for the inverse of f. If no then explain why not.

    Also derive a formula for the composite function f[itex]_{k}[/itex], for k ∈ Z. Here f[itex]^{2}[/itex] denotes the composite function f ◦ f, f[itex]^{3}[/itex] denotes the composite function f ◦ f ◦ f, etc. (You are asked to derive the formula for f[itex]_{k}[/itex] for general k ∈ Z.) Is f[itex]_{k}[/itex] a bijection? If yes then give a proof and derive a formula for its inverse. If no then explain why not.


    3. The attempt at a solution

    So it seems the first function is properly defined since for any value x,y the function always returns a distinct pair of integers.

    I'm confused as to how i would prove it is a bijection. Can i just compute the inverse to prove it (since any function with an inverse is bijective)?
     
  2. jcsd
  3. Nov 10, 2012 #2

    jgens

    User Avatar
    Gold Member

    Yes. If you can show that f has a two-sided inverse, then that will prove that it is a bijection.
     
  4. Nov 10, 2012 #3
    I guess what confuses me is that they ask for a proof AND for the inverse. Which implies that the inverse is not an ample proof. Perhaps it's just a typo or poor wording.

    I'm not sure how to calculate the inverse of f(m,n) = ( m - n, n ) since we've only done the inverses of functions with 1 parameter in class. Normally i'd substitute f(x) with y, then swap every x with y and vice versa, then solve for y.

    If i do f(m,n) = y, it doesn't work the same way.
     
    Last edited: Nov 10, 2012
  5. Nov 10, 2012 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In principle, you might be able to prove it's bijective by some means other than demonstrating a two-sided inverse.
    That's because f yields a pair of numbers, not one number. Try f(m,n) = (x, y)
     
  6. Nov 10, 2012 #5
    Hmm, i can't figure out any other proof method other than computing the inverse. Would an attempted proof by contradiction be sufficient?

    So inverting (x,y) would be as simple as just making it (y,x), right? Would my inverted function just be f(m,n) = (n,m-n)?
     
  7. Nov 10, 2012 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I was not trying to suggest you come up with a non-constructive proof. I'm just explaining why the question as posed asked for a proof and a construction - just in case you provided a non-constructive proof.
    No. If f(m,n) = (m-n,n) = (x,y), you want to find g: Z² to Z² s.t. g(x,y) = (m,n).
    What equations can you write relating m, n, x and y?
     
  8. Nov 11, 2012 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Use the definition. A function is "bijective" if and only if it is both "injective" (if f(m,n)= f(x,y) then x= m and y= n) and "surjective" (for any integers, m, n, there exist (x, y) such that f(x,y)= (m,n)

    So suppose (m-n, n)= (x- y, y). What can you say about m and x, n and y?

    Suppose m and n are integers. Can you find x and y such that (x- y, y)= (m, n)?
     
  9. Nov 11, 2012 #8
    There is an example in my book which states something similar to what i am going to say: f(m,n) is one-to-one since f(m-n,n) =/= f(x-y,y) for all values x and y when x =/= m and y =/= n.

    It is also onto since for any value x and y, there exist values m and n such that f(x-y,y) = (m,n).

    This is how my textbook does it but it doesn't actually give a proof, is this enough?

    To find the inverse, i first suppose m-n = x, n = y.

    g(x,y) = (x+y,y) = (m,n)... i think...
     
    Last edited: Nov 11, 2012
  10. Nov 11, 2012 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Need to be quite precise here. To show it is 1-1 you need to show f(m-n,n) ≠ f(x-y,y) for all values x and y when (x,y) ≠ (m,n), i.e. when either x ≠ m or y ≠ n. Have you shown that?
    Again, not quite right. You need that for any values x and y, there exist values m and n such that f(m,n) = (x,y).
    Yes.
     
  11. Nov 11, 2012 #10
    Ah, i missed the "or" in my one-to-one proof.

    to show the formula for f[itex]_{k}[/itex] would i simply write [itex]f_{k}(m,n) = (m-(n*k),n) [/itex] ?
     
  12. Nov 11, 2012 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Bijective Function Proof
  1. Proof of Bijection (Replies: 3)

  2. Function Proof . . . (Replies: 2)

Loading...