Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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')$.

share|improve this answer
    
Thank you for your explanation! –  Garth Marenghi Dec 14 '12 at 20:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.