Question

What is a partially ordered set? Prove that the inclusion relation `is a subset of’ is a partial ordering on the power set of a finite set S.

Answer 1

A partially ordered set is a set $X$  with a partial ordering $\leq$  on $X$ . A partial ordering $\leq$  on $X$  is a binary relation on $X$  satisfying the following properties:

• for all $x, y, z\in X$ , if $x\leq y$  and $y\leq z$ , then $x\leq z$  (transitivity)
• for all $x\in X$ , $x\leq x$  (reflexivity)
• for all $x, y\in X$ , if $x\leq y$  and $y\leq x$ , then $x=y$  (antisymmetry)

Let $\mathcal{P}(S)$  denote the power set of $S$ . Below we show that $\subseteq$  on $\mathcal{P}(S)$  is a partial ordering.

• Transitivity. Let $T_0, T_1, T_2\in \mathcal{P}(S)$ . Assume that $T_0\subseteq T_1$  and $T_1\subseteq T_2$ . For all $t\in T_0$ , $t\in T_1$  because $T_0\subseteq T_1$ , and $t\in T_2$  because $T_1\subseteq T_2$ . Therefore, $T_0\subseteq T_2$ .
• Reflexivity. Let $T\in \mathcal{P}(S)$ . For all $t\in T$ , $t\in T$  is true. Hence $T\subseteq T$ .
• Antisymmetry. Let $T_0, T_1\in \mathcal{P}(S)$ . Assume that $T_0\subseteq T_1$  and $T_1\subseteq T_0$ . Then $T_0=T_1$  by the definition of set equality.