Why an equivalence relation cuts its set into disjoint classes, and why the cut can be run backwards

0:00There is a sentence people reach for almost without noticing: this one is related to that one, so they belong together. Belonging together means sitting in the same box, and boxes have a property that relations do not automatically have. Two boxes either are the same box or they share nothing at all. There is no third possibility, because a box is not the kind of thing that can half overlap another one.

0:30A relation, on the other hand, can do anything it likes. So reading related to as in the same box is a real claim, and it is false for most relations. This video is about exactly which relations you are allowed to read that way, and about what each of the three demands buys you. The answer is that all three are needed and none of them is spare. And the reading runs in both directions: given the boxes you can recover the relation, which means the two are one object described twice.

1:09Start with the example everything else here grows out of. Take a strip of fifteen consecutive integers, running from minus six up to eight, and relate two of them when their difference is even. Check the first demand: is every integer related to itself? The difference of a number with itself is zero, and zero is even, so yes. Check the second: if the difference of the first and the second is even, is the difference of the second and the first even too?

1:43Reversing a difference changes only its sign, and a sign does not change whether a number is even. Check the third, which is the one worth slowing down for. Suppose the first minus the second is even, and the second minus the third is even. The video asks the checker how many such chains the strip offers, and the answer is eight hundred and fifty-five. Of those eight hundred and fifty-five chains, the number whose two ends have an odd difference is zero.

2:18That zero deserves a reason, not just a count. Write down what the chain gives you: the first minus the second is even, and the second minus the third is even. Now add those two differences together. The second cancels, and what is left is the first minus the third. So the question becomes whether the sum of two even numbers is even, and it is. Two even numbers are two doubles, and the sum of two doubles is a double.

2:50That single line is the whole of the third demand for this relation, and it is why the count came back zero rather than merely small. The count and the reason are doing different jobs. The count says the strip contains no counterexample; the reason says no strip ever could. Now look at what the relation did to the strip. Everything even is related to everything even, and everything odd to everything odd, and nothing crosses.

3:24Ask the checker to collect, for each integer on the strip, the set of everything related to it. It does this one element at a time and never compares one collection with another, so it has no way of arranging the answer. Two distinct collections come back, holding eight integers and seven. Now the census. Walk every ordered pair of those collections and ask one of three questions: are they the same set, do they share nothing, or do they share something without being equal?

3:59Two pairs come back the same, two come back sharing nothing, and the number that overlap partly is zero. That third outcome is available and the walk can report it, which is what makes the zero a reading. And the number of integers on the strip belonging to no collection at all is zero, so the two boxes between them cover everything. The natural next thought is that this was a fact about even numbers.

4:30It was not. Take any set at all, and any relation on it that passes all three demands. For each element, write down the class of that element: everything related to it. Two things are then true, and they are true for the same reason every time. Every element lies in at least one class, so the classes cover the set. And any two classes are either the same class or share nothing, so the classes do not overlap.

5:01Put those together and every element lies in exactly one class. That is what it means to cut a set into boxes, and the cut came from the relation alone. What comes next is the proof, and the point of it is not that the result is true. It is that each of the three demands pays for a different line of it. Here is the argument, and it is shorter than it looks.

5:29Suppose the class of a and the class of b share an element, and call it c. Then c is related to a, and c is related to b. Symmetry turns the first of those around: a is related to c. Transitivity chains that with the second: a is related to b. Now take anything at all in the class of a, and call it x. Then x is related to a, and a is related to b, so transitivity puts x in the class of b.

6:02That gives the whole of the first class sitting inside the second. Run the same argument with a and b exchanged and you get the second sitting inside the first. Two sets each inside the other are the same set. So sharing one element forced the two classes to be identical, which is why partly overlapping never happens. And the covering came from the first demand, one line earlier: a is related to a, so a is in its own class and nothing is left out.

6:37Now watch what happens when you take the demands away one at a time. Each of the three relations here passes exactly two demands and fails the one being tested, and the census is re-run on each. Drop the first demand only. Elements belonging to no box: one. Boxes overlapping partly: zero. So the covering breaks and nothing else does — the first demand is what puts every element somewhere.

7:10Drop the second demand only. Elements belonging to no box: zero. Boxes overlapping partly: two. Drop the third demand only. Elements belonging to no box: zero. Boxes overlapping partly: six. Three demands, three different kinds of damage, and no two of them the same pair of numbers. That is the cleanest demonstration there is that none of the three clauses is redundant. Everything so far went from a relation to boxes.

7:47Now run it the other way. Take the same strip of fifteen integers and hand over three boxes instead: the multiples of three, the numbers one more than a multiple of three, and the numbers two more. Five integers in each. Define a relation by one rule and nothing else: two integers are related when they sit in the same box. The checker builds that relation without ever being told whether the boxes are any good, and compares it pair by pair with the relation that admits two integers when three divides their difference.

8:27They are the same relation. And it passes all three demands: three boxes, five in each, and zero pairs of them overlapping partly. Now feed the same routine bad boxes, so you can see what the good ones bought. Boxes that overlap give a relation that fails the third demand. Boxes that leave an element out give a relation that fails the first. Covering buys reflexivity, not overlapping buys transitivity, and same box reading the same in either order buys symmetry.

9:05So the construction runs both ways, and a relation and a division are the same information written twice. A finite rehearsal, because the integer examples are misleadingly tidy. Take the numbers one to seven and relate two of them when they are both odd or both even. It passes all three, and it produces two boxes holding four numbers and three. Four and three, not four and four. Take one to five and relate two of them when their difference is even: two boxes again, holding three and two.

9:44Now the set of integers from nought to twelve, thirteen of them, related when their difference is divisible by four. Four boxes, of sizes four, three, three and three, and those sizes add back to thirteen. The one you get by asking what is related to one is the set holding one, five and nine. And then the case that looks like a joke and is not. On the same thirteen numbers, relate two of them when they are equal.

10:15That passes all three demands, and it produces thirteen boxes, each holding one number. Thirteen boxes, one hundred and fifty-six pairs of them sharing nothing, and zero overlapping partly. Equal sizes were never part of the definition. A class is a set, and a set does not know which of its members you named it after. On the strip cut into three, the box holding nought is the box holding three, and the box holding minus six.

10:51Ask the checker how many of the fifteen integers on the strip name that same box, and the answer is five — exactly its members. So one box, five names, and none of them more official than the others. This is where the notation misleads. Writing the class of nought and the class of three side by side makes them look like two things, because nought and three are two things.

11:18They are one thing. The element in the bracket is a name for the box, chosen from inside it, and any member would have done. The only question worth asking is whether two names pick out the same box, and that is settled by whether the two elements are related. Here is a cut you can look at. Take the points of a plane and relate two of them when they are the same distance from the origin.

11:48Same distance is an equality between two numbers, so all three demands pass without any work. The classes are the circles drawn about the origin, one for each radius. Except for one. Take a grid of forty-nine points about the origin and let the checker collect the classes: ten of them come back. Of those ten, the number holding a single point is one, and that one is the class of the origin itself.

12:20The other nine hold more than one point each. The origin is at distance zero from itself and from nothing else, so its class is a single point and a single point is not a circle. That is why any careful statement of this one says: for any point other than the origin. The exclusion is not a technicality to skip past — it is the whole reason the picture needs one point drawn outside the family of circles.

12:53The same objects can be cut in more than one way, and which cut you get is decided entirely by the relation you chose. Take three right-angled triangles with sides three, four and five; five, twelve and thirteen; and six, eight and ten. All three are right-angled — nine plus sixteen is twenty-five, twenty-five plus a hundred and forty-four is a hundred and sixty-nine, and thirty-six plus sixty-four is a hundred.

13:26Cut them by similarity and you get two boxes, of sizes one and two, because the third triangle has sides exactly double the first. Cut them by congruence and you get three boxes of one each. Now add a square and a pentagon, and cut all five by how many sides they have: three boxes. Cut them by side count and then by shape: four boxes. The triangle of sides three, four and five shares a box with three of them one way, and with two of them the other.

14:02One cut is finer than the other, and neither is a relabelling of the other. One warning about the sides. A fourth triangle with sides three, four and six shares two sides with the first and is neither right-angled nor similar to it. Two sides agreeing is not enough; the third side is what decides. Two more relations worth putting side by side, because one of them is a trap.

14:33Take a set of thirty-five straight lines, and relate two of them when they are parallel. Five boxes, seven lines in each, sorted by slope. Notice what makes the first demand pass here: a line counts as parallel to itself. All thirty-five are parallel to themselves, and the number of lines at a right angle to themselves is zero. Same set of lines, two relations, and the first demand goes one way for one and the other way for the other, purely on a convention.

15:08Now the trap. Take two relations that both pass all three demands, and intersect them. The result passes all three as well, and that is a real theorem, not bookkeeping. Take the union instead and it can fail. On three elements, one relation joins the first two and the other joins the last two; their union holds the first related to the second and the second to the third, and does not hold the first to the third.

15:40Run every ordered pair of the equivalence relations on three elements — twenty-five pairs. All twenty-five intersections pass all three demands. Nineteen of the twenty-five unions do, which leaves six that do not. Almost every relation in this topic is one machine wearing different clothes. Take any function, and relate two inputs when the function sends them to the same output. Same page count, same distance, same number of sides, same slope, same remainder — every one of those is that machine.

16:20The classes are the sets of inputs sharing an output. Five different functions on a twelve-element set were tried, and all five produce a relation passing all three demands. One of them cuts the twelve into five boxes of sizes two, two, two, three and three, adding back to twelve. And here is the same idea running in reverse, once more. Two descriptions of one relation on nine numbers: divisible by three on one side, three named blocks on the other.

16:56The pairs one description holds and the other does not: zero, in both directions. Twenty-seven pairs out of the eighty-one available, described twice. Which brings us to counting. Counting equivalence relations directly means testing every relation on the set. Counting divisions into boxes means listing divisions. On sets of one, two, three and four elements those two counts are one, two, five and fifteen — and they agree, by two routines that share no code.

17:32So a question like how many equivalence relations on three elements hold one related to two is not a search at all. Five divisions, of which two keep one and two in the same box. The answer is two, and you never had to look at a relation.