1
00:00:00,500 --> 00:00:02,830
The following content is
provided under a Creative
2
00:00:02,830 --> 00:00:04,340
Commons license.
3
00:00:04,340 --> 00:00:06,680
Your support will help
MIT OpenCourseWare
4
00:00:06,680 --> 00:00:11,050
continue to offer high quality
educational resources for free.
5
00:00:11,050 --> 00:00:13,660
To make a donation or
view additional materials
6
00:00:13,660 --> 00:00:17,566
from hundreds of MIT courses,
visit MIT OpenCourseWare
7
00:00:17,566 --> 00:00:18,191
at ocw.mit.edu.
8
00:00:23,480 --> 00:00:29,670
MARTEN VAN DIJK: So today we're
going to talk about relations.
9
00:00:29,670 --> 00:00:32,380
We're going to talk
about partial orders.
10
00:00:32,380 --> 00:00:33,701
Wow this is loud.
11
00:00:33,701 --> 00:00:34,950
Could you put it a bit softer?
12
00:00:38,130 --> 00:00:40,870
So we're going to
talk about relations,
13
00:00:40,870 --> 00:00:45,590
partial orders, and then
parallel task scheduling.
14
00:00:45,590 --> 00:00:50,450
So well, we'll start out with
a few definitions as usual
15
00:00:50,450 --> 00:00:55,760
and examples will explain what
you're talking about here.
16
00:00:55,760 --> 00:00:58,320
So what about relations?
17
00:00:58,320 --> 00:01:03,300
Well, relations are
very simple definition.
18
00:01:03,300 --> 00:01:15,880
A relation from a
set A to a set B
19
00:01:15,880 --> 00:01:23,610
is really a subset of the
cross product of the two.
20
00:01:23,610 --> 00:01:26,270
So let me give an example.
21
00:01:26,270 --> 00:01:32,330
It's a subset R that has its
elements in a cross product
22
00:01:32,330 --> 00:01:35,720
of A and B, which really
means that it has pairs where
23
00:01:35,720 --> 00:01:38,010
the first element
is drawn from A
24
00:01:38,010 --> 00:01:40,976
and the second
element is from B.
25
00:01:40,976 --> 00:01:45,700
So for example, if you're
thinking about the classes
26
00:01:45,700 --> 00:01:50,650
that you're taking as say,
set B and all the students
27
00:01:50,650 --> 00:01:54,140
set A, well, then
you can describe
28
00:01:54,140 --> 00:01:58,160
this is as a relationship
where we have tuples
29
00:01:58,160 --> 00:02:08,080
a, b where a student
a is taking class b.
30
00:02:08,080 --> 00:02:15,540
So a relation is really
just a set of pairs.
31
00:02:15,540 --> 00:02:21,440
The first part of the pair is
in set A, the second one in B.
32
00:02:21,440 --> 00:02:23,630
Now, we will use
different notation
33
00:02:23,630 --> 00:02:29,740
for indicating that a
pair is in this subset,
34
00:02:29,740 --> 00:02:32,340
so we'll be talking
about further properties,
35
00:02:32,340 --> 00:02:35,460
then it will become more
clear, but we will also write
36
00:02:35,460 --> 00:02:38,550
that a is to relate this to b.
37
00:02:38,550 --> 00:02:43,530
So instead of the pair
a, b is an element of R,
38
00:02:43,530 --> 00:02:48,390
you may write a R b,
or we say a and then
39
00:02:48,390 --> 00:02:54,830
we use this symbol
with a subscript R b.
40
00:02:54,830 --> 00:03:00,810
So we use the relational
symbol in between a
41
00:03:00,810 --> 00:03:03,609
and b in these two cases.
42
00:03:03,609 --> 00:03:05,150
And the reason for
that becomes clear
43
00:03:05,150 --> 00:03:07,240
if you start talking
about the properties,
44
00:03:07,240 --> 00:03:10,080
but let me first give
a few more examples
45
00:03:10,080 --> 00:03:15,015
and talk about the
types of relations
46
00:03:15,015 --> 00:03:16,390
that you're really
interested in.
47
00:03:16,390 --> 00:03:23,370
We really are interested
in a relation on a set A,
48
00:03:23,370 --> 00:03:31,250
and this is really
a subset R that
49
00:03:31,250 --> 00:03:33,550
is a cross product
of A with itself.
50
00:03:33,550 --> 00:03:37,130
So essentially, A is equal
to B in the definition
51
00:03:37,130 --> 00:03:39,420
right up here.
52
00:03:39,420 --> 00:03:42,110
Now, examples that we
have for this one is,
53
00:03:42,110 --> 00:03:46,770
for example, we may have A
to B, all in the integers,
54
00:03:46,770 --> 00:03:52,400
positive and negative, and
then we can say, for example, x
55
00:03:52,400 --> 00:03:56,810
is related to y if
and only if x is,
56
00:03:56,810 --> 00:04:02,560
for example, congruent
to y modulo 5.
57
00:04:02,560 --> 00:04:06,036
This would be a proper relation.
58
00:04:06,036 --> 00:04:08,620
We have not yet talked
about special properties.
59
00:04:08,620 --> 00:04:10,320
We will come to that.
60
00:04:10,320 --> 00:04:12,200
Other examples
are, well, we could
61
00:04:12,200 --> 00:04:20,029
take all the positive
integers, 0, 1, and so on
62
00:04:20,029 --> 00:04:23,130
and so forth, and
then right so x
63
00:04:23,130 --> 00:04:26,140
is related to y if and
only if, for example, you
64
00:04:26,140 --> 00:04:29,070
could say that x defines y.
65
00:04:29,070 --> 00:04:31,660
That's another relationship
that we could use.
66
00:04:31,660 --> 00:04:36,250
Notice, by the way that
in the correct [INAUDIBLE]
67
00:04:36,250 --> 00:04:39,530
that I put here, I already
used sort of relational symbols
68
00:04:39,530 --> 00:04:42,990
right in the middle
between x and y over here.
69
00:04:42,990 --> 00:04:46,630
So that's already
indicating why we are using
70
00:04:46,630 --> 00:04:49,670
a notation that I put up here.
71
00:04:49,670 --> 00:04:53,100
So another example
is, for example,
72
00:04:53,100 --> 00:05:03,570
we have that x is related to y
if and only if x is at most y.
73
00:05:03,570 --> 00:05:05,947
This is also a relation.
74
00:05:05,947 --> 00:05:07,780
So now what are the
special property that we
75
00:05:07,780 --> 00:05:11,570
are interested in and those
that will make relations
76
00:05:11,570 --> 00:05:16,100
special and then we can
talk about-- actually,
77
00:05:16,100 --> 00:05:20,520
I forgot one item
that we will talk
78
00:05:20,520 --> 00:05:23,600
about as well, which
are equivalents
79
00:05:23,600 --> 00:05:32,050
classes, equivalence relations.
80
00:05:32,050 --> 00:05:34,500
So we will see when we
talk about the properties
81
00:05:34,500 --> 00:05:37,820
right now that we
will be defining
82
00:05:37,820 --> 00:05:40,110
very special types
of relations and we
83
00:05:40,110 --> 00:05:42,680
will talk about these
two, equivalents relations
84
00:05:42,680 --> 00:05:45,781
and partial orders.
85
00:05:45,781 --> 00:05:46,905
So what are the properties?
86
00:05:51,600 --> 00:05:54,180
Actually before we go
into those properties,
87
00:05:54,180 --> 00:05:57,800
let us just first describe what
the relationship, how we can
88
00:05:57,800 --> 00:06:01,160
describe it in a different way.
89
00:06:01,160 --> 00:06:05,190
Actually relation is nothing
more than a directed graph,
90
00:06:05,190 --> 00:06:11,940
like R over here is a subset
of a cross product with a.
91
00:06:11,940 --> 00:06:16,080
So that's pairs and you can
think of those as being edges.
92
00:06:16,080 --> 00:06:18,220
So let us write it down as well.
93
00:06:18,220 --> 00:06:32,120
So set A together with
R is a directed graph.
94
00:06:35,600 --> 00:06:39,456
And the idea is very simple.
95
00:06:39,456 --> 00:06:44,300
The directed graph has
vertices V and edge set
96
00:06:44,300 --> 00:06:54,640
E where we take V to be equal to
A and the edge set equal to R.
97
00:06:54,640 --> 00:07:00,650
So for example, we could
create a small little graph,
98
00:07:00,650 --> 00:07:06,380
for example, for three
persons, Julie and Bill
99
00:07:06,380 --> 00:07:08,970
and another one, Rob.
100
00:07:08,970 --> 00:07:10,700
And suppose that
the directed edges
101
00:07:10,700 --> 00:07:13,820
indicate whether one
person likes the other.
102
00:07:13,820 --> 00:07:19,620
So for example Julie likes
Bill and Bill likes himself,
103
00:07:19,620 --> 00:07:20,830
but likes no one else.
104
00:07:23,690 --> 00:07:26,670
Julie also likes Rob,
but does not like herself
105
00:07:26,670 --> 00:07:29,510
and Rob really likes Julie,
but does not like himself.
106
00:07:29,510 --> 00:07:35,530
So for example, you
could create a graph
107
00:07:35,530 --> 00:07:42,980
where all the directed edge
really represent the relations
108
00:07:42,980 --> 00:07:45,260
that you have described by R.
109
00:07:45,260 --> 00:07:51,207
So we will use this later on
and the special properties
110
00:07:51,207 --> 00:07:56,030
that we are interested
in are the following.
111
00:07:56,030 --> 00:08:03,620
So the properties are that
relations can be reflexive.
112
00:08:03,620 --> 00:08:16,970
So a relation R
on A is reflexive
113
00:08:16,970 --> 00:08:34,900
if x is related to itself for
all x, so for all x in A. Well,
114
00:08:34,900 --> 00:08:39,120
for example, in this particular
graph, that is not the case.
115
00:08:39,120 --> 00:08:42,200
If Julie and Rob would
also like themselves,
116
00:08:42,200 --> 00:08:47,220
then the relationship up here
would actually be reflexive.
117
00:08:47,220 --> 00:08:55,410
We have symmetry, so we call
a relationship symmetric
118
00:08:55,410 --> 00:09:05,040
if x likes y, then that should
imply that y also likes x
119
00:09:05,040 --> 00:09:07,550
and it should, of course,
hold for all x and y.
120
00:09:14,040 --> 00:09:20,760
We have a property that
we call antisymmetric,
121
00:09:20,760 --> 00:09:22,270
which is the opposite of this.
122
00:09:22,270 --> 00:09:36,540
Antisymmetric means that if x
likes y and y likes x, then x
123
00:09:36,540 --> 00:09:38,990
and y must be the same.
124
00:09:38,990 --> 00:09:41,640
So this really
means that it's not
125
00:09:41,640 --> 00:09:45,240
really possible to
like someone else
126
00:09:45,240 --> 00:09:49,620
and that someone
else also likes x,
127
00:09:49,620 --> 00:09:53,870
because according to the
antisymmetrical property,
128
00:09:53,870 --> 00:09:57,080
that would then imply that
x is actually equal to y.
129
00:09:57,080 --> 00:10:01,950
So these two definitions are
opposite from one another.
130
00:10:01,950 --> 00:10:05,095
And the final one that we're
interested in is transitivity.
131
00:10:13,400 --> 00:10:24,880
So the relationship is
transitive if x likes y and y
132
00:10:24,880 --> 00:10:30,420
likes z, then x also likes z.
133
00:10:33,110 --> 00:10:35,970
So let's have a look
at these few examples
134
00:10:35,970 --> 00:10:41,020
and see whether we can figure
out what kind of properties
135
00:10:41,020 --> 00:10:42,890
they have.
136
00:10:42,890 --> 00:10:49,990
So let's make a
table and let's first
137
00:10:49,990 --> 00:10:52,310
consider that x
is congruent to y
138
00:10:52,310 --> 00:11:02,250
modulo 5 and next divisibility
and the other one is less than
139
00:11:02,250 --> 00:11:03,830
or equal to.
140
00:11:03,830 --> 00:11:08,614
So are they reflexive
is the first question
141
00:11:08,614 --> 00:11:10,280
and they we want to
know whether they're
142
00:11:10,280 --> 00:11:18,165
symmetric and antisymmetric
and transitive.
143
00:11:23,080 --> 00:11:26,810
So what about this
one over here?
144
00:11:26,810 --> 00:11:29,770
So can you help me figure
out whether they're
145
00:11:29,770 --> 00:11:33,170
reflexive and symmetric or
antisymmetric and transitive?
146
00:11:33,170 --> 00:11:35,970
What kind of properties
does this one have?
147
00:11:35,970 --> 00:11:39,795
So when we look at x is
congruent to y modulo 5,
148
00:11:39,795 --> 00:11:44,890
it really means that the
difference between x and y
149
00:11:44,890 --> 00:11:48,180
is divisible by 5.
150
00:11:48,180 --> 00:11:51,120
So is it reflexive?
151
00:11:51,120 --> 00:11:53,440
Is x congruent to x modulo 5?
152
00:11:53,440 --> 00:11:55,020
It is right.
153
00:11:55,020 --> 00:11:56,520
That's easy.
154
00:11:56,520 --> 00:11:58,430
So we have yes.
155
00:11:58,430 --> 00:12:04,000
Now, if x is congruent
to y module 5,
156
00:12:04,000 --> 00:12:07,630
is y also congruent
to x modulo 5?
157
00:12:07,630 --> 00:12:10,410
It is because the
difference between x and y
158
00:12:10,410 --> 00:12:13,810
is divisible by 5
and stays the same.
159
00:12:13,810 --> 00:12:16,840
So y is congruent to x as well.
160
00:12:16,840 --> 00:12:19,920
So it is symmetric.
161
00:12:19,920 --> 00:12:24,750
Now what about
the antisymmetric?
162
00:12:24,750 --> 00:12:29,690
If x is congruent to
y modulo 5 and y is
163
00:12:29,690 --> 00:12:35,084
congruent to x modulo 5, does
that mean that x is equal to y?
164
00:12:35,084 --> 00:12:36,250
It's not really true, right?
165
00:12:36,250 --> 00:12:39,820
You can give a
counterexample for that.
166
00:12:39,820 --> 00:12:48,840
So for example, we could have
that 7 is congruent to 2 modulo
167
00:12:48,840 --> 00:13:03,220
5 and 2 is congruent to 7 modulo
5, but they're not the same.
168
00:13:03,220 --> 00:13:05,690
So this is not true.
169
00:13:05,690 --> 00:13:07,040
No.
170
00:13:07,040 --> 00:13:09,350
What about transitivity?
171
00:13:09,350 --> 00:13:12,050
Is this true?
172
00:13:12,050 --> 00:13:15,090
So let's consider
this example as well.
173
00:13:15,090 --> 00:13:20,030
So if I have that 2 and 7 are
congruent to one another modulo
174
00:13:20,030 --> 00:13:24,780
5, well, 7 is also, for example,
congruent to 12 modulo 5.
175
00:13:27,390 --> 00:13:30,420
Does it mean that 2 and 12
are congruent to one another?
176
00:13:30,420 --> 00:13:36,240
So we have 2 is
congruent to 7 modulo 5.
177
00:13:36,240 --> 00:13:40,100
We have, say 7 is
congruent to 12 modulo 5.
178
00:13:42,640 --> 00:13:45,700
Well, we can look at
the difference between 2
179
00:13:45,700 --> 00:13:49,440
and 12, which is 10,
is also divisible by 5.
180
00:13:49,440 --> 00:13:53,690
So actually this does imply that
2 is congruent to 12 modulo 5.
181
00:13:53,690 --> 00:13:55,450
Now, this is, of
course, not a proof
182
00:13:55,450 --> 00:13:57,900
because this is just
by example, but you
183
00:13:57,900 --> 00:14:00,620
can check for yourself that
this relationship is actually
184
00:14:00,620 --> 00:14:02,600
transitive.
185
00:14:02,600 --> 00:14:05,940
Now, what about divisibility.
186
00:14:05,940 --> 00:14:08,810
Maybe you can help
me with this one.
187
00:14:08,810 --> 00:14:09,905
So is it reflexive?
188
00:14:14,107 --> 00:14:14,690
Is this right?
189
00:14:14,690 --> 00:14:15,520
I hear yes.
190
00:14:15,520 --> 00:14:17,980
That's correct because if x
and y equal to one another,
191
00:14:17,980 --> 00:14:23,270
well, it's 1 times x, so x
divides x, so that's true.
192
00:14:23,270 --> 00:14:24,920
Is it symmetric?
193
00:14:24,920 --> 00:14:32,310
So if x divides y and y
divides x, so let's just see.
194
00:14:32,310 --> 00:14:33,380
We are over here.
195
00:14:33,380 --> 00:14:37,150
So if x divides y, does
that imply that y divides x?
196
00:14:37,150 --> 00:14:39,740
That's the relation
that we want to check.
197
00:14:39,740 --> 00:14:40,840
Is that true?
198
00:14:40,840 --> 00:14:41,470
Not really.
199
00:14:41,470 --> 00:14:46,580
We can have like say 3 divides
9, but 9 does not divide 3,
200
00:14:46,580 --> 00:14:50,840
so this is not true,
but antisymmetry.
201
00:14:50,840 --> 00:14:55,560
So if x defies y and
also y divides x,
202
00:14:55,560 --> 00:14:57,740
then they must be
equal to one another.
203
00:14:57,740 --> 00:15:04,150
So we can see that this
actually is antisymmetric,
204
00:15:04,150 --> 00:15:05,400
so that's interesting.
205
00:15:05,400 --> 00:15:10,800
And transitivity, well, we
have, again, transitivity
206
00:15:10,800 --> 00:15:14,850
because if x divides y and
y divides z, then x also
207
00:15:14,850 --> 00:15:15,550
divides z.
208
00:15:15,550 --> 00:15:20,480
For example, if 2 divides,
say 4 and 4 divides 20,
209
00:15:20,480 --> 00:15:24,570
then 2 also divides 20.
210
00:15:24,570 --> 00:15:28,490
Now this one over here has
actually the same properties
211
00:15:28,490 --> 00:15:31,210
as divisibility.
212
00:15:31,210 --> 00:15:37,800
It's reflexive because x is
at least equal to itself.
213
00:15:41,240 --> 00:15:44,600
It's not symmetric
because if x is at most y,
214
00:15:44,600 --> 00:15:47,780
does not really imply
that y is at most x,
215
00:15:47,780 --> 00:15:52,490
so this particular relation
does not hold, in general,
216
00:15:52,490 --> 00:15:54,700
but it is, again,
antisymmetric because if I
217
00:15:54,700 --> 00:15:58,120
have this inequality
and the other one, well,
218
00:15:58,120 --> 00:16:00,860
x and y must be equal to
one another in that case
219
00:16:00,860 --> 00:16:03,280
and transitive as well.
220
00:16:03,280 --> 00:16:06,330
Now, it turns out that
in these examples,
221
00:16:06,330 --> 00:16:10,130
we have seen a certain
combination of properties
222
00:16:10,130 --> 00:16:12,880
that we will be talking about.
223
00:16:12,880 --> 00:16:17,460
The kind of combination
that we see here
224
00:16:17,460 --> 00:16:22,070
will lead to a definition
of equivalence classes,
225
00:16:22,070 --> 00:16:32,170
equivalence relations, and this
is also a very usual pattern,
226
00:16:32,170 --> 00:16:36,160
and this we will define
as partial orders.
227
00:16:40,420 --> 00:16:45,320
So this is what we are
going to talk about next.
228
00:16:45,320 --> 00:16:51,630
So we'll first start with
equivalence relations,
229
00:16:51,630 --> 00:16:54,120
so let's do this.
230
00:16:54,120 --> 00:16:56,340
What is an equivalence relation?
231
00:16:56,340 --> 00:16:58,190
An equivalence
relation is exactly
232
00:16:58,190 --> 00:17:00,950
a relation that has those
few properties over there.
233
00:17:00,950 --> 00:17:05,569
So there's reflexive,
symmetric, and transitive.
234
00:17:05,569 --> 00:17:21,980
So an equivalence relation is
reflexive and also symmetric
235
00:17:21,980 --> 00:17:23,989
and also transitive.
236
00:17:28,380 --> 00:17:31,360
So we've already
seen some examples
237
00:17:31,360 --> 00:17:35,000
up there or one example, but
a very trivial relation, maybe
238
00:17:35,000 --> 00:17:39,270
you can think of one that
is really straightforward.
239
00:17:39,270 --> 00:17:40,770
What will be an
equivalence relation
240
00:17:40,770 --> 00:17:45,505
if you think about how we write
mathematical formulas down?
241
00:17:45,505 --> 00:17:47,910
We usually like the
equality sign also.
242
00:17:47,910 --> 00:18:02,620
So just equality the equal
sign itself is actually
243
00:18:02,620 --> 00:18:05,120
one example and
the other example
244
00:18:05,120 --> 00:18:07,770
is the one that we have
there and that's, of course,
245
00:18:07,770 --> 00:18:08,500
more general.
246
00:18:08,500 --> 00:18:11,760
We can have x is
congruent to y modulo n.
247
00:18:11,760 --> 00:18:20,100
So for fixed n, we have
another equivalence relation.
248
00:18:20,100 --> 00:18:24,390
So now given those, we can start
defining equivalence classes.
249
00:18:24,390 --> 00:18:29,020
So what is an equivalence class?
250
00:18:29,020 --> 00:18:33,460
That's actually everything
within that class
251
00:18:33,460 --> 00:18:35,030
is related to itself.
252
00:18:35,030 --> 00:18:41,100
So the equivalence class
of an element, x in a
253
00:18:41,100 --> 00:18:52,180
is equal to the set of
all the elements in a that
254
00:18:52,180 --> 00:19:05,720
are related to x
by our relation R.
255
00:19:05,720 --> 00:19:07,350
So we denote this
equivalence class.
256
00:19:09,860 --> 00:19:14,530
So this is denoted by x
with brackets around it.
257
00:19:14,530 --> 00:19:18,870
So let's put it into a formula
and give some examples.
258
00:19:18,870 --> 00:19:22,110
So the formula for
this in mathematics
259
00:19:22,110 --> 00:19:31,280
would be the set of all the y
such that x is related to y.
260
00:19:31,280 --> 00:19:38,500
So as an example, we can do the
one that we started off with.
261
00:19:38,500 --> 00:19:46,040
So let's again look at x
is congruent to y modulo 5
262
00:19:46,040 --> 00:19:48,300
and look at the
equivalence classes.
263
00:19:48,300 --> 00:19:52,310
So one of them, for
example, we could look
264
00:19:52,310 --> 00:19:55,561
at the equivalence class of 7.
265
00:19:55,561 --> 00:19:57,060
We were looking at
this one already.
266
00:19:57,060 --> 00:20:02,410
Well, what are all the
y's that are actually
267
00:20:02,410 --> 00:20:06,030
congruence to 7 modulo 5?
268
00:20:06,030 --> 00:20:08,570
Well, there are a whole bunch.
269
00:20:08,570 --> 00:20:13,420
We have minus 3
and we have 2, 7,
270
00:20:13,420 --> 00:20:18,750
we have 12, 17,
and 22, and so on.
271
00:20:18,750 --> 00:20:23,105
And we add 5 to all these and
this is the equivalence class
272
00:20:23,105 --> 00:20:24,850
that belongs to 7.
273
00:20:24,850 --> 00:20:27,900
Now notice that the
equivalence class of 7
274
00:20:27,900 --> 00:20:32,460
is actually equal to the
equivalence class of 12.
275
00:20:32,460 --> 00:20:34,750
It's the same set.
276
00:20:34,750 --> 00:20:37,380
Everything that is
congruent to 12 modulo 5
277
00:20:37,380 --> 00:20:41,730
is also congruent to 7 module
5 and this is, again, equal
278
00:20:41,730 --> 00:20:44,840
to say, 17, and so on.
279
00:20:49,670 --> 00:20:53,780
So now we can start talking
about a nice property
280
00:20:53,780 --> 00:20:56,930
that equivalence
classes have, which
281
00:20:56,930 --> 00:21:00,230
is that the equivalence classes
together partition the set A.
282
00:21:00,230 --> 00:21:05,270
So I will need to define
first what a partition is.
283
00:21:05,270 --> 00:21:08,530
And it's defined as follows.
284
00:21:08,530 --> 00:21:37,230
A partition of A is a collection
of this joint non-empty sets A1
285
00:21:37,230 --> 00:21:44,010
up to An and they're
all subsets of A.
286
00:21:44,010 --> 00:21:47,850
And the union of all
of those is actually
287
00:21:47,850 --> 00:21:54,057
equal to the set A.
So who's union is A.
288
00:21:54,057 --> 00:21:55,890
So let's have a look,
again, at this example
289
00:21:55,890 --> 00:21:58,790
and see whether we
can figure out what
290
00:21:58,790 --> 00:22:01,700
the equivalence classes are.
291
00:22:01,700 --> 00:22:05,940
So the example is, well,
we can have everything
292
00:22:05,940 --> 00:22:08,110
that this actually
a multiple of 5.
293
00:22:08,110 --> 00:22:10,320
That's this one class.
294
00:22:10,320 --> 00:22:16,790
So we have minus 5, 0, 5,
10, and we go all the way up.
295
00:22:16,790 --> 00:22:20,620
Another equivalence
class is, well,
296
00:22:20,620 --> 00:22:25,310
we just add 1 to each of those
elements here, so if minus 4
297
00:22:25,310 --> 00:22:28,356
is congruent to 1, modulo
5 is congruent to 6,
298
00:22:28,356 --> 00:22:32,590
modulo 5 congruent
to 11, and so on.
299
00:22:32,590 --> 00:22:36,610
And so we can continue and we
actually see that we minus 3
300
00:22:36,610 --> 00:22:41,230
is congruent to 2, to
7, to 12, and so on.
301
00:22:41,230 --> 00:22:44,630
That's the one we had up there.
302
00:22:44,630 --> 00:22:53,320
Another one is
minus 2, 3, 8, 13,
303
00:22:53,320 --> 00:23:01,760
and we have minus 1,
4, 9, 14, and so forth.
304
00:23:01,760 --> 00:23:03,880
So these are all the
equivalence classes
305
00:23:03,880 --> 00:23:05,900
because now we look around.
306
00:23:05,900 --> 00:23:10,380
If we add one more
2 minus 1, we get 0.
307
00:23:10,380 --> 00:23:14,250
So we get 0, 5, 15, and
so on and that's exactly
308
00:23:14,250 --> 00:23:15,980
the same class as this one.
309
00:23:15,980 --> 00:23:21,220
So we see that for this
particular example,
310
00:23:21,220 --> 00:23:26,460
we notice that these equivalence
classes are a partition of all
311
00:23:26,460 --> 00:23:27,980
the integers.
312
00:23:27,980 --> 00:23:32,150
Turns out that this
is a general property
313
00:23:32,150 --> 00:23:36,090
and we're not going
to prove this.
314
00:23:36,090 --> 00:23:38,680
That's pretty straightforward,
so you should actually
315
00:23:38,680 --> 00:23:41,860
think about it yourself.
316
00:23:41,860 --> 00:23:47,840
Let's keep this up
here and take this out.
317
00:23:54,070 --> 00:24:00,728
So the theorem is that every
equivalence relation on a set A
318
00:24:00,728 --> 00:24:04,220
can be partitioned in
its questions classes.
319
00:24:04,220 --> 00:24:23,500
So the theorem is
the equivalence class
320
00:24:23,500 --> 00:24:46,970
of an equivalence relation on
a set A form a partition of A.
321
00:24:46,970 --> 00:24:49,590
Now, I'm not going
to prove this.
322
00:24:49,590 --> 00:24:51,430
It's actually really
straightforward.
323
00:24:51,430 --> 00:24:54,876
You should really look at this
and see that you can prove this
324
00:24:54,876 --> 00:24:56,250
with the properties,
the property
325
00:24:56,250 --> 00:25:00,260
definitions, and the definition
of an equivalence relation.
326
00:25:00,260 --> 00:25:03,720
So this is as far as we go
is equivalence relations.
327
00:25:03,720 --> 00:25:07,040
And so now we will continue
with partial orders.
328
00:25:07,040 --> 00:25:10,000
Again, we go through
a few definitions
329
00:25:10,000 --> 00:25:12,290
and then at some point,
we'll be able to prove
330
00:25:12,290 --> 00:25:15,280
a few interesting properties.
331
00:25:15,280 --> 00:25:17,305
So let's talk about
partial orders.
332
00:25:20,730 --> 00:25:26,290
So notice that we have shifted
now from in this diagram
333
00:25:26,290 --> 00:25:30,739
over here, in this table,
from this pattern that you
334
00:25:30,739 --> 00:25:31,780
were first interested in.
335
00:25:31,780 --> 00:25:33,760
Now, we go to partial
orders and the difference
336
00:25:33,760 --> 00:25:38,270
is going to be that we
do not have symmetry,
337
00:25:38,270 --> 00:25:41,420
but we do have antisymmetry
and that brings out
338
00:25:41,420 --> 00:25:45,110
a whole different structure.
339
00:25:45,110 --> 00:25:56,900
So a relation is-- it's in
brackets I put here-- weak,
340
00:25:56,900 --> 00:25:59,520
I'll explain in a
moment why I do this.
341
00:25:59,520 --> 00:26:11,780
It's a weak partial
order if it is
342
00:26:11,780 --> 00:26:16,855
reflexive, and antisymmetric
and transitive.
343
00:26:28,840 --> 00:26:32,020
So why do I put weak up here?
344
00:26:32,020 --> 00:26:34,700
Well, if you look in the book,
there are two definitions,
345
00:26:34,700 --> 00:26:42,200
one is a weak partial order,
which is with reflexivity
346
00:26:42,200 --> 00:26:45,230
and another one is a
strong partial order.
347
00:26:45,230 --> 00:26:49,420
And that one has a
property that I did not
348
00:26:49,420 --> 00:26:52,240
talk about here
called irreflexibility
349
00:26:52,240 --> 00:26:55,650
and it's something that I will
not talk about in this lecture,
350
00:26:55,650 --> 00:26:58,420
but you should read about
it and all these properties,
351
00:26:58,420 --> 00:27:01,950
all the theorems that we talk
about right now also hold
352
00:27:01,950 --> 00:27:04,250
for the strong version
of a partial order.
353
00:27:04,250 --> 00:27:09,280
But for now, let's just
call partial orders
354
00:27:09,280 --> 00:27:12,810
those that are reflexive,
antisymmetric, and transitive.
355
00:27:15,420 --> 00:27:19,720
Well, we already saw a
few examples up here.
356
00:27:19,720 --> 00:27:29,440
We have divisibility, which has
this property and also the less
357
00:27:29,440 --> 00:27:30,795
than or equal relationship.
358
00:27:35,420 --> 00:27:38,030
Now usually what
we do is, instead
359
00:27:38,030 --> 00:27:43,470
of using a capital letter R,
we will use a relation symbol.
360
00:27:43,470 --> 00:27:58,550
So a partial order relation
is denoted differently,
361
00:27:58,550 --> 00:28:13,900
is denoted with something
like that instead of R. Now
362
00:28:13,900 --> 00:28:19,950
the reason for that is
because we have actually
363
00:28:19,950 --> 00:28:22,450
will show that there's
a partial order,
364
00:28:22,450 --> 00:28:28,990
so this name does
not come by itself.
365
00:28:28,990 --> 00:28:32,910
It turns out that we can give
an order to the order ranking
366
00:28:32,910 --> 00:28:37,200
to the elements, one element
is less than another and so on.
367
00:28:37,200 --> 00:28:47,180
So let's keep this over
here and change up here.
368
00:28:49,890 --> 00:28:58,100
So an example that we will talk
about in the moment, but first
369
00:28:58,100 --> 00:29:00,570
let me introduce
some more notations.
370
00:29:00,570 --> 00:29:12,240
So we call the pair A with
this relationship symbol
371
00:29:12,240 --> 00:29:16,490
is actually called a
partially ordered set.
372
00:29:23,480 --> 00:29:30,005
And we also abbreviate
this by calling it a poset.
373
00:29:34,840 --> 00:29:37,300
Now, in a poset,
again, can be described
374
00:29:37,300 --> 00:29:42,550
by means of a directed graph,
so we can do that as well.
375
00:29:45,980 --> 00:29:52,110
So poset is a
directed graph such
376
00:29:52,110 --> 00:30:01,360
that it has the vertex
set A and the edge set
377
00:30:01,360 --> 00:30:04,060
is defined by the relationship.
378
00:30:04,060 --> 00:30:11,010
So the edge set is
actually this thing.
379
00:30:11,010 --> 00:30:14,040
Notice that in our definition,
this is actually a set, right?
380
00:30:14,040 --> 00:30:14,810
It's still a set.
381
00:30:17,580 --> 00:30:24,050
It's a set of tuples, of
pairs, and we can, again,
382
00:30:24,050 --> 00:30:28,690
create a directed graph by using
this, so nothing has changed.
383
00:30:28,690 --> 00:30:35,950
But for posets, we can actually
create a more sort of easier
384
00:30:35,950 --> 00:30:40,080
to read sort of
representation, which we'll
385
00:30:40,080 --> 00:30:44,870
call a Hesse diagram,
which is also a graph
386
00:30:44,870 --> 00:30:47,470
and let me give an example
to explain how that works.
387
00:30:51,460 --> 00:30:54,023
So I think we can take this out.
388
00:30:57,436 --> 00:31:04,860
So the example is, imagine
that a guy is going to dress up
389
00:31:04,860 --> 00:31:07,430
for something very formal.
390
00:31:07,430 --> 00:31:10,020
So how does he start out?
391
00:31:10,020 --> 00:31:15,590
So let's have as vertices in
the graph, in this diagram
392
00:31:15,590 --> 00:31:21,690
or the elements of A is going to
be all items that he will start
393
00:31:21,690 --> 00:31:24,460
to put on and start wearing,
so his pants, his shirt,
394
00:31:24,460 --> 00:31:24,990
and so on.
395
00:31:24,990 --> 00:31:27,250
So let's have a look.
396
00:31:27,250 --> 00:31:30,620
So what do you start off with?
397
00:31:30,620 --> 00:31:32,970
Well, maybe your underwear
would be a good idea.
398
00:31:36,300 --> 00:31:39,620
So this could be a first
item that you want to put on.
399
00:31:39,620 --> 00:31:44,770
So let's have the relation that
we are interested in to be one
400
00:31:44,770 --> 00:31:47,610
where we say, well, I first
need to put on my underwear
401
00:31:47,610 --> 00:31:53,130
and only after that I can
put on my pants, for example.
402
00:31:53,130 --> 00:31:55,150
So that makes sense too.
403
00:31:55,150 --> 00:31:58,400
And since I'm doing something
very formal later on,
404
00:31:58,400 --> 00:32:01,970
I better first put
on my shirt because I
405
00:32:01,970 --> 00:32:05,470
like to tuck that into
my pants, but it's not
406
00:32:05,470 --> 00:32:08,130
really necessary to
first put on my underwear
407
00:32:08,130 --> 00:32:09,190
or first put on my shirt.
408
00:32:09,190 --> 00:32:10,860
I can do either of the two.
409
00:32:10,860 --> 00:32:15,780
So we're getting sort of
the I don't care so much.
410
00:32:15,780 --> 00:32:22,800
I want to put on a tie,
put on a jacket as well,
411
00:32:22,800 --> 00:32:30,240
and after the pants, I
need to put on my belt,
412
00:32:30,240 --> 00:32:35,590
but I like to finish all that
before I put on my jacket.
413
00:32:35,590 --> 00:32:42,580
And I also have my right
sock that I like to put on
414
00:32:42,580 --> 00:32:49,042
and I need to do this first
before I put on my right shoe.
415
00:32:49,042 --> 00:32:50,025
That makes sense.
416
00:32:53,980 --> 00:32:57,650
And I definitely like to
finish putting on my pants
417
00:32:57,650 --> 00:32:59,380
before I put on my shoes.
418
00:32:59,380 --> 00:33:05,280
So let's have a preference
relationship over here as well.
419
00:33:05,280 --> 00:33:07,420
But I do not really
care, actually.
420
00:33:07,420 --> 00:33:11,930
I can put on my socks
first and then my underwear
421
00:33:11,930 --> 00:33:12,890
and then my shirt.
422
00:33:12,890 --> 00:33:14,780
I don't mind so much.
423
00:33:14,780 --> 00:33:22,370
I also have my left
sock and my left shoe.
424
00:33:25,360 --> 00:33:31,530
And again, I like
this to be preceded
425
00:33:31,530 --> 00:33:33,270
by putting on my pants.
426
00:33:33,270 --> 00:33:36,410
So this could be a relation,
a sort of a description
427
00:33:36,410 --> 00:33:39,690
of a partial order.
428
00:33:39,690 --> 00:33:42,290
Well, because it's
a Hesse diagram,
429
00:33:42,290 --> 00:33:45,370
so let's talk about
it a little bit
430
00:33:45,370 --> 00:33:52,150
and then I will define what the
official definition of this is.
431
00:33:52,150 --> 00:33:53,450
So let's first look at this.
432
00:33:53,450 --> 00:33:56,440
So this is a partial order.
433
00:33:56,440 --> 00:33:59,160
It means [? a ?] percent
of partial order,
434
00:33:59,160 --> 00:34:00,710
so it's reflexive.
435
00:34:07,676 --> 00:34:11,840
The pants are related to
themselves, so I put them on.
436
00:34:16,134 --> 00:34:18,550
Before I put on the pants, I
need to put on the underwear,
437
00:34:18,550 --> 00:34:23,610
but if I need to put on my belt
after I put on my underwear,
438
00:34:23,610 --> 00:34:27,159
then also I notice I first
need to put on my underwear
439
00:34:27,159 --> 00:34:28,989
before I put on my belt.
440
00:34:28,989 --> 00:34:33,329
So you have transitivity
in this example.
441
00:34:37,520 --> 00:34:43,610
It's also the other property
is that it is antisymmetric.
442
00:34:43,610 --> 00:34:46,980
It's not true that I can first
put on my right shoe and then
443
00:34:46,980 --> 00:34:54,409
my right sock, so we only
have one direction over here.
444
00:34:54,409 --> 00:34:56,659
Now, I did not put
in all the edges
445
00:34:56,659 --> 00:34:58,730
that are possible for
this partial order
446
00:34:58,730 --> 00:35:02,080
because if I really
want to continue this,
447
00:35:02,080 --> 00:35:06,840
if I really want to create the
complete directed graph that I
448
00:35:06,840 --> 00:35:13,390
talked about over here-- I think
it talks about it somewhere--
449
00:35:13,390 --> 00:35:16,670
over here, I can create
a directed graph that
450
00:35:16,670 --> 00:35:19,610
has its vertex set A, which
are all the items that I want
451
00:35:19,610 --> 00:35:20,490
to put on.
452
00:35:20,490 --> 00:35:28,800
And in that set that has all
the different relationships.
453
00:35:28,800 --> 00:35:30,620
Now, this is only
an abbreviated form.
454
00:35:30,620 --> 00:35:32,080
This is a Hesse
diagram, but if I
455
00:35:32,080 --> 00:35:34,010
would look at a
directed graph, then I
456
00:35:34,010 --> 00:35:36,260
would need to look at the
closure of this whole thing.
457
00:35:36,260 --> 00:35:39,500
That's how I would call it.
458
00:35:39,500 --> 00:35:44,610
And I know that, for
example, this underwear,
459
00:35:44,610 --> 00:35:47,210
by transitivity,
is also less than
460
00:35:47,210 --> 00:35:50,010
or equal than or
related to the belt.
461
00:35:50,010 --> 00:36:04,240
So in a full graph, I would
have another edge over here.
462
00:36:04,240 --> 00:36:09,570
And in a same way, I would
have an edge from here to here.
463
00:36:09,570 --> 00:36:13,510
I would have an edge over
here by transitivity.
464
00:36:13,510 --> 00:36:16,560
Also I can see that the
shirt goes before the pants,
465
00:36:16,560 --> 00:36:18,840
before the right
shoe, so the shirt
466
00:36:18,840 --> 00:36:24,190
is also related all the
way to the right shoe
467
00:36:24,190 --> 00:36:26,210
and similarly to the left shoe.
468
00:36:26,210 --> 00:36:30,260
I also have that I have
self loops in here,
469
00:36:30,260 --> 00:36:35,440
like a tie is related to itself,
a jacket as well, and so forth.
470
00:36:35,440 --> 00:36:41,800
So I can put in all these
extra edges and as you can see,
471
00:36:41,800 --> 00:36:44,380
this will be quite a
mess, so the Hesse diagram
472
00:36:44,380 --> 00:36:47,440
is a much nicer,
official interpretation
473
00:36:47,440 --> 00:36:49,430
of what's going on.
474
00:36:49,430 --> 00:37:00,890
So let's define what this
really is and then we'll
475
00:37:00,890 --> 00:37:04,436
continue with some nice
properties of this structure.
476
00:37:13,890 --> 00:37:16,430
So what is a Hesse diagram?
477
00:37:16,430 --> 00:37:23,350
A Hesse diagram is
really one in which I
478
00:37:23,350 --> 00:37:30,360
use the set A as the vertices.
479
00:37:33,240 --> 00:37:38,626
So it is a directed graph--
a different one than the one
480
00:37:38,626 --> 00:37:40,000
that we talked
about it up there.
481
00:37:40,000 --> 00:37:52,600
So it's a directed graph in
which we have the vertex set A,
482
00:37:52,600 --> 00:37:55,350
but the edge set is a
little bit different.
483
00:37:55,350 --> 00:38:01,190
So it is the edge set
that corresponds to this,
484
00:38:01,190 --> 00:38:04,230
but they subtract a whole bunch.
485
00:38:04,230 --> 00:38:09,330
First of all, we remove all
the self loops that we have,
486
00:38:09,330 --> 00:38:16,750
so minus all the self
loops and we also
487
00:38:16,750 --> 00:38:24,075
take out all the edges that
are implied by transitivity.
488
00:38:34,760 --> 00:38:36,510
So that's a definition
of a Hesse diagram.
489
00:38:39,910 --> 00:38:48,100
Now, when we look at the
Hesse diagram over here,
490
00:38:48,100 --> 00:38:51,520
so let me take out these
nodes again or these edges.
491
00:38:59,650 --> 00:39:02,440
So looking at this
Hesse diagram,
492
00:39:02,440 --> 00:39:04,920
you really see a nice
structure in there.
493
00:39:04,920 --> 00:39:09,880
It seems like we can talk about
smallest elements like a shirt,
494
00:39:09,880 --> 00:39:12,000
just like a small element.
495
00:39:12,000 --> 00:39:14,720
It's sort of less
than or equal to
496
00:39:14,720 --> 00:39:18,100
if you think about this
as being the 3%, then
497
00:39:18,100 --> 00:39:21,190
the tie and the jacket and
the pants and the right shoe
498
00:39:21,190 --> 00:39:22,260
and so on.
499
00:39:22,260 --> 00:39:25,910
So you can see a clear order
in this particular graph.
500
00:39:30,510 --> 00:39:35,470
So let's have a look at this.
501
00:39:35,470 --> 00:39:39,210
When I look at this graph, I
also do not see any cycles.
502
00:39:39,210 --> 00:39:41,953
I do not see that the
shirt is less than
503
00:39:41,953 --> 00:39:42,927
or equal to the pants.
504
00:39:42,927 --> 00:39:45,510
It's related to the right shoe
and then it's related to itself
505
00:39:45,510 --> 00:39:48,210
again, so I do not
see any cycles.
506
00:39:48,210 --> 00:39:52,260
And this turns out to be
general property of posets
507
00:39:52,260 --> 00:39:54,150
and that's what we are
going to prove next.
508
00:39:57,020 --> 00:40:02,140
So let's do that over here.
509
00:40:14,600 --> 00:40:19,470
So you see that
there are no cycles
510
00:40:19,470 --> 00:40:20,850
and it's a general property.
511
00:40:20,850 --> 00:40:39,880
So the theorem is that a
poset has no directed cycles
512
00:40:39,880 --> 00:40:45,210
other than self loops.
513
00:40:52,260 --> 00:40:54,400
Now, notice that this
property is really necessary
514
00:40:54,400 --> 00:40:58,360
to have a proper representation
by using a Hesse diagram
515
00:40:58,360 --> 00:41:07,740
because otherwise, if you have
a big, directed cycle, then only
516
00:41:07,740 --> 00:41:10,260
one of those edges would be
part of the Hesse diagram
517
00:41:10,260 --> 00:41:13,920
and all the others are implied
by transitivity sort of.
518
00:41:13,920 --> 00:41:16,060
And that is getting
a little bit messy
519
00:41:16,060 --> 00:41:19,810
because then we do not really
have a unique representation.
520
00:41:19,810 --> 00:41:22,560
But luckily, there are
no directed cycles.
521
00:41:22,560 --> 00:41:25,465
So how do we prove this?
522
00:41:25,465 --> 00:41:32,350
Well, let's do this
by contradiction
523
00:41:32,350 --> 00:41:37,560
and see what happens.
524
00:41:37,560 --> 00:41:40,460
So suppose the contrary.
525
00:41:40,460 --> 00:41:46,640
So suppose that actually
there exists at least two,
526
00:41:46,640 --> 00:41:56,330
an integer, at least two, so
at least n distinct elements,
527
00:41:56,330 --> 00:41:59,220
a1 all the way up
to an that form
528
00:41:59,220 --> 00:42:18,720
a cycle, so such that you
have a directed cycle.
529
00:42:18,720 --> 00:42:23,220
So we would put it
in formula like this.
530
00:42:23,220 --> 00:42:35,600
a1 is related to a2 to a3 and so
on all the way up to an minus 1
531
00:42:35,600 --> 00:42:36,643
an.
532
00:42:36,643 --> 00:42:42,480
And we have a cycle, so
this goes back to a1.
533
00:42:42,480 --> 00:42:44,560
So why would this
be a contradiction?
534
00:42:44,560 --> 00:42:47,920
So maybe you can
help me out here.
535
00:42:47,920 --> 00:42:52,150
So what can I already
derive from those properties
536
00:42:52,150 --> 00:42:53,140
that I have over here?
537
00:42:53,140 --> 00:42:58,400
So I know that the partial
order is antisymmetric,
538
00:42:58,400 --> 00:43:00,970
it is transitive,
it's reflexive.
539
00:43:00,970 --> 00:43:07,839
So how can I get to
a contradiction here?
540
00:43:07,839 --> 00:43:09,380
So let's think about
it a little bit.
541
00:43:13,770 --> 00:43:16,790
Is it possible, for example,
that we could violate
542
00:43:16,790 --> 00:43:23,460
the antisymmetry of the poset?
543
00:43:23,460 --> 00:43:27,720
So can we find maybe two
distinct elements such that
544
00:43:27,720 --> 00:43:32,780
say x is related to y
and y is related to x,
545
00:43:32,780 --> 00:43:38,810
but it's not true
that x is equal to y.
546
00:43:38,810 --> 00:43:43,080
For example, if you
have very small cycle,
547
00:43:43,080 --> 00:43:52,940
say a1 is related to an and
then related to a1, again,
548
00:43:52,940 --> 00:43:54,960
well, then I would
have that a1 is related
549
00:43:54,960 --> 00:43:59,930
to an and an is related to a1.
550
00:43:59,930 --> 00:44:02,900
We should have that an is
then equal to a1 but, that's
551
00:44:02,900 --> 00:44:07,850
not true because the issue of
distinct elements over here.
552
00:44:07,850 --> 00:44:09,610
So that seems to be
an interesting idea.
553
00:44:09,610 --> 00:44:15,340
So maybe we can prove
something of that type.
554
00:44:15,340 --> 00:44:21,970
So can we actually show
that a1 is related to an?
555
00:44:21,970 --> 00:44:24,040
We can write what kind
of a property of a poset
556
00:44:24,040 --> 00:44:26,080
do we use here to
make that happen?
557
00:44:29,920 --> 00:44:35,650
I heard something
vaguely, a mumble.
558
00:44:35,650 --> 00:44:37,600
Yeah, the transitive property.
559
00:44:37,600 --> 00:44:38,840
So how do we do it?
560
00:44:38,840 --> 00:44:40,790
Well, we take those
three together
561
00:44:40,790 --> 00:44:45,630
and we conclude that a1
is also related to a3.
562
00:44:45,630 --> 00:44:51,940
We have a4 over here, so
together with this one,
563
00:44:51,940 --> 00:44:55,420
so a1 is related to a3
and a3 is related to a4.
564
00:44:55,420 --> 00:45:00,920
We have that a1 is related to
a4 and you can use induction
565
00:45:00,920 --> 00:45:04,310
if you want to be
very precise here,
566
00:45:04,310 --> 00:45:07,740
which you should, actually,
but I will not do this.
567
00:45:07,740 --> 00:45:11,590
So you will use induction and
go all the way to the fact
568
00:45:11,590 --> 00:45:15,110
that a1 is actually
related to an.
569
00:45:15,110 --> 00:45:16,710
But wait a minute.
570
00:45:16,710 --> 00:45:22,560
We also have this
particular property
571
00:45:22,560 --> 00:45:28,330
and a1 is not equal to
an by our assumption.
572
00:45:28,330 --> 00:45:33,300
So we get a contradiction,
which means that what
573
00:45:33,300 --> 00:45:35,150
we had over here is not true.
574
00:45:35,150 --> 00:45:38,720
So actually, for
all n, at least two,
575
00:45:38,720 --> 00:45:45,440
n distinct elements
a1 up to an that--
576
00:45:45,440 --> 00:45:51,220
well, we have the negative of
this, so there is no cycle.
577
00:45:51,220 --> 00:45:54,910
So this is a great
property, so now we
578
00:45:54,910 --> 00:45:58,510
start to see why a
poset is actually called
579
00:45:58,510 --> 00:46:00,530
a partial ordered, right?
580
00:46:00,530 --> 00:46:02,870
Because there's
no directed cycles
581
00:46:02,870 --> 00:46:06,360
other than the self
loops, so we sort of
582
00:46:06,360 --> 00:46:08,210
have a ranking to the elements.
583
00:46:08,210 --> 00:46:13,180
We can say that
really one element
584
00:46:13,180 --> 00:46:15,170
is ranked less than another.
585
00:46:15,170 --> 00:46:16,890
So this one is ranked
less than this,
586
00:46:16,890 --> 00:46:19,650
it's ranked less than that,
and it cannot circle back again
587
00:46:19,650 --> 00:46:22,760
and say that this one is ranked
less than this because they
588
00:46:22,760 --> 00:46:27,520
don't have cycles, so that
makes a really consistent story.
589
00:46:27,520 --> 00:46:31,270
Notice that this was different
when we talked about tournament
590
00:46:31,270 --> 00:46:32,470
grass, for example.
591
00:46:32,470 --> 00:46:34,450
That was a very
different structure
592
00:46:34,450 --> 00:46:39,920
and we could not think
of a winner in there.
593
00:46:39,920 --> 00:46:44,890
But in this case,
we have a ranking.
594
00:46:44,890 --> 00:46:53,220
And this leads us to a
more general discussion.
595
00:46:53,220 --> 00:46:57,860
But before we go into that,
I'd like to write down
596
00:46:57,860 --> 00:47:00,500
a conclusion of this theorem.
597
00:47:00,500 --> 00:47:15,210
So after deleting the
self loops from a poset,
598
00:47:15,210 --> 00:47:22,020
we actually get a
directed acyclic graph.
599
00:47:22,020 --> 00:47:25,010
And that's what we
defined last week as well.
600
00:47:25,010 --> 00:47:31,650
So a directed acyclic graph
and we abbreviate this
601
00:47:31,650 --> 00:47:33,895
as D-A-G, a DAG.
602
00:47:37,310 --> 00:47:41,300
So that's a very special
property for the poset.
603
00:47:46,430 --> 00:47:50,650
Now a partial order has elements
that cannot be compared,
604
00:47:50,650 --> 00:47:52,090
for example.
605
00:47:52,090 --> 00:47:57,890
Like in this case, these two
have absolutely no relationship
606
00:47:57,890 --> 00:47:59,130
with one another.
607
00:47:59,130 --> 00:48:03,900
Even through transitivity, I
cannot conclude that either
608
00:48:03,900 --> 00:48:08,970
the right sock is related to
the underwear or the underwear
609
00:48:08,970 --> 00:48:11,970
related to the right sock.
610
00:48:11,970 --> 00:48:16,200
And that makes it
a partial order.
611
00:48:16,200 --> 00:48:19,580
It's possible that you have
elements, pairs of elements,
612
00:48:19,580 --> 00:48:21,480
that are incomparable.
613
00:48:21,480 --> 00:48:22,920
So let me write this down.
614
00:48:30,370 --> 00:48:36,650
So what we really
want to though,
615
00:48:36,650 --> 00:48:39,480
is that we have some kind
of consistent ranking
616
00:48:39,480 --> 00:48:43,620
that we can create for
a partial ordered set.
617
00:48:43,620 --> 00:48:46,980
But for now, we know that
certain pairs cannot be
618
00:48:46,980 --> 00:48:50,710
compared to one another and we
would like to achieve something
619
00:48:50,710 --> 00:48:52,170
like this.
620
00:48:52,170 --> 00:48:56,360
So that's why we start to
talk about what it means
621
00:48:56,360 --> 00:49:06,870
if a and b are
incomparable and this
622
00:49:06,870 --> 00:49:19,880
is, if neither a is related
to b nor b is related to a.
623
00:49:19,880 --> 00:49:28,720
And we say that a and
b are comparable well,
624
00:49:28,720 --> 00:49:34,148
if a is related to b
or b is related to a.
625
00:49:37,100 --> 00:49:38,920
Now we can have a
very special order
626
00:49:38,920 --> 00:49:41,620
which we call total order.
627
00:49:41,620 --> 00:49:53,564
In a total order, it's
actually partial order, but all
628
00:49:53,564 --> 00:49:54,730
the elements and comparable.
629
00:49:58,640 --> 00:50:17,490
So it's a partial order in
which every pair of elements
630
00:50:17,490 --> 00:50:18,170
is comparable.
631
00:50:20,730 --> 00:50:22,770
Now, maybe you can
think about the Hesse
632
00:50:22,770 --> 00:50:24,570
diagram of a total order.
633
00:50:24,570 --> 00:50:26,360
What would it look
like if we have
634
00:50:26,360 --> 00:50:31,300
that all the elements
are actually comparable?
635
00:50:31,300 --> 00:50:36,330
Do you have any idea what
kind of a graph would that be?
636
00:50:36,330 --> 00:50:40,260
So in this case, we had the
partial order because we see
637
00:50:40,260 --> 00:50:45,350
that certain items
cannot be compared,
638
00:50:45,350 --> 00:50:47,500
but what happens if
you have a total order?
639
00:50:50,979 --> 00:50:51,770
For example-- yeah.
640
00:50:51,770 --> 00:50:52,720
Do you have a--
641
00:50:52,720 --> 00:50:55,084
AUDIENCE: It would
be a straight line.
642
00:50:55,084 --> 00:50:56,000
MARTEN VAN DIJK: Yeah.
643
00:50:56,000 --> 00:50:56,670
That's correct.
644
00:50:56,670 --> 00:50:58,330
It will be straight line.
645
00:50:58,330 --> 00:51:06,070
And it will look something
like this and it keeps on going
646
00:51:06,070 --> 00:51:09,351
and over here also,
keeps on going like this.
647
00:51:09,351 --> 00:51:10,350
So it's a straight line.
648
00:51:10,350 --> 00:51:15,660
If it's a finite set, we
have a finite line, so just
649
00:51:15,660 --> 00:51:18,070
a finite number of vertices,
but otherwise, it's
650
00:51:18,070 --> 00:51:22,940
just an infinite line or a
half or semi infinite line.
651
00:51:22,940 --> 00:51:26,510
So why is that?
652
00:51:26,510 --> 00:51:29,350
with every two elements, it
can be compared to one another,
653
00:51:29,350 --> 00:51:31,925
so you can rank them
essentially along this line.
654
00:51:31,925 --> 00:51:34,320
So if you think about
the integers and the less
655
00:51:34,320 --> 00:51:36,490
than or equal to
relation, well, we
656
00:51:36,490 --> 00:51:38,605
see that one is less
than or equal to 2
657
00:51:38,605 --> 00:51:40,750
and 2 is less than or
equal to 3 and so on.
658
00:51:40,750 --> 00:51:46,880
So they all are put in Hesse
diagram as a straight line.
659
00:51:46,880 --> 00:51:49,960
So that's is very special order.
660
00:51:49,960 --> 00:51:52,510
We have a ranking
with the total order
661
00:51:52,510 --> 00:51:55,015
through this straight line.
662
00:51:55,015 --> 00:51:57,670
It will be great if you
can also rank the elements
663
00:51:57,670 --> 00:51:59,660
in a partial order
and that's what
664
00:51:59,660 --> 00:52:02,950
we're going to talk about next.
665
00:52:02,950 --> 00:52:07,030
We're going to talk about the
topological sort of a poset.
666
00:52:07,030 --> 00:52:10,920
And what it really means is
that we're going to extend,
667
00:52:10,920 --> 00:52:14,850
essentially the partial
order toward a total order.
668
00:52:14,850 --> 00:52:17,240
And by doing that,
we will manage
669
00:52:17,240 --> 00:52:20,860
to put a ranking
to all the items.
670
00:52:20,860 --> 00:52:23,220
Let me define what's
happening here.
671
00:52:26,500 --> 00:52:33,260
So this is about equivalence
classes and you remember this.
672
00:52:45,550 --> 00:52:49,270
So what is a topological sort?
673
00:52:49,270 --> 00:53:01,780
So the idea is that
if the total order
674
00:53:01,780 --> 00:53:14,110
is consistent with
a partial order,
675
00:53:14,110 --> 00:53:19,620
then it is called
a topological sort.
676
00:53:19,620 --> 00:53:22,975
So let me redefine it
again more formally.
677
00:53:34,780 --> 00:53:37,580
So what is it?
678
00:53:37,580 --> 00:53:47,910
A topological sort of
a poset is formally
679
00:53:47,910 --> 00:53:53,190
defined as a total order.
680
00:53:59,270 --> 00:54:07,560
It's a total order that has the
same set of items of elements A
681
00:54:07,560 --> 00:54:11,490
but has a different
relation that we
682
00:54:11,490 --> 00:54:15,110
will denote by a subscript, t.
683
00:54:15,110 --> 00:54:23,280
And this is such that
well, the original relation
684
00:54:23,280 --> 00:54:28,320
is contained in the new one.
685
00:54:28,320 --> 00:54:30,315
Notice that these
also denote sets,
686
00:54:30,315 --> 00:54:31,940
so that's why I can
write it like this.
687
00:54:31,940 --> 00:54:37,540
So this set that is
defined by this relation
688
00:54:37,540 --> 00:54:41,430
is a subset of this relation.
689
00:54:41,430 --> 00:54:46,420
So it simply means that
if x is related to y,
690
00:54:46,420 --> 00:54:50,170
then it also implies
that x is related
691
00:54:50,170 --> 00:54:53,050
to y in the total order.
692
00:54:57,080 --> 00:54:59,460
So we're interested
in figuring out
693
00:54:59,460 --> 00:55:01,510
where we can find such
a topological sort.
694
00:55:01,510 --> 00:55:03,210
Is it always possible to do so?
695
00:55:10,430 --> 00:55:18,240
Now it turns out that
every finite poset actually
696
00:55:18,240 --> 00:55:20,900
has a topological sort and
we're going to prove this.
697
00:55:30,360 --> 00:55:31,110
How do we do that?
698
00:55:31,110 --> 00:55:33,860
So let me first write
out the theorem.
699
00:55:36,570 --> 00:55:53,290
The theorem is that every finite
poset has a topological sort.
700
00:55:53,290 --> 00:55:56,470
The basic idea is that
in order to prove this,
701
00:55:56,470 --> 00:56:00,070
it's that we're going to look at
a minimal element in the poset.
702
00:56:00,070 --> 00:56:03,370
For example, in the diagram,
we have four minimal elements.
703
00:56:03,370 --> 00:56:05,280
I will define what that means.
704
00:56:05,280 --> 00:56:08,480
The left sock and the right sock
and the underwear and the shirt
705
00:56:08,480 --> 00:56:11,360
are all at the top
of the Hesse diagram.
706
00:56:11,360 --> 00:56:13,720
Those are minimal elements.
707
00:56:13,720 --> 00:56:18,090
I just take one of them,
take it out of the poset
708
00:56:18,090 --> 00:56:20,320
that I'm looking at.
709
00:56:20,320 --> 00:56:23,550
I will get a smaller
poset and recursively, I'm
710
00:56:23,550 --> 00:56:26,890
going to construct
my total order.
711
00:56:26,890 --> 00:56:30,440
So it's a total order
on a smaller poset
712
00:56:30,440 --> 00:56:32,700
and then I add the
minimal element back to it
713
00:56:32,700 --> 00:56:35,490
and then I get a total
order for the whole thing.
714
00:56:35,490 --> 00:56:37,890
So essentially I'm
going to use induction
715
00:56:37,890 --> 00:56:42,770
and before I can do that, I'm
going to first talk about what
716
00:56:42,770 --> 00:56:45,810
it means to have
a minimal element
717
00:56:45,810 --> 00:56:47,630
because that's what we need.
718
00:56:47,630 --> 00:56:57,160
So x in A is called
minimal if it's not true
719
00:56:57,160 --> 00:57:03,810
that there exists a y in A,
which is different from x,
720
00:57:03,810 --> 00:57:11,610
but such that y
is smaller than x.
721
00:57:11,610 --> 00:57:18,380
So there exist no other y
in A that is smaller than x.
722
00:57:18,380 --> 00:57:20,560
Then if that's true, we
call x a minimal element.
723
00:57:20,560 --> 00:57:23,060
And in the same
way, of course, we
724
00:57:23,060 --> 00:57:26,165
can talk about a
maximal element.
725
00:57:29,720 --> 00:57:35,310
It's exactly the same,
but at the very end,
726
00:57:35,310 --> 00:57:40,060
we will have the reverse,
so x is related to y.
727
00:57:40,060 --> 00:57:43,260
Now, it turns out that not every
poset has a minimal element,
728
00:57:43,260 --> 00:57:44,440
actually.
729
00:57:44,440 --> 00:57:50,310
So as an example, we may
consider the integers,
730
00:57:50,310 --> 00:57:53,820
the negative and positive
numbers and then less than
731
00:57:53,820 --> 00:57:56,590
or equal to relation.
732
00:57:56,590 --> 00:57:58,430
There does not exist
a minimal element.
733
00:57:58,430 --> 00:58:00,960
You can always find
a smaller elements.
734
00:58:00,960 --> 00:58:04,030
So it's not really true
that every poset actually
735
00:58:04,030 --> 00:58:05,420
has a minimal element.
736
00:58:05,420 --> 00:58:08,360
It turns out though
that in a finite poset,
737
00:58:08,360 --> 00:58:10,500
we do have minimal
elements and then we
738
00:58:10,500 --> 00:58:15,020
can start doing the
proof by induction.
739
00:58:15,020 --> 00:58:19,860
So let's prove this, that
every finite poset has
740
00:58:19,860 --> 00:58:23,090
a minimal element.
741
00:58:23,090 --> 00:58:27,620
So let's do that up here.
742
00:58:27,620 --> 00:58:30,420
Actually, we do need
this theorem later on.
743
00:58:34,650 --> 00:58:38,070
So let's start out here.
744
00:58:38,070 --> 00:58:41,460
So the limit that
we want to prove
745
00:58:41,460 --> 00:58:55,910
is that every finite poset
has a minimal element.
746
00:58:55,910 --> 00:58:57,645
And in order to do
that, we're going
747
00:58:57,645 --> 00:59:01,760
to define what is
called a chain.
748
00:59:01,760 --> 00:59:05,976
And a chain is this
sequence of elements that
749
00:59:05,976 --> 00:59:07,100
are related to one another.
750
00:59:07,100 --> 00:59:18,160
It's a sequence of
distinct elements
751
00:59:18,160 --> 00:59:26,240
such that a1 is smaller
than a2, smaller than a3,
752
00:59:26,240 --> 00:59:29,470
and so on up to some at.
753
00:59:29,470 --> 00:59:32,500
And the length of a chain
we will denote by t.
754
00:59:32,500 --> 00:59:35,105
So this is going
to be the length.
755
00:59:38,980 --> 00:59:41,960
So now let's have a proof of
this lemma and with that lemma,
756
00:59:41,960 --> 00:59:44,410
we will then be able to prove
the theorem that we want
757
00:59:44,410 --> 00:59:46,960
to do on the topological sort.
758
00:59:54,590 --> 00:59:59,660
So let's see how we can do this.
759
00:59:59,660 --> 01:00:01,895
So what's the proof going to be?
760
01:00:04,440 --> 01:00:07,870
Well, you want to
construct a minimal element
761
01:00:07,870 --> 01:00:10,700
that we think would be minimal
and how are we going to do it?
762
01:00:10,700 --> 01:00:16,070
We're going to look at the
chain that has the largest
763
01:00:16,070 --> 01:00:18,070
length, the maximum length.
764
01:00:18,070 --> 01:00:34,600
So let a1 related to a2 and so
on to an be a maximum length
765
01:00:34,600 --> 01:00:36,090
chain.
766
01:00:36,090 --> 01:00:38,710
Now, I'm cheating
here a little bit
767
01:00:38,710 --> 01:00:42,890
because how do I know that
such a chain actually exists?
768
01:00:42,890 --> 01:00:45,770
Does there exist a
maximum length chain?
769
01:00:45,770 --> 01:00:48,520
So that you may want
to think about it.
770
01:00:48,520 --> 01:00:55,030
So it actually does exist and
if you think about it yourself,
771
01:00:55,030 --> 01:00:59,070
then you will
actually use the fact
772
01:00:59,070 --> 01:01:01,010
that we use a finite poset.
773
01:01:01,010 --> 01:01:02,985
If you have a finite
number of elements,
774
01:01:02,985 --> 01:01:05,300
well, the maximum
length chain can
775
01:01:05,300 --> 01:01:07,340
be at most the number of
elements in the poset,
776
01:01:07,340 --> 01:01:10,910
so you always have
a maximum number,
777
01:01:10,910 --> 01:01:12,370
but you can prove
it more formally
778
01:01:12,370 --> 01:01:14,730
by using the
well-ordering principle.
779
01:01:14,730 --> 01:01:19,550
But I will not do that here, so
we issue for now that this just
780
01:01:19,550 --> 01:01:23,110
exists, but you can prove it.
781
01:01:23,110 --> 01:01:24,620
So let's look at two cases.
782
01:01:27,119 --> 01:01:28,160
So what do we want to do?
783
01:01:28,160 --> 01:01:31,790
We want to show that a1 is
actually minimum element.
784
01:01:31,790 --> 01:01:35,130
So let us consider any
other element in the set
785
01:01:35,130 --> 01:01:37,080
and then we have two case.
786
01:01:37,080 --> 01:01:41,270
Either a is actually
not a part of a1,
787
01:01:41,270 --> 01:01:44,850
a2, all the way up to an.
788
01:01:44,850 --> 01:01:56,180
Well, in that case, if a is less
than a1, well, what goes wrong?
789
01:01:56,180 --> 01:01:58,146
I can put a up front here.
790
01:01:58,146 --> 01:02:00,020
It's a different element
from all the others.
791
01:02:00,020 --> 01:02:01,890
I get a longer chain.
792
01:02:01,890 --> 01:02:03,480
So that's not possible, right?
793
01:02:03,480 --> 01:02:10,560
So we'll get a longer chain
and that's a contradiction.
794
01:02:10,560 --> 01:02:12,060
So this assumption is not true.
795
01:02:12,060 --> 01:02:16,000
So it's not true that
a is less than a1.
796
01:02:20,030 --> 01:02:22,420
What's the other case?
797
01:02:22,420 --> 01:02:27,000
The other case is that a is
an element of one of those.
798
01:02:27,000 --> 01:02:35,000
So it's one of
those in the chain.
799
01:02:35,000 --> 01:02:37,930
Now, let's have a
look what happens if a
800
01:02:37,930 --> 01:02:40,870
is less than or equal to a1.
801
01:02:40,870 --> 01:02:41,620
But wait a minute.
802
01:02:41,620 --> 01:02:48,100
If a is one of these and a
is less than or equal to a1,
803
01:02:48,100 --> 01:02:50,433
then I will have a
cycle, a1 is less than
804
01:02:50,433 --> 01:02:54,120
or equal to a is less
than or equal to a1,
805
01:02:54,120 --> 01:02:56,380
but you just showed
in the theorem
806
01:02:56,380 --> 01:02:59,990
that there are no other
exit cycles in a poset,
807
01:02:59,990 --> 01:03:04,670
so this would imply
that we have a cycle.
808
01:03:04,670 --> 01:03:07,480
And according to the theorem up
there, we have a contradiction.
809
01:03:07,480 --> 01:03:14,080
So also in this case it's not
true that a is less than a1.
810
01:03:14,080 --> 01:03:17,150
Now this is the definition
of a minimal elements.
811
01:03:17,150 --> 01:03:18,910
So let's have a look
at this definition.
812
01:03:18,910 --> 01:03:26,880
We have proof now that for every
possibility every possible item
813
01:03:26,880 --> 01:03:34,670
or element in set
A, it's not true
814
01:03:34,670 --> 01:03:39,240
that that new element
is smaller than a1.
815
01:03:39,240 --> 01:03:42,520
So a1 is actually
a minimum element
816
01:03:42,520 --> 01:03:43,780
according to the definition.
817
01:03:43,780 --> 01:03:48,640
So a1 is minimal, that's
what we have shown.
818
01:03:48,640 --> 01:03:49,245
So great.
819
01:03:49,245 --> 01:03:52,555
We have shown that there
exists a minimum element,
820
01:03:52,555 --> 01:03:55,430
so this is the
end of this proof.