Methods of Proof in Mathematics
Understanding methods of proof in mathematics involves providing convincing arguments to show the truth of propositions. This involves logical deduction, implications, and establishing new facts from known ones. Different techniques like direct proof and specific logical rules such as modus ponens are employed to construct valid proofs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
What is a proof? A convincing argument that a proposition is true. Convincing to whom? Your reader different readers may have different standards In this class you can assume your reader is a student with knowledge of the work we have done. A proof can be given as a sequence of propositions, each of which is given or definition or can be derived from from previously listed statement. You should be able to fill in any gap in your proof if asked.
Derived from the example in the book. For any integers n and k with 2<= k <= n, ~(k|n!+1). Proof: 1. Let k be any integer such that 2<= k <= n 2. Let m = n!/k 3. m Z+ 4. n! = m*k 5. m*k < m*k + 1 < (m + 1) * k 6. k does not divide m*k+1 integral multiples of k 7. k does not divide n!+1 8. If k is an integer, 2<= k <= n, then ~(k|n!+1) by definition of n! Multiply both sides of 1 by k since k >= 2 m*k+1 is between two successive substitution, 4,6 1-7
What if you are challenged to justify step 2? Use definition of !: n! = n*(n-1)* *(k+1)*k*(k-1)* *2*1 n! = n*(n-1)* *(k+1) *(k-1)* *2*1 * k n! = (n*(n-1)* *(k+1) *(k-1)* *2*1) * k n! = m * k, where m = n*(n-1)* *(k+1) *(k-1)* *2*1 m is an integer definition commutivity of multiply associativity product of integers is an integer
What if you are challenged to justify step 5? From step 4: m*k < m*k + 1 < (m + 1) * k Divide through by k (since k>0, inequalities remain) m < (m*k + 1)/k < (m + 1) there is no integer between m and m+1 therefor (m*k + 1)/k is not an integer therefor k does not divide (m*k + 1)
Direct proof Direct proof A direct proof of a proposition starts from known facts and implications, and repeatedly applies logical deduction to derive new facts, eventually leading to the conclusion . (from text) Previous example was a direct proof. What is logical deduction rules like modus ponens or previously established equivalences, such as ~( s S: P(s)) equivalent ( t S: ~P(t)) The Samadian slides included many of these rules.
( x Q ^ y Q) => (x y Q). (text exercise 4.36,stated differently) 1. Assume ( x Q ^ y Q) 2. x Q 3. a Z, b Z, b!=0, x = a/b 4. y Q 5. d Z, g Z, g!=0, y = d/g 6. x y = a/b d/g 7. = ag/bg bd/bg 8. = (ag bd)/bg 9. (ag bd) Z and bg Z, bg!=0 10. x y Q 11.( x Q ^ y Q) => (x y Q) assumption p^q => p and 1 definition Q p^q => p and 1 definition Q 3,5 substitution arithmetic arithmetic product & difference of integers are ints, 3,5 definition Q and 6-9 assume 1, conclude 10
Less formally, you might compress steps 2,3,4,5 and 7,8 1. Assume ( x Q ^ y Q) 2. x = a/b and x = d/g for integers a,b,c,g with b,g != 0 3. x y = a/b d/g 4. = (ag bd)/bg 5. (ag bd) , bg Z, bg !=0 assumption definition Q 3,5 substitution arithmetic operations product & difference of integers are integers definition Q def of => x y Q 6. 7. ( x Q ^ y Q) => (x y Q)
Proof by cases Proof by cases Often an arithmetic proof includes expressions involving one or more variables. The relationships involved may depend on the relationships of the variable. Example: if x and z are two variables involved in the predicate we are trying to prove, we might need to distinguish between two cases: x <= z and x > z. We know that (x <= z) v (x > z) by law of excluded middle ( (x > z) = ~(x <= z)) S if we prove the conclusion, C, when x <= z and also prove the conclusion, C, when x > z, then we have (x <= z) => C and (x > z) => C Since either (x <= z) or (x > z) is true, we can conclude C is true.
Example 4.15 from text on triangle inequality for absolute value x R, y R, z R (|x-y| <= |x-z| + |y-z|) For specific x = a, y = b, z = c, assume a <= b (if not interchange their places in the proof) (sometimes we say: without loss of generality assume ) We also know (c <= a <= b ) v (a < c <= b) v (a <= b < c) is true, so if we prove (|a-b| <= |a-c| + |b-c|) for each case, then we have proven it in general Case1: 1. assume c <= a <= b 2. c <= b 1. and transitivity 3. |a-c| >= 0 def abs val 4. |a-c| + |b-c| >= |b-c| add |b-c| to both sides of 2 5. = b-c 2 and def abs val 6. >= b-a 1, 5 7. = |a-b| 1 and def abs val 8. (|a-b| <= |a-c| + |b-c|) 4-6
Case 2: 1. assume a < c <= b 2. |a-c| + |b-c| = (c-a) + |b-c| def abs val and 1 3. = (c-a) + (b-c) 4. = b-a 5. = |a-b| 6. (|a-b| <= |a-c| + |b-c|) Case 3: 1. assume a <= b < c 2. |a-c| + |b-c| >= |a-c| 3. = c - a 4. >= b-a 5. = |a-b| 6. (|a-b| <= |a-c| + |b-c|) def abs val and 1 arithmetic 1 and def abs val 2 - 5 |b-c| >= 0 by def abs abs val 1, def abs val 1 1. def abs val 2 - 5
Since we have shown that (|a-b| <= |a-c| + |b-c|) for each case and we know that one of these cases must be true, we conclude that (|a-b| <= |a-c| + |b-c|) is true. Since this has been proven for arbitrary a, b, c in R, x R, y R, z R (|x-y| <= |x-z| + |y-z|) Is true by universal generalization.
Proof by Contrapositive Proof by Contrapositive Depends on equivalence: p=>q equivalent to ~q=>~p If we want to prove p => q, we start by assuming ~q, then we argue to get ~p Thus we prove ~q=>~p So by equivalence we have proved p=>q
Example: prove x Z, x2is even => x is even Proof by contrapositive: 1. Assume x is any integer and ~ x is even 2. x is odd, so for some integer y, x = 2y+1 , def of odd 3. x2= (2y + 1)2 4. x2= 4y2+ 4y +1 5. x2= 2(2y2+ 2y) + 1 6. 2y2+ 2y is an integer 7. x2is odd 8. ~x2is even 9. x2is even => x is even substitution arithmetic factoring products and sum of integers are integers 5,6,def of odd def even/odd contrapositive
We can easily prove if x is even then x2is even, using direct proof (how?) So we have then proved: x Z, (x2is even) <=> (x is even)
Proof by contradiction To prove a statement, P, using contradiction, we assume the ~P, then prove that it leads to a statement which is always false a contradiction. The classic example is to prove that squareroot(2) is irrational.
squareroot(2) is irrational. Proof by contradiction: 1. Assume squareroot(2) is rational 2. Sqrt(2) = a/b, a and b integers, no common factors 3. 2 = (a/b)2 = a2/b2 4. 2 b2 = a2 5. a2 is even 6. a is even 7. There is an integer c, so that a = 2c 8. 2 b2 = 4 c2 9. b2 = 2 c2 10. b is even 11. a, b have a common factor, 2 12. a,b have a common factor and a,b do not have a common factor 13. Contradiction. Therefore the assumption 1 is false 14. squareroot(2) is irrational 1, def rational def even 4,7 substitution b2 is even previous result 6, 10 multiply both sides by b2 def even previous result def squareroot 2, 11 1, 13
Given a proposition is it true or false? For statements like x P(x) we need to show it is true by constructing a proof could be direct, by cases, using contrapositive, by contradiction. To show it is false, we simple need one example where it is not true. Example n Z+, (n = a2 + b2) => ~ c, d (Z+ - {a,b}) : n = c2 + d2 If an integer is the sum of two squares, there is no other sum of squares that equals that integer. If we try some examples, it seems like it might be true 5 = 12 + 22 ; 17 = 12 + 42 ; 13 = 22 + 32 Can we prove it? What about 65 = 12 + 82 = 72 + 42 One counterexample disproves x statement!
Thinking about proofs Suppose we are given a statement and asked to prove it or show it false Try several cases see if it is true for all your cases? If so, do you see a pattern that might give you an idea about proof? If not, you have a counterexample and you are done.
Existence proofs Trying to prove a statement of the form: x P(x) Example: <x,y> {1, 101}x {1, 101} : ~(x = y) ^ (100 | x2 y2) In other words, there are two different integers between 1 and 101 such that their squares have the same two last digits. Proof: The possible last two digits are L = {00,01, , 99}. |L| = 100, |{1, 101}| = 101. So the function f: {1, 101} -> L, f(x) = x2 mod 100 must have at least one overlap. (the pigeon-hole principle) Note we have not shown the two values, just proved that they exist. This is a non-constructive proof we know it is true, but we do not know a specific instance.
Constructive proof of existence To prove a statement: x P(x) Show the specific instance. There are two different integers between 1 and 101 such that their squares have the same two last digits. Try 1 and 101 12 = 01, 1012 = 10201 This is a constructive proof we prove existence by showing an instance.
