3
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ Can you be more specific about what parts you do understand and what you don't understand? Can you try to narrow down the part that is confusing you? Otherwise you're just asking us to re-explain the whole thing, and I worry if we try you might say "I didn't understand that either". Do you understand what a partial order is? What a poset is? (Not sure what you mean by "roughly the same order".) Looks like the Wikipedia article is very terse, and all of the content is in the first sentence of the article -- so you'll need to unpack that carefully. $\endgroup$
    – D.W.
    Jan 5 '18 at 19:21
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.