Proof (mathematics)

Summary: The product of deductive reasoning, the nature of proof has long been fundamental.

Deductive proofs have been an essential part of mathematics for over 2000 years, and some equate proof ability with competence in mathematics. Mathematician David Henderson defines an effective proof as a convincing communication that answers “why.” Thus, a proof may connect ideas within a mathematical system or illuminate both the “how” and the “why” underlying the conjecture. Since a proof depends on the accepted standards of the audience or society through some type of peer review, there is also a long history of concerns about the nature of proof. For example, Galileo Galilei and Christoph Clavius debated the legitimacy of pictures, and Leopold Kronecker criticized the use of nonconstructivist methods. In the twentieth and twenty-first centuries, philosophical concerns about proofs continued as mathematicians considered the role of computers or empirical aspects and the implications of Kurt Gödel’s groundbreaking work on consistency. While reasoning and proof have long been a part of mathematics curricula, the concepts took on an increased importance in the United States during the era of Sputnik and the space race, when many different types of proofs were emphasized. In the early twenty-first century, proofs remain fundamental in education, beginning in primary school. In pure mathematics, new research depends on proofs. The notion of proof has been clarified by mathematicians in the field of logic, who explore the foundations of proof.

Brief History

Early civilizations developed sophisticated notions of mathematical argumentation, as documented by evidence such as cuneiform tablets, papyri, and mathematical texts from ancient Babylon, China, and Egypt. The idea of a formal deductive proof arose as a distinct part of ancient Greek mathematics. Greek mathematicians studied and generalized mathematical ideas, using proofs to justify their claims. Mathematics historians theorize that the prevalence of debate in Greek society provided a conducive environment for the development of axiomatic argumentation. Euclid’s Elements became “the” model for using a small set of axioms to deduce a large system of theorems and knowledge, now known as “Euclidean geometry.”

Logic

Logical systems become the foundational structures necessary to create a proof. First, mathematicians use logic tools to argue that one mathematical statement follows as a logical consequence from other mathematical statements, and then they use logic tools to establish a formal proof by building a chain of consequent statements from initial assumptions. These logic tools include connectives (negation, conjunction, disjunction, conditional implications, and equivalence), quantifiers, truth statements, tautologies, and inferential structures (such as modus ponens and reductio ad absurdum).

Direct Proofs

Mathematical proofs can be done in diverse ways, all reflecting different inferential structures. Starting with an initial conjecture (such as H→C) involving a hypothesis H and a conclusion C, Direct Proofs build logical chains of compound statements, using conditional implications as the links. They are usually written in the traditional two-column format using high school geometry. The following illustrates the use of a Direct Proof, though it is not entirely rigorous.

Conjecture: If a and b are prime numbers greater than 2, then their sum a+b is composite.

Proof:

A Proof by Contrapositive is very similar to a Direct Proof, with the difference being the format of the conjecture itself. While a Direct Proof proves the conjecture H→C, a Proof by Contrapositive uses a Direct Proof to prove the contrapositive, ~H→~C. In the previous example, a Proof by Contrapositive would prove the statement “If the sum a+b is prime, then a and b are not both prime numbers greater than 2.”

Indirect Proofs

In contrast to Direct Proofs, an Indirect Proof assumes the negation of the conclusion ~C to be true and then uses a Direct Proof to prove the truth of the negation ~S for some true statement S. By the Law of Logic Contradiction (S and ~S cannot both be true), which implies that the original conclusion C must be true. The following illustrates the use of an Indirect Proof.

Conjecture: The √2 is an irrational number.

Proof:

Using the idea of infinite descent, this Indirect Proof is considered to be one of the most “beautiful” proofs by the mathematical community. Though not as elegant, it would be possible to prove this same conjecture using a Direct Proof. Also, it is important to note that this Indirect Proof uses some outside knowledge from number theory (such as, squares of odd integers are odd), which would have to be proved prior to its use as justification within the Indirect Proof.

Deduction and induction constantly play important roles in the proof process. For example, in the previous Direct Proof, a considerable number of examples could be systematically examined: 3+5=8, 3+7=10, 5+11=16, 23+47=70, and so on. These examples provide inductive evidence that the conjecture is true, nothing more. That is, the cumulative contribution of the examples is only increased confidence that the conjecture is true and that a formal deductive proof is needed. And, a Proof by Exhaustion of All Cases is not possible because the number of pairs of primes to consider is infinite. Nonetheless, a Proof by Induction is often possible in situations involving an infinite number of examples, as illustrated by the following proof.

Assume case for k is true, need to show case for (k+1) is true: Given the assumption

For some conjectures, a visual “Behold!” Proof is possible. A common example is this proof of the Pythagorean Theorem.

Conjecture: In any right triangle, the square of the hypotenuse c (side opposite the right angle) equals the sum of the squares of the other two sides a and b: c²=a²+b².

Proof: Behold!

As in most proofs, effort is needed to understand a “Behold!” Proof. In this example, focus on the common areas and rearrangement of the four triangles. The first large square involves two smaller squares (areas a² and b²) and four triangles, while the second large square involves one small square (area c²) and the same four triangles. Noting that this proof has been traced back to early Chinese mathematics, it is important to add that more than 360 different proofs of the Pythagorean Theorem are known.

Despite their connection to truth, proofs can create mathematical fallacies. Examples include the use of Mathematical Induction to prove that, “All horses are of the same color,” the misleading dependence on a geometrical diagram to prove that all triangles are isosceles or even proofs that disguise computational errors, such as the following:

Conjecture: 1=2

Proof:

In supporting this obviously wrong conclusion, this proof relies on the reader’s literal acceptance of each statement and its justification. That is, the proof seems “true” unless the reader notices that statement five involves division by zero, which is not possible.

When constructing proofs of mathematical conjectures within a system, mathematicians are concerned with many issues related to the logical structure. Is the system “consistent,” in that no proven theorem contradicts another? Is the system “valid,” in that no mathematical fallacies or false inferences will be created? Is the system based on underlying axioms or initial assumptions that are reasonable? And, is the system “complete,” in that every conjecture can be proven either true or false? In the 1930s, logician Kurt Gödel shocked the mathematical world when he proved that a “powerful” mathematical system cannot be both complete and consistent at the same time. For some mathematicians, Gödel’s theorems weakened the foundational structure of mathematics, while others felt that it strengthened it. Mathematicians also debate about the role of computers in proofs. In the seventeenth century, Gottfried Leibniz predicted an automatic counting machine that would vastly improve reasoning. In the twentieth century, Herbert Gelernter wrote a program to prove theorems from Euclid’s Elements, but critics noted the dependence on programmer-supplied rules. Some mathematicians do not accept proofs such as the first proof of the Four-Color Theorem in 1977, which depended on an analysis of many cases by a computer.

Formal proof is a special technique within the realm of mathematics, which is why the public views mathematics as the prime model for establishing truth via argumentation. The idea of proof is invoked in other fields, but with a more limited meaning. For example, in courtrooms, the element of truth is replaced with the phrase “beyond reasonable doubt” given the available evidence. In the sciences, proof is desired but cannot be established by experimental data; at best, the data can support the creation of hypotheses and theories, which will be either further verified or discounted by new experiments and new data.

Bibliography

Cupillari, Antonella. The Nuts and Bolts of Proofs. Belmont, CA: Wadsworth Publishing, 1989.

Laczkovich, Miklós. Conjecture and Proof. Washington, DC: Mathematical Association of America, 2001.

MacKenzie, Donald. Mechanizing Proof: Computing, Risk, and Trust. Cambridge, MA: MIT Press, 2004.

Nelson, Roger. Proofs Without Words: Exercises in Visual Thinking. Washington, DC: Mathematical Association of America, 1997.

Polster, Burkard. Q.E.D.: Beauty in Mathematical Proof. New York: Walker & Company, 2004.

Solow, Daniel. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Hoboken, NJ: Wiley, 1982.

Velleman, Daniel. How to Prove It: A Structured Approach. Cambridge, England: Cambridge University Press, 1994.