1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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. ▣
|
