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

---

S is a set of n elements.

We are saying ordered pairs, means 2 elements of the set are forming something. Means it is something involving n elements first time, and n elements 2nd time so it is a cross product of elements of A with itself means any subset of this cross product is a binary relation of A with itself.

 

Now, the very first and must necessity of an equivalence relation is the reflexive pairs.

And since there are n elements there are n * 1 possibilities for reflexive pairs. Therefore n reflexive pairs are possible.

 

But we can also see that including just only reflexive pairs give us an equivalence relation, as there is no space for transitivity and symmetrivity follows trivially.

 

Therefore the smallest equivalence relation has n pairs.

Now for the largest equivalence relation we must see that if we include all the n square pairs (here we are saying about one relation from the subset of n square relations like for example A:{1,2} total binary relations are 2 power 4 :16 relations but the largest relation is {(1,1),(1,2),(2,1)(2,2)}) we get an equivalence relation as

1. All reflexive pairs are present.

2. All symmetric pairs are present.

3. All transitivity followed.

Hence largest equivalence relation has nnsquare ordered pairs.

 

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.

Answer 4

Atleast your relation should be reflexive for being an equivalence relation.
so min= n
and max = $n^2$

Answer 5

Let S = {1, 2, 3}

Smallest Equivalence Relation = {(1, 1), (2, 2), (3, 3)} => n

Largest Equivalence Relation = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)} => n²

 

Therefore, Correct Option :- B