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?

Improve this question
$\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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented May 7, 2020 at 12:50

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Taras Banakh
    Commented 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$
    – Taras Banakh
    Commented 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$
    – Taras Banakh
    Commented 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 ♦
    Commented 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$
    – Taras Banakh
    Commented May 7, 2020 at 14:58

You must log in to answer this question.

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