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 exceptional situations such as when the games' schedule were disrupted by World War I, World War II and 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 conjecture, have shaped much of mathematical history as new areas of mathematics are developed in order to prove them.
Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true. 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 theory is computably axiomatizable; the axioms include a schema of induction.
In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid.
In mathematics, specifically in the field of finite group theory, the Sylow theorems are a collection of theorems named after the Norwegian mathematician Peter Ludwig Sylow that give detailed information about the number of subgroups of fixed order that a given finite group contains. The Sylow theorems form a fundamental part of finite group theory and have very important applications in the classification of finite simple groups.
A mathematical proof is a deductive 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 mathematics, Hilbert's program, formulated by German mathematician David Hilbert in the early 1920s, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies. As a solution, Hilbert proposed to ground all existing theories to a finite, complete set of axioms, and provide a proof that these axioms were consistent. Hilbert proposed that the consistency of more complicated systems, such as real analysis, could be proven in terms of simpler systems. Ultimately, the consistency of all of mathematics could be reduced to basic arithmetic.
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers:
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.
The language of mathematics has a wide vocabulary of specialist and technical terms. It also has a certain amount of jargon: commonly used phrases which are part of the culture of mathematics, rather than of the subject. Jargon often appears in lectures, and sometimes in print, as informal shorthand for rigorous arguments or precise ideas. Much of this uses common English words, but with a specific non-obvious meaning when used in a mathematical sense.
In mathematics, Burnside's theorem in group theory states that if G is a finite group of order where p and q are prime numbers, and a and b are non-negative integers, then G is solvable. Hence each non-Abelian finite simple group has order divisible by at least three distinct primes.
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 proven by Euclid in his work Elements. There are several proofs of the theorem.
In number theory, Fermat's Last Theorem states that no three positive integers a, b, and c satisfy the equation an + bn = cn for any integer value of n greater than 2. The cases n = 1 and n = 2 have been known since antiquity to have infinitely many solutions.
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.
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.
