GATE CSE 1998 | Question: 1.6

Question

Suppose $A$ is a finite set with $n$ elements. The number of elements in the largest equivalence relation of A is

• A. $n$
• B. $n^2$
• C. $1$
• D. $n+1$

Comments

Smallest = n

---

please share some resource

---

Lectures on NPTEL and then solving their assignments.

---

Let ‘R’ be the equivalence relation on set ‘A’. 

R will have equivalence classes. The set of equivalence classes is known as the partition of set A. In each equivalence class, all the elements are related to each other. 

Let the set be A = {a, b, c, d} ; R is an equivalence relation on set A.

The possible partitions can be: { {a}, {b,c}, {d} }, { {a,b}, {c,d} }, { {a,b,c,d}}, {{a}, {b,c,d}} and so on. In first partition total equivalence relation possible are |R| = 1 + 4 +1=6. in second partition |R| = 4 + 4 = 8. and so on. 

The biggest equivalence class will form the biggest equivalence relation. or the maximum number of equivalence relations will be possible when all the elements of the set A are in the same equivalence class.

So partition for this case will look like π: { {a,b,c,d} }. and eq. class will be [a] = {a,b,c,d}.

So largest equivalence relation possible is |R| = 4*4 = 16. for n element set largest relation possible will be n*n.

 

source: an excellent lecture on this topic. Link. set-theory lecture 6.

 

Answer 1

Answer is $B$.

The largest equivalence relation will be when every element is related to every other element. So, $n \times n = n^2$ possible ordered pairs.

Comments

xpln?

---

Explained..

---

is there a difference withe these two statements:

Suppose A is a finite set with n elements.

Suppose A is a finite set of n elements.

---

Nope

---

Hi Sir, but what will be the number of equivalence classes on this set i,e AXA?

---

There is no condition defined for the relation so it is not possible to find equivalence classes.

Some facts about the realation can be known without it being defined, like, the number of elements in the largest equivalence relation.

---

shouldn't the explanation say every element is related to every other element as well as itself?

---

@aryavart  largest possible relation implies that every element is related with every other element as well as itself so the number of equivalence classes in this case is 1. as equivalence class is nothing but a subset of the Set on which a relation is defined where within that subset every element is related to itself as well as the other elements of that subset.

Answer 2

∣A∣ =n

Largest equivalence relation on set A = A ⨉ A

And the Number of elements in the Largest equivalence relation on set A = ∣A ⨉ A∣ = n^2

The correct answer is (B) n^2

Answer 3

Largest equivalent relation will be the Cartesian product of both the sets. so $n \times n=n^2$ is the answer

Answer 4

|(1,1)                         |   

|  (2,2)                       |

|     ……..                  |

|          ………           |

|                        (n,n)|

 

on the above matrix of n*n 

largest Reflaxive Relation will be : n*n (must be diagonal + non_diagonal present for the purpose of largest)

largest symmetric Relation will be : n*n (diagonal + non_diagonal present for the purpose of largest)

largest Transitive Relation will be : n*n (diagonal + non_diagonal present for the purpose of largest)

 

then conclusion should be for equivalance rel.  ref , symm , trans 

largest equi. rel . = N*N

 

Please  correct if i am wrong 

Thank you !!