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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ Commented May 7, 2020 at 14:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.