Proving injective (1-1) using contrapositive
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$ 22 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
