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

The largest equivalence relation will be when every element is related to every other element

So, A=IAxAI

     A=n^2