The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.9k views
Consider the set $S =\{ a , b , c , d\}$ . Consider the following 4 partitions $π_1,π_2,π_3,π_4$ on

$S : π_1 =\{\overline{abcd}\} , π_2 =\{\overline{ab}, \overline{cd}\},$

$\quad\;\, π_3 = \{\overline{abc}, \overline{d}\}, π_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 (69k points)
edited by | 1.9k 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.

2 Answers

+24 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.

  1. π4 refining π2, π3 . 
  2. π4 & π2 refining π1.  π& π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

answered by Veteran (49.5k 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.
hi,

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

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

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

@amarVashishth

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.
@srestha

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 ?

@sresth

@Akash,

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 ) 

@akash

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 (145 points)
please explain
Now , see the best answer, edited it .. hope it is understandable ..


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

33,705 questions
40,252 answers
114,343 comments
38,862 users