What is mathematical proof?

William Dunham, a historian of mathematics and Truman Koehler Professor of Mathematics at Muhlenberg College, published The Mathematical Universe in 1994, using 26 letters of the alphabet as the title to tell about important problems and figures in the history of mathematics. This article is selected from J-Justification. The biggest difference between mathematics and other subjects is that propositions need to be proved. Mathematics has developed and progressed for thousands of years because of this, and mankind has climbed to the peak of wisdom step by step. Moreover, in the author's opinion, "the standard of mathematical proof is different from the standard in any other field of human activity." So, what is the proof of mathematical theorems? This article gives four basic principles to explain very meaningful issues involving the nature of mathematical proof.

This article is authorized to be selected from "Mathematics: Great Problems and Extraordinary People" (Turing｜People's Posts and Telecommunications Publishing, 2022.3), and the title is added by the editor.

By William Dunham (Professor of Mathematics at Muhlenberg College, USA)

Translated by Feng Su

"Proof," mathematician Michael Atiyah (1929-2019) once said, "is the glue that holds mathematics together." Obviously, what this view means is that proof or argument is the embodiment of mathematics.

Such a view may be controversial. Mathematics is such a broad discipline that it can encompass a variety of activities, such as valuation, constructing counterexamples, testing special cases, and solving everyday problems. Mathematicians do not have to prove theorems 24 hours a day.

Yet, even if the logical demonstration of theoretical propositions is not the whole of mathematics, it is certainly a characteristic of the discipline. Mathematics is inseparable from all other kinds of intellectual endeavor, just as it is inseparable from proof, reasoning, and logical deduction. In comparing mathematics to logic, Bertrand Russell asserted that "it is no longer possible to draw a line of demarcation between the two; in fact, the two are one and the same."

We have analyzed many mathematical arguments in this book. In Chapter A (Arithmetic), we proved the infinity of prime numbers; in Chapter H, we proved the Pythagorean theorem. These proofs are fairly simple, as mathematical arguments go. Others require pages, chapters, or even volumes to reach their final conclusion. The intellectual demands are not for everyone, as the modest Charles Darwin noted: "My power of following long and purely abstract lines of thought is so limited that I could never succeed in either metaphysics or mathematics." Or, as John Locke put it more succinctly: "Mathematical proofs are as hard and clear as diamonds."

What exactly is the proof of a mathematical theorem? This question is not as straightforward as it may seem, as it involves factors from philosophy, psychology, and mathematics. Aristotle had a deep understanding of this, describing a proof as "not a statement on the surface but a meditation on the heart."

Russell also made a convincing comment: mathematicians can never put down on paper "a complete process of reasoning", but must put down "a summary of proofs which will convince the trained mind". What he meant was that any mathematical statement is built on other statements and definitions, which are built on more statements and definitions, so it might be a bit foolhardy to require that proofs be traced back along every logical step. However, in the early 20th century, when Russell co-authored the magnum opus "Principles of Mathematics" with Alfred North Whitehead (1861-1947), he seemed to forget his advice to the world. In this work, they tried to push the whole of mathematics back to the underlying logical principles, sparing details in the process. The result was very grueling. Their development was so thorough that the book was 362 pages long before they finally proved that 1+1=2, which is in Section 54.43 of the chapter "Introduction to Cardinal Arithmetic" (see Figure 1). Principia Mathematica makes the argument go wild.

Figure 1 Russell and Whitehead prove that 1+1=2 | Excerpted from Volume 1 of Principia Mathematica, co-authored by Alfred North Whitehead and Bertrand Russell in 1910. Courtesy of Cambridge University Press

In this chapter, we will try to keep our heads clear. By proof we mean reasoning that is carefully crafted within the laws of logic and that is watertight and convincing about the correctness of an assertion. We will leave questions like "convincing whom?" or "watertight by whose standards?" for later.

Of course, we can choose to consider what proof is not. Statements that appeal to intuition, common sense, or worse, suggestion are not arguments. Proof "beyond a reasonable doubt" as evidence of guilt in criminal prosecutions is not what we mean by proof. Mathematicians believe that proof is not just beyond reasonable doubt, but beyond all doubt.

We can start a discussion about mathematical arguments from many different directions. Here, we give four important basic principles and discuss very interesting questions about the nature of mathematical proofs.

Basic Principle #1: Individual Cases Are Inadequate

Whether in science or in everyday life, when experiments repeatedly confirm a principle, we tend to accept it as true. If the number of confirmed cases is large enough, we say that we have a "proven law."

However, for mathematicians, the results of a few cases may give some hints, but they are by no means proofs. Here is an example of this phenomenon. Consider

Is this true? Obviously, we can substitute a few positive integers to see what the result is. When n=1, we get f(1)=1-28+322-1960+6769-13132+13069-5040=2, so the assertion is true. If we substitute n=2, the result is

f(2)=27-28×26+322×25-1960×24+6769×23-13132×22+13069×2-5040=2

This time the assertion still holds. We encourage readers to take out their calculators and verify that f(3) = 3, f(4) = 4, f(5) = 5, f(6) = 6, and even f(7) = 7.

The evidence for this assertion seems to be established. Some people, especially those who are not enthusiastic about such mechanical calculations, may have declared this statement to be true. However, it is not true. Substituting n=8, we get

The result is not 8 as we expected. Further calculations show that f(9)=40329, f(10)=181450, f(11)=640811, so the assertion not only fails, but is also shockingly wrong. The conjecture that it is true for any positive n, from being true for n=1, 2, 3, 4, 5, 6, 7, is actually incorrect.

If we expand the following expression and combine like terms, we can get the polynomial just discussed

f(n)=n+[(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)]

Obviously, for n=1, the term (n-1) is zero, so all the products in the square brackets are zero; hence f(1)=1+0=1. If n=2, then n-2=0, so f(2)=2+0=2. Similarly, f(3)=3+0=3, and so on to f(7)=7+0=7. But after that, the terms in the brackets are no longer zero, for example, f(8)=8+7!=5048.

This leads to the following challenging extension proposition. Suppose we introduce

g(n)=n+[(n-1)(n-2)(n-3)…(n-1000000)]

And guess that for all positive integers n, g(n)=n.

We multiply and combine the terms of g(n), and we get a staggering equation of degree one million. By exactly the same reasoning as above, we will find that g(1) = 1, g(2) = 2, and so on up to g(1,000,000) = 1,000,000.

After finding a million consecutive correct proofs, any right-thinking person would doubt whether g(n) always produces n. To anyone except a mathematician, a million consecutive successes would be equivalent to ruling out all doubtful proofs. However, if we check again, g(1000001) is actually equal to 1000001+1000000! This number is very large, obviously more than 1 000 001.

The above example highlights the first basic principle of mathematical proofs: we must prove it for all possible cases, not just for the millions.

Basic Principle #2: Simple is Better

Mathematicians admire proofs that are clever. But they admire proofs that are both clever and economical, that is, concise reasoning that gets to the point and gets to the point without any unnecessary extraneous material. Such proofs are considered elegant.

The elegance of mathematics is no different from the elegance of other creative works. It has much in common with the elegance of a Monet painting, a scene of the French countryside that can be depicted with just a few strokes or a few lines of poetry rather than a long essay. Elegance is essentially an aesthetic, not a mathematical property.

Like any ideal, elegance is not always attainable. Mathematicians strive for short, clear proofs, but often have to put up with annoying tedium. For example, the proof of the classification of finite simple groups in abstract algebra took more than 5,000 pages (when it was finally verified). Those who seek elegance should look elsewhere.

By contrast, the ultimate elegance that mathematicians achieve is the so-called "proof without words," in which a beautifully convincing diagram conveys the proof without even needing any explanation. It's hard to get more elegant than that. For example, consider the following example.

But the first basic principle warns that only a fool would jump to conclusions based on a single case. We will use Figure 2 to prove this proposition.

Figure 2

Here we use a step-by-step structure consisting of one block plus two blocks plus three blocks, as shown in the shaded part of Figure 2; we use blocks to form an n×(n+1) rectangular arrangement. This rectangle is composed of two completely identical steps. The area of ​​the rectangle is equal to the product of its length and width, that is, n×(n+1). Therefore, the area of ​​this step must be half of the area of ​​the rectangle, that is,

The proof is complete.

Readers may have noticed that this "silent proof" is still accompanied by a text explanation. However, the verbal explanation is indeed unnecessary, and this diagram is worth a thousand words. ("Silent Proof" is a regular column of the American Journal of College Mathematics.)

Here is another undeniably elegant proof. Suppose we start by adding positive odd numbers together, starting with 1:

1+3+5+7+9+11+13+…

Some experience tells us that no matter how far we carry out this addition, the result is always a perfect square number.

Is this always true? If so, how can we prove this general result?

The following reasoning requires a little algebra, based on the observation that even numbers are multiples of 2, so for some integer n, its form is 2n; and odd numbers are 1 less than a multiple of 2, so for some integer n, its form is 2n-1.

Theorem The sum of consecutive odd numbers starting from 1 is a perfect square.

Proof: Let S be the sum of consecutive odd numbers from 1 to 2n-1 (n>0), that is

S=1+3+5+7+…+(2n-1)

Obviously we can find the sum of all integers from 1 to 2n, and then subtract the sum of even numbers to get the sum of consecutive odd numbers.

S=[1+2+3+4+5+…+(2n-1)+2n]-(2+4+6+8+…+2n)

=[1+2+3+4+5+…+(2n-1)+2n]-2(1+2+3+4+…+n)

Here, we extract a factor of 2 from the expression in the second square bracket.

The first square bracket contains the sum of all integers from 1 to 2n, and the second square bracket contains the sum of all integers from 1 to n. The "silent proof" in Figure 2 shows how to find such a sum, so we use that result twice:

Simplifying the above formula, we get

In a word, the proof is elegant. But if it is the kind of elegance we are looking for, then Figure 3 gives another shorter proof, a proof without words. Here the odd numbers are one square, three squares, five squares, and so on, arranged in a special way. We start with a square in the lower left corner, surrounded by three shaded squares to form a 2×2 square, five unshaded squares to form a 3×3 square, then seven shaded squares to form a 4×4 square, and so on. This diagram clearly shows that the sum of consecutive odd numbers starting with 1 always produces a (geometric) square. The proof is very natural. The ancient Greeks knew it 2000 years ago, and modern descendants can imitate this proof by building blocks.

Figure 3

Winston Churchill said, “Short words are good, and old short words are best.” We can restate this elegant reasoning as old proofs are good, and old short proofs are best.

Fundamental Principle #3: The Value of Counterexamples

There is a very harsh reality in mathematics: to prove a general statement requires a general reasoning; but to refute it, only a special example is needed, an example that makes the statement fail. The latter is called a counterexample, and a good counterexample is worth its weight in gold. For example, suppose we have the following conjecture.

We emphasize that while it may take 50 pages of reasoning to prove a theorem, it may take only one line of counterexample to disprove it. In the battle between proof and disproof, there does not seem to be a level playing field. However, a word of warning: finding counterexamples is not as easy as it seems. The following story is an example.

More than two centuries ago, Euler conjectured that one must add at least three perfect cubes to get another perfect cube, at least four perfect fourth powers to get another perfect fourth power, at least five perfect fifth powers to get another perfect fifth power, and so on.

Readers of Chapter F should realize that this is a special case of Fermat's Last Theorem (n=3).

Going up in power, we can find four perfect fourth powers whose sum equals a fourth power. For example, consider the following, by no means self-explanatory example:

Euler conjectured that the sum of three fourth powers would not produce another fourth power, but he did not give a proof. In general, he said that at least n nth powers are needed so that their sum equals another nth power.

This was true in 1778, and it is still true nearly two centuries later. People who believe in Euler cannot prove Euler's conjecture, but people who do not believe in Euler cannot construct a special counterexample to refute it. This problem is an unsolved problem.

Then, in 1966, mathematicians Leon Lander and Thomas Parkin found the following example:

This shows that three fourth powers, rather than the four fourth powers as Euler said, can also generate a fourth power.

The amount of effort, even computer power, required to find these counterexamples is staggering, and this is a clear corollary of Fundamental Principle #3: sometimes it is harder to disprove than to prove.

Basic Principle #4: You can prove a negative

We often hear this old saying in the barbershop or fast food restaurant: You can't prove a negative. It may be triggered by a conversation like the following:

A: "The supermarket tabloid said a leprechaun had won a prize."

B: "There is no such thing as a leprechaun."

A: "What did you say?"

B: "I said leprechauns don't exist."

A: "Are you sure? Can you prove it doesn't exist?"

B: "Of course... no. But you can't prove it exists either."

This conversation is long. In one sentence, it claims that we have absolutely no way of proving that leprechauns don't exist.

Mathematicians know better. Some of the greatest and most important mathematical inferences have been about demonstrating that certain numbers, certain shapes, certain geometric structures do not and cannot exist. These non-existences have been established using the most powerful weapon of all: rational, rigorous logic.

The common belief that negation is unprovable is fundamentally wrong. To prove that leprechauns don’t exist, it would seem that we would need to turn over every rock in Ireland and every iceberg in Antarctica. This is, of course, an impossible ambition.

To logically establish the non-existence of something, mathematicians use a very different but perfectly good strategy: assume that the object does exist, and then trace the consequences that follow. If we can show that the assumption of existence leads to a contradiction, then the laws of logic allow us to conclude that the assumption of existence we made in the first step was wrong. Thus, we have the incontrovertible conclusion that the object does not exist, while also accounting for the fact that we have taken an indirect route to this result.

In Chapter Q, we will discuss the most famous proof of non-existence: why non-existence is equal to

However, for our immediate purposes, the following example will suffice.

Theorem There is no quadrilateral with side lengths 2, 3, 4, and 10 respectively.

A practical way to approach this problem is to cut the sticks to these lengths and try to arrange them into a four-sided shape. This is just an illustration, but in a logical sense it is the equivalent of finding a leprechaun under a rock. Even if we spend years trying to make a quadrilateral out of these four sticks without success, we cannot rule out the possibility that someone might one day succeed in making a quadrilateral out of them.

The reasonable approach is that we have to prove a negation indirectly. We start by assuming that there is a quadrilateral with side lengths of 2, 3, 4, and 10, and then try to generate a contradiction. This is a strategic leap.

Our hypothetical quadrilateral is shown in Figure 4. Draw the dotted diagonal that divides the quadrilateral into two triangles, and let be the length of this diagonal. As explained in Chapter G (Ancient Greek Geometry), Euclid proved that any side of a triangle is less than the sum of the other two sides. So in △ABC, we know that 10＜4+x. Similarly, in △ADC, x＜2+3. Combining these two inequalities gives

10＜4+x＜4+(2+3)=9

According to the inequality above, we get 10 < 9. This is impossible. Our initial assumption that there is this special quadrilateral leads to this contradiction, so our assumption is invalid.

The order in which the four sides of this quadrilateral appear (clockwise) is 10, 2, 3, 4. There are other ways to place these four sides, as shown in Figure 5, and the same reasoning also leads to a contradiction. In this case, 10＜2+x＜2+(3+4)=9. This is impossible.

Figure 4 and Figure 5

There is no point in searching any further, and there is no point in re-arranging the layout any more times. Such a quadrilateral cannot exist. We have finally proved a negative.

Proof by contradiction is a very good logical strategy. By assuming that the opposite of what we want to prove is true, we seem to be destroying our own goal. But in the end, we avoid disaster. Hardy described proof by contradiction as "one of the best weapons of the mathematician. It is far better than any other strategy of first move: the chess player may sacrifice a pawn or other piece, but the mathematician sacrifices the whole game."

Question: Are humans still needed?

Around the 1970s and 1980s, a disturbing vision intruded upon mathematicians' consciousness: the vision of computers, which took over the job of proving theorems with the speed of light and with virtual reliability.

What puzzled the entire mathematical community was some subsequent use of computers to prove theorems. These cases often decompose a theorem into many sub-cases. If each sub-case is confirmed, then the entire problem can be concluded to have been solved. Unfortunately, this kind of analysis usually requires considering hundreds of cases and thousands of calculations, and it is impossible for humans to repeat all the steps. In short, such proofs can only be checked by other machines.

In 1976, computer proofs made a dramatic entrance into the mathematical arena by solving the four-color conjecture, which states that any map drawn on a plane can be colored with four (or fewer) colors so that any two regions with a common border are painted with different colors. (For example, in Figure 6, we do not want to paint both regions A and B red, because that would obscure their common border. We allow two regions that intersect at a point, such as regions A and C, to be painted the same color, although a point is not a border.)

The four color conjecture was proposed in 1852 and has attracted widespread attention over the next century. Several problems were quickly solved, such as the fact that any flat map can be colored with five colors and that coloring a map with three colors is inadequate. Figure 7 shows such a map. On this map, we must color regions A, B, and C differently because each pair of them has a common boundary, but then it is impossible to color region D unless a fourth color is used.

So five colors are (probably) too many and three are not enough. Clearly four colors are needed. Are four colors enough to color any flat map?

Our previous discussion suggests that there are only two options for solving this problem: either come up with a special counterexample, a special kind of map that cannot be colored with four colors, or devise a general proof that any map can be colored in this way. For mathematicians, this counterexample is hard to find. Every map they make, no matter how intricate, can be colored using only red, yellow, blue, and green. (Readers with crayons may want to sketch a map right away and try this out.)

Figure 6 and Figure 7

But, as we have repeatedly reminded ourselves, proof is not just about finding a few counterexamples. In the past, people would frantically search for general inferences, but it turned out that every case was as difficult as finding counterexamples. The situation was at a standstill.

Later, Kenneth Appel and Wolfgang Haken of the University of Illinois in the United States announced that the four-color conjecture was true, shocking the entire mathematical community. What shocked people was not the conclusion, but their proof technology: the computer completed the most difficult part of the proof.

The way Appel and Haken approached the problem was to divide all the flat maps into certain types and then analyze each type separately. Unfortunately, there were hundreds of types to check, and each type was a lot of work for a high-speed computer. Eventually, the computer declared that the conjecture was true, that all possible types could be colored with four colors. The theorem was proved.

Is this true? To be fair, a sense of unease spread through the mathematical community at the time. Is this a valid argument? The puzzling thing is that answering this question would require a real flesh-and-blood person working 60 hours a week for about 100,000 years to check the computer's calculations. Even the healthiest and most optimistic person would not live that long, and anyway, who would be willing to take the time?

What if the program goes wrong? What if a power surge causes the computer to skip a critical step? What if the computer's hardware design reveals a tiny, rare flaw? In short, can we trust machine brains to give us the truth? As mathematician Ron Graham puts it when considering these complex issues: "The real question is this: If no one can check a proof, is it really a proof?"

To this day, there is no clear answer to this question, and although mathematicians may become a little more comfortable with computer proofs as they become more common, it is fair to say that most mathematicians would breathe a sigh of relief if the four-color theorem had a short, clever, elegant proof written on two pages rather than a proof that relied on the brute force of a computer. Traditionalists would rather the old math not be plugged in.

"Do we still need humans?" The answer to this question is still "yes". After all, someone has to turn on the air conditioner. But we have to admit that this view may be biased because its supporters are humans themselves.

This concludes our discussion of mathematical arguments. Obviously, there is much more to say, other issues to raise, other fundamental principles to be proposed. But the most important conclusion we have reached is this: whether elegant or cumbersome, direct or indirect, relying on computers or human labor, the standards of mathematical proof are different from those in any other field of human activity.

Go to the "Fanpu" public account and click on the picture below or "Read original text" in the lower left corner to purchase↓↓

Special Tips

1. Go to the "Featured Column" at the bottom of the menu of the "Fanpu" WeChat public account to read a series of popular science articles on different topics.

2. Fanpu provides a function to search articles by month. Follow the official account and reply with the four-digit year + month, such as "1903", to get the article index for March 2019, and so on.

Copyright statement: Personal forwarding is welcome. Any form of media or organization is not allowed to reprint or excerpt without authorization. For reprint authorization, please contact the backstage of the "Fanpu" WeChat public account.