Consider the set S = {a,b,c,d}. Consider the following 4 partitions pi_1, pi_2, pi_3, pi_4 on S: pi_1 = {{a,b},{c,d}}, pi_2 = {{a,b,c,d}}, pi_3 = {{a},{b},{c},{d}}, pi_4 = {{a,b},{c},{d}}. Let <= be the partial order on the set of partitions S' = {pi_1, pi_2, pi_3, pi_4} defined as follows: pi_i <= pi_j if and only if pi_i refines pi_j. The poset diagram for (S', <=) is: A. (see diagram A) B. (see diagram B) C. (see diagram C) D. (see diagram D)

GATE 2007 · Discrete Mathematics · Partial Order · medium

Answer: C. The Hasse diagram is a chain: pi_3 (bottom) < pi_4 < pi_1 < pi_2 (top).

1. Determine all refinement relations: pi_3 refines pi_4: {a} subset {a,b}, {b} subset {a,b}, {c} subset {c}, {d} subset {d}. Yes. pi_3 refines pi_1: {a} subset {a,b}, {b} subset {a,b}, {c} subset {c,d}, {d} subset {c,d}. Yes. pi_3 refines pi_2: all singletons subset {a,b,c,d}. Yes. pi_4 refines pi_2: {a,b} subset {a,b,c,d}, {c} subset {a,b,c,d}, {d} subset {a,b,c,d}. Yes. pi_1 refines pi_2: {a,b} subset {a,b,c,d}, {c,d} subset {a,b,c,d}. Yes. Does pi_4 refine pi_1? {c} subset {c,d}? Yes, {c} subset {c,d}. {d} subset {c,d}? Yes. {a,b} subset {a,b}? Yes. So pi_4 refines pi_1! Does pi_1 refine pi_4? {c,d} must be subset of some block of pi_4 = {{a,b},{c},{d}}. {c,d} is not subset of {c} or {d} alone. No. So pi_1 does NOT refine pi_4.
2. Build the Hasse diagram from cover relations: Order from bottom: pi_3 < pi_4 < pi_1 < pi_2. This is a chain (total order)! Cover relations: pi_4 covers pi_3, pi_1 covers pi_4, pi_2 covers pi_1. The Hasse diagram is a straight chain with pi_3 at bottom, pi_4 next, pi_1 above that, pi_2 at top. This matches option C.