Chapter Summary: Mixed Solved Problems on Relations

Transcript

0:00Introduction

Hello everyone! Let's start with a small proof. Take a relation R that is symmetric and transitive. If a is related to b, symmetry says b is related to a. Then transitivity says a is related to itself. So every symmetric and transitive relation is reflexive. Simple, right? But look, this proof is wrong! Can you spot the mistake? Keep thinking. This is our chapter summary on relations: mixed problems, quick tricks, and the traps JEE loves. So, let's begin.

0:37Loops and mirror pairs

So, first the three properties, in one picture. On the left: reflexive. Every element is related to itself: the pair a comma a, a loop. So, a loop at every point, okay? In the middle: symmetric. If a comma b belongs to R, then b comma a must be in R too. The curved symbol is read, belongs to, and the double arrow, implies. Every arrow has a return arrow, so the pairs that are not loops come in twos: a pair, and its mirror pair. Got it? Now a quick question. Can a relation on the set one, two, three be reflexive and symmetric, with exactly four pairs? Got your answer? Alright, let's count. Reflexive, so all three loops are in. Every other pair comes with its mirror, two at a time. So n of R equals three, plus two k, where k is the number of mirror pairs we take, okay? Only three mirror pairs exist here, so k is zero, one, two or three. So n of R is one of three, five, seven or nine. Always odd! Exactly four pairs? Impossible. Is that clear?

1:48Transitive: short-cut every two-step path

Now transitive, the drawing on the right. If a comma b and b comma c are both in R, then the short cut, a comma c, must be in R too. In the picture, two to one to three forces two to three, the dotted arrow. Try this one. On the set one, two, three, four, R has three pairs: one comma two, two comma three, and two comma four. What is the minimum number of pairs we must add, to make R transitive? Now, don't guess. Follow the two-step paths, shown with little arrows. One to two, then two to three: so we need one comma three. One to two, then two to four: so we need one comma four, okay? But wait. Do the new pairs make new paths? They end at three and four, and no pair starts at three or four. So no new path appears, and the minimum is two. Always check your new pairs once more, got it?

2:45The famous wrong proof

Now, back to our opening proof. If a is related to b, symmetry gives b related to a, and then transitivity gives a related to itself. Every step looks correct, right? So where does it break? Yes, the very first step! 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. Classic example: on the integers, the bold Z on screen, a is related to b if and only if a times b is greater than zero. The two-way arrow is read, if and only if. Symmetric? Yes, a b equals b a. Transitive? Also yes: multiply a b and b c, and since b squared is positive, a c is positive. But reflexive? Zero times zero is zero, and zero is not greater than zero. The slashed sign on screen means, not greater than. Zero is related to nothing at all. Symmetric, transitive, but not reflexive. Proof broken! And the repair? If every element is related to at least one element, the proof works, and the relation is reflexive. So it is an equivalence relation. Remember this one!

3:57Topper's trick: the same-value test

Last tool: equivalence relations, reflexive, symmetric and transitive together. Topper's trick: if a related to b means phi of a equals phi of b, for some rule phi, the Greek letter on screen, then R is automatically an equivalence relation. Because equals is all three, right? Like the picture: the same remainder on division by three. Try it. On the integers, a is related to b when a plus b is even. Now tell me, when is a plus b even? When a and b are both odd, or both even, yes! The same parity. So, by the same-value trick, it is an equivalence relation. Now counting. If the classes have sizes n one, n two, up to n k, then n of R is the sum of their squares. Inside one class, every element is related to every element, okay? On one to ten: five odd numbers, and five even numbers. So n of R is five squared plus five squared: fifty. Quick, isn't it?

4:58Example 1: count pairs with a divides b on 1 to 10

Now, example one. On the set one to ten, a is related to b when a divides b. The vertical bar on screen is read, divides. Find n of R, and the number of pairs with a not equal to b, the slashed equals sign. Pause the video, and try it first. Done? Okay, let's check. Don't list all the pairs! Fix the first entry, a. Which b are allowed? The multiples of a, up to ten, exactly! How many? Ten over a, rounded down: that is the bracket with only bottom corners, and the big sigma means, add them all. For one, ten. For two, five. For three, three: three, six and nine. Then two and two, and from six to ten, one each. Total: twenty seven. Now the pairs with a not equal to b. So which pairs in R have a equal to b? The loops, yes! Every number divides itself, so all ten loops are in the relation. Remove them: twenty seven minus ten, seventeen. Remember these loops; they come back in the next example.

6:09Example 2: JEE Main 2023, n(R1 - R2) for divides

Now a harder one, straight from JEE Main twenty twenty three. The set is one to twenty. R one is, a divides b. R two is, a is an integral multiple of b. Find n of R one minus R two: the pairs in R one, but not in R two. Pause the video and try it. Hint: use example one. Done? Okay, let's check. Same method: count the multiples of each a, up to twenty. Twenty, ten, six, five, four, three: forty eight. Then two, two, two, two: eight more. From eleven to twenty, only the number itself: ten ones, as the brace says. So n of R one is sixty six. Now R two: if a is a multiple of b, then b divides a. That is R one with every pair flipped! So R two is R one inverse, the little minus one on top. And flipping never changes the count, so n of R two is also sixty six. So the answer is sixty six minus sixty six, zero, right? No, no, careful! This is the JEE trap. We remove only the pairs of R one that are also in R two. So which pairs are in both? We need a divides b, and b divides a. That forces a equal to b, okay? Our loops again! One comma one, up to twenty comma twenty: twenty pairs. So, n of R one minus R two equals n of R one, minus n of R one intersection R two. Sixty six minus twenty: forty six. JEE Main, done in two minutes. See?

7:48Quick revision: loops, mirror pairs and short cuts

So, quick revision. One: loops for reflexive, mirror pairs for symmetric, short cuts for transitive. Two: symmetric and transitive is not reflexive, if some element is related to nothing. Three: the same value means equivalence, and for divides, count the multiples of each a, okay? Now go and try the practice problems on this page. You will find them easy, I promise. All the best!