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.