Proving injective (1-1) using contrapositive

$\begingroup$

Given function $f:\mathbb Z \to \mathbb Z$ defined by $f(n) = n - 6$

$\mathbb Z$ in this case is the set of integers.

Suppose for $x_1$, $x_2 \in \mathbb Z$, we have $f(x_1) = f(x_2)$.

This means that $x_1 - 6 = x_2 - 6$

Hence $x_1 = x_2$. By the law of contrapositive, $f$ is 1-1 (injective)

I understand that the contrapositive of the preposition is generally the opposite (I think) but when proving 1-1 you want to prove that $x_1 = x_2$ and $f(x_1) = f(x_2)$ This proves that they are equal, why would you want to prove this? it violates 1-1? I feel like I'm missing the point of contrapositive proof..

$\endgroup$ 2

2 Answers

$\begingroup$

There are different equivalent definitions that can be given for injectivity. For example, "$f$ is injective if $f(x_1)=f(x_2)\implies x_1=x_2$," is one. Another would be its contrapositive, namely: "$f$ is injective if $x_1\neq x_2\implies f(x_1)\neq f(x_2)$."

Whichever one of those is your definition, the other is the contrapositive. In the answer provided by @rogerl, you see proofs of both.

$\endgroup$ $\begingroup$

The statement you are trying to prove is "if $f(x_1) = f(x_2)$ then $x_1 = x_2$". You have indeed proven that, but using a direct proof: you started by assuming $f(x_1)= f(x_2)$ and showed that indeed $x_1 = x_2$.

The contrapositive of this statement is "If $x_1\ne x_2$ then $f(x_1) \ne f(x_2)$". A proof by contrapositive would thus proceed something like this: choose $x_1\ne x_2$. Then $f(x_1) = x_1-6$ and $f(x_2) = x_2-6$. But $x_1\ne x_2\ \Rightarrow\ x_1-6\ne x_2-6\ \Rightarrow\ f(x_1)\ne f(x_2)$.

If you think these two proofs do not look very different, you are right. For a statement that is much easily proved by contradiction, try "If $n$ is a positive integer leaving a remainder of 2 or 3 when divided by 4, then $n$ is not a perfect square."

$\endgroup$ 5

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy