Bro can u give us the link of proof that u are saying about in 3rd point??

Dark Mode

591 views

2 votes

Let S$_1$, S$_2$ and S$_3$ are non-empty subsets of set S with cardinality 7 (i.e., |S| = 7),

such that $\bigcup_{i=1}^{3}S_i$ = S and S$_1$ $\cap$ S$_2$ = S$_1$ $\cap$ S$_3$ = S$_2$ $\cap$ S$_3$ = ∅.

Therefore, we can say that S$_1$,S$_2$,S$_3$ are partition set of S, Let R is equivalence relation on S with equivalence class S$_1$, S$_2$ and S$_3$. If x is the maximum cardinality of R and Y is the minimum cardinality of R then X+Y= ___________

such that $\bigcup_{i=1}^{3}S_i$ = S and S$_1$ $\cap$ S$_2$ = S$_1$ $\cap$ S$_3$ = S$_2$ $\cap$ S$_3$ = ∅.

Therefore, we can say that S$_1$,S$_2$,S$_3$ are partition set of S, Let R is equivalence relation on S with equivalence class S$_1$, S$_2$ and S$_3$. If x is the maximum cardinality of R and Y is the minimum cardinality of R then X+Y= ___________

5 votes

Best answer

**Answer : 44**

Before heading to the answer of this question, Let's talk about some general concepts/observations regarding Equivalence Relations.

1. Let $A$ be a Set of $n$ elements. Then $A \times A$ is the biggest relation possible on set $A$ (in terms if cardinality) and

$|A \times A| = n^2$ and $A\times A$ is an Equivalence relation on set $A$ with Only one Equivalence class $S$ which is same as the set $A.$

2. Let $A$ be a Set of $n$ elements. Then Identity relation $I$ ( $(a,a) \in I, \forall a\in A $) is the smalles Equivalence relation possible on set $A$ (in terms if cardinality) and It has $n$ Equivalence classes, each consisting one element of $A.$

3. Let $R$ be an Equivalence relation on set $A$ with $m$ equivalence classes $S_i, 1\leq i \leq m$ then Cardinality of $R$ is :

$|R| = |S_1|^2 + |S_2|^2....+|S_m|^2$

Which is easy to prove because we can see that an Equivalence class with $t$ elements contributes $t^2$ ordered pairs in the Equivalence relation $R.$

In the Question, Since it is given that the Equivalence relation $R$ has Three equivalence classes $S_1,S_2,S_3$, Hence,

$|R| = |S_1|^2 + |S_2|^2 + |S_3|^2$

We need to make the above value minimum and maximum.

For getting minimum cardinality of $R$, Divide elements of set $S$ uniformly among the three equivalence classes i.e. $|S_1|, |S_2| = 2, |S_3| = 3$, hence, $Y = 17$

For getting maximum cardinality of $R$, Divide elements of set $S$ among the three equivalence classes such that One of them has biggest number possible i.e. $|S_1|, |S_2| = 1, |S_3| = 5$, hence, $X = 27$

Hence, $X+Y = 44$

3. Let

Rbe an Equivalence relation on setAwithmequivalence classesSi,1≤i≤mthen Cardinality ofRis :

$|R|=|S1|^2+|S2|^2....+|Sm|^2$

Why this is true ?

let analyses a sample input A = {1,2,3,4,5}

if i want to say, there are 2-equivalence classes with $\color{red}{[1]_{R} \; = \;[2]_{R}\; = \;[3]_{R}}$ and $\color{green}{[4]_{R}\; =\; [5]_{R}}$

Actually, $[x]_{R}$ = { y | x R y }

if $[1]_{R}$ = $[2]_{R}$ means, $[1]_{R}$ should contains 2 ==> (1,2) should be in relation

if $[1]_{R}$ = $[3]_{R}$ means, $[1]_{R}$ should contains 3 ==> (1,3) should be in relation

if $[2]_{R}$ = $[3]_{R}$ means, $[1]_{R}$ = $[1]_{R}$ should contains 3 ==> (2,3) should be in relation

∴ due to symmetric property, (2,1) and (3,1) and (3,2) should be in the relation

∴ due to reflexivity property, (1,1), (2,2) and (3,3) should be in the relation.

with three elements, we can get 3*3 = 9 ordered pairs !

(1,1) (2,1) (3,1)

(1,2) (2,2) (3,2)

(1,3) (2,3) (3,3)

All these pairs should be in my R, if i want to say $[1]_{R}$ = $[2]_{R}$ = $[3]_{R}$ ==> S$_1$ with 3 elements

like that, with three elements, we can get 3*3 = 9 ordered pairs !

(4,4) (5,4)

(5,4) (5,5)

All these pairs should be in my R, if i want to say $[4]_{R}$ = $[5]_{R}$ ==> S$_2$ with 2 elements

3