Mathematical-Reasoning · Unit 7 · Video 1 · Interactive Practice

Proving the Contrapositive When a Direct Proof Stalls

IKey Formulas

Statement	Name	Relation to $P \to Q$
$\neg Q \to \neg P$	Contrapositive: swap the parts and negate both	$P \to Q \equiv \neg Q \to \neg P$ , so a proof of one proves the other
$Q \to P$	Converse: swap the parts, negate neither	Not logically equivalent to $P \to Q$ ; it needs its own proof
$P \leftrightarrow Q$	Biconditional	$P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)$ : prove both directions

Key Insight: A direct proof of “if $n$ is even, then $n^2$ is even” proves “if $n^2$ is odd, then $n$ is odd”. Together with the earlier theorem “if $n$ is odd, then $n^2$ is odd”, it proves that for each integer $n$ , $n$ is odd if and only if $n^2$ is odd.

IICounterexamples Travel with the Contrapositive

A conditional and its contrapositive fail at exactly the same integers; the converse can fail elsewhere.

Statement Form

IIITwo Know-Show Tables

Reaching $n$ from $n^2$ needs a square root; reaching $n^2$ from $n$ only needs squaring.

Route Step 1 Example k 4

Step	Know / Show	Reason
$P$	$n^2$ is an odd integer.	Hypothesis
$P1$	$(\exists k \in \mathbb{Z})(n^2 = 2k + 1)$	Definition of odd integer
$\vdots$	gap
$\vdots$	$n = \pm\sqrt{2k + 1}$ , and no form $2q + 1$ appears: stalled	Square root of both sides of $P1$
$Q1$	$(\exists q \in \mathbb{Z})(n = 2q + 1)$	?
$Q$	$n$ is an odd integer.	Definition of odd integer

Step	Know / Show	Reason
$P$	$n$ is an even integer.	Hypothesis
$P1$	$(\exists m \in \mathbb{Z})(n = 2m)$	Definition of even integer
$P2$	$n^2 = (2m)^2 = 4m^2 = 2(2m^2)$	Substitution and algebra
$P3$	$2m^2$ is an integer.	Closure of the integers under multiplication
$Q1$	$(\exists q \in \mathbb{Z})(n^2 = 2q)$	?Steps $P2$ and $P3$ , with $q = 2m^2$
$Q$	$n^2$ is an even integer.	Definition of even integer

💡 For an integer, “not odd” means “even”; the course takes this fact as given for now.

IVProving Both Directions

Each proved conditional rules out the one truth-table row where it is false.

VQuiz Questions

Problem 1 · Form the Contrapositive

Given: the proposition “For each integer $n$ , if $n^2$ is even, then $n$ is even.” For integers, not even means odd. Which statement is its contrapositive?

✅ Correct! Swap the two parts and negate both:

\neg Q

is “

n

is odd” and

\neg P

is “

n^2

is odd”. This contrapositive is the theorem proved early in the course, so the proposition is already proved too.

❌ That is the converse. It swaps the two parts but negates neither, and a converse is not logically equivalent to the original statement.

❌ Not quite. This negates the conclusion but keeps the hypothesis in place. The contrapositive swaps the hypothesis and the conclusion and negates both of them.

❌ That is the negation. The negation of a true statement is false, while the contrapositive always has the same truth value as the original. The quantifier “for each integer

n

” stays in front of the contrapositive.

Show solution

Let $P$ be “ $n^2$ is even” and $Q$ be “ $n$ is even”. The proposition is $(\forall n \in \mathbb{Z})(P \to Q)$ .

The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ . For an integer, $\neg Q$ (“ $n$ is not even”) becomes “ $n$ is odd”, and $\neg P$ (“ $n^2$ is not even”) becomes “ $n^2$ is odd”. The quantifier stays out in front:

(\forall n \in \mathbb{Z})\,(n \text{ is odd} \to n^2 \text{ is odd}).

So the answer is c. Option a is the converse $Q \to P$ , option b is $P \to \neg Q$ , and option d is the negation of the proposition; none of them is logically equivalent to the original.

Problem 2 · Converse or Contrapositive?

Given: the true statement “For every real number $x$ , if $x = 3$ , then $x^2 = 9$ .” Which statement is logically equivalent to it, and therefore also true?

✅ Correct! This is the contrapositive

\neg Q \to \neg P

, which has the same truth value as

P \to Q

in every row of the truth table.

❌ That is the converse. It is false:

x = -3

gives

x^2 = 9

while

x \neq 3

❌ Not quite. The biconditional contains the converse as one of its two directions, and the converse fails at

x = -3

❌ Close, but… the parts are swapped, yet only the new hypothesis is negated. With

x = 0

the hypothesis

x^2 \neq 9

is true and the conclusion

x = 3

is false.

Show solution

Let $P$ be “ $x = 3$ ” and $Q$ be “ $x^2 = 9$ ”. The given statement is $P \to Q$ .

Contrapositive $\neg Q \to \neg P$ : if $x^2 \neq 9$ , then $x \neq 3$ . Logically equivalent, so it is true. This is d.
Converse $Q \to P$ : if $x^2 = 9$ , then $x = 3$ . False at $x = -3$ .
Biconditional $P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)$ : false, because its second part is the converse.
$\neg Q \to P$ : if $x^2 \neq 9$ , then $x = 3$ . False at $x = 0$ .

Problem 3 · Rescue a Stalled Proof

Given: the proposition “For each integer $n$ , if $5n + 3$ is even, then $n$ is odd.” A direct proof writes $5n + 3 = 2k$ and stalls at $n = \frac{2k - 3}{5}$ . For integers, not odd means even and not even means odd. The proof of the contrapositive writes $n = 2m$ and needs an integer $q$ with $5n + 3 = 2q + 1$ .

Which statement should be proved directly instead?

Which choice completes the proof?

✅ Correct!

5(2m) + 3 = 10m + 3 = 2(5m + 1) + 1

, and

5m + 1

is an integer, so the contrapositive and therefore the proposition are proved.

❌ That is the converse. It swaps the parts without negating them, so proving it would not prove the proposition.

❌ Only half negated. This is

\neg Q \to P

: the new hypothesis “

n

is even” is negated, but the new conclusion “

5n + 3

is even” is not. It is false at

n = 0

, where

5n + 3 = 3

❌ Only half negated. This is

Q \to \neg P

: the conclusion is negated but the hypothesis “

n

is odd” is not. It is false at

n = 1

, where

5n + 3 = 8

❌ Check the form. Swap hypothesis and conclusion, then negate both:

\neg Q

is “

n

is even” and

\neg P

is “

5n + 3

is odd”.

❌ Not an integer.

10m + 3 = 2\left(5m + \tfrac{3}{2}\right)

is true, but

q

must be an integer, and the target form is

2q + 1

, not

2q

❌ The factor of 2 is missing. With

q = 10m + 2

2q + 1 = 20m + 5

, which is not

10m + 3

. Split

10m + 3

(10m + 2) + 1

and factor

2

out of

10m + 2

❌ Off by 2. With

q = 5m

2q + 1 = 10m + 1

, but

5(2m) + 3 = 10m + 3

. Write

10m + 3 = (10m + 2) + 1

instead.

❌ Check the algebra. Compute

2q + 1

for your choice and compare it with

5(2m) + 3 = 10m + 3

Show solution

Let $P$ be “ $5n + 3$ is even” and $Q$ be “ $n$ is odd”. For an integer, $\neg Q$ is “ $n$ is even” and $\neg P$ is “ $5n + 3$ is odd”, so the contrapositive is: for each integer $n$ , if $n$ is even, then $5n + 3$ is odd.

Know: $n$ is even, so there is an integer $m$ with $n = 2m$ .

5n + 3 = 5(2m) + 3 = 10m + 3 = (10m + 2) + 1 = 2(5m + 1) + 1.

By closure of the integers under multiplication and addition, $q = 5m + 1$ is an integer, so $5n + 3 = 2q + 1$ is odd.

The contrapositive is proved for every integer $n$ . Since $P \to Q \equiv \neg Q \to \neg P$ , the original proposition is proved as well.

Problem 4 · Assemble a Biconditional

Given: two proved statements: “for each integer $n$ , if $n$ is even, then $n^2$ is even” (this video) and “for each integer $n$ , if $n$ is odd, then $n^2$ is odd” (early in the course). For integers, not even means odd. What do they prove together?

✅ Correct! The second statement is the contrapositive of “if

n^2

is even, then

n

is even”, so both conditionals hold and their conjunction is the biconditional.

❌ Not quite. “If

n

is odd, then

n^2

is odd” is exactly the contrapositive of “if

n^2

is even, then

n

is even”, so that direction is already proved.

❌ Not quite. With

P

: “

n

is even” and

Q

: “

n^2

is even”, the second statement is

\neg P \to \neg Q

. That is the contrapositive of

Q \to P

, not of

P \to Q

❌ Not quite.

P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)

, so two proved conditionals are a proof of the biconditional.

Show solution

Let $P$ be “ $n$ is even” and $Q$ be “ $n^2$ is even”.

The first statement is $P \to Q$ .
For an integer, “ $n$ is odd” is $\neg P$ and “ $n^2$ is odd” is $\neg Q$ , so the second statement is $\neg P \to \neg Q$ . Its contrapositive is $\neg\neg Q \to \neg\neg P$ , that is, $Q \to P$ .

Both $P \to Q$ and $Q \to P$ are proved for every integer $n$ , so their conjunction is proved, and

(P \to Q) \land (Q \to P) \equiv P \leftrightarrow Q.

Therefore, for each integer $n$ , $n$ is even if and only if $n^2$ is even. The answer is b.

Solved: 0 / 4