edited by
13,297 views
41 votes
41 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:

  1.  
edited by

3 Answers

Best answer
51 votes
51 votes

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.

  1. $π_4$ refining $π_2, π_3.$ 
  2. $π_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

edited by
7 votes
7 votes

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

  1. Partition P* is a refinement of the partition P if P*  covers P i.e. every point of P is a point of P*.
  2.  Take a Partition of a line P1 and P2 as
    1. $a_{0}$ $a_{1}$ $a_{2}$ $a_{3}$...$a_{n}$ 
    2. $b_{0}$ $b_{1}$ $b_{2}$ $b_{3}$…...$b_{n}$   respectively
  3. Now consider a line L having both P1 $\cup $ P2 on L
    1. 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 :)

 

 

0 votes
0 votes

SHORT TRICK

πi refines πj means every element of πi is a subset of some element of πj.

So π4 refines every partition. So it has to be at the bottom of poset diagram.

Moreover, neither π2 refines π3, nor π3 refines π2.

Also π1 is refined by every set, so it has to be at the top.


Only option (C) satisfies all the above properties, so it is the correct answer.

Answer:

Related questions

26 votes
26 votes
3 answers
1
Kathleen asked Sep 21, 2014
8,502 views
Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are:$n$ and $n$$n^2$ and $n$$n^2$ and $0$$n$ an...
64 votes
64 votes
15 answers
4
Arjun asked Jul 6, 2016
36,696 views
Consider the following segment of C-code:int j, n; j = 1; while (j <= n) j = j * 2;The number of comparisons made in the execution of the loop for any $n 0$ is:$\lceil \...