PG2.4 The contrapositive, and proof by cases

Simulate

Check the claim with numbers

Take two claims about integers: if $n^2$ is even, then $n$ is even; and $n^2 + n$ is even for every $n$ . The cell tests both on every integer from $-1000$ to $1000$ .

ns = range(-1000, 1001) print("integers tested:", len(ns)) print("n^2 even but n odd:", [n for n in ns if n**2 % 2 == 0 and n % 2 == 1]) print("n odd but n^2 even:", [n for n in ns if n % 2 == 1 and n**2 % 2 == 0]) print("n^2 + n odd:", [n for n in ns if (n**2 + n) % 2 == 1])

⌘/Ctrl + Enter runs the cell

All three searches come back empty, and the first two look for the same integers in different words. A counterexample to the claim is one to its contrapositive (lesson PG1.2), and the other way round. So the claim can be proved through its contrapositive.

Conjecture

n

Two thousand and one integers agree. The integers never end, so each claim needs a proof that covers every $n$ .

Two more techniques

A direct proof of claim 1 starts from $n^2 = 2k$ . To learn about $n$ it would take a square root, $n = \sqrt{2k}$ , which says nothing about whether $n$ is even. The contrapositive starts from the other end, where the algebra is easy.

Rule: Proof by contrapositive

\begin{gathered} \text{to prove } P \Rightarrow Q, \\ \text{prove } \neg Q \Rightarrow \neg P \end{gathered}

Lesson PG1.2 proved that the two are equivalent, so proving one proves the other. Use it when "not $Q$ " gives you more to work with than $P$ does.

Here $P$ is " $n^2$ is even" and $Q$ is " $n$ is even". Every integer is even or odd and not both (lesson PG2.1), so "not even" means odd. The contrapositive reads: if $n$ is odd, then $n^2$ is odd.

Format 1

Reorder the steps

Here is the proof of claim 1 by its contrapositive, with its lines shuffled. Put them in order.

We prove the contrapositive: if $n$ is odd, then $n^2$ is odd.
Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ .
The contrapositive holds, so the claim does too: if $n^2$ is even, then $n$ is even.
Suppose $n$ is odd, so $n = 2k + 1$ for some integer $k$ .
The number $2k^2 + 2k$ is an integer, so $n^2$ is odd.

Claim 2 has no hypothesis to work from, only "every integer $n$ ". It does split into two pieces that cover every integer: $n$ even and $n$ odd.

Rule: Proof by cases

\begin{gathered} \text{every case is } A \text{ or } B \\ A \Rightarrow Q \qquad B \Rightarrow Q \\ \text{so } Q \end{gathered}

Split the possibilities into cases that together cover everything, and prove the claim in each case. The proof is only as good as the split: a case left out is a gap.

Format 2

Fill the gap

Here is the proof of claim 2 in two cases. Fill each gap as you would a quick answer, such as 2k^2+1, then check.

n

How to type answers

Powers with ^, brackets round a power that is a sum: r^k, r^(k+1).
Fractions with / and brackets: (1-r)/(1+r). Multiply with * or side by side: 2k+1.
Press Enter in any box to check them all.

Simulate

Check a claim about absolute values

A proof by cases fails if a case is missing. Here is a tempting claim: $|x + y| = |x| + |y|$ for all real $x$ and $y$ . The cell tests it on every pair from a grid of halves from $-5$ to $5$ .

from fractions import Fraction xs = [Fraction(k, 2) for k in range(-10, 11)] pairs = [(x, y) for x in xs for y in xs] fails = [(x, y) for x, y in pairs if abs(x + y) != abs(x) + abs(y)] print("pairs:", len(pairs), " the claim fails for:", len(fails)) print("failures with x and y of opposite signs:", sum(x * y < 0 for x, y in fails)) print("x = 3, y = -5:", abs(3 + (-5)), "against", abs(3) + abs(-5))

⌘/Ctrl + Enter runs the cell

The claim fails for 200 of the 441 pairs. Every failure has $x$ and $y$ of opposite signs, such as $x = 3$ and $y = -5$ : 2 against 8.

Format 3

Find the error

This proof by cases claims that $|x + y| = |x| + |y|$ for all real $x$ and $y$ . The simulation says that is false. Select the faulty line, then say what is wrong with it.

P \Rightarrow Q

The contrapositive, and proof by cases