On the comparability of cardinals in the absence of the axiom of choice
Volume 242 / 2018
Abstract
It is a well-known result of Hartogs’ that the statement “for all sets $x$ and $y$, $x\preceq y$ or $y\preceq x$ (where ‘$x\preceq y$’ means that there is a one-to-one map $f:x\to y$)” is equivalent to the Axiom of Choice ($\mathsf{AC}$) (the latter in the disguise of the well-ordering theorem, i.e., “every set can be well-ordered”). A considerably stronger result by Tarski states that for any natural number $n\ge 2$, the statement “if $x$ is a set consisting of $n$ sets, then there exist distinct elements $y,z\in x$ such that $y\preceq z$ or $z\preceq y$” is equivalent to $\mathsf{AC}$.
In this paper, we investigate the set-theoretic strength of the variant of Tarski’s statement which concerns infinite sets of sets, that is, “if $x$ is an infinite set of sets, then there exist distinct elements $y,z\in x$ such that $y\preceq z$ or $z\preceq y$”. We are mostly interested in denumerable (i.e., countably infinite) and continuum sized sets of sets. Among other results, we show that the above statement:
(a) restricted to denumerable sets of sets, implies “every Dedekind-finite set is finite” and Ramsey’s Theorem for pairs, and that the two implications are not reversible in $\mathsf{ZF}$,
(b) is equivalent to its restriction to denumerable sets of sets; {this settles the corresponding open problem} in Feldman and Orhon (2008),
(c) restricted to continuum sized sets of sets, implies a certain version of the Kinna–Wagner selection principle,
(d) restricted to sets of cardinality $2^{\aleph_{\alpha}}$, where $\aleph_{\alpha}$ is a regular aleph greater than $\aleph_{0}$, is not implied by $\mathsf{DC}_{\lambda}$ in $\mathsf{ZF}$, for any infinite cardinal $\lambda \lt \aleph_{\alpha}$,
(e) restricted to sets of cardinality $2^{\aleph_{0}}$, is not implied by any of the following: (1) $\mathsf{AC^{LO}}$ ($\mathsf{AC}$ restricted to linearly orderable sets of non-empty sets; $\mathsf{AC^{LO}}$ is equivalent to $\mathsf{AC}$ in $\mathsf{ZF}$, but not equivalent to $\mathsf{AC}$ in $\mathsf{ZFA}$) in $\mathsf{ZFA}$, (2) $\mathsf{LW}$ (“every linearly ordered set can be well-ordered”; $\mathsf{LW}$ is equivalent to $\mathsf{AC}$ in $\mathsf{ZF}$, but not equivalent to $\mathsf{AC}$ in $\mathsf{ZFA}$) in $\mathsf{ZFA}$, (3) $\mathsf{AC^{WO}}$ ($\mathsf{AC}$ restricted to well-orderable sets of non-empty sets) in $\mathsf{ZF}$.
