Is f(m, n) = (m - n, n) a Bijective Function and What is its Inverse?

[twoski]

Homework Statement

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_{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.

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

 

[jgens]

Can i just compute the inverse to prove it (since any function with an inverse is bijective)?

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

 

[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.

 

[haruspex]

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.

In principle, you might be able to prove it's bijective by some means other than demonstrating a two-sided inverse.

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.

That's because f yields a pair of numbers, not one number. Try f(m,n) = (x, y)

 

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

 

[haruspex]

Hmm, i can't figure out any other proof method other than computing the inverse. Would an attempted proof by contradiction be sufficient?

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.

So inverting (x,y) would be as simple as just making it (y,x), right?

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?

 

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

 

[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...

 

[haruspex]

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.

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?

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

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

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

g(x,y) = (x+y,y) = (m,n)... i think...

Yes.

 

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

 

[haruspex]

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

Yes.