By gifty


2012-07-30 21:06:54 8 Comments

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$.

2 comments

@Asaf Karagila 2012-07-30 21:18:52

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$.

@tomasz 2012-08-01 12:24:42

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.)

@Asaf Karagila 2012-08-01 12:26:32

@tomasz: Yes, that would be equivalent to the axiom of choice.

@tomasz 2012-07-30 21:21:05

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 https://mathoverflow.net/questions/38771 (apparently, it would imply countable choice).

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

Related Questions

Sponsored Content

1 Answered Questions

1 Answered Questions

[SOLVED] Proof that $\bigcup X$ is in bijection with $X$.

  • 2017-05-21 23:27:16
  • user 242964
  • 87 View
  • 3 Score
  • 1 Answer
  • Tags:   set-theory

1 Answered Questions

[SOLVED] Cardinality & Schroder-Bernstein Theorem

2 Answered Questions

[SOLVED] About the Cantor-Schroeder-Bernstein theorem.

  • 2016-12-07 10:29:05
  • Gabriel
  • 1248 View
  • 7 Score
  • 2 Answer
  • Tags:   set-theory

0 Answered Questions

Does this version of Schröder-Bernstein-Cantor imply choice?

1 Answered Questions

[SOLVED] Use Cantor-Schroder-Bernstein to prove |X1|=|X2|

1 Answered Questions

[SOLVED] How does the Schroder-Bernstein Theorem imply this?

  • 2013-11-08 21:25:17
  • Jrx
  • 150 View
  • 1 Score
  • 1 Answer
  • Tags:   set-theory

Sponsored Content