Post-class 04/13

2 files changed, 113 insertions, 0 deletions

diff --git a/1.5.md b/1.5.md
index 3bdb0ab..586ec5f 100644
--- a/1.5.md
+++ b/1.5.md
@@ -90,3 +90,5 @@ Ex. Let S(x) be "x is a student," A(x,y) be "x has asked y a question," and F(x)
 		- True if S(x) or F(y) is false (contradicts the statement)
 
 ---
+
+[1.7 ->](1.7.md)
diff --git a/1.7.md b/1.7.md
new file mode 100644
index 0000000..5508169
--- /dev/null
+++ b/1.7.md
@@ -0,0 +1,111 @@
+[\<- 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<y, then sqrt(x) < sqrt(y)
+	- sqrt(49) < sqrt(59) < sqrt(64)
+	- sqrt(49) = 7
+	- sqrt(64) = 8
+	- Conclusion: 7 < sqrt(59) < 8
+		- Because this follows from the previous **true** propositions, this is **true**
+
+---
+
+## Background for Proofs
+
+- `x∈S` means x is **an element of** set S
+- Famous sets
+	- **Integers**: ℤ = {..., -2, -1, 0, 1, 2, ...}
+	- **Rationals**: ℚ = {(a/b) | a,b∈ℤ, b!=0}
+		- '|' means "such that"
+			- ':' can also mean "such that"
+	- **Reals**: ℝ
+	- ℤ^+, ℚ^+, ℝ^+ are the **positive** integers, rationals, and reals, respectively
+
+- Assume elementary school math e.g.
+	- x,y∈ℤ -> 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. ▣