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.

I think about surjection, injection and bijections from $A$ to $B$ as $\ge$, $\le$, and $=$ respectively in terms of cardinality. Is this correct? And extrapolating from that, are these theorems correct?

If there exist two surjections $f:A\rightarrow B$ and $g:B\rightarrow A$, then $|A|=|B|$ ($|A|\ge|B|$ and $|B|\ge|A|$).

If there exists a surjection $f:A\rightarrow B$ and an injection $g:A\rightarrow B$, then $|A|=|B|$ ($|A|\ge|B|$ and $|A|\le|B|$).

Are these theorems correct?

I know the case for two injections is true.

share|improve this question
1  
Are your sets finite, or arbitrary? If arbitrary, are you assuming the axiom of choice? –  Andres Caicedo Oct 25 '12 at 5:53
    
This contains one part of your question: Proof of a Cantor-Bernstein-like theorem. –  Martin Sleziak Oct 25 '12 at 8:55

2 Answers 2

up vote 2 down vote accepted

If you assume the axiom of choice, then the existence of a surjection $f:A\to B$ implies an injection $e:B\to A$: for $b\in B$ choose $e(b)\in f^{-1}(b)$. Together with the what you know about injections, this gives you everything you want.

share|improve this answer

Nowadays it is commonly accepted to assume the axiom of choice, in which case surjections can always be inverted to injections.

However if one does not assume the axiom of choice then there are surjections which cannot be reversed. In the common models we know where choice fails there are sets which can be mapped onto each other but there is no bijection between them.

The following cases are consistent:

  1. There are $A$ and $B$ such that we can map $A$ onto $B$, but there is no injection between $A$ and $B$ (in either direction).
  2. There are $A$ and $B$ such that $A$ can be mapped onto $B$ and $A$ can be injected into $B$, but there is no bijection between $A$ and $B$.

Note that if there is an injection from $A$ to $B$ then there is a surjection from $B$ onto $A$, therefore the second case we have two sets and surjections between them, but no bijection.

So while it is intuitively reasonable (and to some degree, correct) to think about surjections as a measure of size, formally it fails to upholds the requirements we have from a notion of size (i.e. being a partial order, since this notion lacks antisymmetry as the second case shows).

share|improve this answer

Your Answer

 
discard

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.