# Implications of the existence of a pair of surjective functions, without Axiom of Choice

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?

• Note: it appears to be an open problem whether existence of surjections both way implies AC: mathoverflow.net/q/38771/30186 – Wojowu May 7 at 11:31
• @Wojowu I guess you mean, whether (existence of surjection both ways implies bijection) implies AC? – YCor May 7 at 11:34
• 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$. – YCor May 7 at 11:38
• 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. – YCor May 7 at 12:25
• @TarasBanakh I guess this fitted in a comment, and you have in any case another answer now to accept. – YCor May 7 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.

• 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. – Taras Banakh May 7 at 12:51
• 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. – Taras Banakh May 7 at 12:56
• 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)|$. – Taras Banakh May 7 at 13:13
• 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. – Asaf Karagila May 7 at 13:35
• Yes, I found this your question from 2012 and also the answer of Caicedo that 3 cannot be lowered to 2. – Taras Banakh May 7 at 14:58