Proof is basic to mathematics; we do not know if a proposition is true or false until we have proved or disproved it, which raises the obvious question, what is a mathematical proof? The precise definition of mathematical proof varies from mathematician to mathematician. The famed mathematician GianCarlo Rota once remarked: “Everybody knows what a mathematical proof is, it's a series of steps which leads to the desired conclusion.” A more rigid viewpoint of proof might be manipulating definitions and accepted rules of logic in a valid way, going from the assumption to the conclusion. But regardless of its definition, the history of what constitutes a mathematical proof has gone through several refinements over the years, each refinement attaining a higher level of “rigor” from its predecessors.1 Some mathematical proofs proposed by such greats as Newton and Euler2 do not hold up to today's scrutiny.
As an example of a mathematical proof, consider the proposition:
This proposition has the form P ⇒ Q and says if P is true, then so is Q. A proof of the proposition consists of the following algebraic steps:
Is this proof convincing or is there something about the argument that is lacking? You might also ask if the converse holds. Is it possible to go backwards by starting with the conclusion and reproducing the quadratic equation? In this case, the answer is yes, so we would say that the quadratic equation holds if and only if the given solution holds.
The previous statement is an example of a mathematical theorem.
A theorem3 is a mathematical statement that can be demonstrated to be true by accepted mathematical operations and arguments. The chain of reasoning used to convince one of the truth of the theorem is called a proof of the theorem.4
Theorems are ultimately based on a collection of principles considered so self‐evident and obvious that their truth value is taken as fact. Such accepted maxims are called axioms, and in every area of mathematics, be it real or complex analysis, algebra, geometry, topology, and even arithmetic is based on a collection of self‐evident truths or axioms.
Many theorems in mathematics have the form of a conditional statement or implication P ⇒ Q where one assumes the validity of P, then with the aid of existing mathematical truths and accepted rules of inference, arrives at Q. Although the goal is always to “go from P to Q,” there is more than one way of achieving this goal, which are displayed in Table 1.32.
Table 1.32 Five ways to prove P ⇒ Q.
Five ways to prove P ⇒ Q | |
P ⇒ Q | Direct proof |
∼Q ⇒ ∼ P | Proof by contrapositive |
(P ∧ ∼ Q) ⇒ Q | Proof by contradicting the conclusion |
(P ∧ ∼ Q) ⇒ ∼ P | Proof by contradicting the hypothesis |
(P ∧ ∼ Q) ⇒ (R ∧ ∼ R) | Proof by reductio ad absurdum |
The five statements in Table 1.34 are equivalent inasmuch the five columns numbered (4) through (8) in Table 1.33 that have the same truth values of TFTT. Hence, there are five forms of the basic implication P ⇒ Q, each providing a different approach for proving the basic implication.
Table 1.33 Five equivalent forms for the basic implication.
(1) | (2) | (3) | ||
P | Q | ∼P | ∼Q | P ∧ ∼ Q |
T | T | F | F | F |
T | F | F | T | T |
F | T | T | F | F |
F | F | T | T | F |
(4) | (5) | (6) | (7) | (8) |
P ⇒ Q | ∼Q ⇒ ∼ P | (P ∧ ∼ Q) ⇒ Q | (P ∧ ∼ Q) ⇒ ∼ P | (P ∧ ∼ Q) ⇒ (R ∧ ∼ R) |
T | T | T | T | T |
F | F | F | F | F |
T | T | T | T | T |
T | T | T | T | T |
In this and the next section, we demonstrate different methods of proof. Before presenting some theorems and proofs, we begin by stating a few definitions that are important since they give precise meaning to mathematical concepts.
Indirect proofs 5 refer to proof by contrapositive or some proof by contradiction.
In each case, one assumes the hypotheses P as true and the conclusion Q false and then arrives at a contradiction either contradicting the assumption P in the first case, or contradicting the assumed denial ∼Q in the second case. Both of these proofs by contradiction6 are powerful methods of proof.
This is another form of proof by contradiction. Here, one assumes P true and Q false, then seeks to prove some type of internal contradiction7 (like 1 = 0 or x2 < 0), which is denoted by R ∧ ∼ R.
Before getting into the nitty‐gritty of proving theorems, the following steps are always useful, maybe crucial.
There is no magic bullet for proving theorems. Sometimes the result to be proven provides the starting point, and the theorem can be proven by working backwards. The proof of the following theorem shows how this technique is carried out.
The Prime Number Theorem (PNT): We now prove that there are an infinite number of prime numbers, a proof that goes back to 300 BCE to the Greek mathematician Euclid of Alexandra (present‐day Egypt). Although Euclid proved the theorem by reductio ad absurdum, the German mathematician Dirichet (DEER‐a‐shlay) later developed a direct proof using analytic function theory.
Euler's Proof of the PNT: Another proof that there are an infinite number of prime numbers is obtained from the identity
proved by Leonard Euler (1707–1783), which uses the fact that since the harmonic series on the right diverges, then the product on the left, taken over prime numbers p = 2, 3, 5, 7, …. is also infinite, giving rise to an infinite number of prime numbers.
The next question to ask after knowing there are an infinite number of prime numbers is what proportion of the natural numbers are prime? It was observed by Karl Friedrich Gauss (1777–1856) and A. M. Legendre that although prime numbers do not occur in any regularity, the proportion of prime numbers among the first n natural numbers is approximately 1/ ln(n). For example, of the first million numbers the fraction of primes is 1/ ln(1,000,000) ≐ 0.07. It took almost a hundred years after Gauss and Legendre made their conjecture for French and Belgian mathematicians Jacques Hadamard (1865–1963) and de la Vallee Poussin (1866–1962) to simultaneously and independently prove the Prime Number Theorem correct.
Indirect arguments or proofs by contradiction are not foreign to our psyche. When a parent tells a child not to do something, the child thinks the contrapositive, “If I do it, what will they do to me?”
We now come to one of the most famous theorem of antiquity, the proof of the irrationality of .
is an irrational number.13
Assume the contrary, which says is rational. Hence, we can write , where p, q ∈ ℤ with q ≠ 0 and p and q have no common factors. If they have common factors, we cancel the common factors.
We will now show that even after p/q is reduced to lowest form, both p and q must be even, thus contradicting the fact that we have reduced p/q to lowest form.
We begin by squaring both sides of the above equation, getting
which means p2 is even, but we have seen in Theorem 2 that if p2 is even so is p. But if p is even, it can be written as p = 2k, which implies p2 = 4k2, where k is an integer, hence p2 = 2q2 can be written as
which in turn means q2 is even and thus q is even. Thus, we have shown that both p and q are even, which contradicts the fact we reduced p/q to lowest terms. Hence, our assumption of the rationality leads to a contradiction, and hence, by reductio ad absurdum, we conclude that is irrational. ▌
There is the story about a student who was asked to prove a given theorem or find a counterexample. The student asked the teacher if extra credit was given for doing both.
The reader should know the story of Hippasus, supposedly a Pythagorean who first proved that is irrational. The Pythagoreans were a religious sect that flourished in Samos, Greece, around 500 BCE and founded by the Greek philosopher and mathematician Pythagoras. They believed that all numbers were either natural numbers 1, 2, 3, … or fractions. So when Hippasus proved was irrational, which according to legend was made at sea, the Pythagoreans considered the proof an act of heresy and threw him overboard. So much for making one of the greatest mathematical discoveries of all time.
Many important theorems in mathematics are proven by contradiction. Three of the most famous are
Here are a few guidelines that might be useful for proving theorems.
We are all familiar with the concept of a necessary condition. For example, air is necessary for human survival, since without it there is no life. But on the other hand, air is not sufficient for human life inasmuch as we also need food to survive. Thus, we would say air is a necessary condition for human life, but not a sufficient condition.
On the other hand, there are conditions that are sufficient, but not necessary. For example, being a resident of California is sufficient for being a resident of the United States, but not necessary. In other words, sufficient conditions are more restrictive than necessary conditions.
And finally, there are conditions that are both necessary and sufficient.14 For example, a differential function has a maximum value at x = a is a necessary and sufficient condition for the function to have a zero first derivative and negative second derivative at x = a.
Table 1.34 summarizes these ideas.
Table 1.34 Necessary and sufficient conditions.
(A is sufficient for B) ≡ (A ⇒ B) |
(A is necessary for B) ≡ (B ⇒ A) |
(A is necessary and sufficient for B) ≡ (A ⇔ B) |
When Newton found the derivative (which he called the fluxion) of x2 (which he called the fluent), he arrived at the expression 2x + Δx. The Δx was referred to as an “infinitely small” quantity and thus was omitted, giving the derivative (or fluxion) of 2x. It was not until a hundred years later when mathematicians in the nineteenth century, such as Cauchy, Dedekind, Cantor, and Weierstrass, put mathematics on a more solid logical footing, and the old mathematical expressions like infinitely small were laid to rest, replaced by more precise “limits” and “ε − δ arguments.”
The earlier discussion motivates logical statements of the form P ⇔ Q, which means “P is true if and only if Q is true,” which is often stated as P is a necessary and sufficient condition for Q, due to the logical equivalence
The methodology for proving theorems of this type is to prove both P ⇒ Q and Q ⇒ P. The following theorem illustrates this idea:
Let n be any natural number, then 3 divides n2 − 1 ⇔ 3 does not divide n.
(⇒) First we prove
3 divides n2 − 1 ⇒ 3 does not divide n.
Since 3 is a prime number and divides n2 − 1 = (n − 1)(n + 1), it must divide either n − 1 or n + 1. If 3 divides n − 1, it cannot divide n (it will have a remainder of 1), and if 3 divides n + 1, it cannot divide n (it will have a remainder of 2). Hence, 3 does not divide n.
(⇐) We now prove the other way that 3 divides n2 − 1 ⇐ 3 does not divide n :
If 3 does not divide n, then we can write
or n = 3q + r, where the remainder r is either 1 or 2. If r = 1, then n − 1 = 3q, which means 3 divides (n − 1)(n + 1) = n2 − 1. Finally, if r = 2, then n − 2 = 3q or n + 1 = 3q + 3 = 3(q + 1), which also means 3 divides n2 − 1 = (n − 1)(n + 1).▌
Jerry and Susan have each proven an important theorem with the same conclusion C, and each hopes to win a Field's Medal.15 However, although their conclusions are the same, their hypotheses are different. Jerry has assumed a hypothesis J, so his theorem has the form J ⇒ C, whereas Susan has assumed a hypothesis S, so her theorem has the form S ⇒ C. In their battle to see who has the stronger theorem, or which theorem implies the other, Jerry makes the discovery that his hypothesis J is sufficient for Susan's hypothesis S. That is, J ⇒ S and so he claims he has the stronger theorem. Is Jerry correct? The answer is no! Susan's weaker hypothesis means she has the stronger theorem as can be seen by the implication
The validity of this tautology is left to the reader. Hint: truth table.
The following Theorem 8 is best proved with the aid of the following Lemma 1.
Every natural number n can be written in the form n = s + 3m, where s is the sum of the digits of n and m is some natural number. For example, 675 = 18 + 3(219).
Writing n as
and summing of its digits, getting s = a0 + a1 + ⋯ + ak, we compute the difference
which proves the lemma.▌
We now use this lemma to prove the following interesting result.
(⇒) If 3 divides n, we can write n = 3k, where k is a natural number. Then using Lemma 1, we have 3k = s + 3m and solving for the sum s gives
which proves that the sum of the digits of n is divisible by 3.
(⇐) Assuming 3 divides the sum of the digits of n, we write s = 3k, where k is a natural number. Appealing again to Lemma 1, we have
which proves n is divisible by 3.▌
Corollary: 3 divides 9031827540918.
Prove the following by a direct proof:
Show that a natural number is divisible by 4 if and only if its last two digits are divisible by 4. For example both 256 and 56 are divisible by 4. The same holds for 64 and 34,595,678,206,754,964.
Show that a natural number is divisible by 3 if and only if the sum of its digits is divisible by 3. For example, the number 9,003,186 is divisible by 3.
Prove the following by contradiction:
Prove the following for any natural number n.
A counter16 example is an exception to a rule. Counterexamples are used in mathematics to probe the boundaries of a result. Find counterexamples for the following faulty statement and tell how you could add new hypothesis to make the claim a valid theorem.
If the assumption of a theorem is false, then the conclusion can be false even if the proof of the theorem is valid. For example if you assume there is a largest positive integer N, it is possible to prove N = 1. Can you find such a proof?
Verify the statement
showing if J ⇒ S, then J ⇒ C is the weaker theorem.
Suppose a hypothesis J implies two different results C1 and C2, i.e. J ⇒ C1 and J ⇒ C2, and that C2 is the weaker of the results, i.e. C1 ⇒ C2. Show that J ⇒ C1 is the stronger theorem, or
(C1 ⇒ C2) ⇒ [(J ⇒ C1) ⇒ (J ⇒ C2)]
Infinite decimal expansions are sometimes needed to represent certain fractions. Prove that 1/3 = 0.333. … by writing the decimal form 0.333… as the infinite series
and showing the sum of this series is 1/3.
Prove that log10 3 is irrational.
The following statements are not considered as valid proofs by most of the mathematicians. Maybe the reader knows of a few others.
You are given a column of 100 ten‐digit numbers by adding them, you get a sum of 2,437,507,464,567. Is your answer correct?
The Greek philosopher Plato is recognized as the first person associated with the concept a logical argument. His arguments took the form of two premises followed by a conclusion. This basic logical form is called a syllogism, the most famous being the “Socrates syllogism”:
which has the general form
where
Plato classified each premise and conclusion as one of the four basic types:17
which means there are a total of 4 × 4 × 4 = 64 possible syllogisms, some logically true, some false. For example, a syllogism of type NEN means the first premise is of basic type N, the second premise of type E, and the conclusion of type N. Which of the following syllogism types are valid and which are invalid? Draw Venn diagrams to support your argument.
Euler's totient function, denoted by ϕ(n), gives the number of natural numbers less than a given number n, including 1, that are relatively prime to n, where two numbers are relatively prime if their greatest common divisor is 1.
For example ϕ(p) = p − 1 for any prime number since 1, 2, 3, … , p − 1 are all relatively prime with p. On the other hand, ϕ(12) = 4 since 1, 5, 7, and 11 are the numbers less than 12 relatively prime with 12. Prove that for a power of a prime number pk, k = 1, 2, … the Euler totient function is ϕ(pk) = pk − 1(p − 1) by proving the following results.
In 1899, an Austrian mathematician, Georg Pick, devised a fascinating formula for finding the area A inside a simple polygon whose vertices lie on grid points (m, n) in the plane, where m and n are integers. The formula he came up with was
where B is the number of vertices that lie on the boundary of the polygon, and I is the number of vertices that lie interior to the polygon.
Twin primes are pairs of prime numbers of the form (p, p + 2) of which (17, 19) and (197, 199) are examples. It is not known that if there are an infinite number of such pairs, although it is currently known that there are an infinite number of prime pairs that are at most 246 apart. This leads one to the question about triple primes of the form (p, p + 2, p + 4) of which (3, 5, 7) is an example. Prove this is the only triple prime sequence of this form.
There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward types of mathematical proofs, proof by contradiction, reductio ad absurdum, and prime number theorem.
44.212.93.133