3
$\begingroup$

The classical Cantor-Schroder-Bernstein Theorem says that there exists a bijective function $X\leftrightarrow Y$ if and only if there exist injective functions $X\hookrightarrow Y$ and $Y\hookrightarrow X$.

It is known that without Axiom of Choice the injectivity cannot be replaced by the surjectivity in this result.

Nonetheless, without AC, we have the following simple

Fact. If for two sets $X,Y$ there are surjective functions $X\twoheadrightarrow Y$ and $Y\twoheadrightarrow X$, then there exists a bijective function $\mathcal P(X)\leftrightarrow \mathcal P(Y)$ between the corresponding power-sets.

Can the power-sets in this result be replaced by some simpler sets built over $X$, for example, $X^\omega$ or $X\times\omega$?

More precisely:

Question. Assume that for two sets $X,Y$ there exist surjective functions $X\twoheadrightarrow Y$ and $Y\twoheadrightarrow X$.

Is it true (in ZF) that the sets

(i) $X^\omega$ and $Y^\omega$ have the same cardinality?

(ii) $X\times\omega$ and $Y\times\omega$ have the same cardinality?

$\endgroup$
10
  • $\begingroup$ Note: it appears to be an open problem whether existence of surjections both way implies AC: mathoverflow.net/q/38771/30186 $\endgroup$
    – Wojowu
    May 7, 2020 at 11:31
  • 1
    $\begingroup$ @Wojowu I guess you mean, whether (existence of surjection both ways implies bijection) implies AC? $\endgroup$
    – YCor
    May 7, 2020 at 11:34
  • 2
    $\begingroup$ Take $X=c$ and $Y=t$, the cardinal of $\mathbf{R}/\mathbf{Q}$ (here "cardinal" is set modulo bijection). So, if I'm correct there are injections $c\to t$, and surjections in both ways. Also there is a bijection $c\to c^\omega$, and an injection $t\to t^\omega$. If there was a bijection $c^\omega\to t^\omega$ we would deduce an injection $t\to c$, which is not a theorem in ZF+DC as far I as I know. The same seems to apply to $\times\omega$. $\endgroup$
    – YCor
    May 7, 2020 at 11:38
  • 1
    $\begingroup$ It's explicit and you can find it in Wagon's book on the Banach-Tarski paradox. In spirit it looks like: choose an injection $i:\mathbf{N}^2\to\mathbf{N}$ such that $i(n,m)\ge n!$ for every $n$. Then for $x\in [0,1[$ written in binary expansion $x=\sum_{n\in J} 2^{-n}$, map it to $\sum_{n\in J}\sum_m 2^{-i(n,m)}$. I'm not sure this one works, but some variant in the same spirit should. $\endgroup$
    – YCor
    May 7, 2020 at 12:25
  • 1
    $\begingroup$ @TarasBanakh I guess this fitted in a comment, and you have in any case another answer now to accept. $\endgroup$
    – YCor
    May 7, 2020 at 12:50

1 Answer 1

5
$\begingroup$

No, and here is a counterexample.

Suppose that $|\Bbb R|<|[\Bbb R]^\omega|$, that is, there are more countable subsets of reals than reals. This is indeed possible, e.g. if all sets of Lebesgue measurable.

Since $\sf ZF$ proves there are bi-surjections (in fact, an injection from $\Bbb R$ into $[\Bbb R]^\omega$), this would be a counterexample.

Now, $|\Bbb R^\omega|=|\Bbb R\times\omega|=|\Bbb R|$, and even without carefully checking what is $([\Bbb R]^\omega)^\omega$ and $[\Bbb R]^\omega\times\omega$, the cardinality cannot decrease.

$\endgroup$
5
  • $\begingroup$ Thnk you for the answer. In fact, @YCor suggested a bit different counterexample exploiting linearly independent Cantors sets in the real line. Could I ask another question also related to (the absence of) AC: Is $|X\times X|\le|\mathcal P(X)|$ in ZF? I can only prove (trivially) that $|X\times X|\le\min\{|\mathcal P(\mathcal P(X))|,|\mathcal P(X\times\{0,1\})|\}$, but $X\times\{0,1\}$ need not be equipotent with $X$ in ZF. $\endgroup$ May 7, 2020 at 12:51
  • $\begingroup$ In fact, I am interested in the inequality $\mathcal P^2(X\times X)\le \mathcal P^3(X)$. Is it true in ZF, or the 4-th iterate of the power-set operation is necessary? In its turn, I need this for evaluating the Hartogs' number $\aleph(x)$ of a set $x$. It is easy to see that $\aleph(x)\le|\mathcal P^4(x)|$. So the question is about $|\aleph(x)|\le|\mathcal P^3(x)|$ in ZF. $\endgroup$ May 7, 2020 at 12:56
  • $\begingroup$ I have already found the answer to my "Hartogs" question in caicedoteaching.files.wordpress.com/2009/04/580-choiceless.pdf Indeed, $|\aleph(x)|\le|\mathcal P^3(x)|$. $\endgroup$ May 7, 2020 at 13:13
  • $\begingroup$ To your first question, no. It is consistent that there is a set $X$ such that $|X^2|\nleq|\mathcal P(X)|$. About the 3 Hartogs, you can find a question I asked here many years ago related to this. $\endgroup$
    – Asaf Karagila
    May 7, 2020 at 13:35
  • $\begingroup$ Yes, I found this your question from 2012 and also the answer of Caicedo that 3 cannot be lowered to 2. $\endgroup$ May 7, 2020 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.