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?

  • $\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 '20 at 11:31
  • 1
    $\begingroup$ @Wojowu I guess you mean, whether (existence of surjection both ways implies bijection) implies AC? $\endgroup$ – YCor May 7 '20 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 '20 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 '20 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 '20 at 12:50

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.

  • $\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$ – Taras Banakh May 7 '20 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$ – Taras Banakh May 7 '20 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$ – Taras Banakh May 7 '20 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 '20 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$ – Taras Banakh May 7 '20 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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