5
$\begingroup$

Consider the following statements in $\sf ZF$:

(S) If $A, B$ are nonempty sets, then there is a surjection $s:A \to B$, or there is a surjection $t:B\to A$.

(I) If $A, B$ are sets, then there is an injection $i:A\to B$, or there is an injection $j:B\to A$.

Note that (I) implies (S). Assuming $\sf AC$, both statements are true.

Question. Is there a model of $\sf ZF$ in which (S) holds, but not (I)?

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ Both imply AC... $\endgroup$
    – Asaf Karagila ♦
    Commented Jan 1, 2022 at 15:21

1 Answer 1

Reset to default
16
$\begingroup$

The answer is no. Both (I) and (S) are equivalent to AC over ZF. Indeed, for any set $S$ the class of ordinals $\alpha$ such that $\alpha$ injects into $S$ (resp. $S$ surjects onto $\alpha$) is a set, so there is some ordinal $\beta$ outside this set. Assuming (I) (resp. (S)), there is an injection $S\to\beta$ (resp. surjection $\beta\to S$). In the latter case, we also get an injection $S\to\beta$, by taking any element $S$ to the least element in its preimage. In either case, we see $S$ is well-orderable. Thus both (I) and (S) imply well-ordering theorem and hence AC.

Since both (I) and (S) are equivalent to AC, they are also equivalent to each other.

Improve this answer
$\endgroup$
4
  • $\begingroup$ for any set $S$ the class of ordinals $\alpha$ such that $\alpha$ injects into $S$ (resp. $S$ surjects onto $\alpha$) is a set. Is there a simple argument to see this (especially for the "surjects" part)? $\endgroup$
    – Martin Väth
    Commented Jan 3, 2022 at 20:21
  • $\begingroup$ @MartinVäth For injections: for any $S$, you can form the set $A$ of all isomorphism classes of well-orders on subsets of $S$. By replacement, mapping each element of $A$ to its order type gives the class of ordinals which inject into $S$. For surjections, note that if $S$ surjects onto $\alpha$, then $\alpha$ injects into $P(S)$. $\endgroup$
    – Wojowu
    Commented Jan 3, 2022 at 20:25
  • $\begingroup$ Thank you. So the argument is essentially the same than proving/using Hartog's theorem (for injections) or the analogous Lindenbaum theorem (for surjections). These are not hard, but I was hoping for an essentially simpler proof. $\endgroup$
    – Martin Väth
    Commented Jan 3, 2022 at 20:33
  • $\begingroup$ @MartinVäth Hartogs' and Lindenbaum's theorems are precisely what my argument uses. I have essentially just expanded the arguments for their proofs. $\endgroup$
    – Wojowu
    Commented Jan 3, 2022 at 20:37

You must log in to answer this question.

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