 ## Subtitles section Play video

• The following content is provided under a Creative

• Your support will help MIT OpenCourseWare

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

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

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

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