# How do I eliminate useless subsets?

BACKGROUND / MOTIVATION:

The other day, I was given a finite covering $\mathcal{B} = \{I_1, \ldots, I_n\}$ of $[0, 1]$ by open intervals, and I wanted to refine it by eliminating useless intervals, that is, those $I_k$ which are contained in the union of the others: $$I_k \subseteq I_1 \cup \dots \cup \widehat{I_k} \cup \dots \cup I_n~~(\text{I_k is ommited.)}$$ Since my covering was finite, it was easy to establish an algorithm for doing this: check if $I_1$ is useless; if it is, remove it from the list and proceed to $I_2$, considering the new list now, and so on.

However, I couldn't help but notice that this process depends on the given order. For example, if $I_1 = [0, 1]$, $I_2 = [0, 3/4)$ and $I_3 = (1/4, 1]$, I would eliminate just $I_1$ and I'd be done. If, on the other hand, $I_3$ and $I_1$ switched places, my algorithm would end up eliminating $I_2$ and $I_3$ instead.

I then started wondering whether there is a more direct, non-algorithmic argument to show that such a refinement always exists. A naive guess would be to define $$\mathcal{B}^{\prime} = \bigg\{ I_k \in \mathcal{B} : I_k \not\subseteq \bigcup_{j \neq k} I_j \bigg\},$$ but this may be empty. In the finite case, one could settle for the given algorithm, but the situation becomes troublesome when dealing with arbitrary coverings. This has lead me to the following question.

QUESTION: Suppose you have a set $X$ and an arbitrary family of subsets $\mathcal{A} = \{A_i\}_{i \in I}$ of $X$ such that their union is $X$. How can you prove that there exists a refinement $\mathcal{A}^{\prime} = \{A_j\}_{j \in J}$, $J \subseteq I$, such that no member of $\mathcal{A}^{\prime}$ is useless (contained in some union of other members of $\mathcal{A}^{\prime}$) but $\mathcal{A}^{\prime}$ still covers $X$?

Thanks.

-
There is an exercise in a homework set from April 2010 in Ron Freiwald's topology course that generalizes Brian M. Scott's counterexample: It says that every noncompact topological space has an open cover with no irreducible subcover. – Jonas Meyer Feb 17 '12 at 1:06

You can’t, because it isn’t always true. Let $X=\mathbb{N}$, and for $n\in\mathbb{N}$ let $A_n=\{0,1,\dots,n\}$. Let $\mathscr{A}=\{A_n:n\in\mathbb{N}\}$. Clearly $\mathscr{A}$ is a cover of $\mathbb{N}$. However, if $I$ is any subset of $\mathbb{N}$ such that $\mathscr{A}'=\{A_i:i\in I\}$ covers $\mathbb{N}$, then $I$ is infinite, and $\{A_i:i\in I\setminus\{\min I\}\}$ is a proper subset of $\mathscr{A}'$ that still covers $\mathbb{N}$. Thus, $\mathscr{A}$ has no irreducible subcover.
Added: It’s a useful theorem in general topology that if the cover $\mathscr{A}$ is point-finite, i.e., if $$\operatorname{st}(x,\mathscr{A})\triangleq\{A\in\mathscr{A}:x\in A\}$$ is finite for every $x\in X$, then it has an irreducible subcover. This can be proved using Zorn’s lemma. Let $\mathfrak{R}=\{\mathscr{R}\subseteq\mathscr{A}:\bigcup\mathscr{R}=X\}$, and consider the partial order $\langle\mathfrak{R},\supseteq\rangle$. It’s easy to see that a maximal element in this partial order is an irreducible subcover of $\mathscr{A}$, so we need only show that every chain in $\langle\mathfrak{R},\supseteq\rangle$ has a $\supseteq$-maximal element. Let $\mathfrak{C}$ be a chain in $\langle\mathfrak{R},\supseteq\rangle$, and let $\mathscr{C}=\bigcap\mathfrak{C}$. Suppose that $\mathscr{C}$ does not cover $X$; then there is some $x\in X\setminus\bigcup\mathscr{C}$. Suppose that $x\in A\in\mathscr{A}$; then $A\notin\mathscr{C}$, so there is some $\mathscr{C}_A\in\mathfrak{C}$ such that $A\notin\mathscr{C}_A$. But $\operatorname{st}(x,\mathscr{A})$ is finite, so we can enumerate it as $\{A_1,\dots,A_n\}$ for some $n$, and without loss of generality $$\mathscr{C}_{A_1}\supseteq\dots\supseteq\mathscr{C}_{A_n}\;.$$ But then $\mathscr{C}_{A_n}\cap\operatorname{st}(x,\mathscr{A})=\varnothing$, so $x\notin\bigcup\mathscr{C}_{A_n}$, contradicting the assumption that $\mathscr{C}_{A_n}\in\mathfrak{R}$. Thus, $\mathscr{C}$ does cover $X$, every chain in $\langle\mathfrak{R},\supseteq\rangle$ has a $\supseteq$-maximal element, and Zorn’s lemma applies to yield an irreducible subcover of $\mathscr{A}$.