in Set Theory & Algebra edited by
11,028 views
39 votes
39 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:

  1.  
in Set Theory & Algebra edited by
11.0k views

4 Comments

reshown by

Alomost same question was asked in 1998.

https://gateoverflow.in/1725/gate1998-11

 

1
1

Note that  "bar over of elements in set" just representing the partition. When more than one element are under single bar that means all those element are in one partition. Bar is not related to complement in above question.

Similar question was asked in 1998, see below :-

https://gateoverflow.in/1725/gate1998-11

4
4

For Complete Details of “Refinement of a Partition” with ALL possible variations, GATE questions, and also Applications in Theory of Computation,

Watch the following lecture:

Refinement of a Partition - Complete Details & Analysis

For this GATE 2007 Q 26:

Detailed Video Solution of GATE CSE 2007 Question 26 Refinement of a Partition

3
3

2 Answers

48 votes
48 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

edited by

4 Comments

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 ) 

2
2

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

0
0
3
3
6 votes
6 votes

$\text{Some Mathematical Preliminaries to answer this question}$

  1. Partition P* is a refinement of the partition P if P*  covers P i.e. every point of P is a point of P*.
  2.  Take a Partition of a line P1 and P2 as
    1. $a_{0}$ $a_{1}$ $a_{2}$ $a_{3}$...$a_{n}$ 
    2. $b_{0}$ $b_{1}$ $b_{2}$ $b_{3}$…...$b_{n}$   respectively
  3. Now consider a line L having both P1 $\cup $ P2 on L
    1. i.e. L has all the points  $a_{0}$ $a_{1}$ $a_{2}$ $a_{3}$...$a_{n}$ ,$b_{0}$ $b_{1}$ $b_{2}$ $b_{3}$…...$b_{n}$  

If P1 and P2 are two different partitions of the interval [a,b] then P* = p1 $\cup$ P2 is the common refinement of P1,P2

 

$Now$ $we$ $are$ $eligible$ $to$ $answer$ $this$ $question$

$Given: $  S is partitioned into 4 sets $\pi_{1}$, $\pi_{2}$, $\pi_{3}$ and $\pi_{4}$ given below.

 

$Solution:$

As per our knowledge on refinement, we can say that, 

$\pi_{1}$ = {abcd}

$\pi_{2}$ = {ab,cd}

$\pi_{3}$ = {abc,d}

$\pi_{4}$= {a,b,c,d}

 

Now, let us draw the Hassey Diagram for the relationship between these partitions.

Imagine the elements as the different colored boxes, in order to understand the beauty of mathematics :)

 

 

Answer:

Related questions