[\<- 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. ▣