GATE CS 2007 Q2 — Sets, Relations and Functions

An equivalence relation on a set $S$ must satisfy three properties: reflexivity, symmetry, and transitivity.

• Smallest Equivalence Relation: To satisfy reflexivity, every element $x \in S$ must be related to itself. Thus, the relation must contain at least the identity relation: $$I_S = \{(x, x) \mid x \in S\}$$ Since $I_S$ is also symmetric and transitive, it is the smallest equivalence relation on $S$. The number of ordered pairs in $I_S$ is exactly $n$.
• Largest Equivalence Relation: The largest possible relation on $S$ is the universal relation (Cartesian product of $S$ with itself): $$U_S = S \times S$$ Since $U_S$ is reflexive, symmetric, and transitive, it is the largest equivalence relation on $S$. The number of ordered pairs in $U_S$ is $n \times n = n^2$.

Therefore, the number of ordered pairs in the largest and smallest equivalence relations are $n^2$ and $n$, respectively.