1
00:00:00,000 --> 00:00:02,866
Types of implications. 
So we've seen these

2
00:00:02,866 --> 00:00:04,400
sort of implicitly 
throughout the course,

3
00:00:04,400 --> 00:00:07,766
but we're gonna make a point
right now to just go over the

4
00:00:07,766 --> 00:00:10,766
ways we can use ‘and’s and ‘or’s 
and hypothesis and the conclusion

5
00:00:10,766 --> 00:00:12,533
and how we prove 
these things.

6
00:00:12,533 --> 00:00:15,866
So statement one was: 
“A and B implies C.”

7
00:00:15,866 --> 00:00:17,833
This we saw in…we've 
already seen this.

8
00:00:17,833 --> 00:00:20,266
We've seen this Divisibility of 
Integer Combinations, we've seen this

9
00:00:20,266 --> 00:00:22,133
in Bounds 
By Divisibility.

10
00:00:22,133 --> 00:00:27,033
Remember DIC was, “a implies 
c and b implies c implies that…”

11
00:00:27,033 --> 00:00:28,000


12
00:00:28,000 --> 00:00:32,000
or a divides, sorry… “a
divides b and a divides c,

13
00:00:32,000 --> 00:00:36,000
implies that a divides an integer linear 
combination of b and c.” Okay?

14
00:00:36,000 --> 00:00:37,400


15
00:00:37,400 --> 00:00:40,766
So when we proved it, 
we assumed that a

16
00:00:40,766 --> 00:00:44,433
divided b and 
a divided c,

17
00:00:44,433 --> 00:00:48,466
and when we use it, we prove that 
a divides b and a divides c.

18
00:00:48,466 --> 00:00:51,733
So second one: “ A implies B and 
C.” So what does this mean?

19
00:00:51,733 --> 00:00:55,133
Well when we're trying to prove 
this, we're starting with A,

20
00:00:55,133 --> 00:00:58,366
we're assuming A and we're trying to 
show that both B and C are true,

21
00:00:58,366 --> 00:01:02,566
and when we're using it we're proving A, and 
we get both B and C as being true for free.

22
00:01:02,566 --> 00:01:04,533
So as an example,
let S, T, and U be sets.

23
00:01:04,533 --> 00:01:08,666
If S union T is inside U, then S 
is inside U and T is inside U.

24
00:01:08,666 --> 00:01:10,733
So again, this is sort of a “follow
your nose” type of proof.

25
00:01:10,733 --> 00:01:12,233
You start with
the hypothesis,

26
00:01:12,233 --> 00:01:16,100
well and what are we trying to show? 
Let's start by showing S is inside U.

27
00:01:16,100 --> 00:01:18,733
Take an arbitrary element of 
S, it must be in the union,

28
00:01:18,733 --> 00:01:21,700
the union’s inside U, therefore
every element of S is in U,

29
00:01:21,700 --> 00:01:23,700
and we argue similarly 
for T inside U.

30
00:01:23,700 --> 00:01:26,633
It’s the first time we saw 
the word “similarly” in class.

31
00:01:26,633 --> 00:01:29,000
Round three: "A 'or'
B implies C."

32
00:01:29,000 --> 00:01:32,000
This is actually a 
little bit subtle, okay,

33
00:01:32,000 --> 00:01:35,100
which we'll see in a minute. So 
using this, you either start with

34
00:01:35,100 --> 00:01:38,700
A being true, or B being true, 
and then you get C for granted.

35
00:01:38,700 --> 00:01:41,000
Proving this... what do we 
need to do to prove this?

36
00:01:41,000 --> 00:01:42,833
Well let's take a look
at this example.

37
00:01:42,833 --> 00:01:44,800
The example will kind 
of help us out here:

38
00:01:44,800 --> 00:01:48,000
“x equals 1 or y 
equals 2 implies that

39
00:01:48,000 --> 00:01:51,733
this polynomial equation 
[with] x and y is equal to 2.”

40
00:01:51,733 --> 00:01:53,866
How do we 
prove this? 

41
00:01:53,866 --> 00:01:54,866


42
00:01:54,866 --> 00:01:56,100


43
00:01:56,100 --> 00:01:58,533
We start by assuming 
the hypothesis is true,

44
00:01:58,533 --> 00:02:01,533
and the hypothesis is x 
equals 1 or y equals 2.

45
00:02:01,533 --> 00:02:04,000
Well what does it mean for an
‘or’ statement to be true?

46
00:02:04,000 --> 00:02:06,933
Well it means that at least one 
of these two things is true,

47
00:02:06,933 --> 00:02:08,933
but the question 
is which one?

48
00:02:08,933 --> 00:02:10,000


49
00:02:10,000 --> 00:02:12,000
And the answer to that is you 
don't know. You don't know which

50
00:02:12,000 --> 00:02:14,700
which one of these two facts is true, so 
you have to start with the one fact,

51
00:02:14,700 --> 00:02:16,400
so start with 
x equals 1,

52
00:02:16,400 --> 00:02:20,000
and prove that that alone 
implies this equation is true.

53
00:02:20,000 --> 00:02:21,800
And then start 
with y equals 2,

54
00:02:21,800 --> 00:02:25,800
use that alone to prove that 
this equation is true, okay?

55
00:02:25,800 --> 00:02:28,000
So you have 
to do…

56
00:02:28,000 --> 00:02:30,466
it's not just one thing. You have 
to do both things here, okay?

57
00:02:30,466 --> 00:02:33,600
You have to start with x equals 1, 
and prove the conclusion is true,

58
00:02:33,600 --> 00:02:37,266
then start with y equals 2 and
prove the conclusion is true, okay? 

59
00:02:37,266 --> 00:02:39,266
The last thing

60
00:02:39,266 --> 00:02:41,500
that I want to talk about is part 
four, which is elimination.

61
00:02:41,500 --> 00:02:44,000
This one's an
important one as well.

62
00:02:44,000 --> 00:02:47,133
“A implies B 
or C”, so

63
00:02:47,133 --> 00:02:49,966
the way we can do this is we can
eliminate one of the possibilities.

64
00:02:49,966 --> 00:02:52,633
Why can we do that? Well 
A implies B 'or' C. Well...

65
00:02:52,633 --> 00:02:56,400
so we're gonna take A for granted, and if
B were true, then we'd be done, right,

66
00:02:56,400 --> 00:02:59,700
because then the conclusion is 
true and so the implication is true.

67
00:02:59,700 --> 00:03:01,833
So instead of

68
00:03:01,833 --> 00:03:04,000
trying to prove B 'or' C, 
what we're going to do is

69
00:03:04,000 --> 00:03:07,300
we're going to take ‘not’ B as 
part of our hypothesis as well.

70
00:03:07,300 --> 00:03:10,500
And again why can we do that? If B 
is true, we’re done the question.

71
00:03:10,500 --> 00:03:12,500
So we might as well 
assume that B is false.

72
00:03:12,500 --> 00:03:14,900
If B is false, then the
negation of B is true.

73
00:03:14,900 --> 00:03:17,433
So start with 
A and ‘not’ B.

74
00:03:17,433 --> 00:03:19,800
If you want you can
prove this by, again,

75
00:03:19,800 --> 00:03:21,800
logical equivalences 
things, like that,

76
00:03:21,800 --> 00:03:24,133
but I like that sort of case 
analysis in your head.

77
00:03:24,133 --> 00:03:26,466
You should be able to do 
that in your head by now.

78
00:03:26,466 --> 00:03:30,300
So let's see an example: “if x squared minus 
7x plus 12 is greater than or equal to 0,

79
00:03:30,300 --> 00:03:34,400
then x is less than or equal to 3 
or x is greater than or equal to 4.” 

80
00:03:34,400 --> 00:03:36,000
Let me also note:

81
00:03:36,000 --> 00:03:38,000
you don't have to use elimination
to solve this problem.

82
00:03:38,000 --> 00:03:41,233
It just makes life a little bit 
easier and cleaner if you do.

83
00:03:41,233 --> 00:03:44,100
What does elimination say? Well
I'm going to take one of these two facts,

84
00:03:44,100 --> 00:03:48,400
I'm gonna start with the first one just because, 
and take the negation of that as being true.

85
00:03:48,400 --> 00:03:52,000
So suppose that my hypothesis
is true and that x is greater than 3;

86
00:03:52,000 --> 00:03:56,700
the negation of one of my two 
statements in the conclusion.

87
00:03:56,700 --> 00:03:59,366
Then 0 is bounded below
by this polynomial

88
00:03:59,366 --> 00:04:02,500
and that polynomial factors 
as x minus 3 and x minus 4.

89
00:04:02,500 --> 00:04:04,933
Since x minus 3 is greater 
than 0, we know that

90
00:04:04,933 --> 00:04:07,600
x minus 4 must also be 
greater than or equal to 0,

91
00:04:07,600 --> 00:04:09,666
since the product is 
greater than or equal to 0,

92
00:04:09,666 --> 00:04:12,000
and hence x is greater 
than or equal to 4.

93
00:04:12,000 --> 00:04:15,133
So that's the idea behind an 
elimination. You take one of the terms… 

94
00:04:15,133 --> 00:04:19,733
you take the negation of one of the 
terms of the conclusion as true.

95
00:04:19,733 --> 00:04:21,333


96
00:04:21,333 --> 00:04:23,733
Contradiction, so proof 
by contradiction.

97
00:04:23,733 --> 00:04:25,466
This generalizes a 
proof by contrapositive.

98
00:04:25,466 --> 00:04:29,300
So if you never use contrapositive, 
you're not going to lose anything

99
00:04:29,300 --> 00:04:31,733
in terms of sanity. You should know 
what the word contrapositive means.

100
00:04:31,733 --> 00:04:35,600
There's lots of “C” words:
contrapositive, contradiction, converse.

101
00:04:35,600 --> 00:04:37,500
Make sure that you 
have them all organized,

102
00:04:37,500 --> 00:04:40,500
but in terms of like actually
leaving this course, if you

103
00:04:40,500 --> 00:04:43,466
always use contradiction 
instead of contrapositive,

104
00:04:43,466 --> 00:04:47,400
you're not losing any strength. You're not 
like missing a proof technique sort of thing.

105
00:04:47,400 --> 00:04:49,900
So something to keep in mind, but 
for the purposes of this course,

106
00:04:49,900 --> 00:04:52,400
you should know what 
both of these words mean.

107
00:04:52,400 --> 00:04:54,533
That being said, what is 
a proof by contradiction?

108
00:04:54,533 --> 00:04:57,866
Well let S be a statement then
S and ‘not’ S is false, okay?

109
00:04:57,866 --> 00:04:59,966
That sounds really 
obvious that one of S

110
00:04:59,966 --> 00:05:03,733
or the negation of S is true and the other 
one is false. It seems really clear, but

111
00:05:03,733 --> 00:05:05,033


112
00:05:05,033 --> 00:05:06,600
it's something to 
keep in mind.

113
00:05:06,600 --> 00:05:08,900
How do we use this? How 
does this actually help us?

114
00:05:08,900 --> 00:05:11,733
A really obvious statement 
but it does help us a lot.

115
00:05:11,733 --> 00:05:14,900
What do we do? Well we're going 
to assume the hypothesis is true,

116
00:05:14,900 --> 00:05:17,633
and we're going to assume 
towards a contradiction that

117
00:05:17,633 --> 00:05:19,933
the negation of the
conclusion is also true,

118
00:05:19,933 --> 00:05:23,200
so we get the hypothesis and 
the negation of the conclusion.

119
00:05:23,200 --> 00:05:26,466
Now what are we gonna do? Well we're going 
to break math. What does that mean?

120
00:05:26,466 --> 00:05:28,833
So to break 
math involves...

121
00:05:28,833 --> 00:05:30,500
basically involves this: 
it involves finding a

122
00:05:30,500 --> 00:05:33,466
statement such that S 
and its negation is true.

123
00:05:33,466 --> 00:05:36,533
What that statement is, it's 
not necessarily obvious

124
00:05:36,533 --> 00:05:39,233
when you start, but as you 
go through the proof you

125
00:05:39,233 --> 00:05:42,666
usually know when you’ve broken 
math in some way, shape, or form.

126
00:05:42,666 --> 00:05:45,533
Once you do that, you conclude the 
conclusion must be true, right?

127
00:05:45,533 --> 00:05:49,200
Only one of 
the negation or

128
00:05:49,200 --> 00:05:51,933
itself is true, and so if 
the negation was false...

129
00:05:51,933 --> 00:05:55,333


130
00:05:55,333 --> 00:05:59,733
the negation being true led to a contradiction, 
then the original conclusion must be true. 

131
00:05:59,733 --> 00:06:01,733


132
00:06:01,733 --> 00:06:04,200
Example of a contradiction 
so you use it in the same

133
00:06:04,200 --> 00:06:08,066
situations that you would 
consider using contrapositive. 

134
00:06:08,066 --> 00:06:10,700
Here's an example: “Prove that the 
square root of 2 is irrational.”

135
00:06:10,700 --> 00:06:15,133
So contrapositive you need to use for
implications, contradiction well…

136
00:06:15,133 --> 00:06:16,800
it's a little bit 
more general.

137
00:06:16,800 --> 00:06:19,100
It helps you out in situations like 
this where you don't have

138
00:06:19,100 --> 00:06:22,066
a visible 
implication.

139
00:06:22,066 --> 00:06:24,200
So here we go. So prove 
that root 2 is irrational.

140
00:06:24,200 --> 00:06:27,733
So proof: “Assume towards a contradiction
that the square root of 2 is rational,”

141
00:06:27,733 --> 00:06:30,633
right? Being irrational is a 
difficult condition to deal with.

142
00:06:30,633 --> 00:06:34,333
Being rational is an easy 
condition to start manipulating.

143
00:06:34,333 --> 00:06:35,733


144
00:06:35,733 --> 00:06:37,466
So we're going to assume towards a 
contradiction that square root of 2

145
00:06:37,466 --> 00:06:39,200
is equal to a over 
b, which is rational, 

146
00:06:39,200 --> 00:06:41,633
and here though we're gonna get a 
little bit more. We are going to also

147
00:06:41,633 --> 00:06:45,100
assume that a and b are natural
numbers instead of just integers.

148
00:06:45,100 --> 00:06:47,600
Why can
we do that?

149
00:06:47,600 --> 00:06:50,700
Stop and think about this and 
say, “Okay well root 2 is positive.

150
00:06:50,700 --> 00:06:53,533
So if it's positive, then I 
know that a over b

151
00:06:53,533 --> 00:06:56,700
is a positive number, so I might as well 
assume that both a and b are positive.

152
00:06:56,700 --> 00:06:59,400
If they were both negative…
that's a possibility but

153
00:06:59,400 --> 00:07:01,433
then you can just cancel the 
negatives, and get something

154
00:07:01,433 --> 00:07:02,833
where both terms 
are positive,

155
00:07:02,833 --> 00:07:05,133
and we already 
know that b is not 0

156
00:07:05,133 --> 00:07:07,733
and we know that a is not 0
because root 2 is bigger than 0.

157
00:07:07,733 --> 00:07:09,900
Okay, we have all of those facts 
we are allowed to assume,

158
00:07:09,900 --> 00:07:11,566
in this case, that a and 
b are natural numbers.

159
00:07:11,566 --> 00:07:13,733
You should write this down in 
your proof. I'm not going to

160
00:07:13,733 --> 00:07:16,000
because I want to 
fit on this slide.

161
00:07:16,000 --> 00:07:18,533
“Assume further that a and b 
share no common factor,” right?

162
00:07:18,533 --> 00:07:21,100
If they did share a common factor, 
then you could simplify the fraction

163
00:07:21,100 --> 00:07:24,533
before declaring what 
a and b were, okay?

164
00:07:24,533 --> 00:07:26,366
So we're also
going to do that.

165
00:07:26,366 --> 00:07:30,033
“Then cross multiplying and squaring gives 
us that 2b squared equals a squared,”

166
00:07:30,033 --> 00:07:31,733
and what does that mean? 
Well it means that

167
00:07:31,733 --> 00:07:35,333
a squared must be even, 
and hence a is even, okay?

168
00:07:35,333 --> 00:07:37,466
So if a squared is even, then 
we know that a is even,

169
00:07:37,466 --> 00:07:39,233
we saw that in class
this week as well.

170
00:07:39,233 --> 00:07:41,466
You can check that 
out in lecture 10.

171
00:07:41,466 --> 00:07:44,933
So write a equals 2k 
for some integer k,

172
00:07:44,933 --> 00:07:48,333
then substitute that into a squared is 
equal to 2b squared. What do we get?

173
00:07:48,333 --> 00:07:52,400
So we get 2b squared is equal 
to… plugging it in… 4k squared.

174
00:07:52,400 --> 00:07:56,066
Canceling a 2 shows that b squared is
equal to k squared and then, once again,

175
00:07:56,066 --> 00:07:58,600
b squared is even, 
hence b is even.

176
00:07:58,600 --> 00:08:00,933
Well a is even and b is 
even, so that means that

177
00:08:00,933 --> 00:08:03,733
share a common factor, namely 
2, and that's a contradiction.

178
00:08:03,733 --> 00:08:05,133
Okay?

179
00:08:05,133 --> 00:08:08,066
So what did we contradict? 
Well we said that a and b

180
00:08:08,066 --> 00:08:09,900
had no 
common factor,

181
00:08:09,900 --> 00:08:12,333
but here we've shown that a 
and b have a common factor.

182
00:08:12,333 --> 00:08:15,733
So my statement is: “a and b 
share no common factor.”

183
00:08:15,733 --> 00:08:19,533
Well I've shown that S and 
‘not’ S were both true.

184
00:08:19,533 --> 00:08:23,733
So S and ‘not’ S is true, well that's a 
contradiction. That doesn't make sense.

185
00:08:23,733 --> 00:08:27,566
So because I broke math,
because I've reached a contradiction,

186
00:08:27,566 --> 00:08:31,900
I conclude that the thing 
that I assumed was false.

187
00:08:31,900 --> 00:08:35,733
I assumed that root 2 was rational so 
therefore square root of 2 is irrational.

188
00:08:35,733 --> 00:08:39,233
Should you include a concluding sentence, 
“therefore the square root of 2 is irrational”?

189
00:08:39,233 --> 00:08:42,800
It's good form, I didn't here.
you should probably do it.

190
00:08:42,800 --> 00:08:44,800
Do what I say
not what I do.