# Homework Help: Bijective Function Proof

1. Nov 10, 2012

### twoski

1. The problem statement, all variables and given/known data

Let f : Z² to Z² be deﬁned as f(m, n) = (m − n, n) . Is f a properly deﬁned
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$_{k}$, for k ∈ Z. Here f$^{2}$ denotes the composite function f ◦ f, f$^{3}$ denotes the composite function f ◦ f ◦ f, etc. (You are asked to derive the formula for f$_{k}$ for general k ∈ Z.) Is f$_{k}$ 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. Nov 10, 2012

### jgens

Yes. If you can show that f has a two-sided inverse, then that will prove that it is a bijection.

3. Nov 10, 2012

### twoski

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
4. Nov 10, 2012

### haruspex

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)

5. Nov 10, 2012

### twoski

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

6. Nov 10, 2012

### haruspex

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?

7. Nov 11, 2012

### HallsofIvy

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

8. Nov 11, 2012

### twoski

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
9. Nov 11, 2012

### haruspex

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.

10. Nov 11, 2012

### twoski

Ah, i missed the "or" in my one-to-one proof.

to show the formula for f$_{k}$ would i simply write $f_{k}(m,n) = (m-(n*k),n)$ ?

11. Nov 11, 2012

Yes.