Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Suppose $A$ and $B$ are two infinite sets and cardinality of $B$ is strictly greater than cardinality of $A$.

To prove this strictly gretater than relation between two sets, is it sufficient to only show that there exists no surjective function from $A$ to $B$, or in addition to this, one must also show that there exists a surjection from $B$ to $A$, for proof to be valid.

share|cite|improve this question

First note that the cardinal comparability is done by injections and not by surjections. Assuming the axiom of choice it is the same thing, but without the axiom of choice this is no longer true.

If we assume the axiom of choice then every two cardinals are comparable; and every surjection admits an inverse injection. This means that if we assume the axiom of choice then if there is no surjection from $A$ onto $B$ then there is an injection from $A$ into $B$, and there is no injection from $B$ into $A$ either.

If the framework you are working in does not assume the axiom of choice then you have to show that there is an injection from $A$ into $B$ and there is no injection from $B$ into $A$. It is not sufficient to do so with surjections, nor it is sufficient to show that there is a surjection from $B$ onto $A$ and there is no injection from $A$ into $B$.

share|cite|improve this answer
Why is cardinal comparability done by injections rather than surjections? Is this just a convention? – Stefan Smith Sep 26 '12 at 23:40
@bogus: Without the axiom of choice you still have the Cantor-Bernstein theorem which ensures that injection-based comparison forms a partial order. However you do not necessarily have that for surjections, it is consistent without choice to have two sets which surject onto one another, but have no bijection between them. This means that working with injections is a lot simpler than with surjections. – Asaf Karagila Sep 26 '12 at 23:43
Thanks! (more characters needed) – Stefan Smith Sep 29 '12 at 0:30

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.