Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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