axiom of choice: cardinality of general disjoint union

I have this exercise involving the axiom of choice, but I don't understand where it's needed: Let $(X_i)_{i \in I}$ and $(Y_i)_{i \in I}$ be pairwise disjoint sets with $|X_i| = |Y_i|$. Prove, using the axiom of choice, that $$ \mid\bigcup_{i \in I} X_i\mid = \mid\bigcup_{i \in I} Y_i\mid.$$ I assume that this just means that you have to prove that there exists a bijection between $\mid\bigcup_{i \in I} X_i\mid$ and $\mid\bigcup_{i \in I} Y_i\mid$, which I think is almost trivial, but I don't understand where the axiom of choice (or another form of it) is needed.

I also have the same question involving products (without the pairwise disjoint union statement): prove that, given that $|X_i| = |Y_i|$, $$ \mid\prod_{i \in I} X_i\mid = \mid\prod_{i \in I} Y_i\mid.$$ Again, I don't understand why the axiom of choice is needed, since finding a bijection is trivial and, if axiom of choice doesn't hold, the two products are empty and the equality follows trivially.

What am I missing here ?

Solution 1:

Suppose $A$ and $B$ are two sets of equal cardinalities, without any additional structure there are $2^{|A|}$ many bijections between them.

Using the axiom of choice we can choose $f_i\colon X_i\to Y_i$ which is a bijection, and using these bijections construct one from $\bigcup X_i$ to $\bigcup Y_i$ in the intuitive manner that you'd expect.

However since we are choosing from infinitely many sets at once we cannot just say that the sequence of bijections exists. Such assertion needs to be backed up, and the axiom of choice is exactly what allows us to back it up - the collections of bijections are nonempty, and so we may choose one from each one. From these choices we have a sequence of bijections which we can use to construct the bijection between the unions.

Without the axiom of choice it is possible that we cannot choose the bijections. It is possible to have that $A_i$ is countable for $i\in\omega$ but $|\bigcup A_i|=\aleph_1$, which is of course uncountable.

By your argument we could say that $A_i$ has a bijection with $\{i\}\times\omega$, however $\bigcup A_i$ is uncountable while $\bigcup(\{i\}\times\omega)=\omega\times\omega$ is countable. Therefore the unions are no longer in bijection.

Wait, it gets even worse. It is possible to have a countable family of disjoint pairs (sets of two elements each), and the union of is uncountable. Of course the uncountability of the union does not imply it has cardinality $\aleph_1$, but rather that it cannot be well ordered at all. On the other hand, we can write $\mathbb Z\setminus\{0\}$ as the pairs $\{-n,n\}$. The union of these countably many pairs is indeed countable.

With products the use of choice is even clearer. It is not trivial that the product is nonempty, but it does not imply that every product is empty.

In the above example of the pairs, we have countably many disjoint pairs $P_i$ such that $\prod P_i=\varnothing$. However if you take pairs of natural numbers, for example $\{2n,2n+1\}$ then the product is $2^\omega$ and the union is countable. This, once again, should hint you of the example.

So to answer both questions, the point we use the axiom of choice is in our choice of bijections to construct the bijection between the products or the unions. Of course this can be averted if additional structure exists on the sets, if they are all subsets of the same well ordering, for example.

Further reading on this site:

1. Cardinality of an infinite union of finite sets
2. Finite choice without AC
3. Cardinality of union of ${{\aleph }_{0}}$ disjoint sets of cardinality $\mathfrak{c}$

Solution 2:

For the first part you have that for each $i$ the set $B_i$ of bijections from $X_i$ to $Y_i$ is nonempty. You can construct a bijection between the unions by picking an element of $B_i$ for each $i$, for which you need with the Axiom of Choice.