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

If I there exists an injection $\phi: S_1 \to S_2$ and a surjection $\tau: S_1 \to S_2$, does there necessarily exist a bijection between sets $S_1$ and $S_2$?

I'd like this to be true, but I don't see a way to construct a bijection directly from $\phi$ and $\tau$.

share|cite|improve this question

marked as duplicate by Asaf Karagila, Chris Eagle, Jim, Andreas Caranti, Alexander Gruber Feb 26 '13 at 11:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Depends of AC.. – Gastón Burrull Feb 26 '13 at 1:19
@hchau, could you tell us the level that you're learning at? Depending on if you're learning elementary discrete maths, or axiomatic set theory, it can make a big difference to what form your answer takes. – Dan Rust Feb 26 '13 at 1:23
Oh, so I haven't actually taken an undergraduate set theory course yet, but this question just popped into my mind, so I thought I'd ask it here. – hchau Feb 26 '13 at 1:32
I have actually answered this question at least once on this site (and I believe that it was twice or thrice). – Asaf Karagila Feb 26 '13 at 5:54
up vote 7 down vote accepted

The statement that if there is a surjection from $A$ to $B$, then there is an injection from $B$ to $A$ is known as the Partition principle. It is a consequence of the axiom of choice, and it’s not known whether it is equivalent to the axiom of choice. Given the partition principle, the existence of both an injection and a surjection from $A$ to $B$ implies the existence of injections from $A$ to $B$ and $B$ to $A$, and the Schröder-Bernstein theorem then implies that there is a bijection from $A$ to $B$.

share|cite|improve this answer

Cantor-Bernstein-Schroeder Theorem

And the fact that, if there exists a surjection from A to B, then there exists an injection from B to A.

share|cite|improve this answer
Assuming the axiom of choice. Which really should be mentioned in this case, since the Schröder-Bernstein theorem itself does not require AC. – Brian M. Scott Feb 26 '13 at 1:07
Strictly speaking, a surjection from A to B only implies an injection from B to A if you have some form of the axiom of choice at your disposal. – Dan Rust Feb 26 '13 at 1:08

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