Relations

On a social network, “follows” and “is friends with” are both connections between people, but they behave differently. If Ana is friends with Ben, Ben is friends with Ana. If Ana follows a celebrity, the celebrity almost certainly doesn’t follow her back.

A relation is any rule that connects pairs of things: “is friends with”, “is taller than”, “has the same birthday as”, “must be done before”. A few simple properties tell you a lot about a relation, and once you can name them, you can predict how it behaves, and which algorithms can use it.

Two kinds come up again and again. Equivalence relations, like “has the same birthday as”, sort things into groups. Orders, like “must be done before”, line things up, which is how your computer decides what to install first or which spreadsheet cell to recalculate first.

The real words

• A relation $R$ on a set $A$ is a subset of $A \times A$, the set of all ordered pairs. Write $a \sim b$ (or $a \mathrel{R} b$) when $(a, b) \in R$.
• The reflexive, symmetric, transitive properties:
  • Reflexive: $a \sim a$ for every $a$. (“Same birthday as”: yes. “Less than”: no.)
  • Symmetric: if $a \sim b$ then $b \sim a$. (“Friends with”: yes. “Follows”: no.)
  • Transitive: if $a \sim b$ and $b \sim c$ then $a \sim c$. (“Less than”: yes. “Friends with”: no, a friend of a friend may be a stranger.)
  • Each property is a $\forall$ statement (F05 lesson 6), which is why the code above uses all().
• An equivalence relation is reflexive, symmetric and transitive. It splits the set into equivalence classes: groups where everything is related to everything else, and the groups don’t overlap.
  • “Same remainder when divided by 3” splits the integers into three classes: $\{\ldots, 0, 3, 6, \ldots\}$, $\{\ldots, 1, 4, 7, \ldots\}$ and $\{\ldots, 2, 5, 8, \ldots\}$. This is the heart of modular arithmetic (lesson 17).
• A partial order is reflexive, antisymmetric (if $a \sim b$ and $b \sim a$ then $a = b$) and transitive, like $\le$ on numbers or $\subseteq$ on sets. “Partial” because some pairs may not be comparable at all: neither task has to come before the other.