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?