3.5: Properties of endorelations

As I mentioned, lots of the relations we care about are endorelations (relations between a set and itself). Some endorelations have one or more of the following simple properties which are useful to talk about. Throughout this section, assume that \(R\) is the relation in question, and it’s defined from set \(A\) to set \(A\).

• Reflexivity. A relation \(R\) is reflexive if \(x R x\) for every \(x \in A\). Other ordered pairs can also be in the relation, of course, but if we say it’s reflexive we’re guaranteeing that every element is in there with itself. “hasSeen" is almost certainly a reflexive relation, presuming that mirrors are relatively widespread in the world. “thinksIsBeautiful" is not reflexive, however: some people think themselves beautiful, and others do not.

• Symmetry. A relation is symmetric if \(x R y\) whenever \(y R x\) and vice versa. This doesn’t mean that \((x,y)\) is in the relation for every \(x\) and \(y\) — only that if \((x,y)\) is in the relation, then \((y,x)\) is guaranteed to also be in the relation. An example would be “hasShakenHandsWith." If I’ve shaken hands with you, then you’ve shaken hands with me, period. It doesn’t make sense otherwise.

• Antisymmetry. A relation is antisymmetric if \(x\)-\(R\)-\(y\) whenever \(y R x\) and vice versa (unless \(x\) and \(y\) are the same.) Put another way, if \((x,y)\) is in the relation, fine, but then \((y,x)\) can’t be. An example would be “isTallerThan." If I’m taller than you, then you can’t be taller than me. We could in fact be the same height, in which case neither the pair (you, me) nor (me, you) would be in the relation, but in any event the two cannot co-exist.

• Note carefully that antisymmetric is very different from asymmetric. An asymmetric relation is simply one that’s not symmetric: in other words, there’s some \((x,y)\) in there without a matching \((y,x)\). An antisymmetric relation, on the other hand, is one in which there are guaranteed to be no matching \((y,x)\)’s for any \((x,y)\).

  If you have trouble visualizing this, here’s another way to think about it: realize that most relations are neither symmetric nor antisymmetric. It’s kind of a coincidence for a relation to be symmetric: that would mean for every single \((x,y)\) it contains, it also contains a \((y,x)\). (What are the chances?) Similarly, it’s kind of a coincidence for a relation to be antisymmetric: that would mean for every single \((x,y)\) it contains, it doesn’t contain a \((y,x)\). (Again, what are the chances?) Your average Joe relation is going to contain some \((x,y)\) pairs that have matching \((y,x)\) pairs, and some that don’t have matches. Such relations (the vast majority) are simply asymmetric: that is, neither symmetric nor antisymmetric.

  Shockingly, it’s actually possible for a relation to be both symmetric and antisymmetric! (but not asymmetric.) For instance, the empty relation (with no ordered pairs) is both symmetric and antisymmetric. It’s symmetric because for every ordered pair \((x,y)\) in it (of which there are zero), there’s also the corresponding \((y,x)\).¹ And similarly, for every ordered pair \((x,y)\), the corresponding \((y,x)\) is not present. Another example is a relation with only “doubles" in it — say, { (3,3), (7,7), (Fred, Fred) }. This, too, is both symmetric and antisymmetric (work it out!)

• Transitivity. A relation is transitive if whenever \(x R y\) and \(y R z\), then it’s guaranteed that \(x R z\). The “isTallerThan" relation we defined is transitive: if you tell me that Bob is taller than Jane, and Jane is taller than Sue, then I know Bob must be taller than Sue, without you even having to tell me that. That’s just how “taller than" works. An example of a non-transitive relation would be “hasBeaten" with NFL teams. Just because the Patriots beat the Steelers this year, and the Steelers beat the Giants, that does not imply that the Patriots necessarily beat the Giants. The Giants might have actually beaten the-team-who-beat-the-team-who-beat-them (such things happen), or heck, the two teams might not even have played each other this year.

All of the above examples were defined intensionally. Just for practice, let’s look at some extensionally defined relations as well. Using our familiar Harry Potter set as \(A\), consider the following relation:

(Harry, Ron)
(Ron, Hermione)
(Ron, Ron)
(Hermione, Ron)
(Ron, Harry)
(Hermione, Hermione)

Consider: is this relation reflexive? No. It has (Ron, Ron) and (Hermione, Hermione), but it’s missing (Harry, Harry), so it’s not reflexive. Is it symmetric? Yes. Look carefully at the ordered pairs. We have a (Harry, Ron), but also a matching (Ron, Harry). We have a (Hermione, Ron), but also a matching (Ron, Hermione). So every time we have a \((x,y)\) we also have the matching \((y,x)\), which is the definition of symmetry. Is it antisymmetric? No, because (among other things) both (Harry, Ron) and (Ron, Harry) are present. Finally, is it transitive? No. We have (Harry, Ron) and (Ron, Hermione), which means that if it’s transitive we would have to also have (Harry, Hermione) in there, which we don’t. So it’s not transitive. Remember: to meet any of these properties, they have to fully apply. “Almost" only counts in horseshoes.

Let’s try another example:

(Ron, Harry)
(Ron, Ron)
(Harry, Harry)
(Hermione, Hermione)
(Harry, Hermione)
(Hermione, Harry)

Is this one reflexive? Yes. We’ve got all three wizards appearing with themselves. Is it symmetric? No, since (Ron, Harry) has no match. Is it antisymmetric? No, since (Harry, Hermione) does have a match. Is it transitive? No, since the presence of (Ron, Harry) and (Harry, Hermione) implies the necessity of (Ron, Hermione), which doesn’t appear, so no dice.

Partial orders and posets

A couple of other fun terms: an endorelation which is (1) reflexive, (2) antisymmetric, and (3) transitive is called a partial order. And a set together with a partial order is called a partially ordered set, or “poset" for short. The name “partial order" makes sense once you think through an example.

You may have noticed that when dogs meet each other (especially male dogs) they often circle each other and take stock of each other and try to establish dominance as the so-called “alpha dog." This is a pecking order of sorts that many different species establish. Now suppose I have the set \(D\) of all dogs, and a relation “isAtLeastAsToughAs" between them. The relation starts off with every reflexive pair in it: (Rex, Rex), (Fido, Fido), etc. This is because obviously every dog is at least as tough as itself. Now every time two dogs \(x\) and \(y\) encounter each other, they establish dominance through eye contact or physical intimidation, and then one of the following ordered pairs is added to the relation: either \((x,y)\) or \((y,x)\), but never both.

I contend that in this toy example, “isAtLeastAsToughAs" is a partial order, and \(D\) along with isAtLeastAsToughAs together form a poset. I reason as follows. It’s reflexive, since we started off by adding every dog with itself. It’s antisymmetric, since we never add both \((x,y)\) and \((y,x)\) to the relation. And it’s transitive, because if Rex is tougher than Fido, and Fido is tougher than Cuddles, this means that if Rex and Cuddles ever met, Rex would quickly establish dominance. (I’m no zoologist, and am not sure if the last condition truly applies with real dogs. But let’s pretend it does.)

It’s called a “partial order" because it establishes a partial, but incomplete, hierarchy among dogs. If we ask, “is dog X tougher than dog Y?" the answer is never ambiguous. We’re never going to say, “well, dog X was superior to dog A, who was superior to dog Y …but then again, dog Y was superior to dog B, who was superior to dog X, so there’s no telling which of X and Y is truly toughest." No. A partial order, because of its transitivity and antisymmetry, guarantees we never have such an unreconcilable conflict.

However, we could have a lack of information. Suppose Rex has never met Killer, and nobody Rex has met has ever met anyone Killer has met. There’s no chain between them. They’re in two separate universes as far as we’re concerned, and we’d have no way of knowing which was toughest. It doesn’t have to be that extreme, though: Suppose Rex established dominance over Cuddles, and Killer also established dominance over Cuddles, but those are the only ordered pairs in the relation. Again, there’s no way to tell whether Rex or Killer is the tougher dog. They’d either need to encounter a common opponent that only one of them can beat, or else get together for a throw-down.

So a partial order gives us some semblance of structure — the relation establishes a directionality, and we’re guaranteed not to get wrapped up in contradictions — but it doesn’t completely order all the elements. If it does, it’s called a total order.

---

1. Wait — how can I say that? How can there be ”the corresponding” ordered pair in a relation that has no ordered pairs?! The answer has to do with the first clause: for every ordered pair (x, y) in it. There are none of these, therefore, no (y, x)’s are required. The condition is trivially satisfied. This is common in mathematics: we say that A requires B, but this means that if A is not true, then B is not forced.