21
$\begingroup$

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.

$\endgroup$
  • 28
    $\begingroup$ Can you explain more what sort of "click" does not happen? I mean, any real world example ("one of X buckets contains the ball; look at all buckets except one; no ball found => ball must be in last bucket") sounds pretty intuitive to me (for finite amounts of buckets, obviously). Can you add a concrete example where you find this difficult? $\endgroup$ – AnoE May 23 '18 at 11:10
  • 11
    $\begingroup$ I think you are referring to a proof by elimination. Exhaustion is another type of proof practiced by the ancients. $\endgroup$ – Mikhail Katz May 23 '18 at 13:15
  • 3
    $\begingroup$ For what @MikhailKatz is referring to, see Wikipedia: Method of exhaustion. $\endgroup$ – Jeppe Stig Nielsen May 23 '18 at 16:25
  • 2
    $\begingroup$ So, when the taxman says "You must pay the bill or I'll cut your fingers off" you don't worry because you figure that even though those are the only two options, not paying the bill doesn't mean he is going to cut your fingers off? .... (I'd love to figure out how to make it click but for the life of me I can't comprehend how it can't click.) $\endgroup$ – fleablood May 23 '18 at 23:17
  • 8
    $\begingroup$ The exhaustion is of the reader, not the cases. Once you start going through the cases, at some point the reader gets exhausted and says "Ugh, fine, I believe this proof". $\endgroup$ – Asaf Karagila May 24 '18 at 6:23
31
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ “or it would be an entirely new group structure of order 8“ which is exactly where you failed to substantiate your argument. There's probably a prove that there are only those five out whatever, but I don't know that and just see a big hole in your argument. $\endgroup$ – DonQuiKong May 23 '18 at 13:41
  • 8
    $\begingroup$ @DonQuiKong It is well known that there are exactly five isomorphism classes of order $8$. $\endgroup$ – Bill Wallis May 23 '18 at 13:42
  • 4
    $\begingroup$ Thanks, I just wanted to point out that a prove by exhaustion only works if you can and do undoubtedly prove all your assumptions. $\endgroup$ – DonQuiKong May 23 '18 at 13:49
  • 20
    $\begingroup$ @DonQuiKong: that's true of any proof, not just proof by exhaustion. $\endgroup$ – Michael Seifert May 23 '18 at 15:11
  • 7
    $\begingroup$ @DonQuiKong Your statement is incorrect. All proofs are based on some set of unproven axioms. There must be facts that you assume to be true somewhere in the proof. Proving one axiom just means replacing it with some different set of axioms and a deduction, effectively making a larger proof. You can never prove anything absolutely. $\endgroup$ – jpmc26 May 24 '18 at 3:29
28
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ +1. Maybe it would be nice to mention the phrase "law of excluded middle" somewhere? $\endgroup$ – User May 23 '18 at 20:40
  • 4
    $\begingroup$ @User Actually, that would be potentially misleading, since in intuitionistic logic from $P\lor Q$ and $\lnot P$ we can infer $Q$, without relying on LEM. I mean, if you want you can use LEM, but there is no need to, since this inference is completely constructive (even if you can't use DeMorgan). $\endgroup$ – chi May 24 '18 at 9:51
  • $\begingroup$ This is quite a different interpretation from that given at en.wikipedia.org/wiki/Proof_by_exhaustion $\endgroup$ – Dan Christensen May 24 '18 at 19:22
  • 1
    $\begingroup$ I don't think the $P_i$ need to be mutually exclusive. $\endgroup$ – Dan Christensen May 25 '18 at 2:32
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think that this is the kind of logic that the OP describes in his question. $\endgroup$ – miracle173 May 24 '18 at 17:28
  • $\begingroup$ @miracle173 From Wikipedia: "Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases and each type of case is checked to see if the proposition in question holds. This is a method of direct proof." en.wikipedia.org/wiki/Proof_by_exhaustion $\endgroup$ – Dan Christensen May 24 '18 at 19:13
  • 1
    $\begingroup$ nevertheless this is not what the OP is asking nor what the answer that he accepted describes. $\endgroup$ – miracle173 May 24 '18 at 19:58
  • $\begingroup$ @miracle173 I agree with you. I've suggested an edit for the question to clear this terminology up, which would render this answer moot. $\endgroup$ – Bill Wallis May 24 '18 at 20:11
  • $\begingroup$ @BillWallis Perhaps yet another wording should be suggested. From Wikipedia, we also have en.wikipedia.org/wiki/Disjunction_elimination This, too, looks a lot like my answer. $\endgroup$ – Dan Christensen May 24 '18 at 21:07
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You have $Pay \lor Break$ or equivalently $\neg Pay \implies Break$. I think that is precisely what the "mafia boss" intended to convey. $\endgroup$ – Dan Christensen May 24 '18 at 3:09
  • $\begingroup$ @DanChristensen um, yes.... $\endgroup$ – fleablood May 24 '18 at 5:12
  • 1
    $\begingroup$ "I just don't get it" ... "You will get it! You will." $\endgroup$ – Matt Coubrough May 24 '18 at 11:26
  • 1
    $\begingroup$ The proof by exhaustion tells us, that when you did not pay two times there is nothing to fear for you when not paying the third time. $\endgroup$ – allo May 24 '18 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.