Prove that the binary relation "is a subset of" is a...

Question

Prove that the binary relation "is a subset of" is a partial order (POSET)?

Should I try to prove this in reference to the power set of a general set?

When is this relation a total order?

Answer 1

To prove that $R \subseteq \mathcal{P}(X) \times \mathcal{P}(X)$ defined by $(A,B) \in R \Leftrightarrow A\subseteq B$ is a partial order you need to show:

• Reflexivity: for all $A\in \mathcal{P}(X)$ we have $A\subseteq A$;
• Anti-symmetry: if $A,B \in \mathcal{P}(X)$ and $A\subseteq B$ and $B\subseteq A$ then $A=B$;
• Transitivity: if $A,B,C \in \mathcal{P}(X)$ and $A\subseteq B$ and $B\subseteq C$ then $A\subseteq C$.

It's very easy to prove these three items just using the definition of $\subseteq$.

Moreover, $\mathcal{P}(X)$ is totally ordered if and only if $X$ has at most 1 element.

Answer 2

See Partially ordered set or poset :

A (non-strict) partial order is a binary relation "≤" over a set $P$ which is reflexive, antisymmetric, and transitive, i.e., which satisfies for all $a, b, c \in P$ :

• $a ≤ a$ (reflexivity);

• if $a ≤ b$ and $b ≤ a$ then $a = b$ (antisymmetry);

• if $a ≤ b$ and $b ≤ c$ then $a ≤ c$ (transitivity).

We have to show that the $\subseteq$ relation over the power set $\mathcal P(X)$ has the three above properties, using the definition :

$A \subseteq B$ iff for all $x$, if $x \in A$, then $x \in B$.