# Half Cantor-Bernstein Without Choice

I had a discussion with one of my teachers the other day, which boiled to the following question:

Assume ZF. Let $A,B$ be sets such that there exist $f\colon A\to B$ which is injective and $g\colon A\to B$ which is surjective.

Is there $h\colon A\to B$ which is bijective?

Of course it is enough to show that there is an injection from $B$ into $A$, and by the Cantor-Bernstein theorem (which does not require choice) we finish the proof.

My intuition says that this is true, his intuition says it is false.

Insights, references and possible solutions will be appreciated!

As Ricky shows below, it depends on $A$ and $B$.

So to a more specific choice of sets (for which I think it is true) we have $A=\mathbb R^\omega$ (i.e. infinite sequences of real numbers) and $B=[\mathbb R]^\omega$ (i.e. countable subsets of real numbers)

-
In general, given a surjection f, it requires Choice to find a right inverse g (so f(g(x))=x). If you have an injection from the domain of f into an ordinal, then you have a well-ordered domain and then can construct the function g without Choice. Gerhard "Ask Me About System Design" Paseman, 2011.05.18 – Gerhard Paseman May 18 '11 at 22:33
Andres Caicedo wrote some days back about these here: mathoverflow.net/questions/38771/… Consider, Statement P: If there is a surjection from A to B then there is an injection from B to A. Statement Q: If there are injections and surjections from A to B then there is a bijection between them. Statement R: If there are surjections from A to B and from B to A then there is a bijection between them. Then AC -> P, P -> Q and Q -> R. It is natural to wonder if R -> Q or Q -> P? – Ashutosh May 26 '11 at 20:59

If $A = \{0\}\times 2^{\omega}$ and $B = (\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)$ and there is no injection from $\omega_1$ to $2^{\omega}$,
then there does not exist such a bijection.

Define $f : (\{0\}\times 2^{\omega}) \to ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1))$ by $f(x) = x$. Obviously, $f$ is injective.
Define $\operatorname{pair} : \omega^2 \to \omega$ by $\operatorname{pair}(\langle m,n\rangle) = ((m+n)\cdot (m+n+1))+(2\cdot n)$.
Define $g_1 : 2^\{\omega\} \to \omega_1$ by

$g_1(x) = \begin{cases} \alpha & \text{if } \{\langle m,n\rangle \in \omega^2 : \operatorname{pair}(\langle m,n\rangle) \in x\} \text{ is a well-order of } \omega \text{ with order type } \alpha \\ 0 & \text{else} \end{cases} \quad .$

Define $g : (\{0\}\times 2^{\omega}) \to ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1))$ by

$g(\langle 0,x\rangle) = \begin{cases} \langle 0,\{n\in \omega : (n+1) \in x\}\rangle & \text{if } 0 \notin x \\ \langle 1,g_1(\{n\in \omega : (n+1) \in x\})\rangle & \text{if } 0\in x\end{cases} \quad .$

Since $g_1$ is surjective, $g$ is also surjective. Let $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)) \to (\{0\}\times 2^{\omega})$ be a function. Define $h_1 : \omega_1 \to 2^{\omega}$ by $h_1(\alpha) = \operatorname{secondentry}(h(\langle 1,\alpha \rangle))$.
$h_1$ is not injective, so $h$ is not injective either.
This works for all functions $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)) \to (\{0\}\times 2^{\omega})$, so
there does not exist a bijection $h : ((\{0\}\times 2^{\omega})\cup (\{1\}\times \omega_1)) \to (\{0\}\times 2^{\omega})$.

if $A = \{\}$ and $B = \{\}$, then there does exist such a bijection.

Define $h : A\to B$ by $h(x) = x$.

Therefore there does not have to be a single answer, it can depend on $A$ and $B$.

If all sets of reals have Baire property, then there is no injection from $[\mathbb R]^\omega$ to $\mathbb R^\omega$.

Let $h : [\mathbb R]^\omega \to \mathbb R^\omega$ be a function. Define $\leq$ as the lexicographic order of $\mathbb R^\omega$.
By this answer there is no total order of ${\mathbb R}/\sim$. All members of ${\mathbb R}/\sim$ are countable subsets of $\mathbb{R}$.
Define $\leq_h$ on ${\mathbb R}/\sim$ by $x\: \leq_h\: y$ if and only if $h(x) \leq h(y)$. Since $\leq_h$ is not a total order, $h$ is not injective. This works for all functions $h : [\mathbb R]^\omega \to \mathbb R^\omega$, therefore there is no injection $h : [\mathbb R]^\omega \to \mathbb R^\omega$.

By shelah.logic.at/files/446.ps (which I can't figure out how to make markdown link to),
$\operatorname{ZF} + \operatorname{DC}(\omega_1)$ does not prove that there is an injection from $[\mathbb R]^\omega$ to $\mathbb R^\omega$.

-
Ricky: Wonderful answer. I have added some more to the original question. – Asaf Karagila May 18 '11 at 22:00

Your teacher's intuition is the correct one.

First of all, recall that a set $S$ is said to be Dedekind finite if there is no bijection between $S$ and any proper subset of $S$. In the early days of forcing Cohen showed that if $ZF$ is consistent, then it is consistent with $ZF$ for there to exist an infinite Dedekind finite set $S$; indeed Cohen's proof shows that $S$ can be arranged to be a collection of real numbers.

Now the key result that answers your question: It is a theorem of Tarski that if $S$ is infinite but Dedekind finite, then by choosing:

$B$ := the set of all finite one-to-one sequences whose members come from $S$, and

$A$ := $B$ \ the empty sequence,

then $A$ and $B$ provide a counterexample for your choice-free surjective version of the Cantor-Bernstein theorem, i.e., there is no bijection between $A$ and $B$ [nontrivial], but there is a injection from $A$ to $B$ [trivial], as well as a surjection from $A$ to $B$ [easy].

The above solution is plagiarized from Exercise 8 [p.162] of Jech's The Axiom of Choice (available as a Dover paperback). The credit to Tarski appears there on p.166.

You may also wish to consult the hints provided for Exercise 2.42 [p.92] of Levy's Basic Set Theory, another excellent text republsihed by Dover.

-
I edited to make it match Jech's exercise. Apart from an obvious typo, the important change is that $B$ (and thus also $A$) should consist of one-to-one sequences. Without that stipulation, there's an easy bijection. – Andreas Blass May 19 '11 at 1:02
The surjection from $A$ to $B$ is trivial; it just deletes the first term from any nonempty sequence. – Andreas Blass May 19 '11 at 1:04
Andreas, thanks for editing; I also edited further to reflect your second comment. – Ali Enayat May 19 '11 at 2:54

To your original question, it seems worth mentioning the point that your hypothesis implies the following:

If $|A| = |A \times 2|$ and there is a surjection from $A$ onto $B$, then $B$ injects into $A$.

This really just generalizes the example given by Ricky, but to see this:

Suppose we have a bijection $b: A \rightarrow A \times \{0, 1\}$ and a surjection $g: A \rightarrow B$. $A$ injects into $A \cup B$ by the inclusion map, and we can get a surjection from $A$ onto $A \cup B$ by mapping an $a \in A$ to itself if the second coordinate of $b(a)$ is $0$ or to $g(a)$ if the second coordinate of $b(a)$ is $1$. In other words, we split $A$ into two copies of itself, mapping the first copy surjectively (bijectively) onto itself via the identity and the second copy surjectively onto $B$ via $g$. By your stated principle, this would then mean that we have a bijection $h$ from $A$ onto $A \cup B$ whereby $h^{-1} \upharpoonright B$ would be an injection from $B$ into $A$.

From this observation, I think it becomes intuitively clear how your principle is a form of choice in disguise. In particular, your principle would imply that $\alpha^+$ injects into $\mathcal{P}(\alpha)$ for every infinite ordinal $\alpha$ since we have a surjection from $\mathcal{P}(\alpha)$ onto $\alpha^+$ (even without choice by virtue of the fact that every ordinal of size $|\alpha|$ is encoded by a subset of $\alpha$). But as I'm sure you're already aware, models of ZF have been constructed where this will not be the case.

-
I should mention that I may be abusing notation slightly, mainly $|A| = |A \times 2|$ is meant as there exists a bijection between $A$ and $A \times 2$ (or that the class of sets in bijective correspondence with $A$ is equal to the class of sets in bijective correspondence with $A \times \{0, 1\}$. I do not mean to imply that we can assign arbitrary sets $A$ an ordinal number for which there is a bijective correspondence (without choice). – Jason May 19 '11 at 6:09
(or that the set of sets of minimal rank equinumerous to $A$ is equal to the set of sets of minimal rank equinumerous to $A\times \{0,1\}$) – Ricky Demer May 19 '11 at 6:52
Jason, that's a nice observation. It is well-known that in the Solovay model $omega_1$ cannot be injected into the reals. I suspect that the same is true in the Feferman-Levy model (in which the reals can be written as a countable union of countable sets). – Ali Enayat May 19 '11 at 18:08