What is "Containment order"? Could I get a friendly explanation?

Question

Reading the Wikipedia page was a little dense for me. Can anyone offer a friendly explanation of what this means? It sounds like it saying that if you have two ordered collections, if they are "ordered by containment" then they will be in roughly the same order with each other?

Answer 1

I'll try a down to earth definition \ example:

When speaking of a set $X$, lets say $X=\{1,...,100\}$, denote the subset $X_i = \{1,...,i\}$

It holds that $X_1\subseteq X_2\subseteq...\subseteq X_{100}$

So you could say there is a containment order over these subsets, because each subset contains the other in an order that I stated. This order came from, and connected to (and isomorphic to) the partial order of $1 \leq 2 \leq ... \leq 100$ or if you prefer more fomally, that $(X,\leq )$ is a poset.

Answer 2

A containment order $\prec$ is a partially ordered set in which the points are labelled by sets, say a point $x$ is labelled by a set $S_x$, and $x \prec y$ iff $S_x \subset S_y$.

As Wikipedia mentions, every partial order can be realized as a containment order. That is, any partial order is isomorphic to a containment order. You can find the proof on Wikipedia, or check the proof below. Because of this, a containment order is a syntactic rather than a semantic property. You can think of a containment order as a partial order which is realized "physically" as a partial order of sets ordered by inclusion.

As an example, let us realize the partial order of the natural numbers $0 < 1 < 2 < \cdots$ as a containment order. This is very simple: we will label a point $x$ by the set $\{0,\ldots,x-1\}$. So $S_0 = \emptyset$, $S_1 = \{0\}$, $S_2 = \{0,1\}$, and so on. You can check that $i < j$ iff $S_i \subset S_j$.

As another example, suppose that we are interested in the partial order on words given by the following rule: $w_1 \prec w_2$ if $w_1$ is a proper prefix of $w_2$ (for example, $a \prec ab$). In this case, we label a string $w$ with the set of all of its prefixes. For example $S_a = \{\epsilon, a\}$ (where $\epsilon$ is the empty string) and $S_{ab} = \{\epsilon, a, ab\}$. Once again, you can check that $w_1 \prec w_2$ iff $S_{w_1} \subset S_{w_2}$.

More generally, given an arbitrary partial order $\prec$, we can define $S_x = \{ z : x \preceq z \}$. We can then check that $x \prec y$ iff $S_x \subset S_y$.

To show this, suppose first that $x \prec y$ and $z \in S_x$. Then $z \preceq x \prec y$, and so $z \in S_y$. This shows that $S_x \subseteq S_y$. Since $x \prec y$, we know that $y \not\preceq x$, and so $y \in S_y$ but $y \notin S_x$, implying that $S_x \subsetneq S_y$.

In the other direction, suppose that $S_x \subset S_y$. Since $x \preceq x$, we have $x \in S_x$, and so $x \in S_y$, implying that $x \preceq y$. Clearly $x \neq y$, since otherwise $S_x = S_y$, and so $x \prec y$.