Zeal Test Series 2019: Set Theory & Algebra - Relations

Question

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= ___________

Answer 1

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$

Comments

 Deepakk+Poonia (Dee)

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

---

@akash.dinkar12

3. Let R be an Equivalence relation on set A with m equivalence classes Si,1≤i≤m then Cardinality of R

is :

$|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

---

@shaik Sir I didnt get the first point that there will be only a single Equivalence class "S” on AXA? Kindly please explain that part.