1

I am fairly new to writing proofs and am having difficulty understanding when to use a proof by contrapositive. A truth table clearly shows that $\neg Q\implies\neg P$ implies that $P\implies Q$. Given true propositions to prove, this is not much of a problem. But something like this is definitely not true:

Proposition: If $k$ is a positive integer, then $k \ge 5$.

Proof: Suppose $k$ is not a positive integer. Then $k$ is a negative integer. Since $k<0$, and $0<5$, it follows that $k<5$. Thus, $k$ is not greater than or equal to $5$.

Though the validity of this statement can easily be determined, I am not sure if I would be able to tell so quickly with a highly complex problem. Is there some sort of checklist to verify that a proof by contrapositive can be used?

Lisa K
  • 13
  • What you have there is not a proof by contrapositive. If you want to prove $P\to Q$, you can instead choose to prove $\neg Q\to \neg P$. But here you're instead proving $\neg P\to\neg Q$, which is neither here nor there. – hmakholm left over Monica Aug 31 '19 at 17:38

3 Answers3

1

Two immediate things:

The Proposition is not true ... and so it has no proof. But you could give a disproof: just point out that something like $k=2$ is a positive integer, but not greater or equal to $5$

Second, your attempt to prove the statement was not a proof by contrapositive. You showed $\neg P \to \neg Q$, rather than $\neg Q \to \neg P$

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • Thank you, upon trying to revise the starting statement to k<5 I found it difficult to draw the conclusion that k is not positive. I'm guessing that this will probably be the case for proof by contrapositive is not applicable. – Lisa K Aug 31 '19 at 17:38
  • Because the statement is not true. The contrapositive has the same truth value of the original statement, which is false. – Derek Luna Aug 31 '19 at 17:40
0

You can use a proof by contraposition whenever you have an implication to prove. A good guideline for when you maybe should use a proof by contraposition is when the negation of the conclusion is easier to work with mathematically than the hypothesis of the statement.

Here's an example. Let's say that in number theory we needed to prove that $a\not\mid b\to a^2\not\mid b^2$. ($a\mid b$ means that $a$ is a factor of $b$.) Starting a proof with $a\not\mid b$ doesn't give me a lot of natural ideas for the next step. But the contrapositive of this statement is $a^2\mid b^2\to a\mid b$. That's much easier to work with. Then I can assume that $a^2\mid b^2$, which lets me pick some integer $k$ such that $b^2=ka^2$, and then I can move on from there.

0

The implication $P\Rightarrow Q$ is logically equivalent to the contraposition $\neg Q\Rightarrow \neg P$.

So instead of proving "If $k$ is a positive integer, then $k\geq 1$'' you could show "If $k<1$, then $k$ is not a positive integer".

Wuestenfux
  • 20,964