Types of Relations and Equivalence Relations | NIMCET

Quick answer: A relation R on a set A is reflexive if $(a, a) \in R$ for every $a \in A$ , symmetric if $(a, b) \in R$ implies $(b, a) \in R$ , and transitive if $(a, b)$ and $(b, c)$ in R imply $(a, c) \in R$ . A relation with all three properties is an equivalence relation, and it splits A into disjoint equivalence classes.

Relations are subsets of $A \times A$ ; see the Cartesian product and relations for the basics.

The properties

Property	Condition
Reflexive	$(a, a) \in R$ for all $a \in A$
Symmetric	$(a, b) \in R \Rightarrow (b, a) \in R$
Antisymmetric	$(a, b) \in R$ and $(b, a) \in R \Rightarrow a = b$
Transitive	$(a, b), (b, c) \in R \Rightarrow (a, c) \in R$
Equivalence	Reflexive, symmetric and transitive

Other special relations:

Empty relation: $R = \phi$ . It is symmetric and transitive, but not reflexive on a non-empty set.
Universal relation: $R = A \times A$ . It is an equivalence relation.
Identity relation: $I_A = \{(a, a) : a \in A\}$ . It is an equivalence relation.

Testing standard examples

Relation	Reflexive	Symmetric	Transitive
$a = b$ on ℝ	Yes	Yes	Yes
$a \le b$ on ℝ	Yes	No	Yes
$a < b$ on ℝ	No	No	Yes
$a$ divides $b$ on ℕ	Yes	No	Yes
Lines: $L_1 \perp L_2$	No	Yes	No
Lines: $L_1 \parallel L_2$ or equal	Yes	Yes	Yes
$a - b$ divisible by $n$ on ℤ	Yes	Yes	Yes
$\lvert a - b\rvert \le 1$ on ℝ	Yes	Yes	No

The relation "≤" is reflexive, antisymmetric and transitive; such a relation is called a partial order.

Equivalence classes

For an equivalence relation R on A, the equivalence class of $a$ is

$[a] = \{x \in A : (x, a) \in R\}$

Key facts:

Any two classes are either equal or disjoint.
The union of all classes is A.

Example: Congruence modulo 3 on ℤ, $a\,R\,b$ if $3 \mid (a - b)$ , has three classes: $[0]$ , $[1]$ and $[2]$ (numbers with remainder 0, 1 and 2).

Counting relations on a set with n elements

Type	Number
All relations	$2^{n^2}$
Reflexive	$2^{n^2 - n}$
Symmetric	$2^{\frac{n(n + 1)}{2}}$
Reflexive and symmetric	$2^{\frac{n(n - 1)}{2}}$
Antisymmetric	$2^n \cdot 3^{\frac{n(n - 1)}{2}}$

Why reflexive gives $2^{n^2 - n}$ : the $n$ diagonal pairs must be included; each of the other $n^2 - n$ pairs can be in or out.

Worked examples

Example 1: checking a relation

On $A = \{1, 2, 3\}$ , let $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ .

Reflexive: all $(a, a)$ are present ✓.
Symmetric: $(1, 2)$ and $(2, 1)$ are both present ✓.
Transitive: $(1, 2), (2, 1)$ give $(1, 1)$ , which is present ✓.

So R is an equivalence relation with classes $\{1, 2\}$ and $\{3\}$ .

Example 2: the smallest equivalence relation

On $A = \{1, 2, 3\}$ , the smallest equivalence relation containing $(1, 2)$ is $\{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ , which has 5 pairs.

Example 3: counting

How many reflexive relations are there on a set of 3 elements?

$2^{9 - 3} = 2^6 = 64$ .

Example 4: not transitive

On ℝ, $R = \{(a, b) : \lvert a - b\rvert \le 1\}$ . Then $(0, 1)$ and $(1, 2)$ are in R, but $(0, 2)$ is not. So R is not transitive.

Summary table

Type	Quick test
Reflexive	Every element is related to itself
Symmetric	Every pair has its reverse
Transitive	Every chain a → b → c has a shortcut a → c
Equivalence	All three; gives disjoint classes
Reflexive count	$2^{n^2 - n}$

Exam tips

To disprove a property, one counterexample is enough.
A relation with only diagonal pairs is automatically symmetric and transitive.
Learn the table of standard examples; "perpendicular to" and "divides" appear often.
Equivalence classes form a partition of the set.

Next, study functions, domain, codomain and range, or see the NIMCET Set Theory chapter.

Common mistakes

Calling a relation reflexive when only some elements have $(a, a)$ .
Assuming the empty relation is not transitive; it is, because there are no pairs to check.
Treating antisymmetric as the opposite of symmetric; a relation can be both.
Forgetting the pair $(a, a)$ when checking transitivity for $(a, b)$ and $(b, a)$ .

Frequently Asked Questions

What is an equivalence relation?

A relation that is reflexive, symmetric and transitive.

How many reflexive relations are there on a set with n elements?

There are 2^(n² − n) reflexive relations.

Is the relation "less than or equal to" an equivalence relation?

No. It is reflexive and transitive but not symmetric.

What is an equivalence class?

The equivalence class of a is the set of all elements related to a. Different classes never overlap.

Can a relation be both symmetric and antisymmetric?

Yes. The identity relation, which contains only pairs (a, a), is both symmetric and antisymmetric.