-3
$\begingroup$

I am having trouble in understanding the difference between a contrapositive and a contradiction. For example, on one of my practice exam, there was a question that asked to prove that $n$ is even if $n$ is an integer and $n^2 + 5$ is odd using both a contrapositive and a contradiction. When I proved it, I assumed $n$ is odd and assigned it to $2k + 1$. What method am I using right now? How would the other method look like.

$\endgroup$
3
  • $\begingroup$ Note that the implication you are dealing with says $$\text{If }\;n \text{ is an integer and } n^2+5 \text{ is odd, then } n \text{ is even }$$ $\endgroup$
    – amWhy
    Dec 9 '16 at 22:43
  • $\begingroup$ Contrapositive, assume $n$ is odd, and then prove $n^2 + 5$ is even. $\endgroup$
    – amWhy
    Dec 9 '16 at 22:44
  • $\begingroup$ Contradiction: Given $n$ is an integer, Assume that $n^2 + 5$ is odd and that $n$ is not even, i.e. $n$ is odd. Using those assumptions, arrive at a contradiction. Conclude that those assumptions cannot both be true. $\endgroup$
    – amWhy
    Dec 9 '16 at 22:48
0
$\begingroup$

There are a few ways to prove a statement of the form "if $A$ then $B$":

  1. Directly: assume $A$, then derive $B$
  2. By Contrapositive: assume not $B$, then derive not $A$
  3. By Contradiction: assume $A$ and not $B$, then derive a contradiction.

So the difference is that in proof by contradiction you assume $A$, while in proof by contrapositive you do not. Also the goals are different: in proof by contradiction you wish to derive a contradiction, whereas in proof by contrapositive you wish to derive not $A$.

In your case, $A$ is "$n^2+5$ is odd" and $B$ is "$n$ is even". It sounds like you were doing contrapositive, because you started by assuming not $B$, i.e., "$n$ is odd" presumably then to derive not $A$, i.e., "$n^2+5$ is even".

$\endgroup$
0
$\begingroup$

To prove the implication $p \rightarrow q$, one can assume $p$ to be true, then show that $q$ follows from it.

Or, one can prove the contrapositive, i.e. $\neg q \rightarrow \neg p$, by assuming $q$ to be false, then showing that $p$ being false follows from it.

Or, one can prove that $p \wedge \neg q$ is a contradiction. i.e., prove $(p \wedge \neg q) \rightarrow F$, by simultaneously assuming $p$ to be true and $q$ to be false, then showing that this leads to an impossible situation.

$\endgroup$

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