Take the 2-minute tour ×
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.

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|improve this question
    
Depends of AC.. –  Gastón Burrull Feb 26 '13 at 1:19
1  
@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. –  Daniel 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
    
add comment

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.

2 Answers

up vote 6 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|improve this answer
add comment

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|improve this answer
3  
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
2  
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. –  Daniel Rust Feb 26 '13 at 1:08
add comment

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