0

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

Adi Dani
  • 16,949
jn025
  • 989
  • 1
    When proving injectivity, you're not proving that $x_1 = x_2$ $\textit{and}$ $f(x_1) = f(x_2)$, you're showing that $\textit{if}$ $f(x_1) = f(x_2)$ is true for some $x_1, x_2$ in the domain, $\textit{then}$ $x_1 = x_2$. – dannum Aug 27 '14 at 12:40
  • The contrapositive of a proposition is not well-described as "the opposite". In fact, the contrapositive of "$p\implies q$" is "$\text{not}-q\implies\text{not}-p$". The statements are both negated, and their order is switched. Both of those things have to happen to get a contrapositive. – G Tony Jacobs Aug 27 '14 at 13:07

2 Answers2

2

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.

G Tony Jacobs
  • 31,218
  • 1
    Would it also be correct to say "$f$ is injective if $f(x_{1}) \neq f(x_{2}) \implies x_{1} \neq x_{2}$"? – Taylor Rendon Jul 11 '22 at 14:16
  • 1
    @TaylorRendon, what you've written is a more fundamental property than injectivity. That's simply the condition that $f(x)$ be single-valued, which we often take as the definition of a function in the first place. If outputs are well-defined for each input, then different outputs must require different inputs.

    Your condition here, and that of being injective, are logical converses of each other.

     – G Tony Jacobs Jul 11 '22 at 14:46
  • Gotcha! With that said, could we say that the standard definition of injectivity could be written as $f(x_{1}) = f(x_{2}) \iff x_{1} = x_{2}$? – Taylor Rendon Jul 11 '22 at 15:44
  • 1
    Sure, that defines an injective functional relation! It also highlights that any injection is essentially a matching, or pairing-off, between elements of the domain and elements of the range. – G Tony Jacobs Jul 11 '22 at 16:24
1

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

rogerl
  • 22,399