Case Against Cases
How to avoid too many cases at least some of the time
Theon of Alexandria was history’s main editor of Euclid’s Elements.
Today I want to talk about case analysis proofs.
The connection is that Euclid is sometimes credited with inventing case analysis proofs. He can also be credited as the first to evince a desire to avoid them. Euclid made a habit of giving just one case and leaving the reader to imitate his proof for others. One example is the theorem that given a triangle with apex , every other point on the same side of the base as makes either or . Euclid gives a proof only for the case where is outside the triangle. In other cases could be inside the triangle or incident to one of its edges.
Theon lived from 335 to 405 CE in Euclid’s town of Alexandria. He was the last Director of the Library of Alexandria before its final destruction by fire toward the end of the 4th century. It is possible that he directed the entire research institution, called the Musaeum in honor of the Muses, that had been built around the library, and whose vestiges and successor the Serapeum were destroyed in or around 391 CE. He was also the father of the mathematician Hypatia, who was gruesomely murdered in 415 by a mob supporting the Christian bishop Cyril against the Roman governor Orestes whom she advised.
Sometimes Euclid left out cases of theorems or proofs because he wasn’t going to use them later. Theon filled in several such cases and even added a theorem or two of his own. His greatest service is that he filled in extra propositions and lemmas to some of Euclid’s arguments to make them easier to follow. Theon’s editions were the only ones known until an earlier one without his emendations was discovered at the Vatican in 1803, and they remained the standard for school texts in Britain and elsewhere clear through the 1800s.
Proofs by Cases
Many theorems have clean proofs, some have technical proofs, some have messy proofs. One type of messy proof uses many different cases. These proofs begin like this:
We note that there are ten possible cases based on the
The proof then proceeds to analyze each of the ten cases. Ugh. I personally do not like such proofs—who does? The main problem with them is the danger of both omission and perdition: If you omit a case that needs to be there then the proof is incomplete—or worse, wrong—while if you include all cases but err on a single one, then the whole proof is lost.
Even if the proof is correct, who will read it? Our friends at Wikipedia redirect “proof by cases” to the old classical name, proof by exhaustion. Today this connotes how the reader might feel. Concretely, they note:
A proof with a large number of cases leaves an impression that the theorem is only true by coincidence, and not because of some underlying principle or connection.
Nevertheless, they note some theorems for which the only known proofs have many cases:
- The nonexistence of a finite projective plane of order 10.
- The classification of finite simple groups.
- The Kepler conjecture.
Moreover, last year’s computerized advance on the Erdős Discrepancy Problem used SAT-solvers in an overt kind of proof-by-exhaustion. Perhaps only a computer can love such a proof.
More concretely, perhaps some theorems elude proof because we humans don’t see a good way to break things down into cases, whereas computers can try many options. But saying this brings the matter around full circle because it is asking us humans for a guiding principle to form the cases. This might encourage us instead to go back and look for a guiding principle by which to do the proof without cases.
Avoiding Case Proofs
Sometimes one can avoid case-analysis proofs. Sometimes finding the right wording will do it. In a pumping-lemma proof that the language is not context-free, one might break into cases according to whether a certain pair of critical substrings includes ‘s, ‘s, and/or ‘s. Or you can just say the pair cannot include all three, so that the three “regions” of a pumpable string cannot stay in sync with each other when forming or and so on. But this is only wording. Can we give a more concrete suggestion?
Here is a method. If you can manage it then I think it is the best method. It is to prove a more general statement that implies what you previously could only prove by case analysis.
Here are some simple examples of what I am thinking about.
Consider the following theorem from a webpage on proofs by exhaustion:
Theorem: If is a positive integer, then is divisible by .
The following is the case analysis proof that is given there:
This is all correct, but not very convincing. A better proof is to show the stronger result:
Theorem: If is a positive integer and is a prime, then is divisible by .
Suppose you have a graph from a certain family and want to prove that it has a path of length . A case analysis might work, but a better method might to note that all graphs in this family have high degree. Then invoke the famous theorem of Andrew Dirac:
Theorem: A graph with vertices is Hamiltonian if every vertex has degree or greater.
Suppose that you are confronted with proving that all the roots of some polynomial are real. You could compute the actual roots of the polynomial, but that is potentially error-prone. A better approach might be to find a symmetric real matrix so that the eigenvalues of are the roots of the polynomial.
A case analysis involving sums can sometimes be tamed by replacing the sums with integrals. Ken recalls a take-home final on which he spent ten pages arranging terms of a multiple summations in various ways according to the values of some parameters, only to learn from the answer key that it was a one-page consequence of Fubini’s Thoerem.
Is there a way to quantify the extent to which a theorem needs case analysis in its proofs?