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.

Let $A,B$ be two sets. The Cantor-Schroder-Bernstein states that if there is an injection $f\colon A\to B$ and an injection $g\colon B\to A$, then there exists a bijection $h\colon A\to B$.

I was wondering whether the following statements are true (maybe by using the AC if necessary):

  1. Suppose $f \colon A\to B$ and $g\colon B\to A$ are both surjective, does this imply that there is a bijection between $A$ and $B$.
  2. Suppose either $f\colon A\to B$ or $g\colon A\to B$ is surjective and the other one injective, does this imply that there is a bijection between $A$ and $B$.
share|improve this question
    
With choice, both are clearly true (if you reverse one of the arrows in 2., as you probably intended). If you mean to ask about the statements in absence of choice, you should add axiom-of-choice tag (and point it out in your question). –  tomasz Jul 30 '12 at 21:08
    
    
@AsafKaragila, Not widely known, it is actually just Schroder-Bernstein. Cantor left the group in the middle of their 1896 concert tour because of poor ticket sales. They called it "creative differences" but that's just a euphemism. –  Will Jagy Jul 30 '12 at 22:29
3  
@Will: Actually Cantor proved it from the linearity of the order of cardinals (choice); Schroeder claimed to have proved it without it, but he had a fatal mistake; Bernstein who was a student of Cantor finally proved it without choice. Dedekind was also involved in this and proved this independently twice or so in between the whole story. There's a link to the history of the theorem somewhere on the site (I think on one of my answers, but in the comments...). –  Asaf Karagila Jul 30 '12 at 22:36
2  
@Asaf: My comment to this answer of yours (the thread you link to in your first comment) links to this page. Isn't that what you have in mind in your last sentence? Also, the book Zermelo's Axiom of Choice: Its Origins, Development, and Influence by G.H. Moore gives quite a detailed account of the history of the result in its first chapter. –  t.b. Jul 31 '12 at 6:08

2 Answers 2

up vote 8 down vote accepted

For the first one the need of the axiom of choice is essential. There are models of ZF such that $A,B$ are sets for which exists surjections from $A$ onto $B$ and vice versa, however there is no bijection between the sets.

Using the axiom of choice we can simply inverse the two surjections and have injections from $A$ into $B$ and vice versa, then we can use Cantor-Bernstein to ensure a bijection exists.

The second one, I suppose should be $f\colon A\to B$ injective and $g\colon A\to B$ surjective, again we need the axiom of choice to ensure that there is a bijection, indeed there are several models without it where such sets exist but there is no bijection between them. Using the axiom of choice we reverse the surjection and use Cantor-Bernstein again.

It should be noted that without the axiom of choice it is true that if $f\colon A\to B$ is injective then there is $g\colon B\to A$ surjective. Therefore if the first statement is true, so is the second, and if the second is false then so is the first.

Another interesting point on this topic is this: The Partition Principle says that if there is $f\colon A\to B$ surjective then there exists an injective $g\colon B\to A$. Note that we do not require that $f\circ g=\mathrm{id}_B$, but simply that such injection exists.

This principle implies both the statements, and is clearly implied by the axiom of choice. It is open for over a century now whether or not this principle is equivalent to the axiom of choice or not.

Lastly, as stated $f\colon A\to B$ injective and $g\colon B\to A$ surjective cannot guarantee a bijection between $A$ and $B$ with or without the axiom of choice. Indeed the identity map is injective from $\mathbb Z$ into $\mathbb R$, as well the floor function, $x\mapsto\lfloor x\rfloor$ is surjective from $\mathbb R$ to $\mathbb Z$ but there is no bijection between $\mathbb Z$ and $\mathbb R$.

share|improve this answer
    
Correct me if I'm wrong, but I think that if you did require that $f\circ g=id$ in the partition principle, it would be equivalent to choice. (By taking $B$ an arbitrary family of disjoint nonempty sets, $A$ its union and $f$ the function which takes an element of $A$ to the only element of $B$ of which it is a member.) –  tomasz Aug 1 '12 at 12:24
    
@tomasz: Yes, that would be equivalent to the axiom of choice. –  Asaf Karagila Aug 1 '12 at 12:26

As stated, 2. is clearly false (just take $A=\{ 0,1\} ,B=\{ 0\}$ with $f$ identically zero, and $g$ likewise). I will assume that it's actually $f:A\to B$ and $g:A\to B$.

Using axiom of choice, both statements can be shown to be true, simply because when we have a surjection $f:A\to B$, then by axiom of choice we can choose a right inverse $f^{-1}:B\to A$ which will be injective, so we can reduce both statements to the usual C-B-S.

Without choice, neither statement can be proved.

For the first one, see http://mathoverflow.net/questions/38771 (apparently, it would imply countable choice).

For the second one, see http://mathoverflow.net/questions/65369/half-cantor-bernstein-without-choice.

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.