1
00:00:00,690 --> 00:00:03,440
- [Instructor] Hi, we've
got some material coming up

2
00:00:03,440 --> 00:00:04,540
that involves sets,

3
00:00:04,540 --> 00:00:07,470
we're gonna look at equivalence relations

4
00:00:07,470 --> 00:00:11,820
and equivalence classes,
disjoint sets and so on.

5
00:00:11,820 --> 00:00:13,820
And so I thought it would be helpful

6
00:00:13,820 --> 00:00:16,230
if we just had a quick review of sets.

7
00:00:16,230 --> 00:00:21,230
If you're totally on top of
sets, then you can skip this.

8
00:00:21,890 --> 00:00:24,840
If you want a quick
refresher, it can't hurt,

9
00:00:24,840 --> 00:00:26,940
but we're just gonna go
over the rudiments of sets

10
00:00:26,940 --> 00:00:29,360
so we have the foundation that we need

11
00:00:29,360 --> 00:00:31,703
to cover the material
that's coming up next.

12
00:00:32,650 --> 00:00:34,280
So again, a lot of this is gonna look

13
00:00:34,280 --> 00:00:35,493
pretty familiar to you.

14
00:00:36,770 --> 00:00:38,550
So let's start with a set.

15
00:00:38,550 --> 00:00:43,020
A set is an unordered
bag of stuff, basically.

16
00:00:43,020 --> 00:00:45,530
And sometimes we draw pictures of sets

17
00:00:45,530 --> 00:00:48,590
with some shape that represents
the boundary of a set.

18
00:00:48,590 --> 00:00:50,690
And inside the boundary is all the stuff

19
00:00:50,690 --> 00:00:52,390
that belongs to the set.

20
00:00:52,390 --> 00:00:55,070
So here we have the set
of all capital letters

21
00:00:55,070 --> 00:00:56,443
in the English alphabet.

22
00:00:57,630 --> 00:00:59,700
And the stuff outside the boundary

23
00:00:59,700 --> 00:01:01,870
is all the stuff that's not in the set.

24
00:01:01,870 --> 00:01:06,870
The lowercase letter d here
is not an element of this set.

25
00:01:08,200 --> 00:01:10,010
Here's a set of some foods,

26
00:01:10,010 --> 00:01:13,730
and we refer to contents of a
set as the elements of a set.

27
00:01:13,730 --> 00:01:17,450
So pizza is an element
of the set of foods.

28
00:01:17,450 --> 00:01:21,023
And so is pretzel, and so is cheese, okay?

29
00:01:23,350 --> 00:01:25,270
Now, a set may have just one element.

30
00:01:25,270 --> 00:01:28,723
If so, we call this a singleton,
this is a singleton set.

31
00:01:31,340 --> 00:01:33,130
Sets can be empty too.

32
00:01:33,130 --> 00:01:35,570
That is a set might not have any elements,

33
00:01:35,570 --> 00:01:38,610
in which case we call it the empty set,

34
00:01:38,610 --> 00:01:40,770
and we denote it with this symbol here.

35
00:01:40,770 --> 00:01:43,773
An empty set is a set
that has no elements.

36
00:01:46,210 --> 00:01:48,270
Now, let's take this
set that we saw before

37
00:01:48,270 --> 00:01:52,980
and we'll give it a name, A,
just for notation purposes.

38
00:01:52,980 --> 00:01:57,860
And we'll say that pretzel
is an element of A,

39
00:01:57,860 --> 00:02:02,700
this symbol here indicates
that this object here

40
00:02:02,700 --> 00:02:06,070
is an element of the set that we called A.

41
00:02:06,070 --> 00:02:09,250
So yep, pretzel's in there, there's A,

42
00:02:09,250 --> 00:02:10,833
pretzel is an element of A.

43
00:02:12,880 --> 00:02:14,600
We strike through that symbol

44
00:02:14,600 --> 00:02:17,260
to indicate that something
is not an element of A.

45
00:02:17,260 --> 00:02:19,120
So here we have the sailing ship,

46
00:02:19,120 --> 00:02:24,120
and the sailing ship is clearly
not an element of this set.

47
00:02:24,520 --> 00:02:25,970
So we strike that through

48
00:02:25,970 --> 00:02:29,113
and we read this sailing
ship is not an element of A,

49
00:02:30,010 --> 00:02:33,860
or sometimes not contained
in A, same thing.

50
00:02:33,860 --> 00:02:37,030
Now, we call the number
of elements in a set

51
00:02:37,030 --> 00:02:40,120
the sets cardinality, and
we write this with two bars.

52
00:02:40,120 --> 00:02:42,600
It looks like absolute value notation.

53
00:02:42,600 --> 00:02:45,490
But when we're talking about
sets, when this A is a set,

54
00:02:45,490 --> 00:02:47,510
we're talking about the
cardinality of the set,

55
00:02:47,510 --> 00:02:49,310
the number of elements in the set.

56
00:02:49,310 --> 00:02:52,660
So here we have one,
two, three, four, five,

57
00:02:52,660 --> 00:02:55,080
the cardinality of A is five.

58
00:02:55,080 --> 00:02:57,650
Do keep in mind that
some sets are infinite.

59
00:02:57,650 --> 00:02:59,700
For example, the set of integers.

60
00:02:59,700 --> 00:03:01,200
We'll get to that in a minute.

61
00:03:02,650 --> 00:03:04,300
Now, what can we do with sets?

62
00:03:04,300 --> 00:03:06,470
Well, we have some operations on sets

63
00:03:06,470 --> 00:03:09,780
and the two most basic are
union and intersection.

64
00:03:09,780 --> 00:03:12,440
We can take the union of two or more sets,

65
00:03:12,440 --> 00:03:15,430
and the result of the
union will be another set

66
00:03:15,430 --> 00:03:18,680
that contains all the elements
in the sets under union.

67
00:03:18,680 --> 00:03:23,350
So here we have the set, we
take the union with this set,

68
00:03:23,350 --> 00:03:25,370
and we get a result that contains

69
00:03:25,370 --> 00:03:27,393
all of these elements, okay?

70
00:03:29,700 --> 00:03:32,410
We can also take the
intersection of two sets.

71
00:03:32,410 --> 00:03:36,090
The intersection of two sets
consists of the set of elements

72
00:03:36,090 --> 00:03:39,530
that are in all of the
sets under intersection.

73
00:03:39,530 --> 00:03:43,660
So here we have the set here,
here we have the set here,

74
00:03:43,660 --> 00:03:48,070
this is the symbol for intersection,
and this is our result.

75
00:03:48,070 --> 00:03:48,903
Why?

76
00:03:48,903 --> 00:03:52,660
Well, because the football,
the American football

77
00:03:52,660 --> 00:03:57,280
is in both sets, and the
volleyball is in both sets,

78
00:03:57,280 --> 00:03:59,160
but those are the only two elements

79
00:03:59,160 --> 00:04:02,890
that are common to both sets,
that's the intersection.

80
00:04:02,890 --> 00:04:05,460
Now, you may have seen
Venn diagrams before,

81
00:04:05,460 --> 00:04:07,830
and Venn diagrams are commonly used

82
00:04:07,830 --> 00:04:09,360
to indicate such an intersection.

83
00:04:09,360 --> 00:04:12,150
They don't have to, but
they're commonly used for this.

84
00:04:12,150 --> 00:04:15,600
So here we see the same two sets,

85
00:04:15,600 --> 00:04:17,660
and the intersection is shown

86
00:04:17,660 --> 00:04:22,390
as the part where the interiors
of those sets overlap.

87
00:04:22,390 --> 00:04:24,290
That's a Venn diagram.

88
00:04:24,290 --> 00:04:25,950
Here's another example.

89
00:04:25,950 --> 00:04:28,500
We have the set of all
things that are red,

90
00:04:28,500 --> 00:04:30,650
we have the set of all flowers,

91
00:04:30,650 --> 00:04:33,023
and roses here sits in the intersection.

92
00:04:35,020 --> 00:04:38,740
Now, two sets may not have an intersection

93
00:04:38,740 --> 00:04:41,713
or I should say their
intersection is empty.

94
00:04:42,590 --> 00:04:46,610
And that is that two sets
have no elements in common.

95
00:04:46,610 --> 00:04:48,990
And if two sets have
no elements in common,

96
00:04:48,990 --> 00:04:50,380
we call them disjoint.

97
00:04:50,380 --> 00:04:53,230
So here's the set of all football teams.

98
00:04:53,230 --> 00:04:56,530
Here's the set of things
in my top desk drawer.

99
00:04:56,530 --> 00:04:58,820
And you see, they have no common elements,

100
00:04:58,820 --> 00:05:00,163
there is no intersection.

101
00:05:01,020 --> 00:05:06,020
So we would write A
intersection B is the empty set.

102
00:05:07,320 --> 00:05:11,000
That's assuming that we call
the set of all football teams A

103
00:05:11,000 --> 00:05:13,910
and the set of all things
in my top desk drawer B.

104
00:05:13,910 --> 00:05:16,633
A intersection B is the empty set.

105
00:05:17,470 --> 00:05:19,883
These two sets again are disjoint.

106
00:05:22,510 --> 00:05:25,120
Now, sets can be contained within sets.

107
00:05:25,120 --> 00:05:28,030
In which case we can speak of subsets.

108
00:05:28,030 --> 00:05:31,220
So, here we have the
set of all vertebrates,

109
00:05:31,220 --> 00:05:33,720
those are animals with a backbone.

110
00:05:33,720 --> 00:05:37,770
And the set of all mammals is a subset

111
00:05:37,770 --> 00:05:40,120
of the set of all vertebrates.

112
00:05:40,120 --> 00:05:44,100
And the set of all cats is a subset

113
00:05:44,100 --> 00:05:46,120
of the set of all mammals.

114
00:05:46,120 --> 00:05:49,760
And the set containing fluffy is a subset

115
00:05:49,760 --> 00:05:52,093
of the set of all cats, and so on.

116
00:05:53,960 --> 00:05:56,630
And we have a convenient
notation for writing this.

117
00:05:56,630 --> 00:05:58,782
We have a subset symbol,
this is a subset symbol.

118
00:05:58,782 --> 00:06:02,130
So here's the set containing fluffy.

119
00:06:02,130 --> 00:06:05,300
We indicate a set in curly braces,

120
00:06:05,300 --> 00:06:09,700
and this set is a subset
of the set of all cats,

121
00:06:09,700 --> 00:06:13,350
which is in turn a subset
of the set of all mammals,

122
00:06:13,350 --> 00:06:16,423
which in turn is a subset of
the set of all vertebrates.

123
00:06:18,800 --> 00:06:20,770
So as far as that notation goes,

124
00:06:20,770 --> 00:06:23,000
we have two flavors, basically.

125
00:06:23,000 --> 00:06:28,000
We have this symbol, which is
meant to be a strict subset.

126
00:06:28,210 --> 00:06:30,660
Now, some authors will
use this differently,

127
00:06:30,660 --> 00:06:33,810
but this is how it's most
commonly done, I believe.

128
00:06:33,810 --> 00:06:36,570
And this is certainly the
way I'll present things.

129
00:06:36,570 --> 00:06:39,650
This symbol means that
it's a strict subset.

130
00:06:39,650 --> 00:06:43,630
It means it's not
coincident with all cats.

131
00:06:43,630 --> 00:06:45,350
The set containing fluffy

132
00:06:45,350 --> 00:06:49,240
is smaller than the set of all cats.

133
00:06:49,240 --> 00:06:51,860
So the set containing fluffy

134
00:06:51,860 --> 00:06:56,203
does not equal the set of all
cats, this is a strict subset.

135
00:06:57,130 --> 00:07:00,083
And we use this symbol,
which is also true.

136
00:07:01,150 --> 00:07:03,383
You can think of this
as subset or equal to,

137
00:07:04,410 --> 00:07:06,600
and that's also true in this case,

138
00:07:06,600 --> 00:07:09,083
but it's not as strong a claim, right?

139
00:07:11,460 --> 00:07:14,760
Now, some sets are so
commonly used and so important

140
00:07:14,760 --> 00:07:17,270
that we give them their
own special symbols.

141
00:07:17,270 --> 00:07:19,760
This is of course for mathematics,

142
00:07:19,760 --> 00:07:22,120
but we use these in computer
science quite a bit,

143
00:07:22,120 --> 00:07:24,730
especially the first two.

144
00:07:24,730 --> 00:07:27,670
This symbol or double strike Z

145
00:07:27,670 --> 00:07:30,180
represents the set of all integers.

146
00:07:30,180 --> 00:07:32,850
That would be all integers

147
00:07:32,850 --> 00:07:35,130
positive or negative, including zero.

148
00:07:35,130 --> 00:07:39,310
We get the letter Z from the German Zolan

149
00:07:39,310 --> 00:07:40,383
which means number.

150
00:07:42,240 --> 00:07:45,990
This double strike n symbolizes the set

151
00:07:45,990 --> 00:07:47,310
of all natural numbers.

152
00:07:47,310 --> 00:07:48,860
Those are the counting numbers,

153
00:07:48,860 --> 00:07:50,363
one, two, three, four, five.

154
00:07:51,420 --> 00:07:54,510
And then we also have the double strike R

155
00:07:54,510 --> 00:07:56,880
which represents the
set of all real numbers.

156
00:07:56,880 --> 00:07:59,760
And that's again, an infinite set.

157
00:07:59,760 --> 00:08:02,063
Here's some examples, five, 2.2, PI,

158
00:08:03,095 --> 00:08:05,890
negative 17.62 one third.

159
00:08:05,890 --> 00:08:09,800
All of these in fact are infinite sets.

160
00:08:09,800 --> 00:08:11,180
Now, the last thing I wanna cover

161
00:08:11,180 --> 00:08:13,060
is what's called set builder notation,

162
00:08:13,060 --> 00:08:14,830
and this gives us a convenient way

163
00:08:14,830 --> 00:08:16,840
of indicating elements in a set

164
00:08:16,840 --> 00:08:19,210
without having to enumerate all of them,

165
00:08:19,210 --> 00:08:20,280
which can get tedious,

166
00:08:20,280 --> 00:08:22,230
especially if you have very large sets.

167
00:08:23,200 --> 00:08:25,150
So here are a few examples.

168
00:08:25,150 --> 00:08:28,980
First we have the set A, and the set A

169
00:08:28,980 --> 00:08:33,780
consists of all acts that
are elements of the integers,

170
00:08:33,780 --> 00:08:36,300
such that we read this bar such that,

171
00:08:36,300 --> 00:08:40,560
and it indicates a condition
for being a member in the set

172
00:08:40,560 --> 00:08:43,390
such that x is greater than seven.

173
00:08:43,390 --> 00:08:47,063
So this would be the
integers eight and greater.

174
00:08:48,670 --> 00:08:53,670
Here's the set B where we don't
specify any underlying set,

175
00:08:54,230 --> 00:08:57,940
so we assume it's the set
of all possible objects,

176
00:08:57,940 --> 00:09:00,600
and the condition is y is blue.

177
00:09:00,600 --> 00:09:03,960
So this is the set of all blue things.

178
00:09:03,960 --> 00:09:06,460
And here's another set C,

179
00:09:06,460 --> 00:09:11,460
which is the set of all z such
that z has four wheels, okay?

180
00:09:11,860 --> 00:09:13,420
So think about what those are.

181
00:09:13,420 --> 00:09:16,380
Again, in the case of A,

182
00:09:16,380 --> 00:09:18,423
we have the integers greater than seven.

183
00:09:19,650 --> 00:09:21,830
In the case of B, we have the sky,

184
00:09:21,830 --> 00:09:24,020
we have blueberries, we have Neptunes.

185
00:09:24,020 --> 00:09:27,653
There's no other condition
other than the y is blue, okay?

186
00:09:28,980 --> 00:09:30,890
And in the last case,

187
00:09:30,890 --> 00:09:34,180
we have things like cars,
shopping carts and lawnmowers,

188
00:09:34,180 --> 00:09:37,840
but you see, this as a
very convenient shorthand

189
00:09:37,840 --> 00:09:42,000
for writing a set, call
that set builder notation,

190
00:09:42,000 --> 00:09:44,993
also sometimes called
a conditional notation.

191
00:09:46,220 --> 00:09:49,590
And that's really all we're
gonna need for this class.

192
00:09:49,590 --> 00:09:51,610
Subsequently, we're
gonna look like I said,

193
00:09:51,610 --> 00:09:53,090
at equivalence relations,

194
00:09:53,090 --> 00:09:55,410
equivalence classes, disjoint sets,

195
00:09:55,410 --> 00:09:59,210
we're going to work with
taking the unions of sets.

196
00:09:59,210 --> 00:10:02,263
And this was intended just
to give you a quick overview.

197
00:10:04,020 --> 00:10:05,420
See you in the next lecture.