1.4
Mathematical Proofs

1.4.1 Introduction

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.

1.4.2 Types of Proofs

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.

1.4.3 Analysis of Proof Techniques

  • Direct Proofs [P ⇒ Q] A direct proof starts with an assumption P, then uses existing accepted mathematical truths and rules of inference to establish the truth of the conclusion Q.

Indirect proofs 5 refer to proof by contrapositive or some proof by contradiction.

  • Proof by Contrapositive [∼Q ⇒  ∼ P] Here, one assumes the conclusion Q false and then proves the hypothesis P false.
  • Proofs by Contradiction The two proofs by contradiction have the form
    equation
    equation

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.

  • Reductio ad absurdum
    equation

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.

1.4.4 Modus Operandi for Proving Theorems

Before getting into the nitty‐gritty of proving theorems, the following steps are always useful, maybe crucial.

  1. Be sure you understand the terms and expressions in the theorem.
  2. Ask yourself if you believe the theorem is true or false.
  3. Write the theorem in the language of first‐order logic so that you understand its logical structure.
  4. Determine how the proof might proceed, i.e. a direct proof, proof by contrapositive, or a proof by contradiction.
  5. Start the proof.

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

equation

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.

We now come to one of the most famous theorem of antiquity, the proof of the irrationality of images.

1.4.5 Necessary and Sufficient Conditions (NASC)

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)

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

equation

The methodology for proving theorems of this type is to prove both P ⇒ Q and Q ⇒ P. The following theorem illustrates this idea:

The following Theorem 8 is best proved with the aid of the following Lemma 1.

We now use this lemma to prove the following interesting result.

Corollary: 3 divides 9031827540918.

Problems

  1. Direct Proof

    Prove the following by a direct proof:

    1. The sum of two even integers is even.
    2. The sum of an even and an odd integer is odd.
    3. If a divides b, and b divides c, then a divides c.
    4. The product of two consecutive natural numbers plus the larger number is a perfect square.
    5. Every odd integer n greater than 1 can be written as the difference between two perfect squares. Give examples.
    6. If n is an even positive integer, then n is the difference of two positive integer squares if and only if n = 4k for some integer k > 1.
    7. If a, b are real numbers, then a2 + b2 ≥ 2ab.
    8. The sum of two rational numbers is rational.
    9. Let p(x) be a polynomial, where E is the sum of the coefficients of the even powers, and O is the sum of the coefficients of the odd powers. Show that E + O = p(1) and E − O = p(−1), where by p(1) and p(−1) we mean p(x) evaluated at x = 1 and x =  − 1, respectively.
  2. Divisibility by 4

    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.

  3. Divisibility by 3

    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.

  4. Proof by Contradiction

    Prove the following by contradiction:

    1. If n is an integer and 5n + 2 is even, then n is even.
    2. If I is an irrational number and R is a rational number, then I + R is irrational.
  5. Divisibility Problem

    Prove the following for any natural number n.

    1. 5 | n2 ⇒ 5 | n.
    2. 9 ∣ n if ⇔ 9 divides the sum of the digits of n.
    3. 3n + 1 even ⇒ n odd.
  6. Counterexamples

    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.

    1. If a > b, then |a| > |b|.
    2. If (a − b)2 = (m − n)2, then a − b = m − n.
    3. If images.
    4. If f is a continuous function defined on [a, b], then there exists a c ∈ (a, b) such that
      equation
  7. Valid Proof: Invalid Conclusion

    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?

  8. Comparing Theorems

    Verify the statement

    equation

    showing if J ⇒ S, then J ⇒ C is the weaker theorem.

  9. Comparing Theorems

    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)]

  10. Hmmmmmmmm

    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

    equation

    and showing the sum of this series is 1/3.

  11. Another Irrational Number

    Prove that log10 3 is irrational.

  12. Not Proofs

    The following statements are not considered as valid proofs by most of the mathematicians. Maybe the reader knows of a few others.

    1. Proof by obviousness: Too trivial to prove.
    2. Proof by plausibility: It sounds good, so it must be true.
    3. Proof by intimidation: Do not be stupid; of course, it's true!
    4. Proof by definition: I define it to be true.
    5. Proof by tautology: It's true because it's true.
    6. Proof by majority rule: Everyone I know says it's true.
    7. Proof by divine words: And the Lord said, “Let it be true,” and it was true.
    8. Proof by generalization: It works for me, that's enough.
    9. Proof by hope: Please, let it be true.
    10. Proof by intuition: I got this gut feeling.
  13. Just a Little Common Sense

    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?

  14. Syllogisms

    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”:

    • First premise: All men are mortal.
    • Second premise: Socrates is a man.
    • Conclusion: Therefore, Socrates is mortal.

    which has the general form

    • First premise: M ∼ R
    • Second premise: S ∼ M
    • Conclusion: S ∼ R

    where

    • M =  “ being a man”
    • S =  “ being Socrates”
    • R =  “ being mortal”

    Plato classified each premise and conclusion as one of the four basic types:17

    • E Every A is B (example: Every dog has a tail.)
    • S Some A is B (example: Some dogs have black hair.)
    • N No A is B (example: No dog has orange hair.)
    • SN Some A are not B (example: Some dogs are not poodles.)

    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.

    1. NEN   Ans: true
    2. ESS   Ans: true
    3. NSSN   Ans: true
    4. SSS   Ans: false
    5. EES   Ans: false
    6. SES    Ans: false
  15. Euler's Totient Function

    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.

    1. Find the number of natural numbers strictly between 1 and pk that are not relatively prime with pk, i.e. divide pk.
    2. Subtract the result a) from pk − 1 to obtain ϕ(pk).
  16. Pick's Amazing Formula

    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

    equation

    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.

    1. Verify that Pick's formula yields an area of 1 for a simple square bounded by four adjacent vertices.
    2. Use Pick's formula to find the area inside the polygons in Figure 1.9.
    3. Prove that Pick's formula yields the correct area of mn inside a rectangle with m rows and n columns. We draw a m = 8 by n = 11 rectangle in Figure 1.10 for illustration
    Diagram applying Pick's formula displaying connected dots forming three solid polygons.

    Figure 1.9 Applying Pick's formula.

    Diagram displaying dots connected by a solid line forming a rectangle.

    Figure 1.10 The area of mn inside an m × n rectangle.

  17. Twin Prime Conjecture

    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.

  18. Internet Research

    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.

Notes

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
44.212.93.133