Half Cantor-Bernstein without choice

Question

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)

Answer 1

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 https://shelah.logic.at/papers/466/ $\operatorname{ZF} + \operatorname{DC}(\omega_1)$ does not prove that there is an injection from $[\mathbb R]^\omega$ to $\mathbb R^\omega$.

Answer 2

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.

Answer 3

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.