Functions Problem 4

Recap of definitions: \(h:\mathbb{Z}\rightarrow \mathbb{Z}\) is known to be onto. \(f:\mathbb{Z}^2\rightarrow \mathbb{Z}\) is defined by \(f(x,y) = h(x)+h(y)\).

Getting started

Before trying to write the proof, you need to figure out how to take an output value k and find a pre-image for it. For example, suppose k=17. How are you going to find values for x and y such that f(x,y) = 17?

Notice that h is known to be onto. So if I pick some value of k, e.g. k=17, I know there is an x such that h(x)=17. I don't know exactly what x is, but I know it exists. This also works for special values. E.g. if I want to have h(x) = 1, there is a value for x that will do that.

It might help to first consider the simpler function g, defined by g(x,y) = x + y. How would you find input values for x and y that would give you (say) 17 as the output value? If I give you a symbolic output value k, can you find me values for x and y such that g(x,y) = k?

Writing the final draft

Once you've solved the above, you need to write out your proof in logical order. Pick a random output value k. Then tell the reader your choices for x and y (typically defined in terms of k and h). Then verify that f(x,y) = k.