Down-set closure of subsets

249 Views Asked by At

I am confused by the following statement in my lecture notes on down-set closure of subsets: "The family of down-sets containing a given subset $E \subseteq S$ is nonempty since $E \subseteq S$ and $S$ is a down-set. It follows that the intersection of all down-sets containing E, $$Cl^\downarrow(E):= \bigcap_{L \supseteq E} L,$$ is the smallest down-set containing E.

This is confusing to me because isn't $Cl^\downarrow(E)$ simply equivalent to $E$ if only everything in $E$ is is common to all $L$'s? Furthermore, if so, why then isn't $E$ also the smallest down-set containing $E$? (Of course in the case that there's more in common between the $L$'s than just $E$, then it is even clearer that $E$ would be the smallest down-set containing itself, right...?)

1

There are 1 best solutions below

2
On BEST ANSWER

To answer the last question first, $E$ cannot be the smallest downset containing $E$ if $E$ is not a down-set in the first place. Consider the set $E=\{1,3\}$ in $\Bbb Z$, the set of integers, with its usual ordering: $E$ is clearly not a down-set, since, for instance, $0\le 1\in E$, but $0\notin E$. For each $n\in\Bbb Z$ let $D(n)=\{k\in\Bbb Z:k\le n\}$; then $D(n)$ is a down-set, and every non-empty down-set is either one of these sets $D(n)$ or $\Bbb Z$. So what down-sets contain $E$? It’s not hard to see that $D(n)\supseteq E$ if and only if $n\ge 3$: $D(3),D(4),D(5),\ldots$ all contain $E$, and $D(2),D(1),D(0),\ldots$ do not. Of course $\Bbb Z\supseteq E$, so

$$\begin{align*} \operatorname{Cl}^\downarrow(E)&=\bigcap\{L\subseteq\Bbb Z:L\supseteq E\text{ and }L\text{ is a down-set}\}\\ &=\Bbb Z\cap\bigcap_{n\ge 3}D(n)\\ &=D(3)\;, \end{align*}$$

since $D(3)\subseteq D(4)\subseteq D(5)\subseteq\ldots\subseteq\Bbb Z$. In other words, the down-set closure of $\{1,3\}$ is $D(3)=\{k\in\Bbb Z:k\le 3\}$, the set of all integers less than or equal to $3$; a little thought should convince you that this really is the smallest down-set containing $\{1,3\}$, and it’s certainly not equal to $\{1,3\}$.

This example is especially simple because this partial order is actually a linear (or total) order; this makes the down-sets very easy to describe, and it makes it very easy to see what the smallest down-set containing a given set is. However, the definition works as claimed in any partial order. I’ll expand what’s in your notes a bit to try to make this clearer.

If $\langle S,\le\rangle$ is any partial order, then $S$ is a down-set: this just means that if $x\le y\in S$, then $x\in S$, which is certainly true. Now let $E$ be any subset of $S$, and let

$$\mathscr{D}=\{D\subseteq S:D\supseteq E\text{ and }D\text{ is a down-set}\}\;;$$

we’ve just seen that $S\in\mathscr{D}$ — it’s a down-set, and it contains $E$ — so $\mathscr{D}\ne\varnothing$. Your definition of the down-set closure of $E$ then says that $\operatorname{Cl}^\downarrow(E)=\bigcap\mathscr{D}$. To show that this is the smallest down-set containing $E$, we have to show three things:

  1. it contains $E$;
  2. it’s a downset; and
  3. if $D$ is any down-set containing $E$, then $\operatorname{Cl}^\downarrow(E)\subseteq D$.

(1) is easy: $\operatorname{Cl}^\downarrow(E)$ is the intersection of sets that all contain $E$, so $\operatorname{Cl}^\downarrow(E)\supseteq E$.

(2) isn’t much harder. Suppose that $x\le y\in\operatorname{Cl}^\downarrow(E)$. Then for each $D\in\mathscr{D}$ we have $x\le y\in D$, and since $D$ is a down-set this implies that $x\in D$. Thus, $x$ is an element of every $D\in\mathscr{D}$, and therefore $x\in\operatorname{Cl}^\downarrow(E)$; this shows that $\operatorname{Cl}^\downarrow(E)$ is a down-set.

(3) is very easy: if $D$ is a down-set containing $E$, then $D\in\mathscr{D}$, so $\operatorname{Cl}^\downarrow(E)=\bigcap\mathscr{D}\subseteq D$.

In short, $\operatorname{Cl}^\downarrow(E)$ is exactly what was claimed: the smallest down-set containing $E$, smallest in the sense that it’s a subset of every down-set that contains $E$.

If $E$ is itself a down-set, then of course $E\in\mathscr{D}$, and in that case we have

$$E\subseteq\operatorname{Cl}^\downarrow(E)=\bigcap\mathscr{D}\subseteq E$$

and hence $\operatorname{Cl}^\downarrow(E)=E$, but this happens only when $E$ is a down-set to begin with.