Guidelines on using Proof by Contrapositive

Question

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?

Answer 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$

Answer 2

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.

Answer 3

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