10
$\begingroup$

Looking at the top answer on this page a user Asaf Karagila said:

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.

Can anyone give an example of this?

If A is the set of real numbers and B is the set of natural numbers, then there will be a surjection from A to B, but no surjection from B to A.

Is this what surjection even means? For example $A \mapsto \text{int}(A)$, which maps

$$ 1.5 \mapsto 1 \\ \sqrt{2} \mapsto 1 \\ 2.3 \mapsto 2 \\ 2.6 \mapsto 2 \\ \vdots $$ is a surjection from the reals to the naturals. But there is no surjection from the naturals to the reals (Cantor's diagonal proof).

So, how is it even possible to have "There exists surjections from $A$ onto $B$ and vice versa, and there is no bijection between the sets"? Did he, maybe, mean there is no way to find the formula for the bijection?

$\endgroup$

1 Answer 1

15
$\begingroup$

It is provable from $\sf ZF$ that there is a surjection from $\Bbb R$ onto $\{A\subseteq\Bbb R\mid A\text{ is countable}\}$. This is because it is provable that the cardinality of $\Bbb R$ is equal to the cardinality of $\Bbb{R^N}$, and then we can just map each sequence of real numbers to the set of numbers appearing in the sequence.

And of course, there is a surjection from $\{A\subseteq\Bbb R\mid A\text{ is countable}\}$ onto $\Bbb R$, simply map $\Bbb N\cup\{r\}$ to $r$ for all $r\notin\Bbb N$; and $\Bbb N\setminus\{n\}$ to $n$ for all $n\in\Bbb N$, and any other countable set to $0$.

But it is provable that if there is a bijection between $\Bbb R$ and $\{A\subseteq\Bbb R\mid A\text{ is countable}\}$, then there is a set which is not Lebesgue measurable. Since it is consistent with $\sf ZF$ that all sets of reals are Lebesgue measurable, it follows that it is consistent that there is no bijection between these two sets.

Note, by the way, that the second surjection onto the reals has an easy injective inverse. If we could find an injection from $\{A\subseteq\Bbb R\mid A\text{ is countable}\}$ to $\Bbb R$, then the Cantor–Bernstein theorem (which requires no choice for its proof) would imply the existence of a bijection. So the problem is indeed finding an inverse to the first surjection.

In other words, it is impossible to uniformly assign every countable set of reals an enumeration without using the axiom of choice.


More generally, however, note that since the axiom of choice implies that given two sets with mutual surjections there is a bijection between them, it is generally not a trivial task to imagine "how such two sets which contradict this" would look like. We are just lucky enough that in this case we can find these sets in the realm of the real numbers. But generally, counterexamples to the axiom of choice are as intangible as its consequences (e.g. a well-ordering of the real numbers).

$\endgroup$
4
  • 1
    $\begingroup$ Another argument (skipping Lebesgue measurability) is that it is consistent that $\omega_1$ does not inject into $\mathbb R $, but any set has more well-orderable subsets than elements. $\endgroup$ Commented Sep 9, 2017 at 15:28
  • $\begingroup$ Yes, but that won't give you two surjections, though. $\endgroup$
    – Asaf Karagila
    Commented Sep 9, 2017 at 15:30
  • 1
    $\begingroup$ I'm not sure I understand. Your two surjections are always there, all I'm saying is that it suffices that $\omega_1\not\le\mathfrak c $ to conclude that $|[\mathbb R]^{\aleph_0}|>\mathfrak c $. $\endgroup$ Commented Sep 9, 2017 at 15:35
  • $\begingroup$ Ah. Okay. I thought you were suggesting $\Bbb R$ and $\omega_1$ as two sets consistently with surjections between them but no bijection. $\endgroup$
    – Asaf Karagila
    Commented Sep 9, 2017 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .