Answer to Question #225729 in Discrete Mathematics for Prince

Question

1) Draw the Hasse diagram for inclusion on the set P(S), where S = {a, b, c, d}

2) Let S = {1,2,3,4} with lexicographic order "<=" relation
a. Find all pairs in S x S less than (2, 3)
b. Find all pairs in S x S greater than (3, 1)
c. Draw the Hasse diagram of the poset (S x S, <)

Answer 1

Part 1 and 2

Part a

(2, 2), (2, 1),(1, 4), (1, 3), (1, 2), (1, 1)

Part b

(3, 2), (3, 3),(3, 4), (4, 1), (4, 2), (4, 3), (4, 4)

Part c

$P(A) = \big \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{b, c\}, \{a,c\}, \{a, b,c\} \big \}.$

Let's show $S=(P(A), \subseteq)$ is a poset. Let's show that $S$ satisfies the following three properties.

1. Reflexivity. For every $x \in P(A) \ x \subseteq x$ is trivially true.
2. Antisymmetry. Let $x, y \in P(A)$ and $x \subseteq y \wedge y \subseteq z$.Then $x=y$ from the definition.
3. Transitivity. Let $x, y,z \in P(A)$ and $x \subseteq y \wedge y \subseteq x$. Then for all$a \in x$ we have $a \in y$, and therefore $a \in z$. Thus $x \subseteq z$.

The Hasse diagram for $(P(A), \subseteq)$ is shown below.