Dark Mode

11,028 views

39 votes

Consider the set $S =\{ a , b , c , d\}.$ Consider the following $4$ partitions $π_1,π_2,π_3,π_4$ on

$S : π_1 =\{\overline{abcd}\},\quad π_2 =\{\overline{ab}, \overline{cd}\},$ $\quad π_3 = \{\overline{abc}, \overline{d}\},\quad π_4 =\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\}$.

Let $\prec$ be the partial order on the set of partitions $S' = \{π_1,π_2,π_3,π_4\}$ defined as follows: $π_i \prec π_j$ if and only if $π_i$ refines $π_j$. The poset diagram for $(S',\prec)$ is:

4

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 2007 Q 26:

Detailed Video Solution of GATE CSE 2007 Question 26 Refinement of a Partition

3

48 votes

Best answer

Answer is option C.

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

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

Refer https://www.cs.sfu.ca/~ggbaker/zju/math/equiv-rel.html

$π_4 $ refines all of them.

- $π_4$ refining $π_2, π_3.$
- $π_4$ & $π_2$ refining $π_1.$ $π_4$ & $π_3$ refining $π_1.$ $( π_2$ refines $π_1,$ i.e., $(ab)$ and $(cd)$ in $π_2$ are joined as $(abcd)$ in $π_1.$ And $π_3$ refining $π_1$ i.e., $(abc) (d)$ in $π_3$ are joined as $(abcd)$ in $π_1)$

That symbol $(\overline {x} )$ represents a **partition** $\ldots \overline{x}$ means $(x).$

As it is poset we are not showing transitive dependency.

Partition concept :- https://en.wikipedia.org/wiki/Partition_of_a_set

6 votes

**$\text{Some Mathematical Preliminaries to answer this question}$**

- Partition P* is a refinement of the partition P if P* covers P i.e. every point of P is a point of P*.
- Take a Partition of a line P1 and P2 as
- $a_{0}$ $a_{1}$ $a_{2}$ $a_{3}$...$a_{n}$
- $b_{0}$ $b_{1}$ $b_{2}$ $b_{3}$…...$b_{n}$ respectively

- Now consider a line L having both P1 $\cup $ P2 on L
- i.e. L has all the points $a_{0}$ $a_{1}$ $a_{2}$ $a_{3}$...$a_{n}$ ,$b_{0}$ $b_{1}$ $b_{2}$ $b_{3}$…...$b_{n}$

If P1 and P2 are two different partitions of the interval [a,b] then P* = p1 $\cup$ P2 is the common refinement of P1,P2

$Now$ $we$ $are$ $eligible$ $to$ $answer$ $this$ $question$

$Given: $ S is partitioned into 4 sets $\pi_{1}$, $\pi_{2}$, $\pi_{3}$ and $\pi_{4}$ given below.

$Solution:$

As per our knowledge on refinement, we can say that,

$\pi_{1}$ = {abcd}

$\pi_{2}$ = {ab,cd}

$\pi_{3}$ = {abc,d}

$\pi_{4}$= {a,b,c,d}

Now, let us draw the Hassey Diagram for the relationship between these partitions.

Imagine the elements as the different colored boxes, in order to understand the beauty of mathematics :)