[\<- 1.5](1.5.md) --- # 1.7 Intro to Proofs p1 A **proof** is a valid argument where each proposition before the conclusion is **true (≡T)**, so the conclusion is **true (≡T)** - e.g. Prove 7 < sqrt(59) < 8 - Brainstorming - 7 = sqrt(49) - 8 = sqrt(64) - Because 59 is between 49 and 64, the statement should be true - 49 < 59 < 64 - If x >= 0, y >= 0 and x x+y∈ℤ - m * (a/b) = (ma/b) - 1/(m/n) = (n/m) - a∈ℚ -> -a∈ℚ - Do **not** assume things like odd+odd = even Def: An integer n is even iff Ǝk∈ℤ s.t. n=2k Def: An integer n is odd iff Ǝk∈ℤ s.t. n=2k+1 --- - Aside: people often write "assume p" whn they mean "assume p is true" Ex. Prove that the square of an odd integer is odd - Rewrite the sentence: "∀(integers)x, if x is odd, then x^2 is odd" - Aside: To show a proposition is true ∀x∈S, one method is to show it is true for an arbitrary x∈S - Can we say "5 is odd and 5^2 = 25 is odd" so the proposition is true? - This does not prove it, since it only shows the statement is true for 5, and 5 is not arbitrary Scratch Work |Given/Know/Assumptions|Want to Show| |----------------------|------------| |x is odd |x^2 is odd | |x=2k+1 for some k∈ℤ |x^2 = 2(ℤ)+1| - The second to last step is called the "penultimate step" - Let x be an arbitrary odd integer. - Then, Ǝk∈ℤ s.t. x=2k+1. - Then, x^2 = (2k+1)^2 = 4k^2 + 4k +1 = 2(2k^2 + 2k)+1 - Since (2k^2 + 2k)∈ℤ, x^2 is odd. ▣ - ▣ is a symbol to show "done with proof" - Scratch Work is useful for constructing a proof, but it is not necessary to submit in an hw assignment - If scratch work is included it MUST be clearly differentiated from the actual proof This was an example of a **direct proof** of an implication. To show `p->q`, we assume p is true and show that it follows that q is true --- ## Proof by Contraposition - Recall, `p->q ≡ ┓q->┓p`, so we can prove `p->q` by using the **contrapositive** and 1. assume ┓q is true (q is false) 2. show it follows that ┓p is true (p is false) # 1.7 Intro to Proofs p2 - Ex. For all integers a,b is a*b is even, then a is even or b is even Scratch Work |Known|Want to Show| |-----|------------| |ab is even|a is even or b is even| |ab = 2l, l∈ℤ|a=2(ℤ) or b=2(ℤ)| - Direct Proof: - Let a,b be arbitrary integers where a*b is even. Then, Ǝl∈ℤ s.t. ab = 2l. a = (2l)/b = 2(l/b). We need to prove that l/b is an integer, but we don't know that it is :( ### Proof by Contraposition - Prove if ┓(a is even or b is even), then ┓(a*b is even) - If a is odd and b is odd, then a*b is odd Scratch Work |Known|Want to Show| |-----|------------| |a is odd, b is odd|ab is odd| |a = 2k+1, k∈ℤ|ab = 2(ℤ)+1| |b = 2l+1, l∈ℤ|| - 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)