GATE CSE 2007 | Question: 2

Question

Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are:

• A. $n$ and $n$
• B. $n^2$ and $n$
• C. $n^2$ and $0$
• D. $n$ and $1$

Comments

Refer  --> https://math.stackexchange.com/questions/1081333/prove-that-the-empty-relation-is-transitive-symmetric-but-not-reflexive

Answer 1

Answer is B.

Equivalence relation means it is reflexive, symmetric and transitive

If a relation is reflexive then it must have all the pairs of diagonal elements and relation with only diagonal elements is also symmetric and transitive. Therefore smallest such relation is of size $n.$

With diagonal elements, we can include all the elements as well.  Therefore largest equivalence relation is of size $n^2.$

Comments

when we include all the element's of the sets(for making it largest set) then there would be no way it is not equivalence,because we include all the elements which is making our relation equivalence i.e reflexive symmetric and transitive.

---

@Arjun sir I have a doubt here.

I have read that ordered pairs means : (a,b) where a != b

So here ans should be : (n^2 - n) and (0)

Please correct me

---

No, it can be a=b, an ordered pair (a, b) is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (a, b) is different from the ordered pair (b, a) unless a = b. 

Ref : https://en.wikipedia.org/wiki/Ordered_pair

Answer 2

Smallest Equivalence relation on set S = ∆ ( Diagonal relation )

                                            Number of elements in  Diagonal relation = ∣S∣  = n  

                                           So, cardinality of Smallest Equivalence relation on set S  = n

 Note: Empty relation on Non-empty set will never be an equivalence relation because it does not satisfy the reflexive property.Whereas Empty relation on empty set will always be an equivalence relation.

Largest Equivalence relation on set S = S ⨉ S = ∣ S ⨉ S ∣ = n^2

                             So, cardinality of Largest Equivalence relation on set S  = n^2

The correct answer is, (B) n^2  and n

Comments

Please explain with example for largest equivalence relation.

---

Let ,S= {a,b}

S⨉S ={(a,a),(a,b),(b,a),(b,b)}

Largest equivalence relation on S =S⨉S ={(a,a),(a,b),(b,a),(b,b)} because it follows all the three properties Reflaxive ,Symmetric and transitivity and it is the largest set .

Smallest equivalence relation on S  ={(a,a),(b,b)} and cardinality is 2.

---

thanx 4 explaining wid an e.g

Answer 3

Let S be a set of n elements say (1, 2, 3,... n).

Now the smallest equivalence relation on S must contain all the reflexive elements ((1, 1), (2, 2). (3, 3),..., (n, n)} and its cardinality is therefore n.

The largest equivalence relation on S is Sx S, which has cardinality of nxn = r².

 The largest and smallest equivalence relations on S have cardinalities of n² and n respectively.