6
$\begingroup$

I don't know a name for it, so let me call "even bipartition principle" the statement that every infinite set $X$ is equinumerous to $X \times \mathbf{2}$, where $\mathbf{2} = \{0, 1\}$ — in other words, every infinite set $X$ can be partitioned into two subsets $Y, Z$ such that $X, Y, Z$ are all equinumerous.

It is pretty intuitive, and quite easily provable in ZFC. For example, one can well-order $X$, then, for all limit ordinal $\kappa$ and all integer $e$, put the element associated to $\kappa + e$ in either part of the partition depending on the parity of $e$. Alternatively, apply Zorn's lemma to the set of functions $f : X \to \mathbf{2}$ such that $|f^{-1}(0)| = |f^{-1}(1)|$, ordered by graph inclusion, then send the one possibly remaining element indifferently to 0 or 1.

On the other hand, as I learn from Noah Schweber here, it is consistent with ZF that there exists an amorphous set, i.e., an infinite set which cannot even be partitioned into two infinite subsets (not even requiring that they are equinumerous to the original set).

A related principle is: every infinite set $X$ can be partitioned into $|X|$ many subsets which are equinumerous to it, or put differently, $|X| = |X \times X|$. This is also provable in ZFC, and it is a theorem of Tarski that it implies choice over ZF. The proof is the following. Let $X$ be an infinite set, and let us prove that $X$ can be well-ordered. Using the Hartogs number construction, we can find (in ZF) an ordinal $\kappa$ which cannot be injected into $X$. By assumption, there is a bijection $f : (X \uplus \kappa) \leftrightarrow (X \uplus \kappa) \times (X \uplus \kappa)$. The image of $X$ cannot cover any of the "fibers" $(X \uplus \kappa) \times \{x\}$ for $x \in X$ because that would give an injection $\kappa \to X$. So, if we define $g(\gamma)$ for $\gamma \in \kappa$ to be the second component of $f(\gamma)$ when it is in $X$, we get a partial function $g : \kappa \dashrightarrow X$ which is surjective. Thanks to the well-ordering on $\kappa$, we can find a section for this surjection without the axiom of choice, by setting $h(x) = \min g^{-1}(\{x\})$, which gives an injection $h : X \to \kappa$. Now define $(x ≤ y) := (h(x) ≤ h(y))$: it is a well-ordering on $X$ by injectivity.

Question: Can we assess the axiomatic strength of this "even bipartition principle"? I don't see a way to modify the proof above in order to prove that it implies choice over ZF. Is it strictly weaker? Is it equivalent to some known variant of choice or any more well-known axiom?

$\endgroup$
5
  • 1
    $\begingroup$ Inequivalence with choice was open for a while on this and the eventual proof by Sageev has always seemed very intimidating to me. (Howard and Halpern also wrote a paper with some results on cardinals so-partitionable but it doesn't directly address the question of the strength of every cardinal being of this sort.) $\endgroup$ Commented Jul 26 at 22:42
  • 1
    $\begingroup$ (Oh and the intro to Sageev mentions Halpern and Howard proved inequivalence over ZFA in another paper.) $\endgroup$ Commented Jul 26 at 22:45
  • $\begingroup$ Oooof, little did I imagine that this little simple question would take a 184-page paper to answer. Thanks for the pointer! I think you can convert your comment to an answer. $\endgroup$ Commented Jul 26 at 22:56
  • 1
    $\begingroup$ Perhaps not directly related, but still in the same kind of area, you might be interested in this paper: arxiv.org/pdf/math/0605779 which shows that $\vert 3 \times X\vert = \vert 3 \times Y\vert$ implies $\vert X \vert = \vert Y \vert$ without AC. $\endgroup$ Commented Jul 26 at 23:49
  • 2
    $\begingroup$ @ChrisEagle And similarly for 2 rather than 3. Whereas "for all $X,Y$ $X^2 = Y^2$ implies $X=Y$" is equivalent to AC. $\endgroup$ Commented Jul 27 at 0:15

1 Answer 1

5
$\begingroup$

Gershon Sageev proved that $X+X=X$ does not imply the axiom of countable choice. However it is an easy exercise to show that it implies there are no infinite Dedekind finite sets (e.g., amorphous sets are infinite Dedekind finite sets).

Sageev, Gershon An independence result concerning the axiom of choice. Ann. Math. Logic 8 (1975), 1–184.

On the other hand, as a choice principle itself this statement is not provable from $\sf ZF+DC_\kappa$ for any $\kappa$ (see The relationship of ${\frak m+m=m}$ to AC).

$\endgroup$

You must log in to answer this question.

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