Subtitles section Play video Print subtitles 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.