# surjective map and cardinality

I work in $\mathsf{ZF}$(without the axiom of choice). Let $A, B$ be sets such that $\left| A \right |$ and $\left|B \right |$ are both defined and let $f \colon A \to B$ a surjective function. Can I prove that $\left| A \right | \ge \left|B \right |$? Or it can't be provable?

-

If $A$ is well-orderable, then the answer is yes.

One classic example is in models where $\aleph_1\nleq2^{\aleph_0}$. But we can still prove in $\sf ZF$ that there is a surjection from $\mathcal P(\omega)$ onto $\omega_1$.

Another classic example is when we have an infinite set without a countably infinite subset. In that case we can prove that there is such set which can be mapped onto $\omega$; but by definition there is no injection back.

The assertion that if $f\colon A\to B$ is surjective then there is $g\colon B\to A$ injective is known as The Partition Principle. It is clearly implied by the axiom of choice, and we can show quite easily that it is not provable in $\sf ZF$ itself (it has quite a lot of consequences which we know are consistent).

However the question whether or not the partition principle implies the axiom of choice is the oldest [still] open question in set theory.

-
How I can prove that the Partition Principle isn't provable in ZF? Thank you. – andreasvr Mar 25 '14 at 20:36
Exhibiting the consistency of either one of the examples with $\sf ZF$ would suffice. (For the former try the Feferman-Levy model, for the latter any model with an infinite Dedekind-finite set, e.g. Cohen's first model.) – Asaf Karagila Mar 25 '14 at 20:41
@Andres: Yes. Sleep deprivation does that. Thank you. – Asaf Karagila Mar 25 '14 at 21:49

If $A$ and $B$ are finite, they yes, via the Pigeonhole Principle.

For infinite sets, see Dedekind Infinite Sets in ZF and the summary at the top of that article.

-
Sorry, but in your link I don't find the answer at my question. Could you be more precise? – andreasvr Mar 25 '14 at 20:31