The Gateway to Computer Science Excellence
+27 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:

in Set Theory & Algebra by Veteran (52.2k points)
edited by | 4.1k views

 Here refines means when smaller pockets can be combined to get bigger pockets..

For eg: π2 refines   π1  ,As  ab and cd in  π2 are joined as abcd in   π1  ..

but they are put under the same complement, Its a good observation but not some mathematically robust thing to say.

I guess the operation is like : take complement of both, product them and then complement the whole.

does πi ≺ πj here mean that πi is related to πj only if πi refines πj? Doing it this way we can form a relation as follows.

R ={(π4,π1), (π4,π2), (π4,π3), (π2,π1), (π3,π1)}

and now we can easily draw the hasse diagram.


Alomost same question was asked in 1998.


1 Answer

+36 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$.


$π_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 :-

by Boss (41.9k points)
edited by

in partition of a set, we need to put elements together, example:
for a set = { 1, 2, 3 }
partitions = { {1, 2}, {3} }

but here are no brackets, operation of taking complement is performed for the final element.

+how does your answer justify the word refinesplease elaborate

Yes you are correct. This is little confusing. I used to think it as sets( Kind of have ignored those compliments !), There might be some mistake, lets see if someone gets it.

that bar won't represent complement , it represents a partition. that is symbol used for showing each parition.

until we are sure of the word refine, we cannot accept that.

check this

even you can refer descrete maths nptel video link given in gatecse site


Are you sure about meaning of refinement now ?


yes, but that's not a good way to ask question. they should mention that bar is used as brackets.

C,D both are correct, but C is more correct than D
how D can be correct ???
π4 refines all of them(π1,π2,π3)

Neither π2 refines π3 nor π3 refines π2.

And π1 does not refines any partition.

Hence option C is correct.

Anyone can u pls give a better explanation to this question ?  Not able to understand
it is a simple partitioning question

$(abcd)'$ partitioned into $(abc)'(d)'$ and $(ab)'(cd)'$ and further partitioned to$(a)'(b)'(c)'(d)'$

Is any other partition possible? No rt?
@Akash, $\pi_4$ refines p1, but since we have relation $\pi_4$ refines $\pi_3$ and $\pi_3$ refines p1 due to transitivity, we avoid having an edge between $\pi_4$and $\pi_1$right?
i can also say like phi 4---phi2---phi3---phi1 ..rt na ?



Your  Answer is Correct, but words are contradicting them. Its π4 refining π2, π3 . 

π4 & π2 refining π1.  π4 & π3 refining π1. Some one please edit his answer.


Ayush Upadhyaya 

Yes, you are correct ..

π4 refining π1  but  due to transitivity, we avoid having an edge between π4 and π1 ( as S is a poset ) 



As  it is poset we are not showing transitive dependency.

:O why ?

partial order itself means to satisfy refelexive , antisymmetric and transitive property right ?


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,157 users