recategorized by
5,778 views
8 votes
8 votes

Suppose $A$ is a finite set with $n$ elements.The number of elements and the rank of the largest equivalence relation on $A$ are

  1. $\{n,1\}$
  2. $\{n,n\}$
  3. $\{n^2,1\}$
  4. $\{1,n^2\}$
recategorized by

4 Answers

Best answer
12 votes
12 votes

Suppose n=3 i.e A contains 3 elements - a1,a2,a3
The largest equivalence relation is possible when every element is related to every other element.
n2 = 32 = 9 ordered pairs are possible.

Matrix for the largest Equivalence relation-
Rel(A)= $\begin{bmatrix} 1& 1 &1 \\ 1& 1& 1\\ 1& 1 & 1\end{bmatrix}$

Here Rel(Ai,j) means i is related to j

R2→R2-R1
R3→R3-R1

Rel(A)= $\begin{bmatrix} 1& 1 &1 \\ 0& 0& 0\\ 0& 0 & 0\end{bmatrix}$

Rank of the Relation Matrix = 1
 

NOTE- Rank of Equivalence Relation means "Number of equivalence classes "
Here only 1 equivalence class is possible. 
C is the correct answer -  {n2,1} 

selected by
3 votes
3 votes
Ans - option c.

because the largest equivalence relation will be when every element is related to other element so, n * n = n^2 possible ordered pair.

since each pair is related to one another for example {a1} = {a1,a2,a3} , {a2} = {a1,a2,a3} , {a3} = {a1,a2,a3}

rank means number of equivalence classes in this case it is 1, hence rank is 1

{n^2,1} is the correct answer.
0 votes
0 votes
Let A contain the elements a1,a2,a3 and equivalence relation follow rst property (reflexive,symmetric,transitive)

In largest equivalence relation every element is related to every element

 

So if A has n elements the number of elements in relation is n^2

And R is equivalence relation it divides the base set into unique partion

The rank of equivalence relation is equal to number of equivalence classes

Hence answer is (n^2,1)
edited by
Answer:

Related questions

6 votes
6 votes
3 answers
1
gatecse asked Dec 17, 2017
2,650 views
If $C$ is a skew-symmetric matrix of order $n$ and $X$ is $n\times 1$ column matrix, then $X{^T} CX$ is ascalar matrixnull matrixunit matrixmatrix will all elements $1$
1 votes
1 votes
2 answers
2
gatecse asked Dec 17, 2017
1,511 views
If vectors $\vec{a}=2\hat{i}+\lambda \hat{j}+\hat{k}$ and $\vec{b}=\hat{i}-2\hat{j}+3\hat{k}$ are perpendicular to each other, then value of $\lambda$ is$\dfrac{2}{5}$ $2...
9 votes
9 votes
2 answers
3
gatecse asked Dec 17, 2017
3,706 views
Consider the following $C$ function#include<stdio.h int main(void) { char c[]="ICRBCSIT17" char *p=c; printf("%s",c+2[p]-6[p]-1); return 0; }The output of the program is ...
5 votes
5 votes
2 answers
4
gatecse asked Dec 17, 2017
2,723 views
Which of the following related to snowflake schema is true?Each dimension is represented by a single dimensional tableMaintenance efforts are lessDimension tables are nor...