# Dual Schroeder-Bernstein theorem

This question was motivated by the comments to Dual of Zorn's Lemma?

Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement

For any sets $A$ and $B$, if there are surjections from $A$ onto $B$ and from $B$ onto $A$, then there is a bijection between them.

In set theory without choice, assume that the Dual Schroeder-Bernstein theorem holds. Does it follow that choice must hold as well?

I strongly suspect this is open, though I would be glad to be proven wrong in this regard. In all models of ZF without choice that I have examined, DSB fails. This really does not say much, as there are plenty of models I have not looked at. In any case, I don't see how to even formlate an approach to show the consistency of DSB without AC.

The only reference I know for this is Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375–381. In this paper it is shown that a strengthening of DSB does imply AC, namely, that whenever there are surjections $f:A\to B$ and $g:B\to A$, then there is a bijection $h:A\to B$ contained in $f\cup g^{-1}$. (Note that the usual Schroeder-Bernstein theorem holds -without needing choice- in this fashion.)

The partition principle is the statement that whenever there is a surjection from $A$ onto $B$, then there is an injection from $B$ into $A$. As far as I know, it is open whether this implies choice, or whether DSB implies the partition principle. Clearly, the reverse implications hold.

If you are interested in natural examples of failures of DSB in some of the usual models, Benjamin Miller wrote a nice note on this, available at his page.

Added Sep. 21. [Edited Aug. 14, 2012] It may be worthwhile to point out what is known, beyond the Banaschewski-Moore result mentioned above.

Assume DSB, and suppose $x$ is equipotent with $x\sqcup x$. Then, if there is a surjection from $x$ onto a set $y$, we also have an injection from $y$ into $x$. (So we have a weak version of the partition principle.) This idemmultiple hypothesis that $x\sqcup x$ is equipotent to $x$, for all infinite sets $x$, is strictly weaker than choice, as shown in Gershon Sageev, An independence result concerning the axiom of choice, Ann. Math. Logic 8 (1975), 1–184, MR0366668 (51 #2915).

Also, as indicated in Arturo Magidin's answer (and the links in the comments), H. Rubin proved that DSB implies that any infinite set contains a countable subset.

• About DSB not being provable without (some amount of) choice: Without choice, it is consistent that there is a quotient of the reals that is strictly larger than the reals. This shows that DSB is not provable without choice: R and its quotient both are surjective images of each other, but there is no bijection between them. This holds, for example, in Solovay's model where all sets of reals are Lebesgue measurable. The note by Miller has more sophisticated versions of this example and interesting variants. – Andrés E. Caicedo Sep 15 '10 at 15:15
• Vaguely related, another choice principle related to DSB (and stronger than it as well): mathoverflow.net/questions/81204/… – Asaf Karagila Aug 14 '12 at 15:40

Let $U$ be an infinite set. Let $A$ be the set of all $n$-tuples of elements of $U$ with $n\gt 0$ and even, and let $B$ be the set of all $n$-tuples of $U$ with $n$ odd. There are surjections from $A$ onto $B$ (delete the first element of the tuple) and from $B$ onto $A$ (for the $1$-tuples, map to a fixed element of $A$; for the rest, delete the first element of the tuple). If we assume the dual of Cantor-Bernstein holds, then there exists a one-to-one function from $f\colon B\to A$ (in fact, a bijection). Rubin writes that "a 1-1 mapping from $B$ to $A$ quickly gives a countable subset of $U$", but right now I'm not quite seeing it...
• In mathoverflow.net/questions/81204/… , Joel Hamkins indicates an easier proof: Given $U$ infinite, take as $A$ the set of injective finite sequences from $U$. Note that if $\omega$ injects into $A$, then it also injects into $U$. Now, there is a surjection from $A$ onto $A\sqcup\{0\}$: Map the emptyset to $0$, and each nonempty sequence to the sequence resulting from removing its first coordinate. By DSB, there is a bijection between $A$ and $A\sqcup\{0\}$, so $\omega$ injects in $A$, so it injects in $U$. – Andrés E. Caicedo Aug 25 '12 at 21:31