Is the following equivalent to the axiom of choice?

Let $A = \{a_i: i \in I\}$ be a collection of pairwise-disjoint non-empty sets indexed by $I$. Similarly, let $B = \{b_i : i \in I \}$. Further assume that for every $i \in I$, $|a_i| = |b_i|$. Then $|\bigcup A| = |\bigcup B|$

I'm interested in this question because the proposition seems like one of the more intuitively obvious ways to state the axiom of choice, but I'm getting stuck on proving that it actually is one!

It's easy to see that the axiom of choice implies the proposition. The argument is essentially to choose a bijection between $a_i$ and $b_i$ for every element $i \in I$, and combine them to form a bijection. In trying to show the reverse implication, I'm stuck on the fact that we might have a bijection between $\bigcup A$ and $\bigcup B$ that mixes up the partitioning sets.

I've also heard of Russell Cardinals, and that it is is consistent with $ZF$ to assume that there exists a countable union of countable sets that is itself uncountable.

  • $\begingroup$ possible duplicate of axiom of choice: cardinality of general disjoint union $\endgroup$ – vadim123 Mar 30 '14 at 4:08
  • 3
    $\begingroup$ I've edited the question to provide some background/motivation, and removed the implicit declaration that the equivalence is true. $\endgroup$ – Sebastian Conybeare Mar 30 '14 at 4:47
  • 1
    $\begingroup$ I never heard of Russell Cardinals, what are they? $\endgroup$ – bof Mar 30 '14 at 4:59
  • $\begingroup$ There might (conceivably) be a better chance of proving that the (apparently) stronger statement, if $|a_i|\le|b_i|$ for each $i$ then $|\bigcup A|\le|\bigcup B|$, implies the axiom of choice. Not that I see any way of doing that. $\endgroup$ – bof Mar 30 '14 at 5:03
  • 2
    $\begingroup$ @bof: Russel cardinals are cardinals of sets which can be written as a countable union of pairs, without a choice function. Herrlich has a couple of papers on the topic. $\endgroup$ – Asaf Karagila Mar 30 '14 at 5:41

The answer is that we don't know how to prove that this is equivalent to the axiom of choice.

Higasikawa, Masasi "Partition principles and infinite sums of cardinal numbers." Notre Dame J. Formal Logic 36 (1995), no. 3, 425–434.

In the above paper the author shows that this principle (which he names $\sf FB$) implies the partition principle (if there is a surjection from $A$ onto $B$, then there is an injection from $B$ into $A$). The question whether or not the partition principle implies the axiom of choice is open.

You can also find this principle in Gregory Moore's book about the axiom of choice. This is principle 1.4.12, and it is indicated to be open whether or not it is equivalent to the axiom of choice. However, it is also indicated that in conjunction with the following principle, we can prove the axiom of choice:

"If every member of an infinite set $A$ has the same cardinality of $A$ then $\bigcup A$ has the same cardinality as $A$."

So all in all, this question is another open question from the list of "very easy to formulate, very difficult to prove equivalent to the axiom of choice".

| cite | improve this answer | |
  • $\begingroup$ Doesn't the statement in quotation marks imply the axiom of choice all by itself? Doesn't it imply that every infinite cardinal is equal to its square? Am I missing something? $\endgroup$ – bof Mar 30 '14 at 6:23
  • 1
    $\begingroup$ On paper, I agree it seems reasonable. But then again Sierpinski was the one to formulate this principle. I assume that himself and Tarski, and probably Moore too, would have noticed if that was the case. No, there must be something hiding in there to make it more difficult. $\endgroup$ – Asaf Karagila Mar 30 '14 at 6:28
  • 2
    $\begingroup$ Let $X$ be an infinite set. For $x\in X$ let $a_x=\{x\}\times X$, and let $A=\{a_x:x\in X\}$. Then $|a_x|=|X|=|A|$, and $\bigcup A=X\times X$, so $|X\times X|=|\bigcup A|=|A|=|X|$. Where's the mistake? $\endgroup$ – bof Mar 30 '14 at 6:40
  • 1
    $\begingroup$ There is no possibility that you subtly misstated the proposition? $\endgroup$ – bof Mar 30 '14 at 7:43
  • 2
    $\begingroup$ @bof: The statement that Asaf gave is the same (modulo using "cardinality" instead of "power") as that given in Moore's book. (For a nice coincidence, there it is numbered (4.1.12).) In Moore the following sketch of (1.4.12)+(4.1.12) implies AC is given: Let $A$ be any infinite disjoint family of sets, each equipollent to $A$. By (4.1.12) $|A|=|\bigcup A|$. As $|a|=|A|$ for each $a \in A$, by (1.4.12) $|\bigcup A| = | \bigcup \{ A \times \{ a \} : a \in A \}|$, the latter set being $A \times A$. (Like Asaf, I cannot see any gap in your proof.) $\endgroup$ – user642796 Mar 30 '14 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.