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).