Direct proof and proof by cases

Knowing exactly what a statement claims does not tell you how to establish it, and most statements worth proving are conditionals about every number of some kind.

The previous lesson gave the language: "for all", "there exists", and the rules for negating them. It closed on a claim it could state but not prove, that the square of every odd integer is one more than a multiple of $8$ . This lesson supplies the method, the direct proof, and proves that claim along the way. It works with two definitions, divisibility and parity, then splits proofs into cases, and proves that things exist, both by producing them and without saying what they are.

Assume the hypothesis, reach the conclusion

A conditional $P \Rightarrow Q$ is false in exactly one situation: $P$ true and $Q$ false. So to prove it, there is only one situation to rule out. Assume $P$ , and derive $Q$ from it, using definitions, axioms and results already proved. If $P$ happens to be false, the conditional is true anyway, which is why a proof never has to say anything about that case. This is a direct proof: it starts at the hypothesis and walks forward to the conclusion.

Most theorems are also universal. "If an integer is divisible by $4$ , it is even" means $\forall n \in ℤ (4 divides n \Rightarrow n is even)$ , and no list of cases can cover every $n$ . The move that does is to let $n$ be arbitrary: name an integer $n$ , assume nothing about it except the hypothesis, and reason about it. Whatever follows then follows for every integer, because nothing in the argument depended on which one was named. The proofs in the previous lesson that ended "as $x$ was arbitrary, the statement holds" used exactly this.

Together these fix the opening and closing lines of almost every proof in this course. The first sentence names the arbitrary object and states the hypothesis: "Let $n$ be an integer divisible by $4$ ." The last sentence states the conclusion and says which definition it satisfies: "so $n$ is even." Everything in between is the work, and each line of it must be justified by what came before.

Once $n$ is named, the proof may not quietly assume it is positive, or prime, or small, unless the hypothesis says so. Checking $n = 4$ , $8$ and $12$ is not a proof about an arbitrary $n$ ; it is three examples.

Finding a proof usually runs the other way. On scrap paper, write the conclusion out by its definition, so that " $n$ is even" becomes " $n = 2 \times$ (some integer)", and ask what would produce that expression. Then write the argument forwards, from hypothesis to conclusion, for the reader. The scrap paper is how you found the route; the proof is the route.

Divisibility

For integers $a$ and $b$ , $a$ divides $b$ , written $a ∣ b$ , if there is an integer $k$ with $b = a k$ . So $3 ∣ 12$ because $12 = 3 \times 4$ , and $- 4 ∣ 12$ because $12 = (- 4) (- 3)$ . Every integer divides $0$ , since $0 = a \times 0$ , and $1$ divides every integer. On the other hand $0 ∣ b$ only when $b = 0$ , since $0 \times k$ is always $0$ .

Two points about the notation catch almost everyone once. First, $a ∣ b$ is a statement, true or false, while $\frac{b}{a}$ is a number: " $3 ∣ 12$ " is true, and writing " $3 ∣ 12 = 4$ " mixes a sentence with a calculation. Second, the order matters: $3 ∣ 12$ is true and $12 ∣ 3$ is false, because no integer $k$ gives $3 = 12 k$ .

The definition has the same shape as the definitions of even and odd from the first lesson of this course, a "there is an integer $k$ ", and it is used in the same two ways. To use $a ∣ b$ , name the $k$ and write $b = a k$ . To prove $a ∣ b$ , produce an integer $k$ with $b = a k$ . Parity is a special case: an integer $n$ is even exactly when $2 ∣ n$ .

Example. Prove that for all integers $a$ , $b$ and $c$ , if $a ∣ b$ and $b ∣ c$ , then $a ∣ c$ .

Let $a$ , $b$ and $c$ be integers with $a ∣ b$ and $b ∣ c$ . By the definition of divisibility, there is an integer $k$ with $b = a k$ , and there is an integer $m$ with $c = b m$ . Substituting the first equation into the second gives $c = (a k) m = a (k m)$ . Since $k$ and $m$ are integers, $k m$ is an integer. So $c$ is $a$ times an integer, and by the definition of divisibility, $a ∣ c$ .

The two quotients get different letters, $k$ and $m$ , because nothing says they are equal. The scrap-paper route was short: the goal asked for $c$ in terms of $a$ , and the hypotheses chain $c$ to $b$ and $b$ to $a$ . This property, transitivity, lets divisibility pass along a chain: from $3 ∣ 12$ and $12 ∣ 60$ , without any division, $3 ∣ 60$ .

Now you. Prove that for all integers $a$ , $b$ and $c$ , if $a ∣ b$ and $a ∣ c$ , then $a ∣ (b x + c y)$ for all integers $x$ and $y$ .

Answer

Let $a$ , $b$ and $c$ be integers with $a ∣ b$ and $a ∣ c$ , and let $x$ and $y$ be any integers. By the definition of divisibility, there are integers $k$ and $m$ with $b = a k$ and $c = a m$ . Then $b x + c y = a k x + a m y = a (k x + m y)$ . Since $k$ , $m$ , $x$ and $y$ are integers, $k x + m y$ is an integer, so by the definition of divisibility, $a ∣ (b x + c y)$ . Taking $x = y = 1$ gives $a ∣ (b + c)$ , and taking $x = 1$ , $y = - 1$ gives $a ∣ (b - c)$ .

Proof by cases

Sometimes no single argument covers every value, but a few arguments do, each covering part. A proof by cases splits the hypothesis into possibilities that together exhaust it, and gives a direct proof in each. Its logic is the rule for "or": if $P_{1} \lor P_{2}$ holds, and $P_{1} \Rightarrow Q$ and $P_{2} \Rightarrow Q$ both hold, then $Q$ holds.

The commonest split is by parity, which rests on a fact taken as known here: every integer is even or odd, and none is both. (That fact comes from division with remainder, not from the definitions alone.) Take the claim that $n^{2} + n$ is even for every integer $n$ .

Let $n$ be an integer. If $n$ is even, then $n = 2 k$ for some integer $k$ , and $n^{2} + n = 4 k^{2} + 2 k = 2 (2 k^{2} + k)$ , which is even. If $n$ is odd, then $n = 2 k + 1$ for some integer $k$ , and $n^{2} + n = (4 k^{2} + 4 k + 1) + (2 k + 1) = 2 (2 k^{2} + 3 k + 1)$ , which is even. Since $n$ is even or odd, $n^{2} + n$ is even in every case.

A result once proved becomes a tool. Here is the previous lesson's open claim. Let $n$ be an odd integer, so $n = 2 k + 1$ for some integer $k$ . Then $n^{2} = 4 k^{2} + 4 k + 1 = 4 (k^{2} + k) + 1$ . By the result just proved, applied to the integer $k$ , there is an integer $m$ with $k^{2} + k = 2 m$ . So $n^{2} = 8 m + 1$ , and $8 ∣ (n^{2} - 1)$ . For $n = 7$ that is $49 = 8 \times 6 + 1$ , and for $n = 11$ it is $121 = 8 \times 15 + 1$ . No case split was needed in this proof; the one inside the lemma did the work.

The triangle inequality

The absolute value of a real number is itself defined by cases: $| x | = x$ if $x \geq 0$ , and $| x | = - x$ if $x < 0$ . So any claim about absolute values invites a proof by cases on signs, because in each case the bars can be replaced by something plain.

Example. Prove that $| x + y | \leq | x | + | y |$ for all real numbers $x$ and $y$ .

Let $x$ and $y$ be real numbers. There are three cases, according to their signs.

If $x \geq 0$ and $y \geq 0$ , then $x + y \geq 0$ , so $| x + y | = x + y = | x | + | y |$ .

If $x < 0$ and $y < 0$ , then $x + y < 0$ , so $| x + y | = - (x + y) = (- x) + (- y) = | x | + | y |$ .

If one is non-negative and the other negative, the claim is symmetric in $x$ and $y$ , so we may suppose $x \geq 0 > y$ . Then $| x | = x$ and $| y | = - y$ . Now $| x + y |$ is either $x + y$ or $- (x + y)$ . In the first event, $x + y < x \leq x - y = | x | + | y |$ , since $y < 0$ . In the second, $- (x + y) = - x - y \leq - y \leq x - y = | x | + | y |$ , since $x \geq 0$ .

The three cases exhaust all pairs of real numbers, and the inequality holds in each, so it holds for all $x$ and $y$ .

Two things make a case split sound. The cases must between them cover everything, which is why "one non-negative and one negative" had to be there; checking only the first two cases would prove nothing about $x = 3$ , $y = - 5$ . And "we may suppose" is honest only when the omitted case is the same argument with the letters swapped. The cases may overlap harmlessly, but none may be missing.

Now you. Prove that $| x y | = | x | | y |$ for all real numbers $x$ and $y$ .

Answer

Let $x$ and $y$ be real numbers. If $x \geq 0$ and $y \geq 0$ , then $x y \geq 0$ , so $| x y | = x y = | x | | y |$ . If $x < 0$ and $y < 0$ , then $x y > 0$ , so $| x y | = x y = (- x) (- y) = | x | | y |$ . Otherwise one is non-negative and one negative; the claim is symmetric, so suppose $x \geq 0 > y$ . Then $x y \leq 0$ , so $| x y | = - x y = x (- y) = | x | | y |$ (when $x y = 0$ both readings of $| x y |$ give $0$ ). The cases cover every pair, so the equation always holds.

Proving that something exists

A claim $\exists x P (x)$ is proved most plainly by producing an $x$ and checking $P (x)$ . Such a proof is constructive. When the claim is $\forall k \exists n$ , the $n$ may depend on $k$ , so the proof must give a recipe.

Take the claim that for every natural number $k$ there are $k$ consecutive natural numbers, none of them prime. Let $k$ be a natural number and write $N = (k + 1)!$ , the product $1 \times 2 \times \dots \times (k + 1)$ . Consider the $k$ numbers $N + 2, N + 3, \dots, N + (k + 1)$ . Each has the form $N + j$ with $2 \leq j \leq k + 1$ . Then $j ∣ N$ , since $j$ is one of the factors of $N$ , and $j ∣ j$ , so $j ∣ (N + j)$ by the Now you on divisibility. As $2 \leq j < N + j$ , the number $N + j$ has a divisor other than $1$ and itself, so it is not prime.

For $k = 5$ the recipe gives $N = 720$ and the run $722$ to $726$ . It is far from the first such run, which is $24$ to $28$ . A constructive proof must produce a witness, not the best one.

Existence without a witness

Some existence proofs never say which object works. Here is the classic, which assumes that $\sqrt{2}$ is irrational (the next lesson proves it).

Example. Prove that there are irrational numbers $a$ and $b$ with $a^{b}$ rational.

Consider the real number ${\sqrt{2}}^{\sqrt{2}}$ . It is either rational or irrational. If it is rational, take $a = b = \sqrt{2}$ : both are irrational and $a^{b} = {\sqrt{2}}^{\sqrt{2}}$ is rational. If it is irrational, take $a = {\sqrt{2}}^{\sqrt{2}}$ and $b = \sqrt{2}$ , both irrational, and then $a^{b} = ({\sqrt{2}}^{\sqrt{2}})^{\sqrt{2}} = {\sqrt{2}}^{\sqrt{2} \cdot \sqrt{2}} = {\sqrt{2}}^{2} = 2$ , which is rational. In either case a suitable pair exists.

This is a proof by cases in which the cases are never resolved. It establishes that one of two pairs works without saying which, so it is non-constructive. The answer is known from outside the proof: Aleksandr Gelfond and Theodor Schneider showed, independently in the 1930s, that ${\sqrt{2}}^{\sqrt{2}}$ is irrational, so the second pair is the one. Some mathematicians, the constructivists, reject such proofs, because they rest on the claim that every statement is true or false even when nobody can say which.

Now you. Given that $\sqrt{2}$ and $\log_{2} 9$ are irrational, give a constructive proof of the same claim.

Answer

Take $a = \sqrt{2}$ and $b = \log_{2} 9$ , both irrational. Since $\sqrt{2} = 2^{\frac{1}{2}}$ , we get $a^{b} = 2^{\frac{1}{2} \log_{2} 9} = 2^{\log_{2} 3} = 3$ , using $\frac{1}{2} \log_{2} 9 = \log_{2} 9^{\frac{1}{2}} = \log_{2} 3$ . So $a^{b}$ is rational, and this time the pair is named.

Where the direct route stalls

Every proof above ran forwards: unpack the hypothesis by its definition, then rearrange until the conclusion's definition appears. Try the same on "for every integer $n$ , if $n^{2}$ is even then $n$ is even". Let $n$ be an integer with $n^{2}$ even, so $n^{2} = 2 k$ for some integer $k$ . The goal is $n = 2 \times$ (an integer), and all the hypothesis offers is $n = \pm \sqrt{2 k}$ , which is not visibly twice anything.

The hypothesis is about $n^{2}$ and the conclusion is about $n$ , and information does not flow backwards through squaring. Cases on the parity of $n$ only help by ruling the odd case out, which is a different method in disguise. The statement is true, and the next lesson proves it by turning the conditional round, the same move that proves $\sqrt{2}$ irrational.