2.7k 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:

edited | 2.7k views
+7

refines == ?

+7

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.
+9
0
..

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 :- https://en.wikipedia.org/wiki/Partition_of_a_set

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

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

+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
&pi;4 refines all of them(&pi;1,&pi;2,&pi;3)

Neither &pi;2 refines &pi;3 nor &pi;3 refines &pi;2.

And &pi;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,

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

+1

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 ?

Ans is C
0
+1
Now , see the best answer, edited it .. hope it is understandable ..

1
2