Placeholder Image

Subtitles section Play video

  • 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.

The following content is provided under a Creative

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it