The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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:

asked in Set Theory & Algebra by Veteran (59.5k points)
edited by | 2.3k views

refines == ?


 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.
Please explain this Question&Answer properly ? i am still confused after reading different different comments here.

2 Answers

+25 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 :-

answered by Boss (42.6k 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, pi4 refines p1, but since we have relation pi4 refines pi3 and pi3 refines p1 due to transitivity, we avoid having an edge between pi4 and pi1 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 ?

+2 votes
Ans is C
answered by (131 points)
please explain
Now , see the best answer, edited it .. hope it is understandable ..

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

38,000 questions
45,496 answers
48,633 users