Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I get that if all the other options are proven wrong, then the only option left must be the correct option. But why does this work? What is the logic behind it? It just doesn't click with me for some reason, although I know I should get it because I "understand" it, at least at a cursory level.
Update: "Exhaustion" changed to "elimination" in the title to avoid confusion.
To reword my comment, consider this.
There are five cats in a room, and you know that exactly one of them is black. If you show that four of them are not black, then you can reasonably conclude that since one must be black, it has to be the final one. Otherwise, if the last one was also not black, then it would have been false to say that there is exactly one black one in the first case.
My first experience with this type of proof was a group theory proof. I had a group of order $8$, and I needed to show that it belonged to a particular isomorphism class (that is, that it was isomorphic to one of the 'standard' order $8$ groups). Since it was a group of order $8$, it must be isomorphic to one of the five 'standard' order $8$ groups.
Rather than construct the isomorphism explicitly, I could show that it was not isomorphic to four of the 'standard' order $8$ groups easily, which meant that it had to be isomorphic to the final 'standard' group of order $8$.
If it were not, then either it wasn't an order $8$ group to start with, which would be false, or it would be an entirely new group structure of order $8$, which is also false. Thus it had to be isomorphic to the final case.
Some other (fairly trivial) examples include:
Let $n$ be an integer, and we clarify that $0$ is even. Either $n$ is odd or $n$ is even. If you show that it's not divisible by $2$, you've shown that it's not even ($0$ is divisible by $2$), so it must be odd. This is how you typically check if something is even or odd.
Let $a$ be a real number. Then it's either positive, negative, or zero. If you show that it's neither negative nor zero, it must be positive. Similarly, this is why the phrase "$a$ is non-negative" is equivalent to "either $a$ is zero or $a$ is positive".
Let $x$ be a positive integer. Then modulo $4$, its remainder is one of $0$, $1$, $2$, or $3$. If you show that its remainder is none of $0$, $1$, or $2$, then its remainder must be $3$.
Let $G$ be a cyclic group of order $4$ with elements $a, b, c, d$. It is known that the elements must have order $1$, $2$, or $4$. Thus if you show that, say, the element $a$ does not have order $1$ or order $2$ (showing that neither itself nor its square are the identity), it must have order $4$ and it would be a generator. See here for an example.
I'll stress that the proof by elimination method is unlikely the best proof method for a lot of the above examples, but it would still work if you know that your object has to satisfy one of the cases you were going to check. A simple counterexample is to let $a$ be a real number, show that it's not divisible by $2$, and conclude then that it must be odd. This is clearly false since real numbers cannot be partitioned into only even and odd numbers, so it is true that it could be neither.
See Disjunctive syllogism :
\begin{align} \frac{P \lor Q \ \ \ \lnot P}{Q} \end{align}
which amounts to the following principle :
if we know that the ball is either black or white and we know that the ball is not black, then it must be white.
If we call $P_1,P_2,\ldots, P_n$ the available options, we may assert the disjunction :
$(P_1 \lor P_2 \lor \ldots \lor P_{n-1}) \lor P_n$.
Thus, if we have established that $P_1,P_2,\ldots, P_{n-1}$ do not hold, we may assert :
$(\lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_{n-1})$,
which , by De Morgan, is equivalent to :
$\lnot (P_1 \lor P_2 \lor \ldots \lor P_{n-1})$.
Thus, having rejected all the first $n-1$ options, we are licensed to conclude that the last one must hold.
Consider the following statement:
Every possible combination of two numbers from 0 to 10 (both 0 and 10 inclusive) multiplied together does not yield 13.
This are $\binom{11}{2}$ = 55 possible combinations.
Proof by exhaustion means that you try every single combination and look if it yields 13. After trying all combinations, you have in fact proven that the above sentence is true.
For this to work you need a limited number of options which you can all try out. This does not work for proofs which an unlimited number of possibilities, like the Goldbach conjecture or Fermat's Last Theorem.
In the above example, it is also demonstrated that..it is kind of dumb. Every mathematician knows that 13 is a prime and cannot be built by multiplying two numbers.
But there are many cases where in fact proof by exhaustion was exactly the proof for the problem. One is the Four color theorem, splitting the problem in 1936 possible maps and checking for each map that in fact four colors are sufficient. Another is the Kepler conjecture where the best possible outcome was known and you "only" needed to prove that any combination is worse.
Here is my understanding of proof by exhaustion (or cases, or elimination):
Suppose, for example, that $P_1 \lor P_2 \lor P_3$ is true, i.e. at least one of these 3 propositions must be true.
If you can prove that $P_1\implies Q$, $P_2\implies Q$, and $P_3\implies Q$, then you can infer that $Q$ must be true.
The logic you describe is the logic people often use in entertainment events like quiz shows or mathematic exams that are based on multiple choice question and where you know that exactly one of the answers is correct. If you don't know the correct answer then you try to eliminate all answers except one. This remaining one then must be the correct answer.
A few comments and answers have mentioned the law of excluded middle, so I'm posting this answer to give an intuitionistic proof of $Q$ from the hypotheses $P \vee Q$ and $\neg P$.
In intuitionistic logic, in order to derive $R$ from $P \vee Q$, it suffices to derive $R$ from $P$ and to derive $R$ from $Q$: $$\cfrac{\begin{matrix}\phantom{[P]}\\\phantom{\vdots}\\P \vee Q\end{matrix} \qquad \begin{matrix}[P] \\ \vdots \\ R\end{matrix} \qquad \begin{matrix}[Q] \\ \vdots \\ R\end{matrix}}{R}$$ (The square brackets indicate a cancelled hypothesis, i.e. something which is assumed temporarily in the proof but is not a global assumption.)
In our case, $R$ is simply $Q$, so we need to prove $Q$ from $P$, and we need to prove $Q$ from $Q$.
The proof of $Q$ from $Q$ is immediate; the proof of $Q$ from $P$ follows from the assumption $\neg P$ and the principle of explosion (ex falso sequitur quodlibet):
$$\cfrac{\cfrac{P \qquad \neg P}{\bot}}{Q}$$
So the complete intuitionistic proof looks like this:
$$\cfrac{\begin{matrix} \phantom{X} \\ P \vee Q \end{matrix} \qquad \cfrac{\cfrac{[P] \qquad \neg P}{\bot}}{Q} \qquad \begin{matrix} \phantom{X} \\ [Q] \end{matrix}}{Q}$$
No law of excluded middle is required! But we do rely on the principle of explosion, so this inference is not valid in minimal logic.
So the mafia boss says. "Pay me your money or I'll break your kneecaps! And believe me: Those are the ONLY two options; you will either pay me your money or I will break you kneecaps". And God looks down and nods His head and says "Yes, those are the only two options".
So you go home and sit on the couch and your friend says, "Are you going to pay him your money" and you say "No."
Your friend say "What! That means he's going to break your kneecaps!"
And you say "I really don't see how that follows. It just doesn't click."
....
I'm not sure how that can be made any clearer.
