Equivalence Relations

Transcript

0:00Introduction

Hello everyone! So, let's start with a proof. One student once told me: why do we check three properties for an equivalence relation? Two are enough! Look. If a is related to b, then by symmetry, b is related to a. Now use transitivity: a related to b, and b related to a, so a is related to a. Reflexive, for free! So symmetric and transitive together give reflexive. Is this proof correct? Hmm. By the end of this video, you will catch the mistake yourself. And trust me, JEE asks this topic again and again. So, let's begin.

0:40Equivalence relation: all three properties

So, first the definition. Take a relation R on a set A, okay? Number one, reflexive. Every element is related to itself, so every pair a comma a belongs to R, okay? This curved symbol on screen means belongs to. Think of R as arrows between elements: then every element has a loop on itself. Clear? Number two, symmetric. If a is related to b, then b must be related to a. The arrow on screen means implies. Every arrow has a return arrow, like a mirror image, right? Number three, transitive. If a is related to b, and b is related to c, then a must be related to c. So every two step path has a short cut, okay? Now, a relation that has all three, reflexive, symmetric and transitive, is called an equivalence relation. We often write it with this little wave sign, the tilde, and read it as: a is equivalent to b. All three, okay? Not two out of three. Remember that student's proof? Wait for it.

1:39The real meaning: the same, in some respect

Alright, now the real meaning. An equivalence relation always says one thing: is the same as, in some respect. Same remainder. Same city. Same slope. Same value of some quantity. Now think about the simplest relation of all: equals. Is equals reflexive? Symmetric? Transitive? Yes, all three! Every number equals itself, equals works both ways, and equals passes along a chain. So here is the topper's trick, the phi trick. Phi is just this Greek letter on screen: a rule that gives every element a value. Suppose you can rewrite the relation as: a is related to b exactly when phi of a equals phi of b. This double arrow means if and only if: each side gives the other. Then R is automatically an equivalence relation, because equals is reflexive, symmetric and transitive. No need to check three properties one by one. That's it, one line! For example, a is related to b when a minus b is divisible by five. What is this relation really saying? Yes, same remainder on division by five! On screen, this vertical bar means divides: five divides a minus b. So phi is the remainder, and R is an equivalence relation. Done in seconds. But careful, here is a trap. Sometimes a relation becomes phi of a equals minus phi of b. Looks almost the same, right? No, no! That minus sign changes everything. Such a relation is symmetric, reflexive only where phi is zero, and usually not transitive.

3:18JEE trap: the famous wrong proof

Now, back to that proof from the start. The claim: if a relation is symmetric and transitive, then it is reflexive. The argument: if a is related to b, symmetry gives b related to a. Then transitivity gives a related to a. Every step looks correct, doesn't it? So where is the mistake? Look carefully: the proof begins with the word if. The proof needs some b with a related to b. But what if a is related to nothing at all? Then the argument never even starts! Got it? Tiny example: on the set one, two, let R be just the pair one comma one. Two is related to nothing, not even to itself. Symmetric? Yes, the only pair is a loop. Transitive? Yes, a loop never causes trouble. But two comma two is missing, so it is not reflexive. All because of that one little word, if! One more: on the integers, written with this double-struck Z, a is related to b when a times b is greater than zero. That just means a and b are non-zero with the same sign, so it is symmetric and transitive. But zero is related to nothing, not even to itself. So the proof fails again, and the relation is not reflexive.

4:34Combining equivalence relations

Now, let R and S both be equivalence relations on the same set. First, R inverse, with every pair reversed. It is R itself, because R is symmetric: every pair already has its mirror. So, again an equivalence relation. With me? Next, R intersection S, the pairs common to both. Is it also an equivalence relation? Yes, it is! Every loop is in R and in S, so it is in the intersection. Mirrors and short cuts: same story. So the intersection keeps all three properties. But look, the union is different. Loops and mirrors survive, so R union S is reflexive and symmetric. But it need not be transitive, because a short cut may need one pair from R and the next pair from S, okay? Careful, students fall for this in JEE! Take the set one, two, three. R is the identity relation, plus one comma two and two comma one. S is the identity relation, plus two comma three and three comma two. Now one comma two and two comma three are both in the union. But one comma three is in neither of them. So the union is not transitive. Just one counterexample is enough.

5:45Example 1: show a five-pair relation is an equivalence

Alright, Example one. On the set one, two, three, the relation R has five pairs: one comma one, two comma two, three comma three, one comma two, and two comma one. Show that R is an equivalence relation. Pause the video, and try it first. Done? Okay, let's check. Reflexive first: tick off the loops. All three loops are present, so it is reflexive. Clear? Symmetric: the only pairs that are not loops are one comma two and two comma one, mirrors of each other. So, symmetric. Now transitive. This is where students slip. Both one comma two and two comma one are present. So what does transitivity secretly demand? Yes, look at the two step paths, shown with arrows on screen. The path one, two, one needs one comma one. And the path two, one, two needs two comma two. Both loops are present, so it is transitive. Reflexive, symmetric, transitive: all three. So R is an equivalence relation. Really simple!

6:52Example 2: difference a multiple of 4, class of 1, n(R)

Now a harder one, JEE style. The set A has the whole numbers from zero to twelve. And a is related to b when the absolute value of a minus b is a multiple of four. Three questions. Is R an equivalence relation? Which elements are related to one? And how many pairs are in R? Pause and try. Hint: use the phi trick. Done? Okay, let's check. When is the difference a multiple of four? Exactly when a and b leave the same remainder on division by four! Twelve and zero, both remainder zero, difference twelve. Got it? Same remainder: that is the phi trick, with phi as the remainder. So R is an equivalence relation, in one line. That's it! Now, the elements related to one. One leaves remainder one on division by four. Who else from zero to twelve leaves remainder one? Five and nine, exactly! So the set is one, five, nine. And one itself is in it, because R is reflexive, right? Now, the number of pairs. Split the set into groups by remainder. Remainder zero: zero, four, eight, twelve, that is four elements. Then one, five, nine; two, six, ten; and three, seven, eleven: three elements each. Inside a group, everyone is related to everyone, including themselves. So how many ordered pairs come from the group of four? Four times four, sixteen! Not six, not twelve. Every ordered pair counts, loops included. So n of R is four squared, plus three squared, plus three squared, plus three squared. Sixteen plus nine plus nine plus nine: forty three. See how the phi trick made everything easy?

8:44Quick revision: three properties and the same-value trick

So, quick revision. An equivalence relation is reflexive, symmetric and transitive. If a is related to b exactly when phi of a equals phi of b, it is an equivalence relation, automatically. And symmetric plus transitive does not give reflexive, because an element related to nothing breaks the proof. So always check all three. Now go and try the practice problems on this page. All the best!