Let R be an equivalence relation on a finite set A having n elements. Then, the number of ordered pairs in R is
Correct Answer :
Greater than or equal to n
Solution :
The correct option is Greater than or equal to n.
Let us understand why this is the correct answer step-by-step.
Step 1: Understand the definition of an equivalence relation
Let be a finite set containing elements, which we can represent as:
An equivalence relation on set is a binary relation that satisfies three fundamental properties:
1. Reflexivity: For every element , the ordered pair must belong to .
2. Symmetry: If , then .
3. Transitivity: If and , then .
Step 2: Apply the property of Reflexivity
Since is an equivalence relation, it must be reflexive. This means that for each of the elements in the set , the relation must contain the ordered pair representing that element's relation to itself.
Therefore, the relation must contain at least the following ordered pairs:
Step 3: Determine the minimum number of ordered pairs
The list of reflexive pairs shown in Step 2 consists of exactly distinct ordered pairs. Because these pairs must be present in for it to be reflexive, the number of elements (ordered pairs) in , denoted as , cannot be less than .
Thus, we have:
Depending on the specific equivalence relation, there may be additional ordered pairs present in (for instance, the universal relation on set contains ordered pairs). Consequently, the total number of ordered pairs in is always greater than or equal to .
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Crey. Perfect for teachers and institutes.
Copyright © 2026 Crey. All Rights Reserved.