Part B: Relations

Transcript

0:00Introduction

Hello everyone! Okay, one question before we start. Take the small set one, two, three. How many different relations can you make on it? Five hundred and twelve! Five hundred and twelve, on just three elements. Now, how many of them are neither reflexive nor symmetric? Careful, it looks like ten seconds of work, but there is a trap hidden inside. This is our unit problem bank on relations: mixed JEE problems, a few quick tools, and the traps examiners love. By the end, you will crack this one too. So, let's begin.

0:40Testing a listed relation

So, first tool: testing a relation that is given as a list. The picture shows the three tests. Reflexive: a loop at every point. Symmetric: every arrow has a return arrow. Transitive: every two-step path has a short cut, the dashed arrow, okay? Now try it. On the whole numbers, the bold W on screen, x is related to y when x squared plus y squared equals twenty five. First, list the pairs of R, okay? Which pairs of whole numbers give twenty five? Correct! Zero and five, five and zero, three and four, four and three. Four pairs, that's all. Reflexive? No, there is not even one loop. Symmetric? Yes! Every pair has its mirror pair. Clear? Now transitive. Three comma four, four comma three: it all looks so neat and balanced. So transitive also, right? No, no, careful! Zero comma five and five comma zero are both in R; the curved symbol means, belongs to. That two-step path goes from zero back to zero, so transitivity demands zero comma zero. But zero comma zero does not belong to R, the slashed symbol. This is the hidden demand: a pair and its mirror together force both loops. Examiners love this one. Got it?

2:07Equivalence: classes and the square check

Now the same tests on a nicer relation. On one, two, three, four, this R has the four loops, then one comma two, two comma one, three comma four, and four comma three. Is it an equivalence relation, that is, reflexive, symmetric and transitive together? Alright, let's test one by one. All four loops are there, so reflexive. And every pair that is not a loop has its mirror, so symmetric. Easy, right? Transitive? Look, the two-step paths, shown with little arrows. One to two to one needs one comma one. Three to four to three needs three comma three. Such paths need only loops, and all the loops are present. So transitive too, okay? So the classes are one and two together, and three and four together. Now the check toppers always do: square the class sizes and add. Two squared plus two squared is eight, and n of R, the number of pairs in R, is exactly eight. Perfect match!

3:12Topper's trick: find the same remainder

Next, a medium one. On the integers, the bold Z, a is related to b if five divides two a plus three b. The vertical bar means divides, and the two-way arrow means, if and only if. Is this an equivalence relation? Checking each property directly looks messy, right? So here is the trick. Write three b as minus two b, plus five b. Then two a plus three b equals two a minus two b, plus five b. And five b is always divisible by five, okay? So five divides two a plus three b exactly when five divides two times a minus b. And two and five have no common factor, so that means five divides a minus b. That's it! That is congruence modulo five: a and b leave the same remainder on division by five. And same remainder always means an equivalence relation, with five classes, remainders zero to four. The picture shows the same idea for modulo three: three classes. Simple as that.

4:15Counting: forced cells and free cells

Now counting, the JEE favourite. Look at the grid. Every cell is one ordered pair, and making a relation means switching each cell in or out. Three elements give three by three, nine cells. So two to the power nine: five hundred and twelve. Remember? That's our hook number! Now the rule. Some cells are forced: no choice. Every free cell doubles the count, the times two on screen. Reflexive forces the whole diagonal in. Symmetric makes each mirror pair, the two cells of the same colour, go in or out together. Try this. On the set a, b, c, d, how many reflexive relations contain the pair a comma b? Alright, look. Four elements: sixteen cells. The four loops are forced, and a comma b is forced: five cells. The other eleven are free. Two to the power eleven: two thousand and forty eight. And symmetric relations containing a comma b? Now the mirror pair, a comma b and b comma a, is forced in together. Free: the four loops, and the other five mirror pairs. Nine free choices: two to the power nine, five hundred and twelve. With me?

5:32Example 1: classes and n(R) when 7 divides a - b

Time for example one. On the numbers one to one hundred, a is related to b when seven divides a minus b. Find the number of classes, and n of R, okay? Pause the video, and try it first. Done? Okay, let's check. Seven divides a minus b means the same remainder on division by seven. Our same-remainder trick again! Remainders zero to six: seven classes. Now n of R: square the class sizes and add. Seven classes, so take one size, square it, and multiply by seven, right? But tell me, does every class have the same size? No! That is the trap. One hundred is seven times fourteen, plus two. The dot means times. So fourteen full rounds of all seven remainders, and then two extra numbers, ninety nine and one hundred, with remainders one and two. So remainders one and two get fifteen members each, and the other five get fourteen. Now square and add. Two times fifteen squared is four hundred and fifty. Five times fourteen squared is nine hundred and eighty. Total: one thousand four hundred and thirty. And we are done.

6:47Example 2: relations neither reflexive nor symmetric

And now, our hook question, the hard one. On the set one, two, three, how many relations are neither reflexive nor symmetric? Pause the video and try it. Hint: count the opposite first, reflexive or symmetric. Done? Okay, let's check. All relations: five hundred and twelve. Reflexive: three diagonal cells forced, six free, so two to the power six, sixty four. Symmetric: three loops and three mirror pairs, six free choices, again sixty four. So neither equals five hundred and twelve, minus sixty four, minus sixty four: three hundred and eighty four, right? No, no, careful! This is the JEE trap. Some relations are both reflexive and symmetric, and we just subtracted them twice. How many? Loops forced in, and the three mirror pairs free: two cubed, eight. So reflexive or symmetric is sixty four plus sixty four, minus eight: one hundred and twenty. Remember inclusion and exclusion from sets? Exactly the same formula! And neither is everything else: five hundred and twelve minus one hundred and twenty. Three hundred and ninety two. Hook solved! See how the grid made it so easy?

8:09Quick revision: tests, equivalence classes and counting

So, quick revision. One: test a listed relation with loops, mirrors and two-step paths, and remember, for transitivity, a pair with its mirror forces both loops. Two: the same remainder means equivalence, and n of R is the sum of the squares of the class sizes. Three: for counting, forced cells have no choice, and every free cell doubles the count. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!