1
00:00:00,000 --> 00:00:03,266
Now we talk about sets. So a 
set is a collection of elements.

2
00:00:03,266 --> 00:00:04,933
This is a very 
vague definition,

3
00:00:04,933 --> 00:00:06,533
but it's definitely good
enough for us,

4
00:00:06,533 --> 00:00:08,733
and we can do mathematics
with this definition.

5
00:00:08,733 --> 00:00:13,566
Now, you can get into some sticky 
situations if you're not careful

6
00:00:13,566 --> 00:00:16,000
with what you do. You
can define some

7
00:00:16,000 --> 00:00:18,233
paradoxical things.

8
00:00:18,233 --> 00:00:21,400
But for now let's just take for granted
a set as a collection of elements,

9
00:00:21,400 --> 00:00:23,266
and we have some 
examples of some sets.

10
00:00:23,266 --> 00:00:25,233
So for us, the natural 
numbers begin with 1

11
00:00:25,233 --> 00:00:26,933
so I wanted to 
emphasize that here.

12
00:00:26,933 --> 00:00:29,700
For example, we also have 
the rational numbers.

13
00:00:29,700 --> 00:00:32,000
The rational numbers are
fractions a over b,

14
00:00:32,000 --> 00:00:33,700
real numbers,
such that

15
00:00:33,700 --> 00:00:36,166
a is an integer, b is an
integer and b is non-zero.

16
00:00:36,166 --> 00:00:38,733
We say here R
is the universe,

17
00:00:38,733 --> 00:00:40,933
or sometimes the universe 
of discourse, either way. 

18
00:00:40,933 --> 00:00:44,366
That's an example of 
defining the rationals.

19
00:00:44,366 --> 00:00:46,500
We have the examples 
of the empty set,

20
00:00:46,500 --> 00:00:48,966
so the first one’s an empty set, 
second one's the empty set,

21
00:00:48,966 --> 00:00:50,833
and the third one is
not the empty set.

22
00:00:50,833 --> 00:00:53,166
This is the set 
containing the empty set,

23
00:00:53,166 --> 00:00:55,666
so the third set has 
one element in it,

24
00:00:55,666 --> 00:00:57,833
the other two do not 
have an element in it.

25
00:00:57,833 --> 00:01:00,433
There's a big big difference even 
though they look very similar,

26
00:01:00,433 --> 00:01:02,833
so I wanted to throw this out 
here just to remind you, okay

27
00:01:02,833 --> 00:01:06,333
this thing is different this is a set 
consisting of a set, that's possible.

28
00:01:06,333 --> 00:01:09,300
On here, it's the set consisting 
of the empty set.

29
00:01:09,300 --> 00:01:12,000
Last thing I want to mention
is this notation.

30
00:01:12,000 --> 00:01:14,233
So x is in S and 
x is not in S.

31
00:01:14,233 --> 00:01:17,100
For example, 2 is inside
the natural numbers, so

32
00:01:17,100 --> 00:01:20,000
2 in N is a
possibility,

33
00:01:20,000 --> 00:01:22,000
and 0 is 
not in N,

34
00:01:22,000 --> 00:01:23,800
for us.

35
00:01:23,800 --> 00:01:26,033
This is important in 
any proofs with sets.

36
00:01:26,033 --> 00:01:28,266
What do I mean by that? 
Well so sometimes

37
00:01:28,266 --> 00:01:31,566
if you get stuck in a 
set proof question,

38
00:01:31,566 --> 00:01:34,533
one thing that you might want 
to try to do is say, “Okay well

39
00:01:34,533 --> 00:01:35,866
I have an 
element,

40
00:01:35,866 --> 00:01:39,066
however I have it, it’s this element 
x, let's say, in some bigger set,

41
00:01:39,066 --> 00:01:42,933
and now I know it's either in the 
smaller set, or it's not in the smaller set.

42
00:01:42,933 --> 00:01:45,466
And doing things like 
that might help you to

43
00:01:45,466 --> 00:01:47,266
progress in the
proof, right?

44
00:01:47,266 --> 00:01:49,066
Elements are either in 
sets or not in sets.

45
00:01:49,066 --> 00:01:52,000
There's no limbo for elements 
and membership in sets.

46
00:01:52,000 --> 00:01:56,000
You're either in or you're out, 
there's no on the fence. 

47
00:01:56,000 --> 00:01:59,466
So that's the
rough intro to sets.

48
00:01:59,466 --> 00:02:02,066
Some other set 
examples, so

49
00:02:02,066 --> 00:02:04,766
we did some exercises in 
class with these two,

50
00:02:04,766 --> 00:02:08,600
so I wanted to give two examples. The two
most important ones that we did in class.

51
00:02:08,600 --> 00:02:11,266
Set of even numbers between 
5 and 14 inclusive.

52
00:02:11,266 --> 00:02:14,066
Well if you're just dealing with the set 
of even numbers between 5 and 14,

53
00:02:14,066 --> 00:02:17,466
you can just write down all the
even numbers between 5 and 14.

54
00:02:17,466 --> 00:02:18,933
There's no problem. You 
don't have to use

55
00:02:18,933 --> 00:02:20,400
set notation if you 
don't want to.

56
00:02:20,400 --> 00:02:24,433
So if you don't it's just 6, 8, 10, 
12, 14. That's perfectly fine.

57
00:02:24,433 --> 00:02:27,700
If you do use set notation, then 
something like this will work, for example

58
00:02:27,700 --> 00:02:29,300
n is a natural 
number

59
00:02:29,300 --> 00:02:32,400
such that 5 is less or equal to 
n is less or equal to 14,

60
00:02:32,400 --> 00:02:35,166
and 2 divides n. So here again 
we see that divisibility sign;

61
00:02:35,166 --> 00:02:37,666
it’s gonna pop up
everywhere in this course.

62
00:02:37,666 --> 00:02:39,766
As another example, 
all odd perfect squares.

63
00:02:39,766 --> 00:02:42,566
So here we're gonna 
do it in a different way.

64
00:02:42,566 --> 00:02:44,466
So here we're 
going to define

65
00:02:44,466 --> 00:02:48,266
the members to be the elements of
the form 2k plus 1 squared, 

66
00:02:48,266 --> 00:02:52,000
and here what's k? Well k is 
a member of the integers.

67
00:02:52,000 --> 00:02:54,733
You can also do it as k as a
member of the natural numbers,

68
00:02:54,733 --> 00:02:57,133
the difference here is that 
when k is in the integers,

69
00:02:57,133 --> 00:03:00,166
you're going to get multiple representations 
of the same element of a set.

70
00:03:00,166 --> 00:03:03,133
So remember that sets
don't have overlap.

71
00:03:03,133 --> 00:03:05,233
So, I mean, you 
can't have like

72
00:03:05,233 --> 00:03:06,900
three copies of 
1 in your set.

73
00:03:06,900 --> 00:03:09,100
Once 1 is in your set, it's 
in your set. That's it.

74
00:03:09,100 --> 00:03:11,500
There's not multiple
levels of 1.

75
00:03:11,500 --> 00:03:14,066
There's just 1 and
that's it, okay?

76
00:03:14,066 --> 00:03:16,933
So here even though there's multiple 
ways to write the same element,

77
00:03:16,933 --> 00:03:19,333
it still describes the 
same set, that's fine. 

78
00:03:19,333 --> 00:03:21,300
Multiple numbers have
different representations,

79
00:03:21,300 --> 00:03:23,300
there’s sort of 
no avoiding this. 

80
00:03:23,300 --> 00:03:27,733
Well in this case there is avoiding 
it but in many cases it's not.

81
00:03:27,733 --> 00:03:30,733
I guess I should say, 
so be careful here.

82
00:03:30,733 --> 00:03:33,900
If you use N you actually miss 1, 
I really should say 2k minus 1.

83
00:03:33,900 --> 00:03:36,000
Not a 
huge deal.

84
00:03:36,000 --> 00:03:38,000


85
00:03:38,000 --> 00:03:40,000
Okay. Set 
operations.

86
00:03:40,000 --> 00:03:44,000
So let S and T be sets. We have 
a couple of definitions,

87
00:03:44,000 --> 00:03:46,333
so if 
you see

88
00:03:46,333 --> 00:03:49,100
the octothorpe, or 
the pound symbol, S

89
00:03:49,100 --> 00:03:51,833
or if you see two vertical 
bars with the [letter] S,

90
00:03:51,833 --> 00:03:54,100
that is the size 
of the set S.

91
00:03:54,100 --> 00:03:55,600


92
00:03:55,600 --> 00:03:58,000
The second notation 
is more common -

93
00:03:58,000 --> 00:03:59,900
magnitude is more common 
than this pound notation,

94
00:03:59,900 --> 00:04:01,700
but you might 
see either or.

95
00:04:01,700 --> 00:04:03,333
S union T,

96
00:04:03,333 --> 00:04:05,166
this is a set of elements 
x such that

97
00:04:05,166 --> 00:04:07,733
x is in S 
[or] T.

98
00:04:07,733 --> 00:04:12,000
S intersect T, this is a set of 
elements in both S and T.

99
00:04:12,000 --> 00:04:15,833
So notice the similarity 
between the logic notations.

100
00:04:15,833 --> 00:04:18,533
Union and ‘or’ 

101
00:04:18,533 --> 00:04:21,966
and intersection 
and ‘and’.

102
00:04:21,966 --> 00:04:26,333
They're similar and they're not 
completely independent, but

103
00:04:26,333 --> 00:04:28,433
they are different 
so don't use

104
00:04:28,433 --> 00:04:30,100
'or’ when you're 
talking about sets,

105
00:04:30,100 --> 00:04:32,966
and don't use union when you're 
talking about statements.

106
00:04:32,966 --> 00:04:36,500
S minus T is set difference, 
so x is in S and x is not in T.

107
00:04:36,500 --> 00:04:39,666
S bar or S c. I think
we’re gonna use

108
00:04:39,666 --> 00:04:43,400
S bar in this course, 
but S c is also common.

109
00:04:43,400 --> 00:04:45,700
This is the complement of S, 
so what does that mean?

110
00:04:45,700 --> 00:04:49,866
It means x is inside my universe 
U such that x is not in S.

111
00:04:49,866 --> 00:04:52,000
So if you use that, you can actually 
write this with set difference,

112
00:04:52,000 --> 00:04:54,000
it's just to set 
U minus S.

113
00:04:54,000 --> 00:04:57,500
The last thing I want to talk about is
Cartesian Product, so S cross T.

114
00:04:57,500 --> 00:04:58,566


115
00:04:58,566 --> 00:05:01,100
It’s the set of 
ordered pairs

116
00:05:01,100 --> 00:05:02,066


117
00:05:02,066 --> 00:05:06,200
x comma y such that
x is in S and y is in T.

118
00:05:06,200 --> 00:05:09,233
This is important, 
right, so

119
00:05:09,233 --> 00:05:11,733
notice that the 
elements x and y

120
00:05:11,733 --> 00:05:13,366
are completely independent 
of themselves, so

121
00:05:13,366 --> 00:05:15,766
even if you take 
something like Z cross Z,

122
00:05:15,766 --> 00:05:18,000
it's not just all the 
elements of the form

123
00:05:18,000 --> 00:05:20,700
(1,1), (2,2), 
(3,3), (4,4), etc.

124
00:05:20,700 --> 00:05:22,500
(1,2) is in 
that set

125
00:05:22,500 --> 00:05:25,633
and (2,1) [is] in that set, right? Those
are two different elements in that set,

126
00:05:25,633 --> 00:05:27,166
(1,2) and (2,1).

127
00:05:27,166 --> 00:05:31,066
So it's the set of ordered pairs,
order matters in a Cartesian Product.

128
00:05:31,066 --> 00:05:32,500


129
00:05:32,500 --> 00:05:36,533
Something to write about. Again, 
this is just ways to combine sets

130
00:05:36,533 --> 00:05:39,233
to make new sets 
from old sets.

131
00:05:39,233 --> 00:05:42,100
Okay, so that's the end
of set operations.

132
00:05:42,100 --> 00:05:43,700
A little bit more of
set terminology.

133
00:05:43,700 --> 00:05:47,166
So there are a lot of
symbols in this notation. Now,

134
00:05:47,166 --> 00:05:49,066
if you managed to find this 
video, the chances are you've

135
00:05:49,066 --> 00:05:51,300
already looked at the Math
135 Resources Page,

136
00:05:51,300 --> 00:05:53,233
and know that there
are symbol cheat sheets.

137
00:05:53,233 --> 00:05:55,133
You might need these 
for the first little bit

138
00:05:55,133 --> 00:05:57,066
just to help you remember 
what all the symbols mean.

139
00:05:57,066 --> 00:05:59,866
Again, it's a bad idea - 
really bad idea - to

140
00:05:59,866 --> 00:06:02,766
try to answer a question if you
don't know what the symbols mean,

141
00:06:02,766 --> 00:06:05,100
if you don't understand 
the notation.

142
00:06:05,100 --> 00:06:07,166
Best advice is: 
don't do it.

143
00:06:07,166 --> 00:06:10,733
If you don't understand the notation,
don't try to answer problems.

144
00:06:10,733 --> 00:06:13,500
Try to understand the notation first and 
then try to answer the problem.

145
00:06:13,500 --> 00:06:15,633
It's far easier 
that way.

146
00:06:15,633 --> 00:06:17,500
Okay, so let S 
and T be sets.

147
00:06:17,500 --> 00:06:19,666
Then S is a 
subset of T,

148
00:06:19,666 --> 00:06:23,766
that's denoted by this symbol, and that 
means that every element of S is in T.

149
00:06:23,766 --> 00:06:27,066
Here S is a proper subset, 
or a strict subset, of T. So

150
00:06:27,066 --> 00:06:30,366
S is a subset of T and there's some 
element in T that's not in S,

151
00:06:30,366 --> 00:06:32,033
so they're 
not equal.

152
00:06:32,033 --> 00:06:34,000
Equality we'll get 
to in a minute.

153
00:06:34,000 --> 00:06:37,266
So S contains T, and 
S properly contains T.

154
00:06:37,266 --> 00:06:40,033
It's similar except now 
T is a subset of S 

155
00:06:40,033 --> 00:06:42,166
and T is a subset of S 
and S is not equal to T

156
00:06:42,166 --> 00:06:44,733
so there’s some element
of S that's not in T.

157
00:06:44,733 --> 00:06:45,733


158
00:06:45,733 --> 00:06:47,800
S equals T, what 
does that mean?

159
00:06:47,800 --> 00:06:50,133
So, set equality, 
this is sort of the…

160
00:06:50,133 --> 00:06:52,800
this is something that's  really 
really important here, set equality.

161
00:06:52,800 --> 00:06:56,000
Now what does this 
mean? S equals T

162
00:06:56,000 --> 00:07:00,000
It means this. It means that S is a 
subset of T, and T is a subset of S.

163
00:07:00,000 --> 00:07:02,000
That's what set 
equality means.

164
00:07:02,000 --> 00:07:04,233
It's different than
equality of integers

165
00:07:04,233 --> 00:07:07,300
or equality of variables, 
things like this.

166
00:07:07,300 --> 00:07:10,533
The equality operator 
does get overloaded.

167
00:07:10,533 --> 00:07:12,666
So S equals T

168
00:07:12,666 --> 00:07:15,700
does mean that S is a subset 
of T and T is a subset of S.

169
00:07:15,700 --> 00:07:19,033
So if you are asked to prove that two 
sets are equal, you must show

170
00:07:19,033 --> 00:07:22,433
that S is a subset of T 
and T is a subset of S.

171
00:07:22,433 --> 00:07:26,166
We're gonna see an example that we 
saw in class on the next slide

172
00:07:26,166 --> 00:07:29,600
that helps, again,

173
00:07:29,600 --> 00:07:32,300
reiterate this fact 
and emphasize it.

174
00:07:32,300 --> 00:07:34,233


175
00:07:34,233 --> 00:07:37,266
So show that the set 
S equals the set T

176
00:07:37,266 --> 00:07:41,366
if and only if S intersect 
T equals S union T.

177
00:07:41,366 --> 00:07:43,633
That's what we're 
going to prove.

178
00:07:43,633 --> 00:07:46,266
This is an ‘if and only if’ proof 
so we have to prove

179
00:07:46,266 --> 00:07:48,566
the implication and 
its converse.

180
00:07:48,566 --> 00:07:50,633
So the implication is,
“Suppose that S equals T

181
00:07:50,633 --> 00:07:53,800
and we'd like to show that S 
intersect T is equal to S union T.”

182
00:07:53,800 --> 00:07:55,733
To show this, we 
need to show that

183
00:07:55,733 --> 00:07:57,866
S intersect T is a 
subset of S union T

184
00:07:57,866 --> 00:08:02,033
and that S intersect T
contains S union T.

185
00:08:02,033 --> 00:08:04,300
How do we show
the first thing?

186
00:08:04,300 --> 00:08:07,333
So to show that S intersect T 
is a subset of S union T,

187
00:08:07,333 --> 00:08:09,666
start with an element 
of S intersect T

188
00:08:09,666 --> 00:08:12,466
and show that it 
must be in S union T.

189
00:08:12,466 --> 00:08:15,033
First, suppose that x is 
inside the intersection.

190
00:08:15,033 --> 00:08:18,300
Well what does that mean? That 
means that x is in S and x is in T.

191
00:08:18,300 --> 00:08:20,500
Well if x is in S 
and x is in T,

192
00:08:20,500 --> 00:08:23,600
then definitely x 
is in S or T,

193
00:08:23,600 --> 00:08:26,700
and so x is an
element of S union T.

194
00:08:26,700 --> 00:08:28,933
Next, suppose that x is 
an element of the union,

195
00:08:28,933 --> 00:08:32,600
so x is in S 
or x is in T.

196
00:08:32,600 --> 00:08:35,366
Well what does that 
mean? Since S equals T…

197
00:08:35,366 --> 00:08:37,800
so this is something that we didn't 
need in the first half of the proof,

198
00:08:37,800 --> 00:08:39,533
but in this half 
of the proof

199
00:08:39,533 --> 00:08:44,000
we're going to use that fact. 
Well if x is in S, then X is in T,

200
00:08:44,000 --> 00:08:47,633
and if x is in T, then X is in 
S because S is equal to T.

201
00:08:47,633 --> 00:08:50,900
So, in either case, we know
that x is in S and x is in T.

202
00:08:50,900 --> 00:08:53,100
And so thus, x must be 
in the intersection.

203
00:08:53,100 --> 00:08:55,266
So what have we shown? We 
showed that an arbitrary element

204
00:08:55,266 --> 00:08:58,033
in the union must be 
in the intersection,

205
00:08:58,033 --> 00:09:00,400
and previous to that we showed 
that an arbitrary element

206
00:09:00,400 --> 00:09:02,366
of the intersection
must be in the union.

207
00:09:02,366 --> 00:09:05,766
Here I've used the same letter x 
to mean different things, okay?

208
00:09:05,766 --> 00:09:08,000
You could have 
chose different letters.

209
00:09:08,000 --> 00:09:10,600
The way I'm viewing this and
the way I'm reading this

210
00:09:10,600 --> 00:09:12,633
is that x ends
after the bullet,

211
00:09:12,633 --> 00:09:15,600
so the scope of x is
only each bullet, okay?

212
00:09:15,600 --> 00:09:19,300
It's probably sloppy, you should probably 
use different letters. It's not a huge deal. 

213
00:09:19,300 --> 00:09:22,166
It might be a huge deal
if you start confusing them.

214
00:09:22,166 --> 00:09:25,766
For me, I guess I know what I 
wrote, so I understand what I'm doing.

215
00:09:25,766 --> 00:09:26,866


216
00:09:26,866 --> 00:09:29,100
Just keep that in 
mind though, okay? 

217
00:09:29,100 --> 00:09:30,300


218
00:09:30,300 --> 00:09:31,866
Okay.

219
00:09:31,866 --> 00:09:34,466
So that shows the direction, 
if S is equal to T, then

220
00:09:34,466 --> 00:09:36,733
S intersect T is equal
to S union T. 

221
00:09:36,733 --> 00:09:39,433
Now we need to start… now we
need to prove the converse.

222
00:09:39,433 --> 00:09:42,166
So what does the converse say? Well 
we need to start with the conclusion,

223
00:09:42,166 --> 00:09:43,800
S intersect T
equals S union T, 

224
00:09:43,800 --> 00:09:45,633
and we want to show
that S equals T.

225
00:09:45,633 --> 00:09:47,800
How do we do that? We
show that S is a subset of T

226
00:09:47,800 --> 00:09:49,566
and T is a subset 
of S, okay?

227
00:09:49,566 --> 00:09:51,633
Don't try to make your
own rules up.

228
00:09:51,633 --> 00:09:55,900
Try to follow this reasonably 
mechanically and you should

229
00:09:55,900 --> 00:09:57,933
struggle less 
with sets. So,

230
00:09:57,933 --> 00:10:00,000
if we're showing that 
S is a subset of T,

231
00:10:00,000 --> 00:10:02,966
start with an element of S, an
arbitrary element of S, 

232
00:10:02,966 --> 00:10:05,800
well if x is in S then 
x is inside S union T

233
00:10:05,800 --> 00:10:09,033
because well x is in S so 
it's definitely in S or T, 

234
00:10:09,033 --> 00:10:11,500
and S union T is equal 
to the intersection.

235
00:10:11,500 --> 00:10:14,833
But if x is in the intersection, 
then x is in S and x is in T.

236
00:10:14,833 --> 00:10:17,033
So hence, 
X is in T.

237
00:10:17,033 --> 00:10:19,466
Now in class, I mentioned well 
this is... you can actually

238
00:10:19,466 --> 00:10:21,466
use the word "similarly", right? So 
now what I'm going to do is

239
00:10:21,466 --> 00:10:23,733
I'm gonna just
replace this letter S 

240
00:10:23,733 --> 00:10:26,600
with this letter T, and go through 
the proof exactly the same way.

241
00:10:26,600 --> 00:10:29,333
x is in T so therefore 
x is in S union T,

242
00:10:29,333 --> 00:10:31,300
which is equal to the
intersection. Hence,

243
00:10:31,300 --> 00:10:34,300
instead of x being
in T, now x is in S 

244
00:10:34,300 --> 00:10:37,500
and that proves the
inclusion S is a subset of T.

245
00:10:37,500 --> 00:10:38,600


246
00:10:38,600 --> 00:10:41,100
Now I’ve proved that S is a 
subset of T, T is a subset of S,

247
00:10:41,100 --> 00:10:44,333
therefore they're equal, 
and that's the end of it.

248
00:10:44,333 --> 00:10:46,433
So that is an ‘if and 
only if’ proof with sets,

249
00:10:46,433 --> 00:10:48,600
so there's a lot on this
slide; a lot to digest.

250
00:10:48,600 --> 00:10:51,166
If you understand this slide 
and what happened here,

251
00:10:51,166 --> 00:10:55,199
I feel like you're in pretty good shape with 
both sets and ‘if and only if’ statements.