Relations

Reflexive, symmetric, transitive — and the transitive closure.

The idea

A relation on a set records which elements stand in a given relationship to which others, as "is less than", "divides" and "has the same birthday as" each do. All the information lies in the pairs for which the relationship holds, so we define a relation $R$ on a set $S$ to be a set of ordered pairs of elements of $S$, and write $a\,R\,b$ to mean $(a, b) \in R$, read as "$a$ is related to $b

Relations are classified by the properties their pairs satisfy; three are fundamental.

- Reflexive: $(a, a) \in R$ for every $a \in S$ — each element is related to itself. - Symmetric: whenever $(a, b) \in R$, also $(b, a) \in R$. - Transitive: whenever $(a, b) \in R$ and $(b, c) \in R$, also $(a, c) \in R$.

Each property is checked directly against the list of pairs. Confirming one means checking every required case; refuting one takes a single missing pair.

Ways to work on it

• Walkthrough. Test the three core properties on one relation.
• Practice. Decide whether a small relation has a named property.
• Hardest. Build the transitive closure of a chain.

Not sure where to start? Take the ten-question placement test.