0
$\begingroup$

By surjective comparability I mean the following principle:

"For any nonempty sets $A,B$: there exists a surjective function $f$ from $A$ to $B$ or there exists a surjective function $g$ from $B$ to $A$."

  1. Is this statement provable in $ZF$?

  2. If not then what exactly that principle is equivalent to (over $ZF$)?

$\endgroup$
2
$\begingroup$

This principle (for nonempty sets, to avoid a trivial counterexample) is equivalent to the axiom of choice. One direction is in a previous answer. For the converse, let $X$ be an arbitrary set (which I want to well-order). Apply Hartogs's theorem to get an ordinal $\alpha$ so large that it cannot be mapped one-to-one into the power set $\mathcal P(X)$. Then $X$ cannot be mapped onto $\alpha$, because if $f:X\to\alpha$ were surjective then $\alpha\to \mathcal P(X):\beta\mapsto f^{-1}(\{\beta\})$ would map $\alpha$ one-to-one into $\mathcal P(X)$. So, by your principle, there is a surjection $g:\alpha\to X$. Then $X$ can be well-ordered by setting $x\prec y$ iff the first $\beta$ with $g(\beta)=x$ is smaller than the first $\beta$ with $g(\beta)=y$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ possibly you meant: $\alpha \to \mathcal P(X): \beta \mapsto \{x \in X| f(x)=\beta\}$, this would be a one-to-one map from $\alpha$ to $\mathcal P(X)$ and the proof would work through. $\endgroup$ – Zuhair Oct 16 '19 at 11:56
  • $\begingroup$ @Zuhair What you wrote in your comment seems to be just a long way to say the same thing that I wrote. Remember that, when $Z$ is a subset of the domain of a function $f$, the notation $f^{-1}(Z)$ means $\{x:f(x)\in Z\}$. In the case at hand, $Z$ is $\{\beta\}$. $\endgroup$ – Andreas Blass Oct 16 '19 at 12:46
  • $\begingroup$ Yes, but that should have been written as: $\alpha\to \mathcal P(X):\beta\mapsto f^{-1}(\{\beta\}) $ $\endgroup$ – Zuhair Oct 16 '19 at 13:43
  • $\begingroup$ @Zuhair Thanks for pointing out the missing $\mathcal P$. I'll correct it. $\endgroup$ – Andreas Blass Oct 16 '19 at 16:50
-1
$\begingroup$

In ZFC you can well-order any set (in fact, this is equivalent to AC over ZF). Thus you can compare cardinalities of any two sets and then you have a surjection in (at least) one direction. In general, it is impossible to do this without AC.

| cite | improve this answer | |
$\endgroup$

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