When we do really need the axiom of choice

Question

Let us suppose that $\{X_i: i \in I\}$ is a family of nonempty subsets of $X$ such that either $X_i\cap X_j=\emptyset$ or $X_i=X_j$ for all $i,j \in I$.

Fact using the AC: We can define an equivalence relation $\equiv$ on $I$ by saying that $i\equiv j$ if and only if $X_i=X_j$. Denote by $K$ the quotient space of $I$ modulo $\equiv$. Then, for each $k \in K$, we can find equivalence class of $X^\bullet_k$. By the AC, we can choose $X_k$ in the class $X_k^\bullet$, for each $k \in K$. It follows that $\{X_k:k \in K\}$ is made by pairwise disjoint sets and $\cup_k X_k=\cup_i X_i$.

Question: Do we really need the axiom of choice to obtain the existence of the family $\{X_k:k \in K\}$?

Answer 1

I assume that $K$ is the quotient set of $I$ modulo the equivalence relation $\equiv$ defined by $i \equiv j$ iff $X_i = X_j$ and you are trying to construct a family of sets indexed by $K$ that eliminates possible duplication in the $X_i$. Then for $k$ in $K$ you can define $X^{\bullet}_k = \bigcup_{i\in k} X_i$ to define the family of sets you want without using AC.

Answer 2

Yes, you do in fact need choice.

It is consistent with ZF (= set theory without choice) that there is a set $I$ which can be partitioned into pairs of sets $I=\bigcup_{g\in G}J_g$, $\vert J_g\vert =2$, but such that there is no choice function for $\{J_g: g\in G\}$.

We can now construct a set $X_i$ $(i\in I)$ of sets such that $X_i=X_{i'}$ iff $i, i'\in J_g$ for some $g$, and $X_i\cap X_{i'}=\emptyset$ otherwise.

---

More generally: suppose that the axiom of choice fails, and $\{Y_g: g\in G\}$ is a family of disjoint sets with no choice function. Let $I=\bigcup_{g\in G} Y_g$, and let (for $i\in I$) $X_i=\{Y_g\}$ where $i\in Y_g$. Note that $X_i=X_{i'}$ iff $i$ and $i'$ are in the same $Y_g$. Then the set $\{X_i: i\in I\}$ has no "selector" set. So, in fact, your statement is equivalent to the axiom of choice.