Types of Relations

The four definitions

A relation $R$ on a set $A$ is a collection of ordered pairs from $A$. It is:

• Reflexive if $(a,a) \in R$ for every $a \in A$.
• Symmetric if $(a,b) \in R$ always forces $(b,a) \in R$ too.
• Transitive if $(a,b) \in R$ and $(b,c) \in R$ together force $(a,c) \in R$.
• An equivalence relation if it's all three at once: reflexive, symmetric, and transitive.

Worked example: reflexive and transitive, but not symmetric

Show that the relation $R = \{(a,b) : a \le b\}$ on the real numbers is reflexive and transitive, but not symmetric.

Solution: $a \le a$ is always true, so $R$ is reflexive. If $a \le b$ and $b \le c$, then $a \le c$, so it's transitive too. But $a \le b$ doesn't force $b \le a$ (e.g. $1 \le 2$, but $2 \le 1$ is false), so $R$ is not symmetric, and therefore not an equivalence relation.

Worked example: checking symmetry directly

Is $R = \{(a,b) : a-b \text{ is divisible by } 5\}$ symmetric on $\mathbb{Z}$?

Solution: If $5$ divides $a-b$, then it also divides $b-a = -(a-b)$ (a divisor of a number always divides its negative). So $R$ is symmetric.

Worked example: fixing a relation to make it symmetric

On $A=\{a,b,c\}$, let $R = \{(a,a),(a,b),(a,c),(b,c),(c,a)\}$. Which pairs need to be added to make $R$ symmetric?

Solution: Check each pair for its reverse: $(a,a)$ is its own reverse, fine. $(a,b)$ needs $(b,a)$: missing. $(a,c)$ needs $(c,a)$: already there. $(b,c)$ needs $(c,b)$: missing. $(c,a)$ needs $(a,c)$: already there. So $(b,a)$ and $(c,b)$are exactly what's missing.