Proofs with cases

Section 5.2 Proofs with cases

\begin{equation*} ((P \lor Q) \implies R) \equiv ( (P \implies R) \land (Q \implies R)) \end{equation*}

This tells us how to structure a proof when the hypothesis is a disjunction. That is, when the hypothesis can be broken into two (or more) cases.

Take another look at Example 5.0.2. At first glance, the hypothesis is just a single statement “\(n\) is an integer”, and it is not immediately obvious that it can be broken into separate cases. However there is a clue in the conclusion, “\(n^2+5n-7\) is odd”; it tells us to think about parity. Any integer is either even or it is odd, so we can break the hypothesis into two cases

\(n\) is even, or
\(n\) is odd.

Because of this, the original statement can be massaged into the form of Lemma 4.2.8.

\begin{equation*} ((n \text{ is even}) \lor (n \text{ is odd}) ) \implies n^2+5n-7 \text{ is odd} \end{equation*}

Lemma 4.2.8 then tells us that this is logically equivalent to

\begin{equation*} (n \text{ is even} \implies n^2+5n-7 \text{ is odd}) \land (n \text{ is odd} \implies n^2+5n-7 \text{ is odd}). \end{equation*}

To show that this conjunction is true, we just need to show that both parts are true. That is, our proof will split into two cases.

Prove that \((n \text{ is even} \implies n^2+5n-7 \text{ is odd})\text{.}\)
Prove that \((n \text{ is odd} \implies n^2+5n-7 \text{ is odd})\text{.}\)

This is an example of proof by cases.

Of course, we don’t just leap into things and write “Proof 1” and “Proof 2”; we need to explain to the reader what is happening. We need to explain that the hypothesis breaks into separate cases, and then we should make it clear where each case starts and where it ends. And, it won’t hurt to summarise at the end of the proof that since we have proved all the cases, the result is true. Be nice to your reader — an extra sentence or two can make their life much easier.

Proof.

Let \(n \in \mathbb{Z}\text{.}\) Since \(n\) can be either even or odd, we consider both cases separately.

Case 1: Assume \(n\) is even. Then \(n = 2k\) for some \(k \in \mathbb{Z}\) and \(n^2-3n+9 = 4k^2-6k+9 = 2(2k^2-3k+4)+1\text{.}\) Since \(2k^2-3k+4\) is an integer, \(n^2-3n+9\) is odd.
Case 2: Now assume \(n\) is odd, then \(n=2k+1\) for some \(k \in \mathbb{Z}\) and \(n^2-3n+9 = (4k^2+4k+1)-(6k+3)+9 = 4k^2-2k+7 = 2(2k^2-k+3)+1\text{.}\) Since \(2k^2-k+3\) is an integer, \(n^2-3n+9\) is odd.

Since both cases are true, the result follows.

The above shows the very standard structure of proof by cases or proof by case analysis. Of course, not all such proofs consist of just two cases. More generally the structure will be as follows.

Proof.

The hypothesis breaks into \(N\) cases.
Here is my proof of case 1.
Here is my proof of case 2.
\(\displaystyle \vdots\)
Here is my proof of case \(N\text{.}\)
Since I’ve proved all \(N\) cases the proof is done.

One of the hardest parts of case-analysis is to be sure that you have found all the cases. And since each case is really its own proof, it is possible that a single case breaks into several sub-cases, each of which requires its own proof. Case analysis is also sometimes called Proof by exhaustion! As an extreme example, the original proof of “The four colour theorem” by Appel & Haken in 1976 required the checking of about 1900 different cases. Thankfully that was done by a computer; though that was very controversial at the time.

4 colours by computer.

The 4 colour Theorem tells you that any map (eg, a map of countries of the world) can be coloured using no more than 4 colours, so that no two neighbouring regions have the same colour. The interested reader can search-engine their way to many articles on the topic. The original proof by Appel & Haken was one of the first computer-aided proofs. The idea of getting a computer is not without objections — if a proof involves so many logical steps that it cannot be verified by a human, then is it really a proof? Again, the interested reader should search-engine their way to articles on philosophical questions that emerge from computer-aided proof.

Note that it is significantly easier to prove that you need no more than 5 colours, and we might even do it at the end of this text (assuming the author gets around to it). No computers are required! The proof actually started as a flawed attempt to prove the 4 colour Theorem by Kempe in 1879 which was rescued a decade later by Heawood as the 5 colour Theorem.

Remark 5.2.1. Keep cases just in case “without loss of generality” causes mistakes.

You will have noticed that the two cases in the proof above are very similar. This is not unusual. It is very often the case that the cases in proof by cases are very similar to each other³⁸. Many writers will omit one or more of these similar cases and instead write “The proof of the second case is similar to the proof of the first, so we omit it”. You might also see “Without loss of generality (we will only do the first case)”, which busy hard-working mathematicians will contract to “WLOG”.

“WLOG” is a notoriously dangerous mathematical phrase³⁹ in mathematics. It sits with phrases such as

Clearly
Obviously
It is easy to show that
A quick calculation shows

Every mathematician has been caught out by one of these. What we thought would be an easy turned out to be much harder due to that little detail we didn’t consider.

Premature optimisation is the root of all evil

One should be very careful using WLOG (and its siblings). We should be very sure that the cases really are very similar. Indeed, it is much safer (as a general rule for the inexperienced prover) to actually do all those cases in your scratch work. Then determine whether or not they really are similar enough that skipping them is not going to cause any problems. And on then skip them when writting up the proof.

Here are another couple of results to play with

Lemma 5.2.2.

If two integers \(a\) and \(b\) have opposite parities then their sum is odd.

Proof.

Let \(a\) and \(b\) be integers and assume they have opposite parities. Now either \(a\) is even or \(a\) odd; we prove each case in turn.

Assume \(a\) is even. Since \(a\) and \(b\) have opposite parities, we know that \(b\) is odd. Hence we can write \(a=2k, b=2\ell+1\) for some \(k,\ell \in \mathbb{Z}\text{.}\) This means that \(a+b=2k+2\ell+1 = 2(k+\ell)+1\text{.}\) Since \(k+\ell\in\mathbb{Z}\) we know that \(a+b\) is odd.
Now assume \(a\) is odd. Since \(a\) and \(b\) have opposite parities, we know that \(b\) is even. Hence we can write \(a=2k+1, b=2\ell\) for some \(k,\ell \in \mathbb{Z}\text{.}\) This means that \(a+b=2k+2\ell+1 = 2(k+\ell)+1\text{,}\) and since \(k+\ell\in\mathbb{Z}\) we know that \(a+b\) is odd.

In both cases, \(a+b\) is odd as required.

and

Lemma 5.2.3.

Let \(a,b \in \mathbb{Z}\text{.}\) The number \(ab\) is even if and only if \(a\) is even or \(b\) is even.

Proof.

Let \(a,b\) be integers. We prove each implication in turn.

To prove the forward implication we prove the contrapositive. Hence assume that both \(a,b\) are odd. So we can write \(a=2k+1\) and \(b=2\ell+1\) where \(k,\ell \in \mathbb{Z}\text{.}\) Now \(ab = (2k+1)(2\ell+1) = 4k\ell + 2k+2\ell+1 = 2(2k\ell + k + \ell)\text{.}\) Since \(2k\ell+k+\ell \in \mathbb{Z}\) we know that \(ab\) is odd as required.
The reverse implication breaks into two cases.
- Assume \(a\) is even. Then we can write \(a=2k\) where \(k\in\mathbb{Z}\text{.}\) So \(ab=2kb=2(kb)\text{.}\) Since \(kb\in\mathbb{Z}\) it follows that \(ab\) is even.
- Now assume that \(b\) is even. Then we can write \(b=2\ell\) where \(\ell\in\mathbb{Z}\text{.}\) So \(ab=2a\ell=2(a\ell)\text{.}\) Since \(a\ell\in\mathbb{Z}\) it follows that \(ab\) is even.
In either case \(ab\) is even as required.

Remark 5.2.4. Symmetry and WLOG.

These last two results display a great deal of symmetry. That is, one can swap \(a\) and \(b\) without changing the result. That symmetry indicates that it may be possible to shorten the proof, by appealing to that symmetry to justify why a case can be skipped. However, correctly identifying such symmetries and their consequences takes practice. Consequently we still recommend that you avoid WLOG-ing when working through this book, and only WLOG once you have spent many more hours proving things.

Result 5.2.5.

Let \(n \in \mathbb{Z}\text{,}\) then \(3 \mid n\) if and only if \(3 \mid n^2\text{.}\)

In order to prove this we’ll make use of Euclidean division. We stated this at the beginning of Chapter 3 as Fact 3.0.3. Please revise it before continuing.

Fact 3.0.3 tells us that every integer \(n\) can (by dividing by two) be written uniquely as either

\begin{equation*} n = 2k \qquad \text{ or } \qquad n=2k+1 \end{equation*}

for some integer \(k\text{.}\) That is, every integer is either even or odd. The same result tells that every integer \(n\) can (by dividing by three) be written uniquely as

\begin{equation*} n = 3k \qquad \text{ or } \qquad n=3k+1 \qquad \text{ or } \qquad n=3k+2 \end{equation*}

for some integer \(k\text{.}\) It is this consequence of Euclidean division that will help us prove our result. Time for some scratch work.

It is a biconditional statement so we need to prove both the forward implication and the reverse implication.

\((\implies)\text{:}\) Assume \(3\mid n\text{,}\) so \(n = 3k\) where \(k\) is some integer. Hence \(n^2 = 9k^2\) which is a multiple of 3. Not so bad.
\((\Leftarrow)\text{:}\) If we try assuming that \(3 \mid n^2\) we aren’t going to get very far, so instead we look at the contrapositive.

\begin{equation*} 3 \nmid n \implies 3\nmid n^2 \end{equation*}

Here is where we can use Euclidean division.
Any integer \(n\) can be written uniquely as one of \(n=3k, n=3k+1\) or \(n=3k+2\) where \(k \in \mathbb{Z}\text{.}\) Now, we assume that \(3 \nmid n\text{,}\) so we cannot have \(n=3k\text{.}\) Hence we have 2 cases to explore, namely \(n=3k+1, n=3k+2\text{.}\)
- If \(n=3k+1\) then \(n^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1\text{,}\) and so is not divisible by 3
- If \(n=3k+2\) then \(n^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1\text{,}\) and so is not divisible by 3
Since both cases work out, we are ready to write things up nicely.

Proof of Result 5.2.5.

We prove each implication in turn.

We start with the forward implication. Assume that \(3\mid n\text{,}\) so \(m=3k\) where \(k\in\mathbb{Z}\text{.}\) Hence \(n^2=3(3k^2)\text{,}\) and since \(3k^2 \in \mathbb{Z}\) we know that \(3 \mid n^2\text{.}\)
To prove the reverse implication we prove the contrapositive. Assume that \(n\) is an integer, and that \(3 \nmid n\text{.}\) Hence (by Euclidean division), we know that either \(n=3k+1\) or \(n=3k+2\) where \(k\) is some integer.
- Assume that \(n=3k+1\text{,}\) then \(n^2=3(3k^2+2k)+1\text{,}\) and so is not divisible by 3.
- Similarly, if we assume that \(n=3k+2\text{,}\) then \(n^2=3(3k^2+4k+1)+1\text{,}\) and so is not divisible by 3.
In either case we conclude that \(3\nmid n^2\) as required.

Remark 5.2.6. The importance of uniqueness.

Notice that in the above scratch work and proof we have used the uniqueness of Euclidean divison to show that \(n^2\) is not divisible by 3. Once we have shown (in a case) that \(n^2 = 3\ell+1\) for some integer \(\ell\text{,}\) Fact 3.0.3 tells us that there is no other way to write \(n^2 = 3q\) with \(q \in \mathbb{Z}\text{.}\) Similarly, in the case where we show that \(n^2=3\ell+2\text{,}\) the uniqueness of Euclidean division means that there is no way for us to write \(n^2\) as 3 times an integer.

We have now had some practice with direct and contrapositive proofs, as well as proof by cases. It will soon be time to go back and do some more logic; we really need to look at quantifiers. But before that, we should do one two more examples of proof by cases — congruence modulo \(n\text{,}\) and the triangle inequality.

Enough cases for a luggage related pun if only we could pack one in here. Sorry.

We keep a list. Well — we should keep a list.

PLP: An introduction to mathematical proof

Search Results:

Section 5.2 Proofs with cases

Proof.

Proof.

Remark 5.2.1. Keep cases just in case “without loss of generality” causes mistakes.

Lemma 5.2.2.

Proof.

Lemma 5.2.3.

Proof.

Remark 5.2.4. Symmetry and WLOG.

Result 5.2.5.

Proof of Result 5.2.5.

Remark 5.2.6. The importance of uniqueness.