Proof by cases
   HOME

TheInfoList



OR:

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 A mathematical proof is a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...
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. 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
computer A computer is a machine that can be Computer programming, programmed to automatically Execution (computing), carry out sequences of arithmetic or logical operations (''computation''). Modern digital electronic computers can perform generic set ...
s has greatly increased the convenience of using the method of exhaustion (e.g., the first computer-assisted proof of
four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...
in 1976), though such approaches can also be challenged on the basis of mathematical elegance.
Expert system In artificial intelligence (AI), an expert system is a computer system emulating the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning through bodies of knowledge, represented mainly as ...
s 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. In the Curry–Howard isomorphism, proof by exhaustion and case analysis are related to ML-style
pattern matching In computer science, pattern matching is the act of checking a given sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually must be exact: "either it will or will not be a ...
.


Example

Proof by exhaustion can be used to prove that if an
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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. 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'' = 3''p'', then ''n''3 = 27''p''3, which is a multiple of 9. *Case 2: If ''n'' = 3''p'' + 1, then ''n''3 = 27''p''3 + 27''p''2 + 9''p'' + 1, which is 1 more than a multiple of 9. For instance, if ''n'' = 4 then ''n''3 = 64 = 9×7 + 1. *Case 3: If ''n'' = 3''p'' − 1, then ''n''3 = 27''p''3 − 27''p''2 + 9''p'' − 1, which is 1 less than a multiple of 9. For instance, if ''n'' = 5 then ''n''3 = 125 = 9×14 − 1.
Q.E.D. Q.E.D. or QED is an initialism of the List of Latin phrases (full), Latin phrase , meaning "that which was to be demonstrated". Literally, it states "what was to be shown". Traditionally, the abbreviation is placed at the end of Mathematical proof ...


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 The Summer Olympic Games, also known as the Summer Olympics or the Games of the Olympiad, is a major international multi-sport event normally held once every four years. The 1896 Summer Olympics, inaugural Games took place in 1896 in Athens, ...
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 The COVID-19 pandemic (also known as the coronavirus pandemic and COVID pandemic), caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2), began with an disease outbreak, outbreak of COVID-19 in Wuhan, China, in December ...
.). 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 Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
). 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 endgame The endgame (or ending) is the final stage of a chess game which occurs after the middlegame. It begins when few pieces are left on the board. The line between the middlegame and the endgame is often not clear, and may occur gradually or with ...
puzzle A puzzle is a game, problem, or toy that tests a person's ingenuity or knowledge. In a puzzle, the solver is expected to put pieces together ( or take them apart) in a logical way, in order to find the solution of the puzzle. There are differe ...
might involve considering a very large number of possible positions in the
game tree In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe. A game tree can be us ...
of that problem. The first proof of the four colour theorem was a proof by exhaustion with 1834 cases. 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 Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
)—are considered more
elegant Elegance is beauty that shows unusual effectiveness and simplicity. Elegance is frequently used as a standard of tastefulness, particularly in visual design, decorative arts, literature, science, and the aesthetics of mathematics. Elegant t ...
. However, there are some important theorems for which no other method of proof has been found, such as * The proof that there is no finite
projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane (geometry), plane. In the ordinary Euclidean plane, two lines typically intersect at a single point, but there are some pairs of lines (namely, paral ...
of order 10. * The
classification of finite simple groups In mathematics, the classification of finite simple groups (popularly called the enormous theorem) is a result of group theory stating that every List of finite simple groups, finite simple group is either cyclic group, cyclic, or alternating gro ...
. * The
Kepler conjecture The Kepler conjecture, named after the 17th-century mathematician and astronomer Johannes Kepler, is a mathematical theorem about sphere packing in three-dimensional Euclidean space. It states that no arrangement of equally sized spheres filling s ...
. * The
Boolean Pythagorean triples problem The Boolean Pythagorean triples problem is a problem from Ramsey theory about whether the positive integers can be colored red and blue so that no Pythagorean triples consist of all red or all blue members. The Boolean Pythagorean triples problem w ...
.


See also

*
British Museum algorithm The British Museum algorithm is a general approach to finding a solution by checking all possibilities one by one, beginning with the smallest. The term refers to a conceptual, not a practical, technique where the number of possibilities is enorm ...
*
Computer-assisted proof Automation describes a wide range of technologies that reduce human intervention in processes, mainly by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machine ...
*
Enumerative induction Inductive reasoning refers to a variety of methods of reasoning in which the conclusion of an argument is supported not with deductive certainty, but with some degree of probability. Unlike ''deductive'' reasoning (such as mathematical inducti ...
*
Mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots  all hold. This is done by first proving a ...
*
Proof by contradiction 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 pr ...
* Disjunction elimination


Notes

{{Mathematical logic Mathematical proofs Methods of proof Problem solving methods de:Beweis (Mathematik)#Vollständige Fallunterscheidung