Suppose A = {a,b,c,d} and H_1 = {{a,b},{c},{d}} is the following partition of A. a. List the ordered pairs of the equivalence relations induced by H_1. b. Draw the graph of the above equivalence relation. c. Let H_2 = {{a,b},{c,d}} and H_3 = {{a,b,c,d}}. Draw a Poset diagram of the poset ({H_1, H_2, H_3}, refines).

GATE 1998 · Discrete Mathematics · Partial Order · medium

Answer: Equivalence relation E_1 = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a)}. Refinement Poset: H_1 < H_2 < H_3 (a chain with H_1 at the bottom).

1. List ordered pairs of the equivalence relation induced by H_1: Block {a,b}: pairs (a,a),(b,b),(a,b),(b,a). Block {c}: pair (c,c). Block {d}: pair (d,d). So E_1 = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a)}.
2. Check refinement relationships between H_1, H_2, H_3: H_1 refines H_2: {a,b}={a,b}, {c} subset {c,d}, {d} subset {c,d}. Yes. H_2 refines H_3: {a,b} subset {a,b,c,d}, {c,d} subset {a,b,c,d}. Yes. H_1 refines H_3 (transitively). So the order is H_1 < H_2 < H_3 (a chain).
3. Draw Hasse diagram of ({H_1, H_2, H_3}, refines): H_2 covers H_1 (no partition strictly between them), H_3 covers H_2. Hasse diagram: H_3 at top, H_2 in middle, H_1 at bottom, with edges H_1-H_2 and H_2-H_3.