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

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

### Related Questions

#### Sponsored Content

#### 0 Answered Questions

### Schroder-Bernstein Theorem using AC

**2019-03-14 16:47:59****Robert Singleton****41**View**0**Score**0**Answer- Tags: proof-verification set-theory

#### 1 Answered Questions

### [SOLVED] There exists surjections from A onto B and vice versa, and there is no bijection between the sets?

**2017-09-09 14:36:05****Adam53****226**View**9**Score**1**Answer- Tags: set-theory

#### 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

**2017-04-17 12:44:45****Roger****159**View**2**Score**1**Answer- Tags: real-analysis functions cardinals decimal-expansion

#### 2 Answered Questions

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

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

#### 0 Answered Questions

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

**2014-10-29 01:16:21****Stefan Mesken****82**View**0**Score**0**Answer- Tags: set-theory axiom-of-choice

#### 1 Answered Questions

### [SOLVED] Help explain the set being constructed in this Cantor-Schroder-Berstein proof

**2014-09-10 16:00:52****mauna****73**View**1**Score**1**Answer- Tags: functions elementary-set-theory proof-writing infinity

#### 1 Answered Questions

### [SOLVED] How to prove this version of the Cantor-Schroder-Bernstein theorem?

**2014-09-09 17:03:02****mauna****557**View**3**Score**1**Answer- Tags: functions elementary-set-theory proof-verification proof-writing

#### 1 Answered Questions

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

**2014-05-01 22:29:16****ItsMe****172**View**4**Score**1**Answer- Tags: elementary-set-theory functions

#### 1 Answered Questions

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

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

## 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 Principlesays 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

didrequire that $f\circ g=id$ in the partition principle, itwouldbe 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.