Reflexive, symmetric and transitive as three demands that can fail independently

0:00You are about to be handed three tests, and they arrive together, in one definition, lettered a, b and c. That packaging is misleading, and the whole of this is about why. They look like three items on one checklist, as though a relation either has the properties or does not. But each of the three asks about a different sized piece of the grid of pairs. The first looks at one element at a time.

0:29The second looks at two. The third looks at three. And because they look at different things, no one of them can force another. That is not obvious, and it is not going to be argued; it is going to be shown, by exhibiting a relation for every possible combination of passing and failing. So from here on, the answer to what properties does this relation have is never a word.

0:58It is three separate verdicts, and each failing verdict comes with the exact pair or triple that killed it. The first demand: every element is related to itself. On the grid of pairs, that is one line of cells - the diagonal, running from the top left corner to the bottom right. The demand is that every cell on that diagonal is shaded. Notice the word every. There is no partial credit inside a definition.

1:30A relation on three elements that misses all three diagonal cells fails, and a relation that misses only one of them fails exactly as completely. And notice how little the demand looks at: it never mentions a second element at all. You can settle it by running your eye down one diagonal and stopping at the first gap. That gap is the witness, and naming it is the whole proof that the demand fails.

2:02The second demand: whenever a pair is in the relation, the pair with its two entries swapped is in as well. On the grid that is a reflection. Fold the grid along its diagonal and every shaded cell must land on a shaded cell. This one needs two elements to say at all - there is nothing to swap with only one. And here is the trap that catches people: confirming instances never settle it.

2:32You can check five pairs, find all five swap correctly, and still be wrong, because the demand is about all pairs and you have looked at five. One failing pair, on the other hand, settles it completely and for ever. So a verdict of fails is cheap - one witness - and a verdict of passes is expensive, because it needs an argument covering every case. That asymmetry is not a quirk of this topic; it is what a claim about all things is like.

3:07The third demand: whenever you can follow one pair into another, the shortcut across the two ends is there too. Draw an arrow from a to b, and an arrow from b to c. The demand is that the arrow from a straight to c is also drawn. Three elements to say it, and that is the first time three have been needed. Two things about this one are worth pinning down now, because both cause trouble later.

3:36First, the demand is stated for a chain of exactly two steps, and nothing longer. Longer chains do follow, by applying it again and again, but the definition itself is about two steps. Second - and this is the single point people find hardest here - if there is no chain of two steps anywhere in the relation, then there is nothing to demand, and the demand is met. We will come back to that, because it feels like cheating and it is not.

4:10Start with a relation that passes all three, so you can see what that looks like. Take triangles, and relate one to another when they are congruent. Here are eight triangles described by their three side lengths, and among them there are four genuinely different shapes; the rest are the same triangles written with their sides in a different order. Counting every pair that is congruent gives eighteen out of the sixty-four pairs available - so this is not the everything relation wearing a disguise.

4:46Now the three verdicts. A triangle is congruent to itself, so the first demand passes. If one triangle is congruent to another, the second is congruent to the first - congruence read backwards is still congruence - so the second passes. And congruence chains: if the first matches the second and the second matches the third, the first matches the third. Three passes, and a relation that passes all three has its own name; it is called an equivalence relation.

5:22Hold on to how easy that felt, because it is about to stop being easy. Now lines in a plane, related when they meet at a right angle. Take thirty-six directions, evenly spread, and count the pairs at a right angle: thirty-six of them. Second demand first, because it is the one that passes. If one line is at a right angle to another, the other is at a right angle to it - a right angle does not care which line you name first.

5:56So perpendicularity is symmetric, and comfortably so. First demand: is a line at a right angle to itself? No line is, ever. Take the horizontal direction as the witness and the demand is dead. Third demand, and this is the one worth drawing. Take a horizontal line, a vertical line at a right angle to it, and another horizontal line at a right angle to the vertical. Follow the chain: horizontal to vertical, vertical to horizontal.

6:32The shortcut would need the two horizontals to be at a right angle to each other, and they are parallel. Every one of the thirty-six chains of two right angles lands on a pair of parallel lines - all thirty-six, without exception. So chaining perpendicularity does not fail sometimes; it fails every single time. So far one relation passing all three and one passing only the second. Here is the cleanest example in the other direction.

7:07On the three elements one, two and three, take five pairs: one-one, two-two, three-three, one-two, and two-three. All three diagonal cells are shaded, so the first demand passes. The second: one-two is in, and two-one is not. That single pair is the witness and symmetry is finished. The third: one-two is in and two-three is in, so there is a chain from one through two to three. The shortcut, one-three, is not there.

7:38One relation, five pairs, and the first demand passing while the other two fail - which is already enough to prove that the first does not force either of the others. And notice: the whole verdict took three glances at different shapes of the same picture. Now the argument that trips almost everybody, and it is worth saying out loud because it sounds airtight. The claim: if a relation is symmetric and transitive, then it must be reflexive.

8:12The argument goes like this. Take any element a. Find some b that a is related to. By symmetry, b is related to a. Now chain those two: a to b, then b back to a, so by transitivity a is related to a. Done for every a, and the relation is reflexive. Every line of that is correct except one word, and the word is find. Nothing in the definitions promises that any such b exists.

8:44Here is the relation that kills it: on our three elements, the single pair one-one, and nothing else. It is symmetric, because the only pair it holds is its own swap. It is transitive, because the only chain available runs from one to one to one, and the shortcut is the pair we already have. And it is not reflexive: run the argument at the element two and it stops at the second line, because two is related to nothing at all and there is no b to find.

9:19Two and three are never dragged onto the diagonal, because nothing connects them to anywhere. That relation passed the third demand for a reason worth its own section, because it is the single most counterintuitive thing here. Consider a relation whose pairs are one-six, two-seven and three-eight. Its first entries are one, two and three; its second entries are six, seven and eight; and the two lists share nothing. So take any pair and try to continue it.

9:54You land on six, and no pair starts at six. The number of chains of two steps available anywhere in this relation is zero. The third demand says: whenever there is a chain, there must be a shortcut. There is never a chain. So there is never a missing shortcut, and the demand is met - not by luck, but because a demand about all chains is satisfied by having none.

10:22This is exactly how the empty relation gets to be transitive too. It feels like cheating and it is not; it is what a universally quantified sentence means. The relation fails the first two demands, by the way - it has no diagonal pairs and no swaps - so it passes only the third. Now some rules read straight off, and classified. On the first fourteen counting numbers, relate a pair when three times the first equals the second: that is four pairs, and it fails all three demands.

11:02On six elements, relate a pair when the first divides into the second: fourteen pairs, and it passes the first and the third while failing the second, because one divides into two and two does not divide into one. On the integers, relate a pair when the difference is a whole number. That sounds like a restriction and excludes nothing: on a stretch of eleven integers there are a hundred and twenty-one pairs available and it takes all one hundred and twenty-one.

11:36It passes all three, and the lesson is that you cannot read a verdict off the wording of a rule; the set matters as much as the rule. Two relations among people, to show the same spread outside arithmetic. Take six people living across three neighbourhoods and relate two of them when they live in the same one: fourteen pairs, and all three demands pass. Now relate one person to another when the first is taller than the second by exactly seven centimetres.

12:11Across a range of forty-one recorded heights that is thirty-four pairs, and it fails all three. Nobody exceeds their own height; taller reverses to shorter; and two steps of seven centimetres make fourteen, not seven, so the chain has no shortcut. Here is the most efficient thing in this whole topic. Three relations on the numbers, differing by one symbol. The first: relate a to b when a is at most b.

12:44The second: when a is at most b squared. The third: when a is at most b cubed. Test all three over the same stated range of twenty values, and count the failures rather than arguing. The plain one fails the first demand zero times and the third demand zero times; it fails symmetry a hundred and ninety times, which is exactly what you would expect from an ordering. Now square the right-hand side.

13:15The first demand starts failing, and it fails at one value: a half, because a half is bigger than a quarter. Symmetry fails seventy-five times, and transitivity, which was flawless a moment ago, fails a hundred and twenty times. One witness chain is ten, four, two: ten is at most sixteen, four is at most four, and ten is not at most four. Cube it instead and the same thing happens with different numbers: the first demand fails at a half again, symmetry fails fifty-five times, transitivity eighty-six.

13:55One symbol changed and a relation that passed two demands now passes none. Three demands, each passing or failing, makes eight possible patterns. The claim was that no demand forces another, and that claim is now a counting question with an answer. Go through every relation on a three-element set - there are five hundred and twelve of them - and sort them by which pattern they make. All eight patterns occur.

14:27Five of the five hundred and twelve pass all three; two hundred and sixty fail all three; two hundred and ten pass exactly one; thirty-seven pass exactly two. Every pattern has at least one relation making it, so no demand can possibly force another - if it did, one of the eight boxes would be empty. Now do the same on a two-element set, where there are sixteen relations. Only five of the eight patterns occur.

15:00Three patterns simply cannot be built on two elements at all - including the one you would most want, a relation passing the first two demands and failing the third. So three elements is not an arbitrary choice of playground. It is the smallest arena in which the independence is fully visible, and that is a measurement rather than a preference. One last kind of question, and it is the one that turns all this into work.

15:33You are given a pattern and asked how many relations make it. On three elements, how many relations hold both one-two and two-three, pass the first and third demands, and fail the second? The answer is three, and the reason is the interesting part: reflexivity forces the diagonal in, transitivity then forces the shortcut one-three in, and every further pair you add forces more in until the relation becomes symmetric, which disqualifies it.

16:09The demands push against each other, and only three relations survive the squeeze. Change the question slightly: how many hold one-two and one-three, pass the first and second demands, and fail the third? Now exactly one relation qualifies, and it holds seven of the nine available pairs. Reflexivity forces the three diagonal pairs, symmetry forces two-one and three-one, and that seven-pair relation already fails transitivity - two is related to one and one to three, with no two-three to close it.

16:49The only pairs left are two-three and three-two, and symmetry says they must come as a couple; add them both and you have all nine pairs, which is transitive and therefore disqualified. So: one relation. And notice what did the work in both of those counts. Not a feeling about which properties go together, but three separate tests, applied one at a time, each with its own witness when it failed.

17:19That is the whole method, and it is the only thing that survives contact with a hard question.