0.0: Introduction to proofs
This page is a draft and is under active development.
( \newcommand{\kernel}{\mathrm{null}\,}\)
Introduction to Proofs/Contradiction
In this section, we will explore different techniques of proving a mathematical statement "If p then q". (p→q). This is a conditional statement.
From DR. THI DINH'S PROOF WRITING HANDBOOK THIS BIBLE:
In the beginning...
Let P and Q be statement variables. When needed, suppose that P = P(x) depends on a variable x. The symbol "∀" means "for all" or "for any". The symbol ∃ means "there exists".
Type of statement | What must we do to prove that it is true |
(1) If P, then Q (2) ∀P, Q |
Suppose that P is true. Prove that Q is true. |
(3) ∃xP(x) such that Q |
Choose x so that P(x) is true. Prove that Q is true. Note: You need not explain how you find x. |
The first (and only) commandment
To prove that a statement is false, thou shalt write out the negation of the statement and prove that.
The five cardinal sins
- When proving any of the types of statements (1), (2), or (3):
1. Thou shalt not: suppose that Q is true.
2. Thou shalt not: overuse symbols and violate the rules of English grammar. You must write in full sentences and use symbols correctly.
- When proving a statement of the form (2) P,Q:
3. Thou shalt not: choose or exhibit an example in place of a proof.
- When proving a statement of the form (3) "∀xP(x) such that Q:
4. Thou shalt not: attempt to construct all possible x so that P(x) and Q are true.
- When proving a statement by contradiction:
5. Thou shalt not: claim a contradiction has been reached without explanation. You must clearly identify the contradiction being made by making a statement of the form "P and NOT P, which is a contradiction".
Direct Proof
In this technique, we shall assume p and show that q is true.
Theorem 0.0.1
Let n be an integer. If n is even then n2 is even.
- Proof
-
Assume that n is even. Then n=2m for some integer m.
Consider n2=(2m)2=4m2=2(2m2). Since m is an integer, (2m2) is an integer.
Thus n2 is even.◻
Example 0.0.1
Show that for all integers n, if n is odd then n2 is odd.
- Proof
-
Assume that n is odd. Then n=2m+1 for some integer m.
Consider n2=(2m+1)2=4m2+4m+1=2(2m2+2m)+1.
Since m is an integer, (2m2+2m) is an integer.
Thus n2 is odd.◻
Proof by Contrapositive
In this technique, we shall assume ¬p and show that ¬q is true.
Theorem 0.0.2
Let n be an integer. If n2 is even then n is even.
- Proof
-
We shall prove this statement by assuming n is odd. Then n=2m+1 for some integer m.
Consider n2=(2m+1)2=4m2+4m+1=2(2m2+2m)+1.
Since m is an integer, (2m2)+2m is an integer.
Thus n2 is odd.◻
Example 0.0.2
Show that for all integers n, if n2 is odd then n is odd.
- Proof
-
We shall prove this statement by assuming n is even. Then n=2m for some integer m.
Consider n2=(2m)2=4m2=2(2m2).
Since m is an integer, (2m2) is an integer. Thus n2 is even.◻
Proof by Contradiction
In this technique, we shall assume the negation of the given statement is true, and come to a contradiction.
Theorem 0.0.3
√2 is irrational.
- Proof
-
Assume that √2 is rational. Then √2=ba, where b∈Z,a∈Z∖{0}, with no common factors between a and b. Now, √2a=b. Then 2a2=b2. Since 2 divides 2a2, 2 divides b2. Thus b2 is even. Therefore, b is even, (by theorem 2). Since b is even, 2 divides b. Therefore, 22 divides b2.
Since 2a2=b2, 22 divides 2a2. Therefore, 2 divides a2. Which implies a is even. This contradicts the fact that a and b have no common factors. Thus √2 is irrational.◻
Proof by Counterexample
Example 0.0.3:
Decide whether the statement is true or false and justify your answer:
For all integers a,b,u,v, and u≠0,v≠0, if au+bv=0 then a=b=0.
Solution: The statement is false.
Counterexample: Choose a=1,b=−1,u=2,v=2, then au+bv=0, but a≠0.b≠0,a≠b.
Mathematical Induction
Process of Proof by Induction
Let p(n) be a mathematical statement, n∈N i.e., n≥1.
-
Prove the statement is true for the lowest value of n.
-
Assume that p(n) is true for all n=k.
-
Prove p(k+1) is true.
Prove 2n>n+4 for n≥3,n∈N.
- Proof
-
Let n=3. Then 23>3+4 is true since clearly 8>7. Thus the statement is true for n=3.
Assume that 2n>n+4 is true for some n=k.
We will show that 2k+1>(k+1)+4.
Consider 2k+1=2⋅2k>2⋅(k+4)=2k+8.
Since 2k>k+1 and 8>4, we have 2k+8>(k+1)+4.
Thus the statement is true for all n=k.
By induction, 2n>n+4 for all n≥3,n∈Z.◻
Show that 9|(10n+1+3(10n)+5),∀n≥1.
- Proof
-
Let n=1. Then 9|(102)+3(10)+5, which is 9|135, which is true since 135=9(15) and 15∈Z.
Assume that 9|(10n+1+3(10n)+5 is true for some n=k.
We will show that 10k+1+1+3(10k+1)+5=9m for some m∈Z.
Consider 10k+1+1+3(10k+1)+5=10(10k+1+3(10k)+5)−9(5)
=10(9m)−9(5)
=9(10m−5), where 10m−5∈Z.
By induction, 9|(10n+1+3(10n)+5),∀n≥1.◻
Show that 1+2+3+⋯+n=n(n+1)2,∀n≥1.
- Proof
-
Let n=1. Then 1=1(1+1)2 which is true.
Assume 1+2+3+⋯+n=n(n+1)2 is true for some n=k.
We will show that 1+2+3+⋯+n+(n+1)=(n+1)(n+1+1)2
Consider 1+2+3+⋯+n+(n+1)=[1+2+3+⋯+n]+(n+1).
=n(n+1)2+(n+1)
=n(n+1)+2(n+1)2
=(n+1)(n+1+1)2.
By induction, 1+2+3+⋯+n=n(n+1)2,∀n≥1.◻
Prove that 3|(10n+1+10n+1),∀n≥1.
- Proof
-
Let n=1. Then 3|(102+10+1) is true since 111=3(37) and 37∈Z.
Assume that 3|(10n+1+10n+1) for some n=k.
We will show that 10k+1+1+10k+1+1=3m,m∈Z.
Consider 10k+1+1+10k+1+1=10(10k+1+10k+1)−9(1)
=10(3m)−3(3)
=3(10m−3) where 10m−3∈Z.
By induction, 3|(10n+1+10n+1),∀n≥1.◻
Bi-conditional statements
Bi-conditional statements are conditional statements which depend on both component propositions. They read "p if and only if q" and are denoted p↔q or "p iff q", which is logically equivalent to (p→q)∧(q→p).
Consider the statement: "Two lines are perpendicular if and only if they intersect to form a right angle."
The component propositions are:
- p: Two lines are perpendicular
- q: [The lines] intersect to form a right angle
Logically, we can see that if two lines are perpendicular, then they must intersect to form a right angle. Also, we can see that if two lines form a right angle, then they are perpendicular.
If two lines are not perpendicular, then they cannot form a right angle. Conversely, if two lines do not form a right angle, they cannot be perpendicular. This is why, if both propositions in a biconditional statement are false, the statement itself is true!
Proof Do's and Dont's
Do's:
- Write the statement to be proved. It should be clear what you are proving.
- Clearly mark the beginning of your proof with the word "Proof".
- Make your proof self-contained. In particular, identify all variables used in your proof in the body of your proof.
- Write proof in complete English sentences.
Example 0.0.9: Acceptable
Proof: Let n∈Z. Assume n is an even integer. Then n=2k, for some k∈Z.
Example 0.0.10: Unacceptable
Proof: n is even ⟹ 2k.
5. Indicate what method of proof you are using. (The default assumption is that it is a direct proof).
6. Learn the definitions and how they come into play when proving various types of statements.
Don'ts:
- Argue from examples. A general statement can't be proved true by showing it is true for special cases.
- Use the same letter to mean two different things within a proof.
Example 0.0.11:
Proof: Let n∈Z. Assume n is an even integer. Then n=2k, for some k∈Z. So n2=4K2=2(2k2). Thus n2=2k,k∈Z is even. (The reader asks, does n=n2?)
3. Assume what you are trying to prove. This is also known as begging the question. You can do it inadvertently in the middle of proof if you are not careful.