Mathematics Foundations/2.3 Methods of Proof

2.3 Methods of Proof Introduction Mathematical proofs are rigorous arguments that establish the truth of mathematical statements. They form the foundation of mathematical knowledge and provide certainty beyond empirical evidence. This section explores various proof techniques used in mathematics, their applications, and how to construct valid proofs. Structure of a Proof A mathematical proof typically consists of: Theorem Statement: The mathematical claim to be proven Given Information: The assumptions or hypotheses Goal: What needs to be shown Proof Body: The logical argument leading from the given information to the goal Conclusion: The statement that the theorem has been proven (often denoted by Q.E.D. or ■) Direct Proof A direct proof establishes the truth of a statement by starting with known facts and using logical deduction to arrive directly at the conclusion. Example: Sum of Two Even Numbers Theorem: The sum of two even integers is even. Proof: Let a and b be even integers. By definition, a = 2m and b = 2n for some integers m and n. Then a + b = 2m + 2n = 2(m + n). Since m + n is an integer, a + b = 2(m + n) is even by definition. Therefore, the sum of two even integers is even. ■ Proof by Contraposition A proof by contraposition establishes by proving its contrapositive , which is logically equivalent. Example: Divisibility by 3 Theorem: If is divisible by 3, then n is divisible by 3. Proof by Contraposition: We will prove the contrapositive: If n is not divisible by 3, then is not divisible by 3. If n is not divisible by 3, then n = 3k + 1 or n = 3k + 2 for some integer k. Case 1: If n = 3k + 1, then . Since is an integer, leaves remainder 1 when divided by 3, so is not divisible by 3. Case 2: If n = 3k + 2, then . Since is an integer, leaves remainder 1 when divided by 3, so is not divisible by 3. Therefore, if n is not divisible by 3, then is not divisible by 3. By contraposition, if is divisible by 3, then n is divisible by 3. ■ Proof by Contradiction A proof by contradiction (reductio ad absurdum) assumes the negation of the statement to be proved and shows that this assumption leads to a logical contradiction, thereby establishing the truth of the original statement. Example: Irrationality of √2 Theorem: is irrational. Proof by Contradiction: Assume, for contradiction, that is rational. Then for some integers p and q with no common factors and q ≠ 0. Squaring both sides: Multiplying by : This means is even, which implies p is even (as the square of an odd number is odd). So p = 2k for some integer k. Substituting: Dividing by 2: This means is even, which implies q is even. But now both p and q are even, contradicting our assumption that p and q have no common factors. Therefore, is irrational. ■ Proof by Cases A proof by cases divides the problem into several cases and proves each case separately. The cases must cover all possibilities. Example: Absolute Value Function Theorem: For any real number x, . Proof by Cases: Case 1: x ≥ 0 When x ≥ 0, |x| = x by definition. Therefore, |x| = x ≥ x, so |x| ≥ x. Case 2: x < 0 When x < 0, |x| = -x by definition. Since x < 0, we know -x > 0, which means -x > x. Therefore, |x| = -x > x, so |x| > x, which implies |x| ≥ x. Since all possible cases have been covered, we conclude that for any real number x, |x| ≥ x. ■ Mathematical Induction Mathematical induction is a proof technique used to establish that a statement is true for all natural numbers or, more generally, for all integers greater than or equal to some base case. Principle of Mathematical Induction To prove that a statement P(n) is true for all integers n ≥ n₀, we need to show: 1. Base Case: P(n₀) is true. 2. Inductive Step: For any k ≥ n₀, if P(k) is true, then P(k+1) is also true. Example: Sum of First n Natural Numbers Theorem: For all , . Proof by Induction: Let P(n) be the statement: . Base Case: For n = 1, we have , which is true. Inductive Step: Assume P(k) is true for some k ≥ 1. That is, . We need to prove P(k+1): . Starting with the left side: (by the induction hypothesis) This is exactly P(k+1). Therefore, by the principle of mathematical induction, P(n) is true for all n ≥ 1. ■ Strong Induction Strong induction is a variant of induction where the inductive step assumes the statement is true for all values less than or equal to k, not just for k. Principle of Strong Induction To prove that a statement P(n) is true for all integers n ≥ n₀, we need to show: 1. Base Case: P(n₀) is true. 2. Inductive Step: For any k ≥ n₀, if P(n) is true for all n₀ ≤ n ≤ k, then P(k+1) is also true. Example: Every Integer > 1 is a Product of Primes Theorem: Every integer n > 1 can be expressed as a product of prime numbers. Proof by Strong Induction: Let P(n) be the statement: "n can be expressed as a product of prime numbers." Base Case: For n = 2, P(2) is true because 2 is itself a prime number. Inductive Step: Assume P(m) is true for all integers m with 2 ≤ m ≤ k, where k ≥ 2. We need to prove P(k+1): "k+1 can be expressed as a product of prime numbers." There are two cases: Case 1: If k+1 is prime, then it is already expressed as a product of primes (itself). Case 2: If k+1 is not prime, then k+1 = ab for some integers a and b with 2 ≤ a, b ≤ k. By the induction hypothesis, both a and b can be expressed as products of primes. Therefore, k+1 = ab is also a product of primes. By strong induction, P(n) is true for all integers n > 1. ■ Proof by Counterexample To disprove a universal statement ("for all x, P(x)"), it suffices to find a single counterexample where the statement is false. Example: Statement About Prime Numbers Statement: For all integers n > 1, is prime. Disproof by Counterexample: Let's check n = 41: Since is divisible by 41, it is not prime. Therefore, the statement is false. ■ Existence Proofs An existence proof demonstrates that there exists at least one object with a certain property, without necessarily identifying the object explicitly. Constructive Existence Proof A constructive existence proof provides an explicit example or a method to construct an object with the desired property. Example: There exists an irrational number x such that is rational. Proof: Consider . Case 1: If a is rational, then let x = . We know x is irrational, and is rational. Case 2: If a is irrational, then let . Here, x = a is irrational, and is rational. In either case, we have found an irrational number x such that is rational. ■ Non-constructive Existence Proof A non-constructive existence proof demonstrates that an object must exist without explicitly constructing it. Example: There exist irrational numbers a and b such that is rational. Proof: Consider . If is rational, then let a = and b = . If is irrational, then let a = and b = . Then , which is rational. Therefore, there exist irrational numbers a and b such that is rational. ■ Uniqueness Proofs A uniqueness proof demonstrates that there is exactly one object with a certain property, typically by: 1. Proving existence: showing that at least one such object exists. 2. Proving uniqueness: showing that if two objects have the property, they must be the same. Example: Multiplicative Identity Theorem: There is a unique real number e such that for all real numbers x, x·e = x. Proof: Existence: Let e = 1. For any real number x, x·1 = x. So e = 1 has the desired property. Uniqueness: Suppose there are two real numbers e₁ and e₂ such that for all real numbers x, x·e₁ = x and x·e₂ = x. Taking x = 1, we get 1·e₁ = 1 and 1·e₂ = 1, which means e₁ = 1 and e₂ = 1. Therefore, e₁ = e₂ = 1, proving that e is unique. ■ Proof by Minimal Counterexample This technique assumes a counterexample exists, then focuses on the smallest such counterexample to derive a contradiction. Example: Divisibility Property Theorem: Every integer n > 1 is divisible by at least one prime number. Proof by Minimal Counterexample: Assume, for contradiction, that there exists an integer n > 1 that is not divisible by any prime number. Let S be the set of all such integers, and let m be the smallest element in S. Since m > 1, either m is prime or m is composite. If m is prime, then m is divisible by itself, contradicting the assumption that m is not divisible by any prime. If m is composite, then m = ab for some integers a and b with 1 < a, b < m. Since a < m and m is the smallest counterexample, a must be divisible by some prime p. But if p divides a, and a divides m, then p divides m, contradicting the assumption that m is not divisible by any prime. Therefore, no such counterexample exists, and every integer n > 1 is divisible by at least one prime number. ■ Common Proof Errors and Pitfalls Circular Reasoning Circular reasoning occurs when the conclusion of an argument is used (explicitly or implicitly) as one of its premises. Example: "The number n is even because it can be written as 2k for some integer k." (This is circular because being expressible as 2k is the definition of an even number, not a proof.) Affirming the Consequent This logical fallacy takes the form: "If P, then Q. Q is true. Therefore, P is true." Example: "If n is divisible by 4, then n is even. n is even. Therefore, n is divisible by 4." (This is fallacious because n could be even without being divisible by 4, e.g., n = 6.) Denying the Antecedent This logical fallacy takes the form: "If P, then Q. P is false. Therefore, Q is false." Example: "If n is prime, then n has exactly two divisors. n is not prime. Therefore, n does not have exactly two divisors." (This is fallacious because the conclusion doesn't follow from the premises.) Exercises 1. Prove that the product of any two odd integers is odd. 2. Prove by contradiction that there are infinitely many prime numbers. 3. Prove by induction that for all n ≥ 1, . 4. Prove by contraposition: If is odd, then n is odd. 5. Prove that there are infinitely many integers n such that is not prime. 6. Prove that for any positive integer n, if is a perfect cube, then n is a perfect cube. 7. Disprove by counterexample: "For all integers n > 0, is prime."