diff options
Diffstat (limited to '1.7.md')
| -rw-r--r-- | 1.7.md | 65 |
1 files changed, 65 insertions, 0 deletions
@@ -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) |