0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ A poset is a set with a relation, so the relation is not enough. What is the relation defined on? It has to be a set, so it cannot be "all sets." It has to be some set of sets. We'd say "is a subset of" is a partial order of some set, not just that it is a partial order. $\endgroup$ Sep 4, 2014 at 14:07
  • 1
    $\begingroup$ The relation $\subseteq$ is a partial order on the class of all sets, you can immediately verify the defining conditions. As the class of all sets fails to be a set, we do not get a poset this way. However, if we work only with subsets of a "unversal" set, then the universal set together with $\subseteq$ is a poset. $\endgroup$ Sep 4, 2014 at 14:15

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .