Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Andres 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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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. –  Andres Caicedo Sep 15 '10 at 16:15
    
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... –  Andres Caicedo Sep 16 '10 at 6:48
    
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). –  Arturo Magidin Sep 16 '10 at 14:33
    
I got a reply from Don Coppersmith (nothing from Rubin yet). His first proposal is at groups.google.com/group/sci.math/msg/8410fb2145e6bb5c, with a follow-up at groups.google.com/group/sci.math/msg/17ef010aff9acbbb on whether you can prove directly that the resulting set is infinite. –  Arturo Magidin Sep 16 '10 at 21:42
    
Hi Arturo. Thanks! Yes, this is actually a "standard trick": You force some kind of ordering that suffices for the purpose at hand by considering finite tuples rather than finite sets (as I stubbornly kept thinking when I read your outline, even though you wrote "tuple"). I believe the trick originated with Specker. (That Dedekind finite=finite most definitely does not give countable choice, though.) –  Andres Caicedo Sep 22 '10 at 3:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.