## 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?