From c1a5235caccaf8b5fae05e4b2764b926f3a9c851 Mon Sep 17 00:00:00 2001 From: lshprung Date: Wed, 15 Apr 2020 11:12:42 -0700 Subject: Post-class 04/15 --- 1.7.md | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1.8.md | 28 ++++++++++++++++++++++++++++ 2 files changed, 93 insertions(+) create mode 100644 1.8.md diff --git a/1.7.md b/1.7.md index 5508169..1fd525a 100644 --- a/1.7.md +++ b/1.7.md @@ -109,3 +109,68 @@ Scratch Work - Proof: - We proceed by contraposition, and assume a,b, are arbitrary odd integers. This means Ǝk,l∈ℤ s.t. a=2k+1 and b=2l+1. ab = (2k+1)(2l+1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1. Since 2kl+k+l∈ℤ, ab is odd. ▣ + +--- + +### Proof by Contradiction + +**Idea**: To show `p->q` **by contradiction** +1. First assume q is false (┓q is true) +2. Show this leads to a **contradiction** +3. This means our assumption that q is false is **wrong**, which means q is true + +- Ex. Prove that there are no positive integer solutions to `x^2 - y^2 = 1` + - Tipoff to Contradiction: the word "no" + - Try contradition: + +Scratch Work + +|Know/Assumptions|Want to Show| +|----------------|------------| +|Ǝx,y∈ℤ^+ s.t. x^2 - y^2 = 1|Leads to a Contradiction| +||Maybe show both x and y are not positive integers| + +Proof: Assume for the sake of contradiction that there are x,y∈ℤ^+ s.t. `x^2 - y^2 = 1`. Then, `(x-y)(x+y) = 1`. Since x,y∈ℤ, x-y∈ℤ and x+y∈ℤ. There are two possibilities: if both equal 1 or both equal -1. `2x=2` -> `x=1` and `y=0` is a solution. `2x=-2` -> `x=-1` and `y=0`. Neither of these solutions work, since in both, x or y are not ∈ℤ^+. This **contradicts** our assumption that x,y are positive integers. It follows that there are no positive integer solutions to `x^2 - y^2 = 1`. ▣ + +--- + +Recall: An **irrational** number is real, but not rational. (cannot be written as a ratio of integers) +- e.g. π, sqrt(2), sqrt(17), e + +- Ex. Prove that the sum of a rational and an irrational number is irrational. + - Reworded: "Prove if x is ratinoal and y is irratino, then x+y is irrational" + +Direct Proof? x+y = (a/b)+y (a,b∈ℤ, b!=0) = (a +yb)/b. We know the denominator is an integer, but we're not sure if the numerator is an integer :( + +Contraposition? +- "If x+y is rational, then x is irrational or y is rational" +- x+y = a/b: a,b∈ℤ, b!=0 +- It's hard to say something about x,y individually :( + - It is possible, however + +### Proof by Contradition: + +Scratch Work + +|Known/Assumptions|Want to Show| +|-----------------|------------| +|x is rational |Want to show Contradiction| +|y is irrational |Maybe x is irrational or y is rational| +|x+y is ratioan || +|`x` + `y` = `x+y`|| +|`y` = `x+y` - `x`|| + +Proof: Let x be rational and y be irrational. Assume for the sake of contradiction that x+y is rational. Then, x+y = a/b for some a,b∈ℤ, b!=0. Also, x = c/d for some c,d∈ℤ, d!=0. Then, `y=(x+y)-x` = `(a/b) - (c/d)` = `(ad - cb)/(bd)`∈ℚ since `ad-cd` and `bd` are integers and `bd!=0`. This contradicts the statement that y is irrational. It follows that `x+y` is irrational. ▣ + +--- + +## Tips + +1. For proofs about **rationals**, if x∈ℚ, then `x=(a/b)` for some a,b∈ℤ, b!=0 +2. For proofs about ℤ, avoid operations that give you non-integers like division or squareroot + +Warning: When proving `p->q`, never assume what you are trying to prove (q) (it's called **circular reasoning**) + +--- + +[1.8 ->](1.8.md) diff --git a/1.8.md b/1.8.md new file mode 100644 index 0000000..a783ec9 --- /dev/null +++ b/1.8.md @@ -0,0 +1,28 @@ +[\<- 1.7](1.7.md) + +--- + +# 1.8 Proof Methods p1 + +## Proof by Cases + +- Ex. Prove that `n^2 + 5n + 8` is even for all n∈ℤ. + - case 1 (n is odd): Let `n` be odd. Ǝk∈ℤ s.t. `n=2k+1`. Then `n^2 + 5n + 8` = `(2k+1)^2 + 5(2k+1) + 8` = `4k^2 + 4k + 1 + 10k + 5 + 8` = `4k^2 + 14k + 14` = `2(2k^2 + 7k + 7)` which is **even** since (2k^2 + 7k + 7)∈ℤ. + - case 2 (n is even): Let `n` be even. Ǝk∈ℤ s.t. `n=2k`. Then `n^2 + 5n + 8` = `(2k)^2 + 5(2k) + 8` = `4k^2 + 10k + 8` = `2(2k^2 + 5k + 4)` which is **even** since `2k^2 + 5k + 4` is an integer. + - ∴ `n^2 + 5n + 8` is even for all n∈ℤ + - ∴ means "therefore" + +--- + +Sometimes, the proofs of multiple cases are essentially the same, so we will say "without loss of generality" (or **WLOG**) and just show the argument for one of the similar cases and omit the others + +- Ex. Let max(x,y) be the maximum of `x` and `y`. For example, max(7.2, 11.4) = 11.4 and max(-3,-3) = -3. Similarly define min(x,y) as the minimum of `x` and `y`. +- Prove `max(a,b) - min(a,b) = |b-a|` for all a,b∈ℝ. + - We could do cases: + - Case 1: `a>=b` + - Case 2: `b>=a` + - Notice the problem is **symmetric** in a,b (`max(b,a)-min(b,a) = max(a,b)-min(a,b)`) + - `a` and `b` are interchangeable + +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 -- cgit