A relation is nothing more than a chosen part of the product

0:00Three letters. a, b and c. Five names. Amara, Bruno, Bianca, Chloe and Diego. Cross them, and you get fifteen pairs. Every letter with every name, whether or not it means anything. Now a sentence. Keep the pair when the letter opens the name. a with Amara. b with Bruno. b with Bianca. c with Chloe. Four of the fifteen survive. Eleven are thrown away. And look at Diego. Diego is in no surviving pair at all.

0:34Nothing went wrong. D is simply not one of the three letters. So here is the question that matters. What is the thing that just got made? The sentence? Or those four pairs? It is the four pairs. A relation from one set to another is a chosen part of their product. A subset. Nothing else. That is worth sitting with, because it is a stronger claim than it sounds.

1:03It does not say a relation is described by a subset. It says a relation is one. The sentence about opening letters is not the relation. It is a way of saying which subset you meant. Change the sentence and keep the same four pairs, and nothing has changed. Keep the sentence and change the pairs, and everything has. So every question about a relation is a question about a list of pairs.

1:33Which pairs are in it. Which are not. How many there are. The sentence has done its job the moment the list exists. There are two honest ways to say which subset you mean. Write the pairs out. Or state a condition and let it pick them. Writing them out is the plain one, and it is the one to trust. Watch what it forgives. Here is that same relation with b and Bruno written down a second time.

2:04Five pairs written. Four pairs held. It is the same relation. A member written twice adds nothing, because a set is settled by what belongs to it. The condition route is shorter, and it hides a trap. Two conditions that read nothing like each other can pick exactly the same pairs. Take three numbers, one, two and three, crossed with themselves. The entries are equal. Each entry divides the other.

2:34Different sentences. Same three pairs, every time. So a sentence names a relation. It is not the relation, and it is not even the only name. The other way to say which subset you mean is to draw it. Two ovals. Dots for the members. An arrow for each pair you keep. Three dots on the left, five on the right, four arrows. Now move the dots around. The three letters can be drawn in six different orders. The five names in a hundred and twenty.

3:10That is seven hundred and twenty different pictures of the same four arrows. Every single one of the seven hundred and twenty reads off the same relation. The picture moved. The relation did not. But be careful, because there is something that looks like moving the picture and is not. Turn every pair round. a with Amara becomes Amara with a. Still four pairs. Not one of them is in the original relation.

3:42Redrawing is free. Exchanging the two entries is a different relation entirely. Take six numbers, one through six, and cross them with themselves. Thirty-six pairs. Now the sentence. The second entry is one more than the first. One with two. Two with three. Three with four. Four with five. Five with six. Five pairs out of thirty-six. Try to carry on. Six with seven. But seven is not one of the six numbers, so there is no such pair.

4:18The sentence ran out, and the relation simply stopped. Notice something about six. Six never opens a pair. And one never closes one. Nothing anywhere requires every member to be used. A relation is a subset, and a subset is under no obligation to touch everything. Notice one more thing, quietly. Both sets here were the same set. That is allowed, and it needs no new idea. The product of a set with itself is a product like any other.

4:54Here is a drawing that makes the same point from the other side. On the left, three numbers. Nine, four and twenty-five. On the right, seven. Five, three, two, one, minus two, minus three and minus five. Twenty-one pairs are available. The sentence: the left entry is the square of the right one. Nine is three squared, and it is also minus three squared. Two arrows. Four takes two and minus two. Twenty-five takes five and minus five.

5:28Six arrows in all. Two out of every left-hand dot. And the number one on the right sits there with nothing attached to it. One squared is one, and one is not on the left-hand side. The drawing has a dot no arrow reaches, and the relation is perfectly well behaved. Come back to the trap, because it is worth pinning down. Four numbers, one, two, three and five, crossed with three others, four, six and nine.

6:00Twelve pairs. The sentence: the two entries differ by an odd amount. Seven pairs survive. One with four. One with six. Two with nine. Three with four. Three with six. Five with four. Five with six. Five are thrown out. That is an untidy-looking answer, and it is the honest shape of most relations. Now a different sentence. The two entries add to an odd number. Put both sentences to fifty-seven pairs, drawn from three different products.

6:36They disagree about none of them. Not a coincidence. A difference and a sum always have the same parity, so the two sentences can never come apart. One relation, two sentences, and no way to tell from the pairs which sentence you started from. Now the move that settles the whole argument. If a relation is any subset of the product, then counting relations is counting subsets. There is nothing else to count.

7:09Take a set of two and another set of two. Their product has four pairs. For each pair, one decision. In, or out. Build the catalogue by hand. Start with the subset that keeps nothing. Bring in the first pair, and every subset you had gives you a second one with that pair added. One becomes two. Two becomes four. Four becomes eight. Eight becomes sixteen. Sixteen relations from a set of two to a set of two.

7:40Build the same catalogue a second way, by running through the binary numbers and keeping the pairs whose bit is on. Sixteen again, and every subset in one catalogue is in the other, both directions. Two routes that share no machinery, landing on the same sixteen. Look at what those sixteen include. Exactly one of them keeps nothing at all. The empty relation. No pairs. Every pair it holds lies inside the product, because it holds none.

8:15It is a relation. It relates nothing to anything, and it is on the list. At the other end, exactly one keeps all four. Everything related to everything. Fourteen sit between the two. Neither extreme is a special case that has to be argued for. They arrive because the count is a count of subsets, and those are two of the subsets. Now make one side bigger. Three members against two.

8:45Six pairs, and sixty-four relations. Four times as many, for one extra member. Watch the count as the product grows, one pair at a time. One. Two. Four. Eight. Sixteen. Thirty-two. Sixty-four. A hundred and twenty-eight. Two hundred and fifty-six. Five hundred and twelve. A thousand and twenty-four. Eleven products, and at every one of the ten steps the count doubled exactly. The reason is not deep. One more pair is one more decision, and every subset you had splits into two.

9:26But doubling is unforgiving. Six members related to themselves is thirty-six pairs. Thirty-six doublings. Sixty-eight billion, seven hundred and nineteen million, four hundred and seventy-six thousand, seven hundred and thirty-six relations. On six things. And that number is not counting sentences. It is counting subsets. Which is exactly why the next part is uncomfortable. Take three numbers crossed with themselves. Nine pairs. Five hundred and twelve relations. Now bring a stock of short sentences and see how many of the five hundred and twelve they can name.

10:12The entries are equal. The second is one more. Two more. One less. Two less. The second is larger. Smaller. The entries differ. They add to two, to three, to four, to five, to six. The first divides the second. The second divides the first. They add to an even number. To an odd number. Keep every pair. Keep none. Both entries odd. Each divides the other. Neither divides the other.

10:43Twenty-two sentences. Between them they name twenty different relations, because two pairs of them turn out to be saying the same thing. Twenty, out of five hundred and twelve. Four hundred and ninety-two relations that this stock cannot reach. That could be read as a defect, and it is not one. Every one of the five hundred and twelve can still be described. Just not briefly. Write the pairs out. All of them. In order.

11:16Do that for each of the five hundred and twelve, hand the listing to somebody who has never seen the condition, and let them read it back. Five hundred and twelve listings. Five hundred and twelve relations recovered, exactly. Including the one that keeps nothing, whose listing is empty and reads back as empty. So the shortage is a shortage of short sentences, not a shortage of descriptions. The doubling outruns brevity long before it outruns writing things down.

11:51And that is the whole difference between a relation and a rule. The rule is a convenience. The pairs are the object. One more, and this one only exists as a picture. Left oval: five, six, seven. Right oval: three, four, five. Nine pairs available. Three arrows drawn. Five goes to three. Six goes to four. Seven goes to five. There is no sentence anywhere. Only the drawing. So read one off. Each arrow drops the entry by two.

12:27Put that sentence to all nine pairs, and it picks out exactly those three. Now ask how lucky that was. Try every shift. The second is four less than the first, three less, two less, and so on up to four more. Nine sentences. Exactly one of the nine names the drawn relation. And between them the nine name only six of the five hundred and twelve relations available on that product.

12:57Five hundred and six are out of their reach. The picture held a relation that no sentence in that family could have found. So here is the shape of it. A product is everything that could be paired. A relation is a choice of which of those pairs you keep. Not a rule. A choice. A rule is one way of announcing the choice, and a drawing is another, and writing the pairs out is a third.

13:27All three name the same object, and the object is the subset. That is why the count of relations is a count of subsets, and why it doubles with every pair. It is why the empty relation and the whole product are both on the list without argument. It is why a member can go unused, on either side. And it is why two sets can be the same set without anything new being needed.

13:56Every one of those follows from one word. Subset.