3

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?

Community
  • 1
Taras Banakh
  • 40,791
  • Note: it appears to be an open problem whether existence of surjections both way implies AC: https://mathoverflow.net/q/38771/30186 – Wojowu May 07 '20 at 11:31
  • 1
    @Wojowu I guess you mean, whether (existence of surjection both ways implies bijection) implies AC? – YCor May 07 '20 at 11:34
  • 2
    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 07 '20 at 11:38
  • @YCor Yes, I phrased that my previous comment very poorly. – Wojowu May 07 '20 at 11:53
  • @YCor In the second line of your comment you wrote that there exist injections $c\to t$. Why? (I mean in ZF?) And why there exists a surjection $t\to c$? (also in ZF)? – Taras Banakh May 07 '20 at 12:02
  • First if there's an injection $a\to b$ and $a$ is nonempty then there's a surjection $b\to a$ (trivial). For the other part it's easy to explicitly map injectively $c$ into $\mathbf{R}$ so that the image is a subset that is algebraically independent over $\mathbf{Q}$ (see for instance Wagon's book). Hence the composite map $c\to\mathbf{R}/\mathbf{Q}$ is injective. – YCor May 07 '20 at 12:08
  • @YCor I also thought about linearly independent Cantor sets in $\mathbb R$ but is it indeed constructed in ZF without use of Kuratowski-Mycielski Theorem, which uses the Baireness of the hyperspace of non-empty compact sets, which requires the Dependent Choice? But even constructing some canonical tree (representing the linearly independent Cantor set) we shall need dependent choice to show that the boundary of this tree is equipotent with the real line. Or everything is so constructive there? – Taras Banakh May 07 '20 at 12:18
  • 1
    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 07 '20 at 12:25
  • @YCor I would be happy to accept your answer in case you write your cemments as a "legal" answer. By the way, I have another question, but maybe I ask too many questions: writing down the Kuratowski definition of an ordered pair, we can see that $X\times X\subset\mathcal P(\mathcal P(X\times X))$, so $|X\times X|\le|\mathcal P(\mathcal P(X))$ in ZF. What about the inequality $|X\times X|\le|\mathcal P(X)|$? Is it true in ZFC? – Taras Banakh May 07 '20 at 12:43
  • 1
    @TarasBanakh I guess this fitted in a comment, and you have in any case another answer now to accept. – YCor May 07 '20 at 12:50

1 Answers1

5

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.

Asaf Karagila
  • 38,140
  • 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 07 '20 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 07 '20 at 12:56
  • I have already found the answer to my "Hartogs" question in https://caicedoteaching.files.wordpress.com/2009/04/580-choiceless.pdf Indeed, $|\aleph(x)|\le|\mathcal P^3(x)|$. – Taras Banakh May 07 '20 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 07 '20 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 07 '20 at 14:58