PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

On the comparability of cardinals in the absence of the axiom of choice

Volume 242 / 2018

Eleftherios Tachtsis Fundamenta Mathematicae 242 (2018), 247-266 MSC: Primary 03E25; Secondary 03E35. DOI: 10.4064/fm376-11-2017 Published online: 26 April 2018


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}$.


  • Eleftherios TachtsisDepartment of Mathematics
    University of the Aegean
    Karlovassi 83200, Samos, Greece

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image