# Need help on proof for injectivity of a function

I have a function, $f(x, y) = (x + y, x)$.

The proof that this function is injective, is as follows:

Say that $f(x,y)=f(x′,y′)$. We are assuming that two different inputs give the same output. For $f$ to be injective we need to prove that the inputs actually are the same. So we have $f(x,y)=f(x′,y′)$ and we need to prove that $x=x′$ and $y=y′$. That $f(x,y)=f(x′,y′)$ means that $(x+y,x)=(x′+y′,x′)$. But if this is true then we certainly have that $x=x′$.

What I don't understand is the "But if this is true" part. If it is true seems to imply that it also could not be true, so how does this proof anything? I mean, the proof seems to be assuming a couple of things, so how does this make for a concrete proof?

-
I think it may be perhaps eluding to the fact that if the images are equal, we have $x=x'$ and therefore $y=y'$. However, there may be several elements whose images do not equal a particular point in the range of $f$. –  Clayton Dec 14 '12 at 13:37

Our function $f$ takes any $(x,y)$ to $(x+y,x)$.

We want to show that if $f(a,b)=f(a',b')$ then $(a,b)=(a',b')$, meaning that $a=a'$ and $b=b'$.

So suppose that $f(a,b)=f(a',b')$. We will show that $a=a'$ and $b=b'$. (Thus, until the conclusion that $a=a'$ and $b=b'$, we are working under the assumption that $f(a,b)=f(a',b')$.)

We have $f(a,b)=(a+b,a)$ and $f(a',b')=(a'+b',a')$.

(comment later) If $(a+b,a)=(a'+b',a')$, then it is immediate that $a=a'$. (We compared second terms of the ordered pairs.) Half done!

Since $a+b=a'+b'$, and $a=a'$, it follows that $b=b'$. Finished!

Comment: Exactly as in the proof you quoted, we deliberately used "If" language. Remember, we are assuming that $f(a,b)=f(a',b')$. We could have written instead "Since $(a+b,a)=(a'+b',a')$ $\dots$. In this context, that would have meant the same thing. We are only examining situations where $f(a,b)=f(a',b')$.

Remark: There is less to the situation than meets the eye. Suppose for example that we are told that $f(x,y)=(45,12)$. Since $f(x,y)=(x+y,x)$, we must have $x=12$. And since $x+y=45$, we must have $y=33$.

-
But wouldn't that mean that you still can't say if a function is injective? –  Garth Marenghi Dec 14 '12 at 13:53
We (and the original) have proved that for any $(a,b)$ and $(a',b')$, if $f$ sends $(a,b)$ and $(a',b')$ to the same object, then $(a,b)$ and $(a',b')$ must have been the same. That's the definition of injectivity. –  André Nicolas Dec 14 '12 at 13:58

To prove that a function $g$ is injective, we need to show that if $g(a)=g(b)$ then $a=b$. This is equivalent to saying that if $a\neq b$ then $g(a)\neq g(b)$. That is, different elements in the domain are mapped to different elements in the codomain.

In your example, what needs to be shown is that if $f(x,y)=f(x',y')$ then $(x,y)=(x',y')$. So we assume that $f(x,y)=f(x',y')$ holds and try to deduce $(x,y)=(x',y')$ from that.

Now if $f(x,y)=f(x',y')$ then $(x+y,x)=(x'+y',x')$. This is equivalent to saying that $x+y=x'+y'$ and $x=x'$, since equality between ordered pairs means equality in each component. It follows that $x=x'$ and $y=y'$ so that $(x,y)=(x',y')$.

-
Thank you for your explanation! –  Garth Marenghi Dec 14 '12 at 20:23