Equivalence Classes and Partitions

Transcript

0:00Introduction

Hello everyone! Here is one small puzzle before we start. Take all the integers, positive, negative and zero, going on forever. Now sort them into boxes with one rule: two numbers share a box when their difference is divisible by three. Infinitely many numbers, so how many boxes? Infinitely many? No! Just three. Wait, how? Those boxes are called equivalence classes. And look, once you see a relation as boxes, JEE counting questions become two-line answers. So, let's begin.

0:35Equivalence class: everything related to a

So, let R be an equivalence relation on a set A, and take any element of A, call it small a, okay? Its equivalence class is written with square brackets: the set of all x belonging to A, that is the curly e sign, such that x is related to small a. The colon is read, such that. Simple, right? Everything related to small a goes in one box. Now look at the picture: our puzzle. The double-struck Z means all the integers, the long double arrow means, if and only if, and the vertical bar means, divides. So, small a is related to small b if and only if three divides small a minus small b. The class of zero holds minus six, minus three, zero, three, six, and so on. The class of one holds minus five, minus two, one, four, seven. Now you tell me: which box does ten go in? Yes, the class of one! Ten minus one is nine, a multiple of three. Exactly. First property. Small a belongs to its own class, because every element is related to itself. So no class is ever empty. Clear? Second. Two elements are related exactly when their classes are equal. Same double arrow, if and only if. One and four differ by three, so the class of four is the same box as the class of one. So any member can represent its class, okay? Now think. Can two classes share a few elements, but not all? No, never! If one element sits in both boxes, it is related to both, so by the second property, the two classes are the same. So two classes are either identical, or disjoint, with nothing in common. Clean, separate boxes, no sharing. And last: all the classes together give back the whole set. Now our puzzle is solved. Dividing by three leaves only three remainders: zero, one or two. So infinitely many integers, but just three boxes.

2:31Partition: cutting a set into blocks

Alright, now a new word: partition. So, a partition of a set is a collection of non-empty subsets of it. We will call these pieces blocks, okay? Two conditions. The blocks are pairwise disjoint, so no two share anything. And their union is the whole set, so nothing is left out. Like cutting a cake: every crumb is in exactly one piece. Now wait. Non-empty, disjoint, and together they cover the set. Have we seen these three conditions somewhere today? Yes, exactly! They are the properties of equivalence classes. So, the classes of any equivalence relation form a partition of the set. The arrow on screen means, gives. Every equivalence relation cuts the set into blocks. And it works backwards too. Give me any partition, and say: two elements are related when they lie in the same block. The wavy sign is read, is related to. This always gives an equivalence relation. So here is the big theorem: equivalence relations and partitions are two names for one idea.

3:36Topper's trick: count partitions, not pairs

Now the topper's trick. JEE asks: how many equivalence relations are there on a set with n elements? Don't count ordered pairs. Count partitions! They are the same number. This number is called the Bell number, written B with a little n below, okay? Try it with three elements: one, two and three. In how many ways can you cut them into blocks? Let's see. All three separate: one way. All three together: one way. One pair together and one alone: choose the pair, three ways. Total, five! And that is B three, equal to five, right here in the list. Keep these values on your fingertips: one, two, five, fifteen, fifty two, two hundred and three. Sometimes the question fixes the number of classes, say exactly k classes. Then the count is the Stirling number, S of n comma k, okay? Two easy ones. One class means everything in one block: only one way. Exactly two classes: two to the power n minus one, and then minus one. Write that down. Now the other end. With n minus one classes, exactly one pair sits together and everyone else is alone. So just choose that pair: n choose two, the tall brackets on screen. And n classes means everyone alone: one way. Got it? Last, how many ordered pairs does R have? Inside one class, every element is related to every element, itself included, and different classes are never related. So if the class sizes are n one, n two, up to n k, then n of R is n one squared, plus n two squared, and so on up to n k squared. The sum of the squares of the class sizes, okay? Remember this one, it comes in JEE again and again.

5:20Example 1: n(R) and the class of 5 from given classes

Let's do example one. An equivalence relation on the numbers one to six has three classes: one and two, then three alone, then four, five and six. Find the number of ordered pairs in R, and the class of five. Pause the video, and try it first. Done? Okay, let's check. Six elements, so six squared, thirty six pairs, right? No, no, careful! This is the trap. Thirty six means all of A cross A, every element related to every element. That happens only when all six sit in one class. So, square each class separately. The sizes are two, one and three. So n of R is two squared, plus one squared, plus three squared. Four plus one plus nine: fourteen ordered pairs. Quick and clean. And the class of five? Just find the box that holds five: four, five and six. Notice, the class of four and the class of six are this same box. Any member can represent its class, right?

6:22Example 2: count equivalence relations on 4 elements

Now a harder one, JEE level. The set is one, two, three, four. How many equivalence relations have exactly two classes? How many have exactly three? And how many are there in total? Pause and try. Hint: don't touch the ordered pairs, count the partitions. Done? Okay, let's check. Two classes: the sizes must add up to four. So, three plus one, or two plus two. Three plus one first. Choose the block of three: four choose three, four ways. The lonely element is then fixed. Now two plus two. Choose two of the four elements for the first block: four choose two, six ways, right? Hmm. Wait. Pick one, two as the first block, and three, four is left. Pick three, four first, and one, two is left. See that? The same partition, counted twice! So halve it: half of four choose two, six by two, three ways. This is the classic JEE trap: when the two blocks have the same size, don't forget to halve. So, exactly two classes: four plus three, seven. Check with our formula: two to the power n minus one, minus one. That is two cubed minus one: seven. Perfect match! Exactly three classes. The sizes must be two, one and one. Just choose the pair: four choose two, six. That is n choose two from our table, just as we expected. Total. One class: one way. Four classes, everyone alone: one way. One plus seven plus six plus one: fifteen, our Bell number B four! See? Fifteen equivalence relations, and not a single ordered pair written. Just boxes, like our integers at the start.

8:09Quick revision: classes, partitions and n(R)

So, quick revision. One: the class of an element is everything related to it, and two classes are either identical or disjoint. Two: equivalence relations and partitions match exactly, that is the long two-way arrow. So count boxes, not pairs. Three: n of R is the sum of the squares of the class sizes. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!