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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
[\<- 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. ▣
---
### 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)
|
