Composition of Relations and Partial Orders

Transcript

0:00Introduction

Hello everyone! Let's start with one small question. Every morning, you put on your socks, and then your shoes, right? In the evening, you undo it all. What comes off first? The shoes, yes! Then the socks. Socks off first, with the shoes still on? No way, that's impossible! So the order matters, and undoing goes in reverse order. Remember this silly little fact, because today it becomes a JEE formula. Our topic: composition of relations, and then partial orders. So, let's begin.

0:35Composition: two arrows in a row

So, take a relation R from A to B, and a relation S from B to C, okay? See the middle set B: R ends there, and S starts there. That is our bridge. Now the composition. We write S, a small circle, then R, and read it as S circle R, okay? It is the set of all pairs a comma c, such that a comma b is in R, and b comma c is in S, for some b in the middle set. Looks heavy? See, the picture is very simple. Look at the arrows. The element a goes to b by R, and then b goes to c by S, okay? Two arrows in a row. Then a comma c belongs to S circle R, and the middle stop, b, disappears. Now tell me. In S circle R, the letter S is written first. So S acts first, right? No, no, careful! This is the first trap. Look at the arrows again: R acts first, then S, okay? The one written on the right acts first. Clear?

1:32Does the order matter?

Alright, so does the order matter here, like socks and shoes? Yes! In general, S circle R is not equal to R circle S, okay? The slash through the equals sign means, not equal. You will see it in example one. Now, what is the inverse of S circle R? Many students write S inverse circle R inverse: same order, inverse on each. But think. To undo two steps, which one do you undo first? The last step, yes! The last step was S, so undo it first, then undo R, okay? First S inverse, then R inverse, and the first one goes on the right, remember? So, the inverse of S circle R equals R inverse, circle, S inverse. Order reversed! Exactly like socks and shoes: socks on, shoes on; shoes off, socks off. The very same idea. Remember this picture, and you will never write it the wrong way.

2:31The properties, written with composition

So, now take a relation R on a set A, okay? Each property fits in one line. First, reflexive. I A is the identity relation, all the pairs a comma a, one for each element. R is reflexive if and only if I A is a subset of R, okay? The double arrow means, if and only if. Second, symmetric if and only if R equals R inverse, okay? Every arrow has a return arrow, so turning the pairs around gives back the same set. Third, transitive, the best one. Think about R circle R: first R, then R again. Which pairs does it collect? Two-step paths, yes! The element a goes to b, then b goes to c, and that gives a comma c. Transitive means every two-step path can be short-cut, so a comma c must already be in R, right? So, R is transitive if and only if R circle R is a subset of R, okay? Nice and clean. Topper's trick: for a relation in roster form, find R circle R, and check that every pair sits inside R, okay? Even one pair outside, and it is not transitive.

3:42Partial orders

Now the last idea: partial orders. First, recall antisymmetric. If a comma b and b comma a are both in R, then a must equal b, okay? No two different elements are related both ways. Now, any relation that is reflexive, antisymmetric and transitive is called a partial order. Three properties, remember them together, got it? The standard examples: less than or equal to, on the real numbers, the double-lined R; subset of, on the power set, the curly P; and divides, on the natural numbers, the double-lined N, okay? Let's check subset of, quickly. Every set is a subset of itself: reflexive. If X is inside Y, and Y is inside Z, then X is inside Z: transitive. And the line on screen: if X is a subset of Y, and Y is a subset of X, then X equals Y: antisymmetric! So subset of is a partial order. Alright, one tricky question. Subset of is reflexive and transitive. So it is an equivalence relation too, right? Hmm, wait. For an equivalence relation, we also need symmetric. The empty set, the circle with a slash, is a subset of A, okay? But when A is not empty, A is not a subset of the empty set. So, not symmetric, and not an equivalence relation. See, symmetric and antisymmetric are different things. Don't mix them up!

5:12Example 1: find S o R and R o S

Now, example one. R is the set of pairs: one comma two, two comma three, three comma four. And S is: two comma five, three comma six, four comma five. Find S circle R, and R circle S, okay? Pause the video, and try it first. Done? Okay, let's check. First R, then S, okay? One goes to two by R, then two goes to five. Two goes to three, then three goes to six. Three goes to four, then four goes to five. So S circle R is: one comma five, two comma six, three comma five. Three pairs. Now R circle S, so first S, then R, okay? After S, where do we land? Only at five or six, yes! So R must now start from five or six. Is there any such pair in R? None! So R circle S is the empty set. Look, socks and shoes again: one order gives three pairs, the other gives nothing. Order matters!

6:16Example 2: R o R, R o R o R, and is R transitive

Now a slightly harder one, JEE style. On the set one, two, three, R is: one comma two, two comma three, three comma one. Find R circle R and R circle R circle R, and tell me, is R transitive? Pause the video, and try it. Done? Okay, let's check. R circle R means two steps of R, okay? One goes to two, then two goes to three. Two goes to three, then three goes to one. Three goes to one, then one goes to two. So R circle R is: one comma three, two comma one, three comma two. Now three steps. Start at one: two, then three, and back to one! Same for two, and for three. Every element comes back home. So R circle R circle R is one comma one, two comma two, three comma three: exactly I A, the identity relation. Beautiful, right? Now, is R transitive? Many students see that neat identity and say yes. Careful! Our test is about two steps: is R circle R inside R? Look at one comma three. It is in R circle R, but is it in R? No! R has one comma two, not one comma three. So R circle R is not a subset of R, and R is not transitive, okay? One pair outside is enough. Got it?

7:40Quick revision: order of composition and partial orders

So, quick revision. S circle R means first R, then S, and the order matters. The inverse reverses the order, like socks and shoes. Transitive means R circle R sits inside R, and a partial order is reflexive, antisymmetric and transitive. Now go and try the practice problems on this page. Two arrows in a row, that's all. All the best!