11
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ possible duplicate of axiom of choice: cardinality of general disjoint union $\endgroup$
    – vadim123
    Commented Mar 30, 2014 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$ Commented Mar 30, 2014 at 4:47
  • 1
    $\begingroup$ I never heard of Russell Cardinals, what are they? $\endgroup$
    – bof
    Commented Mar 30, 2014 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
    Commented Mar 30, 2014 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
    Commented Mar 30, 2014 at 5:41

1 Answer 1

11
$\begingroup$

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".

$\endgroup$
7
  • $\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
    Commented Mar 30, 2014 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
    Commented Mar 30, 2014 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
    Commented Mar 30, 2014 at 6:40
  • 1
    $\begingroup$ There is no possibility that you subtly misstated the proposition? $\endgroup$
    – bof
    Commented Mar 30, 2014 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
    Commented Mar 30, 2014 at 8:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .