# To what extent can I “disjointize” an arbitary collection of sets?

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.

• The $B_i$ of the second method exist, though you cannot list them in general. The arbitrary union of sets is well defined as well as the difference of two sets. – Javi Jul 28 '18 at 18:35

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.

• Thanks for mentioning what's specifically needed. If I'm on the right track, your defining of $B_i$ for any $i\in I$ requires $B_j$ already defined for $j<i$ and eventually we hit $B_m$ for the least element $m$ of $I$, which we need well-ordering property to exist for infinite sets $I$ (else induct on $I$ finite). And the motivation would be that for any $B_i$, you want to exclude ("set-differencing") at least all the sets that were excluded for defining $B_j$, $j<i$. – palmpo Jul 28 '18 at 21:03
• Now that I think of it, it seems like if we have a path from a starting element to an ending element, we don't need well-ordering property. i.e. a set $I$ s.t. for any two $i,j\in I$, there is some $k_\alpha\in I$ s.t. $iRk_\alpha R...Rk_\beta j$. – palmpo Jul 28 '18 at 21:10
• I apologize for all these questions but I want to know what I can get away with, excluding choice. I don't know much about choice and it seems unintuitive like cheating, since you get something for free. Choice gives us a single well-order (possibly out of many) but at least for a fixed well-order, the $B_i$'s defined are unique. Is there another definition of $B_i$'s that disjointize a set without choice, not caring about uniqueness of the $B_i$'s generated? – palmpo Jul 28 '18 at 21:20
• Unless I'm mistaken, you do indeed need a well-ordering. I skipped some steps (which I will edit in after writing this comment), but the actual process by which one constructs the sets $B_i$ is called transfinite induction. It is a generalization of the usual mathematical induction one encounters with the natural numbers, and requires the set being inducted over to be well-ordered. – D. Brogan Jul 28 '18 at 21:20
• I understand the hesitation to use choice. At first it does seem like cheating, what with all the unintuitive results such as the Banach-Tarski Paradox or even the Well-Ordering Theorem following from it. However, even if one wishes to avoid it, this is an inherently set-theoretic question; moreover one in which we are dealing with arbitrary cardinalities. Choice is almost guaranteed to appear under those conditions. – D. Brogan Jul 28 '18 at 21:24

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.

• Thanks for the additional info, I keep encountering AC when I have to deal with sets without any structure and it just solves all the problems away. – palmpo Jul 28 '18 at 21:24