Why does proof by elimination work?

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.

Tags:

Logic

Proof Theory

Related

Minimizing a symmetric sum of fractions without calculus Understanding the Definition of Well-Founded Induction Probability of landing on the nth stair. Finding an irreducible polynomial of degree $n$ in $\mathbb Q[X]$ with real roots Characterization of the matrix inverse calculating the limit $\lim _{n\rightarrow \infty}((4^n+3)^{1/n}-(3^n+4)^{1/n})^{n3^n}$ Can I Systematically Determine the Cardinality of a Finite Set? Is this integral $\int_0^\infty\frac{\cos(a x+ 2b \arctan x)}{x^2+1}dx$ exactly zero when $b\in\mathbb{N}$? Evaluate $\lim_{n\rightarrow\infty}\sum_{k=1}^n\arcsin(\frac k{n^2})$ complex polynomial has zeroes only in the upper half plane How can a ratio containing only real numbers have a complex value? Intuitively, why are the curves of exponential, log, and parabolic functions all smooth, even though the gradient is being changed at every point?

Recent Posts