EF Proving the contrapositive

Section 6.6 Proving the contrapositive

Recall.

P \to Q \Leftrightarrow \neg Q \to \neg P .

🔗

Procedure 6.6.1. Proof by proving the contrapositive.

🔗

To prove

P \Rightarrow Q,

you can instead prove

\neg Q \Rightarrow \neg P .

🔗

Example 6.6.2.

🔗

In Worked Example 6.3.2, we proved that the square of an even number is also even. Therefore, this also constitutes a proof of the contrapositive statement: if the square of a number is odd, then that number is also odd.

🔗

Worked Example 6.6.3.

🔗

Prove that every prime number larger than

2

is odd.

Solution.

We want to prove the following universally quantified conditional (“for all

p

” omitted, domain is positive integers).

conditional: if ( $p$ is prime and $p > 2$ ) then $p$ is odd.
contrapositive: if $p$ is not odd, then not ( $p$ is prime and $p > 2$ )
DeMorgan substitution: if $p$ is not odd, then ( $p$ is not prime or $p \leq 2$ )

These are all equivalent.

Let’s prove the last statement: as in the procedure for proving conditionals with a disjunction, start by assuming that

p

is not odd and

p > 2 .

We must then show that

p

is not prime. Since

p

is not odd, it is divisible by

2 .

But since

p > 2,

p

is divisible by a number other than

1

and

p

itself. Therefore,

p

is not prime.

🔗

Check your understanding.

🔗

Attempt Exercise 6.12.8.

Elementary Foundations: An introduction to topics in discrete mathematics