2k views

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

1. $n$ and $n$
2. $n^2$ and $n$
3. $n^2$ and $0$
4. $n$ and $1$
retagged | 2k views
0

Answer is $B$.

equivalence relation means it is reflexive, symmetric and transitive

and if the 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 is of size n.

with diagonal elements we can include all the elements therefore largest is $n^2$
edited
0
As question does not say to include all elements in equivalence relation. minimum ordered pair can be 0. So according to me answer should be C). correct me if i am wrong
+3
nopes. Because that relation won't be reflexive.
+1
for be reflexive relation u should include all diagonals elements

becoz smallest reflexive relation is all diagonals elemnents not { }.
0
n^2 would account for total elements,how does it entail equivalence relation?n^2  is the total no of ordered pairs though.Please explain.:)
+2
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.

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
edited by
0
Please explain with example for largest equivalence relation.
+4
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.
0
thanx 4 explaining wid an e.g