GATE CSE 1998 | Question: 11

Question

Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A

$\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$

1. List the ordered pairs of the equivalence relations induced by $\Pi_1$.

2. Draw the graph of the above equivalence relation.

3. Let $\Pi_2 = \left\{\left\{a\right\}, \left\{b\right\}, \left\{c\right\}, \left\{d\right\}\right\}$

    $\Pi_3 = \left\{\left\{a, b, c, d\right\}\right\}$

   and $\Pi_4 = \left\{\left\{a, b\right\}, \left\{c,d\right\}\right\}$

   Draw a Poset diagram of the poset, $\left\langle\left\{\Pi_1, \Pi_2, \Pi_3, \Pi_4\right\}, \text{ refines } \right\rangle$.

Comments

part C answer https://gateoverflow.in/137473/%23settheory

---

Few sources about “refines” :

https://math.stackexchange.com/a/92235/606943

 

A partition $P_1$ is called a refinement of the partition $P_2$ if every set in $P_1$ is a subset of one of the sets in $P_2$

-Discrete Mathematics and Its Applications – Rosen [5^th edition, Exercise 7.5].

---

For Complete Details of “Refinement of a Partition” with ALL possible variations, GATE questions, and also Applications in Theory of Computation,

Watch the following lecture:

Refinement of a Partition - Complete Details & Analysis

For this GATE 1998 Q 11:

Detailed Video Solution of GATE CSE 1998 Question 11 Refinement of a Partition

Answer 1

a. For Calculating Ordered Pairs Just multiply the partition with itself.

$ \{a,b,c\} * \{a,b,c\} = \{ (a,a),(a,b),(a,c),(b.a),(b,b),(b,c),(c,a),(c,b),(c,c)\}$

$ \{d\}*\{d\} = \{(d,d)\}$

$\therefore$ The ordered pairs of the equivalence relations are $= \{ (a,a),(a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c),(d,d) \}$

---

b. For each ordered pair $(a,b)$ in the equivalence relation just make a directed edge from a towards $b$.

---

c. Suppose we have two partitions of a set $S:P_1={A_1,A_2,A_3...}\ and\ P_2={B_1,B_2,B_3...}$

We say that $P_1$ is a refinement of $P_2$ if every $A_i$ is a subset of some $B_j$ . Or We can say that $P_1$ refines $P_2$

---

Additional Note :-

First read definition of refinement given above then relate it to this example.

Refinement means refining/filtering elements.

Suppose like we have { water, ice, sugar, rasna }

now someone told you to make sugarfree rasna so you keep sugar aside like {{water,ice,rasna},{sugar}}

now someone told you to not to put ice in rasna so you do keep ice aside like {{water,rasna,sugar},{ice}}

i.e. {{water,ice,rasna},{sugar}} and {{water,rasna,sugar},{ice}} are refined versions of  { water, ice, sugar, rasna }  in one you have refined sugar and in other you refined ice.

now someone told you to make sugarfree rasna and also not add ice then you do like {{water,rasna},{ice,sugar}}.

Now this is another refined version of  { water, ice, sugar, rasna } and not refined version of  {{water,ice,rasna},{sugar}} or {{water,rasna,sugar},{ice}} . why ?

because {ice,sugar} is not a subset of {water,ice,rasna} or {water,rasna,sugar} but it is a subset of { water, ice, sugar, rasna }

Comments

YES ...i got little confused with harshpeswani's comment.

---

Thanks, now got the concept clearly.

---

@Satbir

How the Graph in part B is not antisymmetric?

There can’t be an edge b/w $\\\prod 1 \:and \: \prod 2$ or 2 edges in opposite direction b/w any partition.

Answer 2

(a) The ordered pairs of the equivalence relations induced $= \{ (a,a),(a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c),(d,d) \}$

PS: equivalence relations = each partition in power set - $\phi$

Comments

@codingo1234-Do you know what refines relation means?

---

@Ayush Upadhyaya,earlier I was not knowing what "refines relation" means ,but I saw Sourav Basu's comment and came to know about when a partition is refinement of other

"A partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that α ≤ ρ." ,

but I was confused regarding drawing graph of equivalence relation of part(a) and I was thinking about hasse digaram(god knows  why everything mixes up in mind),I think it will be directed graph,am i correct?

 

---

@Ayush Upadhyaya Can you please provide a resource to read two-way theorem? 

Answer 3

for C)

https://gateoverflow.in/1224/gate2007-26 check this 

Answer 4

List the ordered pairs of the equivalence relations induced by Π1.

 

Partitions of an equivalence relation are also called equivalence classes.

They go by the property that all the elements in a partition are related to each other, and none of them is related to any element of any other partition.

Example, if A and B are two partitions of some set S, then every element in A relates to all other elements in A.

Also, $A\cup B \cup C\cup D...\cup N = Original$ $Set$

$A\cap B \cap C\cap D...\cap N = \phi$

where A,B,C..,N are partitions of S.

 

Since every element in a partition is related to each other; cross-product a partition with itself to obtain the equivalence relation.

So, $\left \{ (a,a),(a,b),(a,c),(b.a),(b,b),(b,c),(c,a),(c,b),(c,c), (d,d) \right \}$

---

Draw the graph of the above equivalence relation.

In any relation, we all know that (a,b) means a relates to b. NOT b relates to a, too. So for (a,b) and (b,a) we need two directed edges.

---

 

Draw a Poset diagram of the poset...

A "refines" B means that A is finer than B. Or B is coarser than A. In plain English a finer particle would be smaller than a coarser particle. So, A refines B could loosely mean that A has smaller elements than B.

So,

   Π3

  /      \

Π4    Π1

  \     /

   Π2