Why writing a pair in order carries information a set cannot

0:00Two colours. Red and blue. Three things to put them on. A bag, a coat, a shirt. How many ways are there to name a colour and a thing together? Six. Red bag, red coat, red shirt. Blue bag, blue coat, blue shirt. That part is easy. Here is the part that is not. What kind of object is a red shirt? It is not one thing. It is two things, named together.

0:28And each of the two has a job. One of them is the colour. The other is the thing being coloured. Hold on to that. In a few minutes it turns out to be the whole point. You already have a way of naming two things at once. Braces. Put the colour and the garment inside a pair of braces. Red, shirt. Now swap them. Shirt, red. That is the same set. Not a similar one. The same one.

0:59A set is settled by which things belong to it and by nothing else at all. Not the order you wrote them in. Not how many times you wrote them. So braces cannot tell you which of the two was the colour. Measure the damage. Take six names. From six names you can write thirty-six ordered pairs. Put braces round each of the thirty-six, and they collapse to twenty-one. Fifteen distinctions, gone.

1:28Thirty of the thirty-six change when you swap the two entries. The braces notice none of it. So build an object that does remember. Same two names. Round brackets, and a comma. Red, shirt. Now the two positions are not interchangeable. One of them opens the bracket. The other closes it. Give them names. The first element, and the second element. Ask for the first element of this one and the answer is red.

2:01On all thirty-six pairs, both elements read back the way they were put in. And this is a new object, not a set that has been listed carefully. On all thirty-six, the pair is not equal to the set holding its own two entries. Round brackets are not tidier braces. They mean something else. A new object needs a rule for when two of them count as the same. Here it is.

2:30Two pairs are equal when the first elements agree and the second elements agree. Both. Position by position. Never because they happen to hold the same two things. Take the thirty-six pairs and compare every one against every one. One thousand two hundred and ninety-six comparisons. By position, thirty-six come out equal. Each pair equals itself, and nothing else. By contents, sixty-six come out equal. So there are thirty comparisons where holding the same things says yes and the rule says no.

3:09Those thirty are the entire reason this object exists. And a pair equals its own swap only six times out of thirty-six. Exactly when both entries were the same name to begin with. Somewhere this has to earn its keep. Baggage tags. Three airports: London, New York, Singapore. Three flight numbers: oh one, oh two, oh three. A tag is an airport followed by a flight number. Three choices, and then three more.

3:43Nine tags. Draw it as a grid. Airports along the bottom, flight numbers up the side, a dot at every crossing. Nine dots, and every dot is a tag. And here is the rule a tag obeys. It opens with the airport. Check all nine. Nine of them open with an airport. Not one of them opens with a number. Now break that rule on purpose. Put the number first.

4:12Oh one, London. Oh two, New York. There are nine of those as well. Nine one way, nine the other. How many appear on both lists? None. Not a single one. Eighteen different tags, and each one says something the others do not. Now do the whole thing in braces instead. The set holding London and oh one. Nine of those. Swap, and put the number first. The set holding oh one and London.

4:43The same nine. Every single one. So the brackets tell eighteen things apart. The braces tell nine apart. That gap is not decoration. It is a piece of information that you either keep or throw away. Now the definition worth having. Name two sets. Collect every pair whose first element comes from the first set and whose second element comes from the second. That collection is the product of the two sets.

5:16Two colours crossed with three garments is the six outfits. Three airports crossed with three numbers is the nine tags. Two things the product is not. It is not a set of sets. Its members are pairs, and a pair is one object with two slots. And writing a member down twice adds nothing. List red twice, and the machine writes nine outfits down. There are still only six, and it is the same six as before.

5:48What happens if one of the two sets is empty? Every pair needs a second element. If there is nothing available to supply one, no pair gets built at all. So the product is empty. Not smaller. Empty. Take six names, and all sixty-four sets you can make from them. Cross each one with the empty set. Sixty-four empty products. Same answer from the other side. Sixty-four again. And it does not leave the other set alone.

6:21Of the sixty-four, exactly one comes back unchanged, and that one is the empty set itself. Compare that with crossing by a set that has a single member. That keeps the count, for all sixty-four. But it still changes the thing, in sixty-three of them. The pairs are not the members. Here is a claim worth testing. The first set holds m and n. The second holds n and m.

6:52Somebody says their product has two pairs in it. It has four. Those two sets are the same set. A set does not remember which name was written first. So the product is m with m, m with n, n with m, and n with n. Four. Two of the four have entries that are alike. The other two are told apart by order alone, and each of those two has its own swap sitting beside it in the product.

7:22Order does not stop mattering when the two sets coincide. That is where it bites hardest. The rule really earns its keep when you have to solve something. On the left, a pair whose first element is x plus one and whose second is y minus two. On the right, the pair three, one. They are declared equal. The positions have to agree, so one equation becomes two. x plus one equals three. y minus two equals one.

7:56x is two. y is three. Sweep every whole number from minus twenty to twenty for both. One thousand six hundred and eighty-one candidates. Exactly one of them works. Now solve it the wrong way, by matching the two entries as a collection. That lets two answers through. The extra one is x equals zero and y equals five, and it builds the pair one, three. Which is not the pair three, one.

8:27The same method survives fractions. x over three plus one equals five thirds, and y minus two thirds equals one third. x is two. y is one. One more use, and it is the one you will keep. Two numbers along the bottom, one and two. Four up the side, one to four. Eight crossings. If both sets hold numbers, then each pair is a position. First element across, second element up.

8:59So exchanging the two coordinates moves the point. Do it to all eight and watch where they go. Two of them do not move at all. Those are the ones whose two coordinates were equal. Two land on a different crossing of the same grid. And four leave the grid completely. One, three exchanges into three, one, and three, one is nowhere on this grid, because three was never one of the numbers along the bottom.

9:30Two, and two, and four. That is the eight. Now a question worth asking. Have we invented a second kind of object, sitting beside sets, with rules of its own? No. You can build it out of braces after all. Here is how. For the pair a then b, write the set holding two things. The set holding a on its own, and the set holding a and b. The lonely one marks which entry opened.

10:00Now swap. For b then a you get the set holding just b, and the set holding a and b. A different set. The two of them share one part out of two. This version is made of nothing but braces, and it knows nothing about positions. It agrees with the two-slot version on all one thousand two hundred and ninety-six comparisons. And on all thirty-six, both entries can be read back out of it.

10:29The plain set holding a and b is unchanged by the swap on all thirty-six, so there is nothing left in it to read. So what exactly did the round brackets buy? Go back to the six names. Fifteen of the sets hold two different names, and each of those fifteen is what exactly two pairs collapse to. Six of the sets hold one name written twice, and each of those is what exactly one pair collapses to.

11:02Fifteen twos, and six ones. Thirty-six. So on two different names there are two pairs and there is one set. One yes-or-no question, kept instead of discarded. That is the whole of it. And that one question is what everything after this is going to be about. Which one came first. Which airport. Which coordinate. Which input. A set could not have said it. That is why the brackets are there.