To what extent can I "disjointize" an arbitary collection of sets?

Question

Let $A_1,A_2,\dotsc$ be a collection of sets, which may or may not already be disjoint, and define $B_1=A_1,B_{n+1}=A_{n+1}\setminus\bigcup_{i\le n}A_i$ for $n\ge1$. Then $B_1,B_2,\dotsc$ is disjoint and $\bigcup^\infty A_i=\bigcup^\infty B_i$. Now I'm curious if this works given an arbitrary collection of sets $A_i$, $i\in I$, where $I$ is ANY index set. I'm thinking, why not take steal the structure of the original index set for the new one?

Define $J=I$ and $B_j=A_i$ for some $j\in J$ and any $i\in I$, then define $B_k=A_l\setminus\bigcup_j B_j$ where for every new $B_k$ defined, $l\in I$ s.t. $l$ not already chosen and $j$ ranges over the $B_j$ already defined. Then $B_j$, $j\in J$, is disjoint and $\bigcup_{i\in I}A_i=\bigcup_{j\in J}B_j$.

But all this seems very sketchy. For $I=\mathbb{N}$, the method of "disjointizing" $A_i$ seems to work in the that defining the sets $B_i$ is "complete" (so the $B_i$'s exist), i.e. in the sense that we somehow exhaust $i\in\mathbb{N}$, and that the $B_i$'s are unique, since the next $B_{n+1}$ is uniquely determined by the $\le$ relation on $\mathbb{N}$. (I believe we can un-unique them by matching $J=I$ if the second method if it works). But an index set $I$ could have zero structure and any cardinality, and then we need a method to keep track of already chosen elements.

My question is: Does the second method work, i.e. do the $B_i$'s exist? If they do, I don't think they're unique, but it doesn't matter since all we want is disjointness.

Answer 1

The property of $\mathbb{N}$ which allows us to do what you want is the fact that it is well-ordered. For those not familiar:

Definition: An order $\leqslant$ on a set $A$ is a well-ordering if it satisfies the following conditions:

1. $a\leqslant a$ for each $a\in A$ (reflexivity),
2. For each $a,b\in A$, either $a\leqslant b$ or $b\leqslant a$ holds (comperability),
3. $a\leqslant b$ and $b\leqslant a$ implies $a=b$ for each $a,b\in A$ (symmetry),
4. $a\leqslant b$ and $b\leqslant c$ implies $a\leqslant c$ for each $a,b,c\in A$ (transitivity),
5. For each $S\subseteq A$, $S$ has a least element; that is, there is some $s\in S$ such that $s\leqslant a$ for each $a\in S$ (well-ordering).

---

There is a theorem, the Well-Ordering Theorem, which is equivalent to the axiom of choice, which states that every set can be well-ordered. Using this theorem we may "disjointize" any collection of sets.

Let $\mathcal A= \{A_i\}_{i\in I}$ be a collection of sets indexed by the the set $I$. We will construct the sets $B_i$, which have the desired property that $$\bigcup_{i\in I} B_i=\bigcup_{i\in I} A_i,$$ using a process called transfinite induction. Let $\leqslant$ be a well-ordering of $I$. Let $a$ be the least element of $I$ and write $B_a=A_a.$ Now let $i\in I$ be such that for each $j< i$ we have constructed pairwise disjoint sets $B_j$ from the collection $\mathcal{A}.$ Then let $B_i=A_i\setminus \bigcup_{j<i} A_j$. It is clear that $B_i\cap B_j=\varnothing$ for each $j<i$. Since $B_i\subseteq A_i$ for each $i\in I$, we have $$\bigcup_{i\in I} B_i\subseteq\bigcup_{i\in I} A_i.$$ To see the reverse inclusion, observe that for each $x\in\bigcup_{i\in I} A_i$, the set $C_x=\{i\in I\;|\;x\in A_i\}\subseteq I$ has a least element $j$ and that $x\in B_j,$ so $$\bigcup_{i\in I} B_i\supseteq\bigcup_{i\in I} A_i,$$ giving equality of the two sets.

---

At first it may seem that transfinite induction works even with sets which are only totally ordered, such as the closed unit interval $[0,1].$ However, this is not the case. To see this, I recommend reading the proof that transfinite induction works. Intuitively, without a well-ordering, one has trouble "moving on to the next element" while performing the induction. I used the first chapter of Munkres' Topology, but there may be better sources. I enjoyed Munkres because he goes through a good amount of material, and the supplementary exercises at the end of nearly every chapter are challenging and illuminating.

Answer 2

To complement D. Brogan's excellent answer, note that if we assume that every indexed family of sets can be disjointized, then we can prove the axiom of choice. So "every union can be disjointized" is an equivalent formulation of AC.

To see this, suppose we have a family $\{A_i\}_{i\in I}$ of disjoint non-empty sets, and we want to find $\{b_i\}_{i\in I}$ such that $b_i\in A_i$. (This is one of several well-known equivalent formulations of the axiom of choice). Without loss of generality we can assume that $I$ is disjoint from each of the $A_i$s.

Now consider the family $$ \{ \{i,b\} \mid i\in I, b\in A_i \} $$ and disjointize it. Let $b_i$ be the unique $b\in A_i$ such that $\{i,b\}$ is in the disjointized family.