Disjoint refinement of a set of sets

Say I have some set $F$ of sets. This is obviously a cover of $\cup F$. Is there a general algorithm that makes "this" cover disjoint? That is, a set $F'$ of pairwise disjoint sets with the properties $\cup F = \cup F'$ and $(\forall A \in F')(\exists B \in F)(A \subset B)$?

This question covers the countable case.

• You can index $F$ by an ordinal and make the same construction. [If you reject choice, that might not work.] – Daniel Fischer Jun 16 '15 at 15:07
• Heh - we need a flag "someone's about to answer this", so a guy doesn't spend twenty minutes typing an answer to a question that's going to be answered while he's typing... – David C. Ullrich Jun 16 '15 at 15:32
• I liked both answers. Even those parts of the text that does not answered to the main question added ideas and useful information. – Gustavo Jun 16 '15 at 15:41

Let $\leq$ be a well-ordering of $F$ (to do this for arbitrary $F$, use the Axiom of Choice), let $\alpha$ be the unique ordinal order-isomorphic to $(F,\leq)$, so that the elements of $F$ are indexed by the ordinals less than $\alpha$ (i.e. the elements of $\alpha$), so $F=\{F_\beta \mid \beta<\alpha\}$.

Then define via Principle of General Recursion $F'_{\lambda}=F_{\lambda}\setminus \bigcup_{\beta<\lambda}{F'_\beta}$. Then the collection $F'=\{F'_\beta \mid \beta<\alpha\}$ is the one you want.

• Can you please give some reference for the Principle of General Recursion? Thanks – Gustavo Jun 16 '15 at 15:21
• This is usually covered in any introduction to set theory (sometimes also referred to as the Theorem Of Transfinite Recursion), see for example here. – Stefan Mesken Jun 16 '15 at 18:17

I can tell you how to prove that such a refinement exists. It's not entirely elementary, and it probably doesn't count as an "algorithm". I don't know how much set theory you know - you can find the required background for what's below by searching Wikipedia for "ordinal", "Well ordering theorem", and "transfinite recursion" (if you don't find that try transfinite induction).

Ok. The well ordering theorem implies that any set is bijective with some ordinal. So there exists an ordinal $\alpha$ and an "enumeration" of $F$, so that we can write $$F=\{S_\beta\,:\,\beta<\alpha\}.$$ Here $\beta<\alpha$ refers to ordinals $\beta$. Now the magic of transfinite recursion shows that there exists a family of sets $S'_\beta$ (for $\beta<\alpha$) such that for every $\beta<\alpha$ we have $$S'_\beta=S_\beta\setminus\bigcup_{\gamma<\beta}S_\gamma.$$Clearly $S'_\beta\subset S_\beta$, clearly the $S'_\beta$ are pariwise disjoint, and it's easy to check by transfinite induction that $$\bigcup_{\beta<\alpha}S'_\beta=\bigcup_{\beta<\alpha}S_\beta.$$(For that last bit: Say $x\in\bigcup_{\beta<\alpha}S_\beta$. Let $\beta$ be the smallest ordinal with $x\in S_\beta$. Then $x\in S'_\beta$.)

This could also be done by Zorn's Lemma. But, once you get past the machinery of ordinals and transfinite recursion, the proof above is much nicer and more intuitive (imo): It's just like the countable case! (Except different, of course...)

Ok, let's do it by Zorn's lemma, and see whether this answer has appeared by the time I finish typing it...

Let $Z$ be the set of ordered pairs $(S,f)$ such that $S\subset F$, $f:S\to\bigcup F$, $f(x)\subset x$ for every $x\in S$, the sets $f(x)$ for $x\in S$ are pairwise disjoint, and $\bigcup_{x\in S}f(x)=\bigcup S$.

Order $Z$ by extension: $(S,f)\le(S',f')$ if $S\subset S'$ and $f'|_S=f'$.

Zorn's lemma says $Z$ has a maximal element $(S,f)$. An argument like the construction in the other proof shows that $S=F$.