Dual Schroeder-Bernstein theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T14:04:33Z http://mathoverflow.net/feeds/question/38771 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38771/dual-schroeder-bernstein-theorem Dual Schroeder-Bernstein theorem Andres Caicedo 2010-09-15T03:43:19Z 2012-08-14T15:17:10Z <p>This question was motivated by the comments to <a href="http://mathoverflow.net/questions/38754/dual-of-zorns-lemma" rel="nofollow">http://mathoverflow.net/questions/38754/dual-of-zorns-lemma</a></p> <p>Let's denote by the Dual Schroeder-Bernstein theorem (DSB) the statement </p> <blockquote> <p>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.</p> </blockquote> <p>In set theory without choice, assume that the Dual Schroeder-Bernstein theorem holds. Does it follow that choice must hold as well?</p> <p>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.</p> <p>The only reference I know for this is Bernhard Banaschewski, Gregory H. Moore, <em>The dual Cantor-Bernstein theorem and the partition principle</em>, Notre Dame J. Formal Logic <strong>31 (3)</strong>, (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.)</p> <p>The <em>partition principle</em> 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.</p> <p>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 <a href="http://wwwmath.uni-muenster.de:8013/persdb/show_perspage.php?id=674" rel="nofollow">page</a>.</p> <hr> <p><strong>Added Sep. 21. [Edited Aug. 14, 2012]</strong> It may be worthwhile to point out what is known, beyond the Banaschewski-Moore result mentioned above. </p> <p>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 <em>idemmultiple hypothesis</em> that $x\sqcup x$ is equipotent to $x$, for all infinite sets $x$, is strictly weaker than choice, as shown in Gershon Sageev, <em>An independence result concerning the axiom of choice</em>, Ann. Math. Logic 8 (1975), 1–184, MR0366668 (51 #2915). </p> <p>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.</p> http://mathoverflow.net/questions/38771/dual-schroeder-bernstein-theorem/38833#38833 Answer by Arturo Magidin for Dual Schroeder-Bernstein theorem Arturo Magidin 2010-09-15T16:01:48Z 2010-09-15T16:01:48Z <p>This is only a partial answer because I'm having trouble reconstructing something I <em>think</em> I figured out seven years ago...</p> <p>It would seem the Dual Cantor-Bernstein implies Countable Choice. In a <a href="http://groups.google.com/group/sci.math/msg/28543d2b17d8f4ab" rel="nofollow">post in sci.math</a> 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.</p> <p>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...</p>