The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

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$
asked in Set Theory & Algebra by Veteran (52k points)
retagged by | 2.4k views

2 Answers

+22 votes
Best answer
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$
answered by Loyal (8.1k points)
edited by
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
nopes. Because that relation won't be reflexive.
for be reflexive relation u should include all diagonals elements

becoz smallest reflexive relation is all diagonals elemnents not { }.
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.:)
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.
+10 votes

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
answered by Loyal (7.5k points)
edited by
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,121 answers
71,035 users