A relation as a subset of a product set, and the two extreme cases

0:00Two lists of students, one from each of two year groups, and a question that sounds easy: how are they related? Here are five answers, and every one of them means something you could check by asking around the school. One has the other for a brother. One has the other for a sister. One is the older of the two. One scored less than the other. The two live in the same neighbourhood.

0:28Each of those draws a different set of lines between the two lists, and each line is there for a reason a person could tell you. That is what the word relation means in English, and it is the wrong meaning for what comes next. Because in about one sentence, all five of these are going to be thrown away. Here is the definition that replaces them. Take the set of every ordered pair you could build with a first entry from one list and a second entry from the other.

1:03A relation is any collection of those pairs. Any collection at all. Read that again, because the word doing the work is any, and it is doing damage. There is no requirement that the pairs you keep have anything to do with one another. There is no requirement that you could explain your choice. A relation is a subset, and a subset is a decision about each pair taken one at a time, with no obligation to be consistent about it.

1:35Everything the brother relation had - the reason, the meaning, the story - is gone, and what is left is a list of pairs you kept. That looks like a loss, and the rest of this is going to argue that it is the whole gain. Let us make the damage visible on something small. Take the set holding one, two, three and four, and draw every ordered pair you can make from it as a cell in a grid.

2:04Sixteen cells, and a relation is a choice of which ones to shade. Here is one: shade the pair one three, the pair two two, the pair three one, the pair four one, and the pair four four. Five cells, chosen because I felt like it. There is no rule behind that shading, and there does not need to be one; it is a relation because it is a set of pairs, and that is the entire test.

2:33Now, how many of the possible shadings does a rule of a familiar shape ever reach? Take the rule b equals a plus some whole number, and run it over every whole number it can be given: it reaches eight different shadings and then starts repeating. Take the rule the size of the difference is at least some whole number, and do the same: it reaches five. Between them the two families reach twelve shadings.

3:03The definition admits all of them, and it admits the sixty-five thousand five hundred and twenty-four that neither family ever produces. Before going on, one piece of notation, because it trips people who only learned the other one. The pair one three sits inside our shaded relation. You can write that as an ordered pair belonging to a set, which is the honest form, because it says exactly what a relation is.

3:35Or you can write the name of the relation between the two entries, the way you would write is less than, or equals. One R three. That form reads like a verb, and it is why relations feel like actions rather than sets. But there is no second fact there. The pair belonging to the set and the symbol written between the entries are one statement in two costumes, and an exercise is free to hand you either.

4:07Now a narrowing that happens quietly, and matters enormously. We began with two different lists, and a relation running from one to the other. From here on, both entries come from the same set. The reason is not tidiness. Everything that is about to be defined - whether a relation always links a thing to itself, whether it works in both directions, whether links can be chained - needs to compare an element with another element of the same set.

4:40With two different sets those questions cannot even be asked. So: one set, and the pairs are drawn from that set on both sides. Four elements give sixteen ordered pairs, and each of the sixteen is independently in or out. That is two multiplied by itself sixteen times, which is sixty-five thousand five hundred and thirty-six relations on a set of four things. Sixty-five thousand five hundred and thirty-six of them, for a set you can write on a single line.

5:16Somewhere in that pile are the two we are about to name. Take the same four elements and this rule: keep the pair when the first entry minus the second equals ten. Go through the grid honestly, cell by cell, rather than guessing. One minus one is zero, no. One minus four is minus three, no. Four minus one is three, no. Work all sixteen and the count of cells that qualify is zero.

5:48And you can see why without checking, once you have checked: the largest difference this set can produce is three, and the smallest is minus three. Ten is nowhere near that stretch. So the rule is fine, the arithmetic is fine, and the relation it selects is the one holding nothing at all. The grid stays completely unshaded, and that empty grid is a relation, because the set holding no pairs is a subset of the sixteen just as surely as any other.

6:24Now the other end, with a rule that looks equally ordinary. Keep the pair when the size of the difference between the entries is at least zero. The size of a difference is the difference with any minus sign stripped off, so it is never negative. Never. Which means the test is passed before it is applied. On this set the size of the difference takes four distinct values, and the smallest of the four is zero, so nothing is anywhere near failing.

6:57All sixteen cells shade, and the count of pairs on which the size of the difference is negative is zero, because there are none to be had. This is worth pausing on, because the usual instinct is to test two or three pairs and be satisfied. The point is that no pair ever needed testing. And to see that the sixteen was a reading and not a formality, move the zero up to one: now the rule keeps twelve cells and leaves four unshaded.

7:30Same rule, one number changed, and the whole grid stops being full. So here are the two names. A relation that holds no pair at all is called the empty relation, and it is written as the empty set sitting inside the grid. A relation that holds every pair is called the universal relation, and it is written as the grid itself. Together they are called the trivial relations, which is an unfortunate name, because trivial here means at the ends, not unimportant.

8:07And notice what the naming costs: nothing. Neither of them had to be argued into the definition. The empty set is a subset of the grid, so the empty relation qualifies without special pleading. The grid is a subset of itself, so the universal relation qualifies the same way. This is the payoff for throwing the meaning away in the first place. A definition that demanded a recognisable link would have had to decide whether nothing counts as a link, and whether everything does, and it would have got one of them wrong.

8:47Both of those verdicts came out of arithmetic. Here is the same pair of extremes settled by facts about the world instead, which is a useful shock. Take a school that admits boys only, and put every pupil on the roll into one set - here, fourteen of them. First relation: keep the pair when the second pupil has the first for a sister. Nobody on that roll is anybody's sister, so the count of qualifying pairs is zero, and the relation is the empty one.

9:22No algebra was involved; a fact about who the school admits did the whole job. Second relation: keep the pair when the two pupils' heights differ by less than three metres. Every pair qualifies - all one hundred and ninety-six of them - so the relation is universal. And again the reason is not algebra: across those fourteen pupils the largest gap between any two heights is eighty-three centimetres, and three metres is not a distance human beings differ by.

9:58Change the world and the verdict changes with it, which is exactly the point. Now the misunderstanding this topic most often produces. A student sees that the difference-of-ten rule selected nothing and concludes the rule was badly written. It was not. Keep the rule exactly as it is, change nothing about it, and hand it a different set: the whole numbers from one up to twenty. The same rule now selects ten pairs, and the relation is neither empty nor universal.

10:35In fact the smallest set of that shape on which the rule catches anything runs up to eleven, and below that it comes back empty every time. The relation was never a property of the rule. It is a property of the rule and the set together, and dropping either half leaves you unable to say what relation you are talking about. The other half of the same lesson: keep the set and move the rule's number.

11:05Ask for a size of difference of at least each whole number from minus five up to five - eleven settings in all - and eight of those eleven land on one extreme or the other. The two ends are not exotic. You fall into them by accident, constantly. Between the ends there is everything else, and reading one off its rule is the skill this all rests on. Same four elements, and the rule b equals a plus one.

11:36One goes to two, two goes to three, three goes to four. And four goes to five, except five is not in the set, so four contributes nothing. Three pairs out of the sixteen available. Now the same rule with the set running up to six. The same three pairs, and then four to five and five to six as well: five pairs. Nothing about the rule changed; the set got longer and the relation got longer with it.

12:07Run that on every set from one up to n and the count is always one less than the size of the set, which is the last element having nowhere to go. Two things follow. A rule is an instruction for building a list, and the list is the relation. And you can always go back the other way: hand someone the three pairs and they can tell you the rule, or invent a different rule that gives the same three.

12:38Rules can also carry more than one demand, and then membership has to be settled pair by pair, with no shortcut. Take a relation on the counting numbers that keeps the pair when two things both hold: the first entry is two less than the second, and the second entry is bigger than six. Four candidate pairs, and both demands get checked on every one of them. Two and four: two is indeed two less than four, so the first demand passes; but four is not bigger than six, so it fails.

13:15Three and eight: eight is bigger than six, so the second demand passes; but eight minus two is six, not three, so it fails the first. Eight and seven: seven is bigger than six, that passes; but seven minus two is five, not eight, so it fails the first as well. Six and eight: six is two less than eight, and eight is bigger than six. Both demands hold, so that is the one pair in the relation.

13:45Now look at how the three failures fell out, because it is not the tidy way you would expect. Two of them failed the first demand and only one failed the second. Three failures, two demands, and no neat one-each split - which is why each candidate has to be walked through both tests rather than sorted by eye. And this relation is not an extreme: on the first forty counting numbers it holds thirty-four pairs, comfortably between the ends.

14:20So why keep the two extremes, when neither of them tells you anything interesting on its own? Go back to the pile of sixty-five thousand five hundred and thirty-six relations on four elements. Ask which of them is contained inside every single one of the others. Exactly one is, and it is the empty relation. Ask which of them contains every single one. Exactly one does, and it is the universal relation.

14:52The other sixty-five thousand five hundred and thirty-four sit between those two, and every one of them is above the floor and below the ceiling. That is not a coincidence about these two; it is what a floor and a ceiling are. Narrow the pile - keep only the relations that hold one particular pair - and the floor rises to that single pair while the ceiling stays the whole grid.

15:20Keep only the relations that leave that pair out, and the ceiling drops to fifteen pairs while the floor goes back to nothing. The ends move with the collection, which is how you know they were measured and not decreed. Throw the two extremes out of the definition and the pile has holes at both ends: rules you can write in one line would name no relation at all, and every classification built on top would have to carry an exception clause.

15:52Keeping them costs one sentence and buys a definition with no gaps. That is why the meaning was thrown away, and it was worth it.