diff options
Diffstat (limited to '1.8.md')
| -rw-r--r-- | 1.8.md | 124 |
1 files changed, 124 insertions, 0 deletions
@@ -26,3 +26,127 @@ Sometimes, the proofs of multiple cases are essentially the same, so we will say Proof: Let a,b∈ℝ. without loss of generality, assume `a>=b`. Then, LHS (left hand side) = `max(a,b)-min(a,b)` = `a-b`. Note `|x| = x` for `x>0` and `|x| = -x` if `x<=0`. RHS (right hand side) = `|b-a|` = `-(b-a)` = `a-b`. ∴ LHS = RHS as desired. ▣ - We don't need to consider the other case since it would have been identical + +--- + +- To prove `p<->q`, we must show + 1. `p->q` + 2. `q->p` + +- Ex. Let n∈ℤ. Prove `n` is odd iff `n^2` is odd. + +Proof: +- (=>)(implication arrow) "If `n` is odd, then `n^2` is odd" + - We already proved this in [1.7](1.7.md) +- (<=)(implication arrow; reverse direction) "If `n^2` is odd, then `n` is odd" + - **Direct Proof**: + - Ǝk∈ℤ s.t. `n^2 = 2k+1` + - `n = ±sqrt(2k+1)` + - not sure if `±sqrt(2k+1)` is an integer :( + - **Contraposition**: "If `n` is even, then `n^2` is even` + - Let `n` be even. Ǝk∈ℤ s.t. `n = 2k`. + - Then, `n^2 = (2k)^2 = 4k^2 = 2(2k^2)` which is even since `(2k)^2`∈ℤ + - ∴ `n` is odd iff `n^2` is odd. ▣ + +- Definition: A **theorem** is a mathematical statement that can be shown/proven to be true +- Definition: A **proposition** is a "less important" **theorem** +- Definition: A **corollary** is a theorem that is a direct result of another theorem + - Ex. Let n∈ℤ. `n` is even iff `n^2` is even + - Proof Sketch: Both directions are contrapositives of the above example + +--- + +# 1.8 Proof Methods p2 + +- Proposition: `[(p->q)^(q->r)] -> (p->r)` is a tautology. + - Transitive Law + +- Suppose we want to show `p1 <-> p2 <-> p3 <-> ... <-> pn` for `n >= 3`. When this is true we say: + - "the following are equivalent" (TFAE): + 1. `p1` + 2. `p2` + 3. `p3` + n. `pn` + - To prove this, it is sufficient to show: `p1 -> p2 -> p3 -> ... -> pn -> p1` + +- Ex. Let n∈ℤ. Prove TFAE: + 1. `5n+4` is even + 2. `n^2` is even + 3. `n-3` is odd. + +- Proof: (iii) -> (ii) + - Let n∈ℤ s.t. `n-3` is odd + - Then, Ǝk∈ℤ s.t. `n-3 = 2k+1` + - `n^2` = `(2k+4)^2` = `4k^2 + 16k + 16` = `2(2k^2 + 8k + 8)` + - It's **even** since `2k^2 + 8k + 8`∈ℤ +- Proof: (ii) -> (i) + - Let n∈ℤ s.t. `n^2` is even + - We have previously proved that n is even iff n^2 is even. Ǝl∈ℤ s.t. `n = 2l` + - Then, `5n+4` = `5(2l)+4` = `10l+4` + - It's **even** since `5l+4`∈ℤ +- Proof: (i) -> (iii) + - Direct Proof: + - `5n+4 = 2k` + - `n = (2k-4)/5`... too hard, lets use a different strategy + - Contrapositive: "If `n-3` is even, then `5n+4` is odd" + - Let n∈ℤ s.t. `n-3` is even + - Ǝk∈ℤ s.t. `n-3 = 2k` + - Then, `n = 2k+3`, so `5n+4` = `5(2k+3) + 4` = `10k+15+4` = `10k+19` = `10k + 18 + 1` = `2(5k+9) + 1` + - It's **odd** since `5k+9`∈ℤ + +∴ (i), (ii), and (iii) are equivalent. ▣ + +--- + +Ex. Prove that for all nonnegative reals, `x` and `y`, `(x+y)/2 >= sqrt(xy)` +- The left hand is the "Arithmetic Mean" +- The right hand is called the "Geometric Mean +- AM - GM Inequality for `n = 2` +- Direct Proof is hard +- We will use a new method called **Backwards Reasoning** + +### Backward Reasoning + +Show conclusion is **equivalent** to a true statement + +- Proof: + - `(x+y)/2 >= sqrt(xy)` + - <-> `((x+y)/2)^2 >= xy` + - <-> shows that going from the previous step to this step is reversible + - squaring both sides preserves the inequality + - <-> `(x^2 + 2xy + y^2)/4 >= xy` + - <-> `(x^2 + 2xy + y^2) >= 4xy` + - <-> `(x^2 - 2xy + y^2) >= 0` + - <-> `(x-y)^2 >= 0` + - `a^2 >= 0` is a tautology; it's called "Trivial Inequality" + - `≡T` + - Since `(x+y)/2 >= sqrt(xy)` is equivalent to a true statement, this inequality is also true + +- **Note**: For a proof using Backward Reasoning, ensure each step is reversible. Failure to do so could lead to Circular Reasoning + +--- + +Ex: Prove `sqrt(2)` is irrational. + +- Proof: + - Assume for the sake of contradiction that `sqrt(2)`∈ℚ + - Then, `sqrt(2)` = `a/b` for some a,b∈ℤ, `b!=0` + - Suppose `a/b` is written in "lowest terms" + - `(sqrt(2))^2 = (a/b)^2` + - -> `2 = (a^2)/(b^2)` + - -> `2b^2 = a^2` + - This means `a^2` is **even** since `b^2`∈ℤ + - Recall: "`a` is even iff `a^2` is even" + - This implies that `a` is even. + - Ǝk∈ℤ s.t. `a=2k` + - Substituting `a=2k` into `2b^2 = a^2`, we get `2b^2 = (2k)^2` + - -> `2b^2 = 4k^2` + - -> `b^2 = 2k^2` + - This means `b^2` is even since `k^2`∈ℤ + - This implies that `b` is even + - However, `a` and `b` being even **contradicts** the assumption that `a/b` is written in lowest terms + - As a result, `sqrt(2)` is irrational. ▣ + +--- + +[2.1 ->](2.1.md) |