Claim : For non-empty sets $A, B$, (if there's no injection from $A$ to $B$, then there exists a surjection from $A$ to $B$.)
I wonder how to prove or disprove that the 1st(2nd)-order logic sentence is generally true in ZF.
That claim is true in ZFC, since we can well-order both A and B, so A and B have cardinalities, the class of cardinalities are linearly ordered by inclusion. So, the claim isn't generally false in ZF.
The converse is false in ZF, since both surjection and injection can exist between the same set A.
And the similar sentence : for non-empty sets A and B, (if there exists a surjection from A to B, then there exists injection from B to A.), is independent about ZF.
I guess the claim isn't generally true in ZF, and I tried to deduce the sentence which is independent about ZF, but not yet succeeded.
Also, I couldn't construct a model of ZF where the counter example exists.
How can I prove or disprove the claim is independent about ZF?
Best Answer
In fact, this statement is equivalent to the axiom of choice. Given a nonempty set $B$, let $A$ be its Hartogs number, the least ordinal that does not inject into $B$. Then, by your assumption, there must be a surjection $f:A\to B$. But since $A$ is well-ordered, we can use this to construct an injection $g:B\to A$, by letting $g(b)$ be the least $a$ such that $f(a)=b$. This gives a well-ordering of $B$.