Types of relations

A relation on a set $A$ is any subset of $A \times A$. That definition is so wide that almost everything counts as a relation. To extract useful structure we ask which special properties the relation has. Five basic types appear again and again in Class XII: empty, universal, reflexive, symmetric, and transitive. The first two are extreme; the next three describe how a relation interacts with the elements of the set.

Definitions

Let $A$ be a non-empty set and let $R \subseteq A \times A$.

• $R$ is the empty relation if $R = \varnothing$. No element is related to anything.
• $R$ is the universal relation if $R = A \times A$. Every element is related to every other.
• $R$ is reflexive if $(a, a) \in R$ for every $a \in A$.
• $R$ is symmetric if for all $a, b \in A$, $(a, b) \in R \Rightarrow (b, a) \in R$.
• $R$ is transitive if for all $a, b, c \in A$, $\{(a, b), (b, c)\} \subseteq R \Rightarrow (a, c) \in R$.

The empty and universal relations are sometimes called trivial relations because they carry no information about how individual elements compare.

Reading the quantifiers

Every property here is a universal statement. To prove $R$ is reflexive you must verify $(a, a) \in R$ for all $a$. A single missing pair destroys reflexivity. To prove $R$ is symmetric you must show the implication for all pairs $(a, b)$. To disprove any of these properties you only need one counter-example. Many students confuse the two directions and lose easy marks. Memorise the slogan: to prove a universal claim, argue generally; to refute it, exhibit one bad case.

Worked discussion

Take $A = \{1, 2, 3\}$. Consider $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$.

• Reflexive? Yes, all three diagonal pairs are present.
• Symmetric? $(1, 2) \in R$ and $(2, 1) \in R$, no other off-diagonal pairs. Yes.
• Transitive? $(1, 2)$ and $(2, 1)$ are in $R$, so we need $(1, 1) \in R$. Yes. Similarly $(2, 1), (1, 2) \Rightarrow (2, 2)$. Yes. So transitive holds.

Now consider $R' = \{(1, 2), (2, 3), (1, 3)\}$.

• Reflexive? No: $(1, 1) \notin R'$.
• Symmetric? No: $(1, 2) \in R'$ but $(2, 1) \notin R'$.
• Transitive? Check $(1, 2), (2, 3) \Rightarrow$ need $(1, 3)$. Yes, it is there. No other chain to check. So transitive holds.

The second example shows that transitivity does not require reflexivity or symmetry. The three properties are independent.

Counter-examples worth memorising

A relation can have any combination of the three properties. Here are minimal examples on $A = \{a, b, c\}$.

The last entry is subtle and often appears in JEE problems: a symmetric and transitive relation need not be reflexive on $A$. If $(a, b) \in R$ then by symmetry $(b, a) \in R$, and by transitivity $(a, a) \in R$. But this only gives reflexivity at elements that appear in some pair of $R$. An element of $A$ that never shows up forces reflexivity to fail.

A theorem and its proof

Theorem. If $R$ is reflexive and transitive on $A$, then $R \cap R^{-1}$ is an equivalence relation on $A$, where $R^{-1} = \{(b, a) : (a, b) \in R\}$.

Proof. Let $S = R \cap R^{-1}$.

Reflexive. For any $a \in A$, $(a, a) \in R$ (reflexivity of $R$) and $(a, a) \in R^{-1}$ since $(a, a) \in R$. So $(a, a) \in S$.

Symmetric. Suppose $(a, b) \in S$. Then $(a, b) \in R$ and $(a, b) \in R^{-1}$, which means $(b, a) \in R$. Also $(b, a) \in R^{-1}$ because $(a, b) \in R$. So $(b, a) \in R \cap R^{-1} = S$.

Transitive. Suppose $(a, b), (b, c) \in S$. Then $(a, b), (b, c) \in R$ so $(a, c) \in R$ by transitivity of $R$. Also $(b, a), (c, b) \in R$ for the same reason, so $(c, a) \in R$, i.e. $(a, c) \in R^{-1}$. Hence $(a, c) \in S$. $\blacksquare$

This little theorem shows the power of definitions: once you trust them and quote them carefully, proofs are mechanical.

Worked examples

Example 1. On $\mathbb{Z}$, let $a R b \iff a - b$ is even. Show $R$ is reflexive, symmetric and transitive.

• Reflexive: $a - a = 0$, even. So $(a, a) \in R$.
• Symmetric: if $a - b$ is even, then $b - a = -(a - b)$ is even.
• Transitive: if $a - b$ and $b - c$ are both even, then $(a - b) + (b - c) = a - c$ is even.

Example 2. On $\mathbb{R}$, let $a R b \iff a \le b$. Which properties hold?

• Reflexive: $a \le a$, yes.
• Symmetric: $1 \le 2$ but $2 \not\le 1$, no.
• Transitive: $a \le b$ and $b \le c$ implies $a \le c$, yes.

Example 3. On the set of all lines in a plane, let $\ell_1 R \ell_2 \iff \ell_1 \parallel \ell_2$. Take parallelism to include "the same line".

• Reflexive: every line is parallel to itself.
• Symmetric: $\ell_1 \parallel \ell_2 \Rightarrow \ell_2 \parallel \ell_1$.
• Transitive: $\ell_1 \parallel \ell_2$ and $\ell_2 \parallel \ell_3 \Rightarrow \ell_1 \parallel \ell_3$.

So $R$ has all three properties.

Example 4. On $\mathbb{Z} \setminus \{0\}$, let $a R b \iff a \mid b$. Check the three properties.

• Reflexive: $a \mid a$, yes.
• Symmetric: $2 \mid 4$ but $4 \nmid 2$, no.
• Transitive: $a \mid b$ and $b \mid c \Rightarrow a \mid c$, yes.

Example 5. On the set of all triangles in a plane, let $T_1 R T_2 \iff T_1$ is similar to $T_2$. Show $R$ is reflexive, symmetric and transitive.

This is geometric: every triangle is similar to itself (use the identity correspondence). Similarity is symmetric by reversing the correspondence. Transitivity follows from composing two similarity correspondences.

Example 6. On $A = \{1, 2, 3, 4, 5\}$, count the relations that are (i) reflexive, (ii) symmetric. Total relations: $2^{25}$.

• Reflexive: the five diagonal pairs are forced; the remaining $20$ off-diagonal pairs can be present or absent freely. Count $= 2^{20}$.
• Symmetric: pair up off-diagonal positions: $(i, j)$ and $(j, i)$ must be the same. There are $\binom{5}{2} = 10$ such pairs, each free, plus $5$ diagonal entries free. Count $= 2^{10 + 5} = 2^{15}$.

Try it yourself

1. On $\mathbb{N}$, define $a R b \iff a + b$ is even. Check the three properties.
2. On $\mathbb{Z}$, define $a R b \iff a \cdot b > 0$. Is $R$ reflexive? Symmetric? Transitive?
3. Give a relation on $\{1, 2, 3\}$ that is symmetric but neither reflexive nor transitive.
4. On the set of all books in a library, let $a R b$ mean "$a$ and $b$ share an author". Discuss the three properties.
5. Show that the universal relation on any non-empty set is reflexive, symmetric and transitive.
6. On $\mathbb{R}$, let $a R b \iff |a - b| < 1$. Is $R$ transitive? Justify.
7. How many reflexive relations are there on a set of $n$ elements?
8. How many symmetric relations are there on a set of $n$ elements?
9. Construct a relation on $\{1, 2, 3, 4\}$ that is transitive but not reflexive.
10. Prove: if $R$ and $S$ are both reflexive on $A$, then so is $R \cap S$.
11. Prove: if $R$ and $S$ are both symmetric on $A$, then so is $R \cup S$. What about $R \cap S$?
12. Show by example that the union of two transitive relations need not be transitive.
13. Let $R$ be the relation on $\mathbb{Z}$ defined by $a R b \iff a^2 = b^2$. Check the three properties.
14. Prove: if $R$ is symmetric, then $R \cap R^{-1} = R$.

Pitfalls / Tricks

• A relation can be both symmetric and antisymmetric only when it is a subset of the diagonal.
• Transitivity is vacuously true when no chain $(a, b), (b, c)$ exists; this is why singleton relations like $\{(1, 2)\}$ are transitive.
• A reflexive relation always has at least $|A|$ pairs; an empty relation on a non-empty set is never reflexive.
• The trap "symmetric + transitive $\Rightarrow$ reflexive" is false. The standard counter-example: $A = \{1, 2, 3\}$ with $R = \{(1, 1), (1, 2), (2, 1), (2, 2)\}$. Element $3$ is never reflexive.
• When checking symmetry on tabular data, scan only off-diagonal entries; the diagonal is automatically symmetric.

Mastering this section is a matter of patience: every claim is a one-line implication, and writing them out forms the backbone of every later proof in the chapter.