初級 440 タグ追加 保存
動画の字幕をクリックしてすぐ単語の意味を調べられます!
単語帳読み込み中…
字幕の修正報告
The following content is provided under a Creative
Commons license.
Your support will help MIT OpenCourseWare
continue to offer high quality educational resources for free.
To make a donation or view additional materials
from hundreds of MIT courses, visit MIT OpenCourseWare
at ocw.mit.edu.
MARTEN VAN DIJK: So today we're going to talk about relations.
We're going to talk about partial orders.
Wow this is loud.
Could you put it a bit softer?
So we're going to talk about relations,
partial orders, and then parallel task scheduling.
So well, we'll start out with a few definitions as usual
and examples will explain what you're talking about here.
So what about relations?
Well, relations are very simple definition.
A relation from a set A to a set B
is really a subset of the cross product of the two.
So let me give an example.
It's a subset R that has its elements in a cross product
of A and B, which really means that it has pairs where
the first element is drawn from A
and the second element is from B.
So for example, if you're thinking about the classes
that you're taking as say, set B and all the students
set A, well, then you can describe
this is as a relationship where we have tuples
a, b where a student a is taking class b.
So a relation is really just a set of pairs.
The first part of the pair is in set A, the second one in B.
Now, we will use different notation
for indicating that a pair is in this subset,
so we'll be talking about further properties,
then it will become more clear, but we will also write
that a is to relate this to b.
So instead of the pair a, b is an element of R,
you may write a R b, or we say a and then
we use this symbol with a subscript R b.
So we use the relational symbol in between a
and b in these two cases.
And the reason for that becomes clear
if you start talking about the properties,
but let me first give a few more examples
and talk about the types of relations
that you're really interested in.
We really are interested in a relation on a set A,
and this is really a subset R that
is a cross product of A with itself.
So essentially, A is equal to B in the definition
right up here.
Now, examples that we have for this one is,
for example, we may have A to B, all in the integers,
positive and negative, and then we can say, for example, x
is related to y if and only if x is,
for example, congruent to y modulo 5.
This would be a proper relation.
We have not yet talked about special properties.
We will come to that.
Other examples are, well, we could
take all the positive integers, 0, 1, and so on
and so forth, and then right so x
is related to y if and only if, for example, you
could say that x defines y.
That's another relationship that we could use.
Notice, by the way that in the correct [INAUDIBLE]
that I put here, I already used sort of relational symbols
right in the middle between x and y over here.
So that's already indicating why we are using
a notation that I put up here.
So another example is, for example,
we have that x is related to y if and only if x is at most y.
This is also a relation.
So now what are the special property that we
are interested in and those that will make relations
special and then we can talk about-- actually,
I forgot one item that we will talk
about as well, which are equivalents
classes, equivalence relations.
So we will see when we talk about the properties
right now that we will be defining
very special types of relations and we
will talk about these two, equivalents relations
and partial orders.
So what are the properties?
Actually before we go into those properties,
let us just first describe what the relationship, how we can
describe it in a different way.
Actually relation is nothing more than a directed graph,
like R over here is a subset of a cross product with a.
So that's pairs and you can think of those as being edges.
So let us write it down as well.
So set A together with R is a directed graph.
And the idea is very simple.
The directed graph has vertices V and edge set
E where we take V to be equal to A and the edge set equal to R.
So for example, we could create a small little graph,
for example, for three persons, Julie and Bill
and another one, Rob.
And suppose that the directed edges
indicate whether one person likes the other.
So for example Julie likes Bill and Bill likes himself,
but likes no one else.
Julie also likes Rob, but does not like herself
and Rob really likes Julie, but does not like himself.
So for example, you could create a graph
where all the directed edge really represent the relations
that you have described by R.
So we will use this later on and the special properties
that we are interested in are the following.
So the properties are that relations can be reflexive.
So a relation R on A is reflexive
if x is related to itself for all x, so for all x in A. Well,
for example, in this particular graph, that is not the case.
If Julie and Rob would also like themselves,
then the relationship up here would actually be reflexive.
We have symmetry, so we call a relationship symmetric
if x likes y, then that should imply that y also likes x
and it should, of course, hold for all x and y.
We have a property that we call antisymmetric,
which is the opposite of this.
Antisymmetric means that if x likes y and y likes x, then x
and y must be the same.
So this really means that it's not
really possible to like someone else
and that someone else also likes x,
because according to the antisymmetrical property,
that would then imply that x is actually equal to y.
So these two definitions are opposite from one another.
And the final one that we're interested in is transitivity.
So the relationship is transitive if x likes y and y
likes z, then x also likes z.
So let's have a look at these few examples
and see whether we can figure out what kind of properties
they have.
So let's make a table and let's first
consider that x is congruent to y
modulo 5 and next divisibility and the other one is less than
or equal to.
So are they reflexive is the first question
and they we want to know whether they're
symmetric and antisymmetric and transitive.
So what about this one over here?
So can you help me figure out whether they're
reflexive and symmetric or antisymmetric and transitive?
What kind of properties does this one have?
So when we look at x is congruent to y modulo 5,
it really means that the difference between x and y
is divisible by 5.
So is it reflexive?
Is x congruent to x modulo 5?
It is right.
That's easy.
So we have yes.
Now, if x is congruent to y module 5,
is y also congruent to x modulo 5?
It is because the difference between x and y
is divisible by 5 and stays the same.
So y is congruent to x as well.
So it is symmetric.
Now what about the antisymmetric?
If x is congruent to y modulo 5 and y is
congruent to x modulo 5, does that mean that x is equal to y?
It's not really true, right?
You can give a counterexample for that.
So for example, we could have that 7 is congruent to 2 modulo
5 and 2 is congruent to 7 modulo 5, but they're not the same.
So this is not true.
No.
What about transitivity?
Is this true?
So let's consider this example as well.
So if I have that 2 and 7 are congruent to one another modulo
5, well, 7 is also, for example, congruent to 12 modulo 5.
Does it mean that 2 and 12 are congruent to one another?
So we have 2 is congruent to 7 modulo 5.
We have, say 7 is congruent to 12 modulo 5.
Well, we can look at the difference between 2
and 12, which is 10, is also divisible by 5.
So actually this does imply that 2 is congruent to 12 modulo 5.
Now, this is, of course, not a proof
because this is just by example, but you
can check for yourself that this relationship is actually
transitive.
Now, what about divisibility.
Maybe you can help me with this one.
So is it reflexive?
Is this right?
I hear yes.
That's correct because if x and y equal to one another,
well, it's 1 times x, so x divides x, so that's true.
Is it symmetric?
So if x divides y and y divides x, so let's just see.
We are over here.
So if x divides y, does that imply that y divides x?
That's the relation that we want to check.
Is that true?
Not really.
We can have like say 3 divides 9, but 9 does not divide 3,
so this is not true, but antisymmetry.
So if x defies y and also y divides x,
then they must be equal to one another.
So we can see that this actually is antisymmetric,
so that's interesting.
And transitivity, well, we have, again, transitivity
because if x divides y and y divides z, then x also
divides z.
For example, if 2 divides, say 4 and 4 divides 20,
then 2 also divides 20.
Now this one over here has actually the same properties
as divisibility.
It's reflexive because x is at least equal to itself.
It's not symmetric because if x is at most y,
does not really imply that y is at most x,
so this particular relation does not hold, in general,
but it is, again, antisymmetric because if I
have this inequality and the other one, well,
x and y must be equal to one another in that case
and transitive as well.
Now, it turns out that in these examples,
we have seen a certain combination of properties
that we will be talking about.
The kind of combination that we see here
will lead to a definition of equivalence classes,
equivalence relations, and this is also a very usual pattern,
and this we will define as partial orders.
So this is what we are going to talk about next.
So we'll first start with equivalence relations,
so let's do this.
What is an equivalence relation?
An equivalence relation is exactly
a relation that has those few properties over there.
So there's reflexive, symmetric, and transitive.
So an equivalence relation is reflexive and also symmetric
and also transitive.
So we've already seen some examples
up there or one example, but a very trivial relation, maybe
you can think of one that is really straightforward.
What will be an equivalence relation
if you think about how we write mathematical formulas down?
We usually like the equality sign also.
So just equality the equal sign itself is actually
one example and the other example
is the one that we have there and that's, of course,
more general.
We can have x is congruent to y modulo n.
So for fixed n, we have another equivalence relation.
So now given those, we can start defining equivalence classes.
So what is an equivalence class?
That's actually everything within that class
is related to itself.
So the equivalence class of an element, x in a
is equal to the set of all the elements in a that
are related to x by our relation R.
So we denote this equivalence class.
So this is denoted by x with brackets around it.
So let's put it into a formula and give some examples.
So the formula for this in mathematics
would be the set of all the y such that x is related to y.
So as an example, we can do the one that we started off with.
So let's again look at x is congruent to y modulo 5
and look at the equivalence classes.
So one of them, for example, we could look
at the equivalence class of 7.
We were looking at this one already.
Well, what are all the y's that are actually
congruence to 7 modulo 5?
Well, there are a whole bunch.
We have minus 3 and we have 2, 7,
we have 12, 17, and 22, and so on.
And we add 5 to all these and this is the equivalence class
that belongs to 7.
Now notice that the equivalence class of 7
is actually equal to the equivalence class of 12.
It's the same set.
Everything that is congruent to 12 modulo 5
is also congruent to 7 module 5 and this is, again, equal
to say, 17, and so on.
So now we can start talking about a nice property
that equivalence classes have, which
is that the equivalence classes together partition the set A.
So I will need to define first what a partition is.
And it's defined as follows.
A partition of A is a collection of this joint non-empty sets A1
up to An and they're all subsets of A.
And the union of all of those is actually
equal to the set A. So who's union is A.
So let's have a look, again, at this example
and see whether we can figure out what
the equivalence classes are.
So the example is, well, we can have everything
that this actually a multiple of 5.
That's this one class.
So we have minus 5, 0, 5, 10, and we go all the way up.
Another equivalence class is, well,
we just add 1 to each of those elements here, so if minus 4
is congruent to 1, modulo 5 is congruent to 6,
modulo 5 congruent to 11, and so on.
And so we can continue and we actually see that we minus 3
is congruent to 2, to 7, to 12, and so on.
That's the one we had up there.
Another one is minus 2, 3, 8, 13,
and we have minus 1, 4, 9, 14, and so forth.
So these are all the equivalence classes
because now we look around.
If we add one more 2 minus 1, we get 0.
So we get 0, 5, 15, and so on and that's exactly
the same class as this one.
So we see that for this particular example,
we notice that these equivalence classes are a partition of all
the integers.
Turns out that this is a general property
and we're not going to prove this.
That's pretty straightforward, so you should actually
think about it yourself.
Let's keep this up here and take this out.
So the theorem is that every equivalence relation on a set A
can be partitioned in its questions classes.
So the theorem is the equivalence class
of an equivalence relation on a set A form a partition of A.
Now, I'm not going to prove this.
It's actually really straightforward.
You should really look at this and see that you can prove this
with the properties, the property
definitions, and the definition of an equivalence relation.
So this is as far as we go is equivalence relations.
And so now we will continue with partial orders.
Again, we go through a few definitions
and then at some point, we'll be able to prove
a few interesting properties.
So let's talk about partial orders.
So notice that we have shifted now from in this diagram
over here, in this table, from this pattern that you
were first interested in.
Now, we go to partial orders and the difference
is going to be that we do not have symmetry,
but we do have antisymmetry and that brings out
a whole different structure.
So a relation is-- it's in brackets I put here-- weak,
I'll explain in a moment why I do this.
It's a weak partial order if it is
reflexive, and antisymmetric and transitive.
So why do I put weak up here?
Well, if you look in the book, there are two definitions,
one is a weak partial order, which is with reflexivity
and another one is a strong partial order.
And that one has a property that I did not
talk about here called irreflexibility
and it's something that I will not talk about in this lecture,
but you should read about it and all these properties,
all the theorems that we talk about right now also hold
for the strong version of a partial order.
But for now, let's just call partial orders
those that are reflexive, antisymmetric, and transitive.
Well, we already saw a few examples up here.
We have divisibility, which has this property and also the less
than or equal relationship.
Now usually what we do is, instead
of using a capital letter R, we will use a relation symbol.
So a partial order relation is denoted differently,
is denoted with something like that instead of R. Now
the reason for that is because we have actually
will show that there's a partial order,
so this name does not come by itself.
It turns out that we can give an order to the order ranking
to the elements, one element is less than another and so on.
So let's keep this over here and change up here.
So an example that we will talk about in the moment, but first
let me introduce some more notations.
So we call the pair A with this relationship symbol
is actually called a partially ordered set.
And we also abbreviate this by calling it a poset.
Now, in a poset, again, can be described
by means of a directed graph, so we can do that as well.
So poset is a directed graph such
that it has the vertex set A and the edge set
is defined by the relationship.
So the edge set is actually this thing.
Notice that in our definition, this is actually a set, right?
It's still a set.
It's a set of tuples, of pairs, and we can, again,
create a directed graph by using this, so nothing has changed.
But for posets, we can actually create a more sort of easier
to read sort of representation, which we'll
call a Hesse diagram, which is also a graph
and let me give an example to explain how that works.
So I think we can take this out.
So the example is, imagine that a guy is going to dress up
for something very formal.
So how does he start out?
So let's have as vertices in the graph, in this diagram
or the elements of A is going to be all items that he will start
to put on and start wearing, so his pants, his shirt,
and so on.
So let's have a look.
So what do you start off with?
Well, maybe your underwear would be a good idea.
So this could be a first item that you want to put on.
So let's have the relation that we are interested in to be one
where we say, well, I first need to put on my underwear
and only after that I can put on my pants, for example.
So that makes sense too.
And since I'm doing something very formal later on,
I better first put on my shirt because I
like to tuck that into my pants, but it's not
really necessary to first put on my underwear
or first put on my shirt.
I can do either of the two.
So we're getting sort of the I don't care so much.
I want to put on a tie, put on a jacket as well,
and after the pants, I need to put on my belt,
but I like to finish all that before I put on my jacket.
And I also have my right sock that I like to put on
and I need to do this first before I put on my right shoe.
That makes sense.
And I definitely like to finish putting on my pants
before I put on my shoes.
So let's have a preference relationship over here as well.
But I do not really care, actually.
I can put on my socks first and then my underwear
and then my shirt.
I don't mind so much.
I also have my left sock and my left shoe.
And again, I like this to be preceded
by putting on my pants.
So this could be a relation, a sort of a description
of a partial order.
Well, because it's a Hesse diagram,
so let's talk about it a little bit
and then I will define what the official definition of this is.
So let's first look at this.
So this is a partial order.
It means [? a ?] percent of partial order,
so it's reflexive.
The pants are related to themselves, so I put them on.
Before I put on the pants, I need to put on the underwear,
but if I need to put on my belt after I put on my underwear,
then also I notice I first need to put on my underwear
before I put on my belt.
So you have transitivity in this example.
It's also the other property is that it is antisymmetric.
It's not true that I can first put on my right shoe and then
my right sock, so we only have one direction over here.
Now, I did not put in all the edges
that are possible for this partial order
because if I really want to continue this,
if I really want to create the complete directed graph that I
talked about over here-- I think it talks about it somewhere--
over here, I can create a directed graph that
has its vertex set A, which are all the items that I want
to put on.
And in that set that has all the different relationships.
Now, this is only an abbreviated form.
This is a Hesse diagram, but if I
would look at a directed graph, then I
would need to look at the closure of this whole thing.
That's how I would call it.
And I know that, for example, this underwear,
by transitivity, is also less than
or equal than or related to the belt.
So in a full graph, I would have another edge over here.
And in a same way, I would have an edge from here to here.
I would have an edge over here by transitivity.
Also I can see that the shirt goes before the pants,
before the right shoe, so the shirt
is also related all the way to the right shoe
and similarly to the left shoe.
I also have that I have self loops in here,
like a tie is related to itself, a jacket as well, and so forth.
So I can put in all these extra edges and as you can see,
this will be quite a mess, so the Hesse diagram
is a much nicer, official interpretation
of what's going on.
So let's define what this really is and then we'll
continue with some nice properties of this structure.
So what is a Hesse diagram?
A Hesse diagram is really one in which I
use the set A as the vertices.
So it is a directed graph-- a different one than the one
that we talked about it up there.
So it's a directed graph in which we have the vertex set A,
but the edge set is a little bit different.
So it is the edge set that corresponds to this,
but they subtract a whole bunch.
First of all, we remove all the self loops that we have,
so minus all the self loops and we also
take out all the edges that are implied by transitivity.
So that's a definition of a Hesse diagram.
Now, when we look at the Hesse diagram over here,
so let me take out these nodes again or these edges.
So looking at this Hesse diagram,
you really see a nice structure in there.
It seems like we can talk about smallest elements like a shirt,
just like a small element.
It's sort of less than or equal to
if you think about this as being the 3%, then
the tie and the jacket and the pants and the right shoe
and so on.
So you can see a clear order in this particular graph.
So let's have a look at this.
When I look at this graph, I also do not see any cycles.
I do not see that the shirt is less than
or equal to the pants.
It's related to the right shoe and then it's related to itself
again, so I do not see any cycles.
And this turns out to be general property of posets
and that's what we are going to prove next.
So let's do that over here.
So you see that there are no cycles
and it's a general property.
So the theorem is that a poset has no directed cycles
other than self loops.
Now, notice that this property is really necessary
to have a proper representation by using a Hesse diagram
because otherwise, if you have a big, directed cycle, then only
one of those edges would be part of the Hesse diagram
and all the others are implied by transitivity sort of.
And that is getting a little bit messy
because then we do not really have a unique representation.
But luckily, there are no directed cycles.
So how do we prove this?
Well, let's do this by contradiction
and see what happens.
So suppose the contrary.
So suppose that actually there exists at least two,
an integer, at least two, so at least n distinct elements,
a1 all the way up to an that form
a cycle, so such that you have a directed cycle.
So we would put it in formula like this.
a1 is related to a2 to a3 and so on all the way up to an minus 1
an.
And we have a cycle, so this goes back to a1.
So why would this be a contradiction?
So maybe you can help me out here.
So what can I already derive from those properties
that I have over here?
So I know that the partial order is antisymmetric,
it is transitive, it's reflexive.
So how can I get to a contradiction here?
So let's think about it a little bit.
Is it possible, for example, that we could violate
the antisymmetry of the poset?
So can we find maybe two distinct elements such that
say x is related to y and y is related to x,
but it's not true that x is equal to y.
For example, if you have very small cycle,
say a1 is related to an and then related to a1, again,
well, then I would have that a1 is related
to an and an is related to a1.
We should have that an is then equal to a1 but, that's
not true because the issue of distinct elements over here.
So that seems to be an interesting idea.
So maybe we can prove something of that type.
So can we actually show that a1 is related to an?
We can write what kind of a property of a poset
do we use here to make that happen?
I heard something vaguely, a mumble.
Yeah, the transitive property.
So how do we do it?
Well, we take those three together
and we conclude that a1 is also related to a3.
We have a4 over here, so together with this one,
so a1 is related to a3 and a3 is related to a4.
We have that a1 is related to a4 and you can use induction
if you want to be very precise here,
which you should, actually, but I will not do this.
So you will use induction and go all the way to the fact
that a1 is actually related to an.
But wait a minute.
We also have this particular property
and a1 is not equal to an by our assumption.
So we get a contradiction, which means that what
we had over here is not true.
So actually, for all n, at least two,
n distinct elements a1 up to an that--
well, we have the negative of this, so there is no cycle.
So this is a great property, so now we
start to see why a poset is actually called
a partial ordered, right?
Because there's no directed cycles
other than the self loops, so we sort of
have a ranking to the elements.
We can say that really one element
is ranked less than another.
So this one is ranked less than this,
it's ranked less than that, and it cannot circle back again
and say that this one is ranked less than this because they
don't have cycles, so that makes a really consistent story.
Notice that this was different when we talked about tournament
grass, for example.
That was a very different structure
and we could not think of a winner in there.
But in this case, we have a ranking.
And this leads us to a more general discussion.
But before we go into that, I'd like to write down
a conclusion of this theorem.
So after deleting the self loops from a poset,
we actually get a directed acyclic graph.
And that's what we defined last week as well.
So a directed acyclic graph and we abbreviate this
as D-A-G, a DAG.
So that's a very special property for the poset.
Now a partial order has elements that cannot be compared,
for example.
Like in this case, these two have absolutely no relationship
with one another.
Even through transitivity, I cannot conclude that either
the right sock is related to the underwear or the underwear
related to the right sock.
And that makes it a partial order.
It's possible that you have elements, pairs of elements,
that are incomparable.
So let me write this down.
So what we really want to though,
is that we have some kind of consistent ranking
that we can create for a partial ordered set.
But for now, we know that certain pairs cannot be
compared to one another and we would like to achieve something
like this.
So that's why we start to talk about what it means
if a and b are incomparable and this
is, if neither a is related to b nor b is related to a.
And we say that a and b are comparable well,
if a is related to b or b is related to a.
Now we can have a very special order
which we call total order.
In a total order, it's actually partial order, but all
the elements and comparable.
So it's a partial order in which every pair of elements
is comparable.
Now, maybe you can think about the Hesse
diagram of a total order.
What would it look like if we have
that all the elements are actually comparable?
Do you have any idea what kind of a graph would that be?
So in this case, we had the partial order because we see
that certain items cannot be compared,
but what happens if you have a total order?
For example-- yeah.
Do you have a--
AUDIENCE: It would be a straight line.
MARTEN VAN DIJK: Yeah.
That's correct.
It will be straight line.
And it will look something like this and it keeps on going
and over here also, keeps on going like this.
So it's a straight line.
If it's a finite set, we have a finite line, so just
a finite number of vertices, but otherwise, it's
just an infinite line or a half or semi infinite line.
So why is that?
with every two elements, it can be compared to one another,
so you can rank them essentially along this line.
So if you think about the integers and the less
than or equal to relation, well, we
see that one is less than or equal to 2
and 2 is less than or equal to 3 and so on.
So they all are put in Hesse diagram as a straight line.
So that's is very special order.
We have a ranking with the total order
through this straight line.
It will be great if you can also rank the elements
in a partial order and that's what
we're going to talk about next.
We're going to talk about the topological sort of a poset.
And what it really means is that we're going to extend,
essentially the partial order toward a total order.
And by doing that, we will manage
to put a ranking to all the items.
Let me define what's happening here.
So this is about equivalence classes and you remember this.
So what is a topological sort?
So the idea is that if the total order
is consistent with a partial order,
then it is called a topological sort.
So let me redefine it again more formally.
So what is it?
A topological sort of a poset is formally
defined as a total order.
It's a total order that has the same set of items of elements A
but has a different relation that we
will denote by a subscript, t.
And this is such that well, the original relation
is contained in the new one.
Notice that these also denote sets,
so that's why I can write it like this.
So this set that is defined by this relation
is a subset of this relation.
So it simply means that if x is related to y,
then it also implies that x is related
to y in the total order.
So we're interested in figuring out
where we can find such a topological sort.
Is it always possible to do so?
Now it turns out that every finite poset actually
has a topological sort and we're going to prove this.
How do we do that?
So let me first write out the theorem.
The theorem is that every finite poset has a topological sort.
The basic idea is that in order to prove this,
it's that we're going to look at a minimal element in the poset.
For example, in the diagram, we have four minimal elements.
I will define what that means.
The left sock and the right sock and the underwear and the shirt
are all at the top of the Hesse diagram.
Those are minimal elements.
I just take one of them, take it out of the poset
that I'm looking at.
I will get a smaller poset and recursively, I'm
going to construct my total order.
So it's a total order on a smaller poset
and then I add the minimal element back to it
and then I get a total order for the whole thing.
So essentially I'm going to use induction
and before I can do that, I'm going to first talk about what
it means to have a minimal element
because that's what we need.
So x in A is called minimal if it's not true
that there exists a y in A, which is different from x,
but such that y is smaller than x.
So there exist no other y in A that is smaller than x.
Then if that's true, we call x a minimal element.
And in the same way, of course, we
can talk about a maximal element.
It's exactly the same, but at the very end,
we will have the reverse, so x is related to y.
Now, it turns out that not every poset has a minimal element,
actually.
So as an example, we may consider the integers,
the negative and positive numbers and then less than
or equal to relation.
There does not exist a minimal element.
You can always find a smaller elements.
So it's not really true that every poset actually
has a minimal element.
It turns out though that in a finite poset,
we do have minimal elements and then we
can start doing the proof by induction.
So let's prove this, that every finite poset has
a minimal element.
So let's do that up here.
Actually, we do need this theorem later on.
So let's start out here.
So the limit that we want to prove
is that every finite poset has a minimal element.
And in order to do that, we're going
to define what is called a chain.
And a chain is this sequence of elements that
are related to one another.
It's a sequence of distinct elements
such that a1 is smaller than a2, smaller than a3,
and so on up to some at.
And the length of a chain we will denote by t.
So this is going to be the length.
So now let's have a proof of this lemma and with that lemma,
we will then be able to prove the theorem that we want
to do on the topological sort.
So let's see how we can do this.
So what's the proof going to be?
Well, you want to construct a minimal element
that we think would be minimal and how are we going to do it?
We're going to look at the chain that has the largest
length, the maximum length.
So let a1 related to a2 and so on to an be a maximum length
chain.
Now, I'm cheating here a little bit
because how do I know that such a chain actually exists?
Does there exist a maximum length chain?
So that you may want to think about it.
So it actually does exist and if you think about it yourself,
then you will actually use the fact
that we use a finite poset.
If you have a finite number of elements,
well, the maximum length chain can
be at most the number of elements in the poset,
so you always have a maximum number,
but you can prove it more formally
by using the well-ordering principle.
But I will not do that here, so we issue for now that this just
exists, but you can prove it.
So let's look at two cases.
So what do we want to do?
We want to show that a1 is actually minimum element.
So let us consider any other element in the set
and then we have two case.
Either a is actually not a part of a1,
a2, all the way up to an.
Well, in that case, if a is less than a1, well, what goes wrong?
I can put a up front here.
It's a different element from all the others.
I get a longer chain.
So that's not possible, right?
So we'll get a longer chain and that's a contradiction.
So this assumption is not true.
So it's not true that a is less than a1.
What's the other case?
The other case is that a is an element of one of those.
So it's one of those in the chain.
Now, let's have a look what happens if a
is less than or equal to a1.
But wait a minute.
If a is one of these and a is less than or equal to a1,
then I will have a cycle, a1 is less than
or equal to a is less than or equal to a1,
but you just showed in the theorem
that there are no other exit cycles in a poset,
so this would imply that we have a cycle.
And according to the theorem up there, we have a contradiction.
So also in this case it's not true that a is less than a1.
Now this is the definition of a minimal elements.
So let's have a look at this definition.
We have proof now that for every possibility every possible item
or element in set A, it's not true
that that new element is smaller than a1.
So a1 is actually a minimum element
according to the definition.
So a1 is minimal, that's what we have shown.
So great.
We have shown that there exists a minimum element,
so this is the end of this proof.
コツ:単語をクリックしてすぐ意味を調べられます!

読み込み中…

麻省理工學院 離散數學 (Lec 11 | MIT 6.042J Mathematics for Computer Science, Fall 2010)

440 タグ追加 保存
Dou Lin 2016 年 8 月 24 日 に公開
お勧め動画

コメント

読み込み中…
  1. 1. クリック一つで単語を検索

    右側のスプリクトの単語をクリックするだけで即座に意味が検索できます。

  2. 2. リピート機能

    クリックするだけで同じフレーズを何回もリピート可能!

  3. 3. ショートカット

    キーボードショートカットを使うことによって勉強の効率を上げることが出来ます。

  4. 4. 字幕の表示/非表示

    日・英のボタンをクリックすることで自由に字幕のオンオフを切り替えられます。

  5. 5. 動画をブログ等でシェア

    コードを貼り付けてVoiceTubeの動画再生プレーヤーをブログ等でシェアすることが出来ます!

  6. 6. 全画面再生

    左側の矢印をクリックすることで全画面で再生できるようになります。

  1. クイズ付き動画

    リスニングクイズに挑戦!

  1. クリックしてメモを表示

  1. UrbanDictionary 俚語字典整合查詢。一般字典查詢不到你滿意的解譯,不妨使用「俚語字典」,或許會讓你有滿意的答案喔