41
$\begingroup$

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 countably infinite subset.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Andrés E. Caicedo
    Commented Sep 15, 2010 at 15:15
  • $\begingroup$ Vaguely related, another choice principle related to DSB (and stronger than it as well): mathoverflow.net/questions/81204/… $\endgroup$
    – Asaf Karagila ♦
    Commented Aug 14, 2012 at 15:40

1 Answer 1

Reset to default
7
$\begingroup$

This is only a partial answer because I'm having trouble reconstructing something I think I figured out seven years ago...

It would seem the Dual Cantor-Bernstein implies Countable Choice. In a post in sci.math in March 2003 discussing the dual of Cantor-Bernstein, Herman Rubin essentially points out that if the dual of Cantor-Bernstein holds, then every infinite set has a denumerable subset; this is equivalent, I believe, to Countable Choice.

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...

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks for the reference to the sci.math discussion! I believe this is correct, I'll have to think about it once I find some free time (haha). I have in my notes that DSB implies that there are no infinite Dedekind finite sets, which is what you wrote, but as I recall, my argument was different. $\endgroup$
    – Andrés E. Caicedo
    Commented Sep 15, 2010 at 16:15
  • $\begingroup$ Hmm... I'm not sure I see this argument. It looks to me that Rubin is using something like "a countable union of finite sets contains a countable subset", but I don't think this is true without some use of choice. The weaker "a countable union of finite sets is countable" is certainly not true in general without choice. But perhaps he had a different argument in mind... $\endgroup$
    – Andrés E. Caicedo
    Commented Sep 16, 2010 at 6:48
  • $\begingroup$ Like I said, I seem to remember working this out at the time, but it just escapes me at the moment. I will post and ask if he can flesh out the argument (he's still active in sci.math/sci.logic). $\endgroup$
    – Arturo Magidin
    Commented Sep 16, 2010 at 14:33
  • 4
    $\begingroup$ Actually "every infinite set has a countably infinite subset" is weaker than the axiom of countable choice! (Jech The Axiom of Choice Ch. 8, Problem 4 (p. 132) - he credits Pincus for the result) $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 16, 2012 at 20:02
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Andrés E. Caicedo
    Commented Aug 25, 2012 at 21:31

You must log in to answer this question.

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