More About Relations

Why classify relations at all? Because once you know which properties a relation has, you instantly know how it behaves. Reflexive + symmetric + transitive forces a partition (equivalence classes, §4.5). Reflexive + antisymmetric + transitive forces an ordering (§4.4). The three or four small properties below recur everywhere in algebra, logic, computer science, and database design. Getting fluent at spotting these properties, and at building counterexamples when one fails, is the core skill of this chapter.

The four properties

Let $R$ be a relation on a set $A$. We say $R$ is:

• reflexive if $\forall a \in A,, aRa$, everyone is connected to themselves.
• symmetric if $\forall a, b \in A,, aRb \Rightarrow bRa$, arrows come in pairs.
• transitive if $\forall a, b, c \in A,, (aRb \wedge bRc) \Rightarrow aRc$, chains shortcut.
• antisymmetric if $\forall a, b \in A,, (aRb \wedge bRa) \Rightarrow a = b$, the only two-way arrows are self-loops.

To prove a property holds, show the universal statement for all relevant elements. To disprove it, exhibit a single counterexample, one bad pair (or chain) is enough.

Composition of relations

Given $R \subseteq A \times B$ and $S \subseteq B \times C$, the composition $S \circ R \subseteq A \times C$ is

To get an $(a, c)$ pair in $S \circ R$, you need a "stepping-stone" $b$ that links $a$ to $c$ in two hops. Composition is associative: $T \circ (S \circ R) = (T \circ S) \circ R$. It is generally not commutative. A useful identity: $(S \circ R)^{-1} = R^{-1} \circ S^{-1}$, the order reverses, just like for inverse functions.

Pause and think: The "is parent of" relation on a set of people. Is it reflexive? Symmetric? Antisymmetric? Transitive? Build a single counterexample for each property that fails. (Hint: a person is not their own parent; parents don’t parent their parents; if A parents B and B parents C, is A automatically a parent of C?)

Try it

• For $R = {(1,1),(2,2),(3,3),(1,2),(2,1)}$ on ${1,2,3}$, check all four properties.
• Show by counterexample that "is a friend of" is generally not transitive.
• Compute $R \circ R$ when $R = {(1,2),(2,3),(3,1)}$. Then compute $R \circ R \circ R$.
• Predict: if $R$ is symmetric, what does $R \circ R$ look like? Test with a small example.
• Is the relation $<$ on $\mathbb{Z}$ antisymmetric? Argue from the definition.

A trap to watch for

Many students confuse antisymmetric with asymmetric or with "not symmetric." Antisymmetric does not mean "no pairs come in both directions", it allows the pair $(a, a)$ (since trivially $a = a$). So the equality relation ${(1,1),(2,2),(3,3)}$ is both symmetric and antisymmetric. The two properties are not opposites, both can hold. The condition is: if you ever have both $aRb$ and $bRa$, then $a$ must equal $b$. (For the record: an asymmetric relation requires $aRb \Rightarrow \neg bRa$, which forbids self-loops; that is strictly stronger than antisymmetric.)

What you now know

You can list the four basic properties of relations, prove each one with a universal argument, disprove each with a single counterexample, and compose two relations to chain their reach. Section 4.4 specialises to relations that are reflexive + antisymmetric + transitive, orderings, and §4.5 to relations that are reflexive + symmetric + transitive, equivalences.

References

• Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §4.3.
• Hammack, R. (2018). Book of Proof, ch. 11.
• Bloch, E. D. (2011). Proofs and Fundamentals (2nd ed.). Springer, ch. 5.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, §25.2 (transitive closure).