GATE CS 1998 Q1.6 — Sets, Relations and Functions

An equivalence relation $R$ on a finite set $A$ is a subset of the Cartesian product $A \times A$ that satisfies the reflexive, symmetric, and transitive properties.

To find the largest equivalence relation on $A$ (where $|A| = n$), we consider the universal relation:

Let us verify if $R_{max}$ is an equivalence relation:

• Reflexive: Since every element $a \in A$ pairs with itself, $(a, a) \in A \times A$ for all $a \in A$.
• Symmetric: For any $a, b \in A$, if $(a, b) \in A \times A$, then $(b, a) \in A \times A$ is also trivially true.
• Transitive: For any $a, b, c \in A$, if $(a, b) \in A \times A$ and $(b, c) \in A \times A$, then $(a, c) \in A \times A$ is also true.

Since $R_{max} = A \times A$ satisfies all three properties, it is a valid equivalence relation. Since it contains all possible ordered pairs of $A$, no relation on $A$ can have more elements than $R_{max}$.

The number of elements in $R_{max}$ is:

Note: The smallest equivalence relation on $A$ is the identity relation $I_A = \{(a, a) \mid a \in A\}$, which contains exactly $n$ elements.