Proof by Exhaustion

A Proof by Exhaustion is a mathematical proof method based on inductive reasoning.

• AKA: Brute-Force Method.
• See: Mathematical Proof, Inductive Reasoning, Brute-Force Search , Exhaustive Search, Direct Search.

---

---

References

2015

• (Wikipedia, 2015) ⇒ https://www.wikipedia.com/en/Proof_by_exhaustion
  • QUOTE: Proof by exhaustion, also known as proof by cases, perfect 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. A proof by exhaustion contains two stages:

1. A proof that the cases are exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases.
2. A proof of each of the cases.

In the Curry–Howard isomorphism, proof by exhaustion and case analysis are related to ML-style pattern matching

1999

• (Wolfram Mathworld , 1999) ⇒ http://mathworld.wolfram.com/ExhaustiveSearch.html
  • QUOTE: For discrete problems in which no efficient solution method is known, it might be necessary to test each possibility sequentially in order to determine if it is the solution. Such exhaustive examination of all possibilities is known as exhaustive search, direct search, or the "brute force" method. Unless it turns out that NP-problems are equivalent to P-problems, which seems unlikely but has not yet been proved, NP-problems can only be solved by exhaustive search in the worst case.

---

---