retagged by
8,514 views
26 votes
26 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$
retagged by

3 Answers

Best answer
33 votes
33 votes
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.$
edited by
13 votes
13 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
edited by
0 votes
0 votes

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:

Related questions

41 votes
41 votes
3 answers
1
60 votes
60 votes
5 answers
2
Kathleen asked Sep 21, 2014
19,434 views
How many different non-isomorphic Abelian groups of order $4$ are there?$2$$3$$4$$5$
34 votes
34 votes
4 answers
3
Kathleen asked Sep 21, 2014
10,012 views
What is the maximum number of different Boolean functions involving $n$ Boolean variables?$n^2$$2^n$$2^{2^n}$$2^{n^2}$