Post-class 04/20HEADmaster

1 files changed, 124 insertions, 0 deletions

diff --git a/1.8.md b/1.8.md
index a783ec9..e27a6cc 100644
--- a/1.8.md
+++ b/1.8.md
@@ -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)