The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
2.3k views

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
+6

refines == ?

+4

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

+2
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.
+6
0
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$.

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

answered by Boss (42.6k points)
edited by
+1

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

0
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.
+1
hi,

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

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

+4
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
0

@amarVashishth

Are you sure about meaning of refinement now ?

+1

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

0
C,D both are correct, but C is more correct than D
0
how D can be correct ???
+1
π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.
0
@srestha

Anyone can u pls give a better explanation to this question ?  Not able to understand
+4
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?
+1
@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?
+1
i can also say like phi 4---phi2---phi3---phi1 ..rt na ?

@sresth
+1

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

+1

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 ) 

0

@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 (131 points)
0
please explain
+1
Now , see the best answer, edited it .. hope it is understandable ..
Answer:

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
131,570 comments
48,633 users