This article is about the type of mathematical proof. For the method of calculating limits, see Method of exhaustion.
"Brute force method" redirects here. For similarly named methods in other disciplines, see Brute force (disambiguation).
"Proof by cases" redirects here. For the concept in propositional logic, see Disjunction elimination.
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 where each type of case is checked to see if the proposition in question holds.[1] This is a method of direct proof. A proof by exhaustion typically contains two stages:
A proof that the set of cases is exhaustive; i.e., that each instance of the statement to be proved matches the conditions of (at least) one of the cases.
A proof of each of the cases.
The prevalence of digital computers has greatly increased the convenience of using the method of exhaustion (e.g., the first computer-assisted proof of four color theorem in 1976), though such approaches can also be challenged on the basis of mathematical elegance. Expert systems can be used to arrive at answers to many of the questions posed to them. In theory, the proof by exhaustion method can be used whenever the number of cases is finite. However, because most mathematical sets are infinite, this method is rarely used to derive general mathematical results.[2]
Proof by exhaustion can be used to prove that if an integer is a perfect cube, then it must be either a multiple of 9, 1 more than a multiple of 9, or 1 less than a multiple of 9.[3]
Proof: Each perfect cube is the cube of some integer n, where n is either a multiple of 3, 1 more than a multiple of 3, or 1 less than a multiple of 3. So these three cases are exhaustive:
Case 1: If n = 3p, then n3 = 27p3, which is a multiple of 9.
Case 2: If n = 3p+1, then n3 = 27p3+27p2+9p+1, which is 1 more than a multiple of 9. For instance, if n=4 then n3 = 64 = 9×7+1.
Case 3: If n = 3p−1, then n3 =27p3−27p2+9p−1, which is 1 less than a multiple of9. For instance, if n =5 then n3 = 125 = 9×14−1. Q.E.D.
Elegance
Mathematicians prefer to avoid proofs by exhaustion with large numbers of cases, which are viewed as inelegant. An illustration as to how such proofs might be inelegant is to look at the following proofs that all modern Summer Olympic Games are held in years which are divisible by 4:
Proof: The first modern Summer Olympics were held in 1896, and then every 4 years thereafter (neglecting exceptions such as when the games were not held due to World War I and World War II along with the 2020 Tokyo Olympics being postponed to 2021 due to the COVID-19 pandemic.). Since 1896 = 474 × 4 is divisible by 4, the next Olympics would be in year 474 × 4 + 4 = (474 + 1) × 4, which is also divisible by four, and so on (this is a proof by mathematical induction). Therefore the statement is proved.
The statement can also be proved by exhaustion by listing out every year in which the Summer Olympics were held, and checking that every one of them can be divided by four. With 28 total Summer Olympics as of 2016, this is a proof by exhaustion with 28 cases.
In addition to being less elegant, the proof by exhaustion will also require an extra case each time a new Summer Olympics is held. This is to be contrasted with the proof by mathematical induction, which proves the statement indefinitely into the future.
Number of cases
There is no upper limit to the number of cases allowed in a proof by exhaustion. Sometimes there are only two or three cases. Sometimes there may be thousands or even millions. For example, rigorously solving a chess endgamepuzzle might involve considering a very large number of possible positions in the game tree of that problem.
The first proof of the four colour theorem was a proof by exhaustion with 1834 cases.[4] This proof was controversial because the majority of the cases were checked by a computer program, not by hand. The shortest known proof of the four colour theorem today still has over 600 cases.
In general the probability of an error in the whole proof increases with the number of cases. 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. Other types of proofs—such as proof by induction (mathematical induction)—are considered more elegant. However, there are some important theorems for which no other method of proof has been found, such as
↑ Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable. II. Reducibility", Illinois Journal of Mathematics, 21 (3): 504, doi:10.1215/ijm/1256049012, MR0543793, Of the 1834 configurations in 𝓤
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's Last Theorem, have shaped much of mathematical history as new areas of mathematics are developed in order to prove them.
In mathematics, the classification of the finite simple groups is a result of group theory stating that every finite simple group is either cyclic, or alternating, or it belongs to a broad infinite class called the groups of Lie type, or else it is one of twenty-six or twenty-seven exceptions, called sporadic. The proof consists of tens of thousands of pages in several hundred journal articles written by about 100 authors, published mostly between 1955 and 2004.
Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, ... ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), ... . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:
Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung and that from each rung we can climb up to the next one.
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitting the multiplication operation entirely. The axioms include a schema of induction.
Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as
Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.
A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established statements, such as theorems; but every proof can, in principle, be constructed using only certain basic or original assumptions known as axioms, along with the accepted rules of inference. Proofs are examples of exhaustive deductive reasoning which establish logical certainty, to be distinguished from empirical arguments or non-exhaustive inductive reasoning which establish "reasonable expectation". Presenting many cases in which the statement holds is not enough for a proof, which must demonstrate that the statement is true in all possible cases. A proposition that has not been proved but is believed to be true is known as a conjecture, or a hypothesis if frequently used as an assumption for further mathematical work.
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.
In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof, which proves the existence of a particular kind of object without providing an example. For avoiding confusion with the stronger concept that follows, such a constructive proof is sometimes called an effective proof.
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
In mathematics, a minimal counterexample is the smallest example which falsifies a claim, and a proof by minimal counterexample is a method of proof which combines the use of a minimal counterexample with the ideas of proof by induction and proof by contradiction. More specifically, in trying to prove a proposition P, one first assumes by contradiction that it is false, and that therefore there must be at least one counterexample. With respect to some idea of size, one then concludes that there is such a counterexample C that is minimal. In regard to the argument, C is generally something quite hypothetical, but it may be possible to argue that if C existed, then it would have some definite properties which, after applying some reasoning similar to that in an inductive proof, would lead to a contradiction, thereby showing that the proposition P is indeed true.
In mathematics, specifically group theory, Cauchy's theorem states that if G is a finite group and p is a prime number dividing the order of G, then G contains an element of order p. That is, there is x in G such that p is the smallest positive integer with xp = e, where e is the identity element of G. It is named after Augustin-Louis Cauchy, who discovered it in 1845.
A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.
Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers. It was first proved by Euclid in his work Elements. There are several proofs of the theorem.
In mathematics, a proof of impossibility is a proof that demonstrates that a particular problem cannot be solved as described in the claim or that a particular set of problems cannot be solved in general. Such cases are also known as negative proof, proof of an impossibility theorem, or negative result. Proofs of impossibility were often put to rest decades or centuries of work attempting to find a solution. To prove that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a theory. Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic.
In mathematics, the height of an element g of an abelian group A is an invariant that captures its divisibility properties: it is the largest natural number N such that the equation Nx = g has a solution x ∈ A, or the symbol ∞ if there is no such N. The p-height considers only divisibility properties by the powers of a fixed prime number p. The notion of height admits a refinement so that the p-height becomes an ordinal number. Height plays an important role in Prüfer theorems and also in Ulm's theorem, which describes the classification of certain infinite abelian groups in terms of their Ulm factors or Ulm invariants.
In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, xy, together with induction for formulas with bounded quantifiers.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
