[FOM] FW: Schroeder-Bernstein Dual

[Epstein, Adam]

On Tue, 29 May 2007, Bill Taylor wrote:

 >Consider this "dual" to Shroeder-Bernstein:
 >
 >**  If there are surjections   f: X --> Y
 >**                       and   g: Y --> X
 >**
 >**  then there is a bijection between X and Y.


There was a response I was expecting to see, based on something I'd read
in Jech's book "The Axiom of Choice". I wanted to double check first, and
the book just came back to the library this afternoon.

Let's write <= for the usual relation on cardinals: |X|<=|Y| whenever X
injects into Y. Schroeder-Bernstein is the assertion

       |X|<=|Y| and |Y|<=|X|  ==>  |X|=|Y|.

Now, define the relation <=* by |X|<=*|Y| whenever Y surjects onto X, or X
is empty.

Note that without using Choice we have

(*)   |X|<=|Y| ==> |X|<=*|Y|.

Indeed, we may assume X is not empty, so that there exists some a in X.
Given an injection alpha: X -> Y we obtain a surjection beta: Y -> X which
sends each alpha(x) to x, and sends the remaining points of Y to a.


Now, following Jech (exercise 8, p. 162) fix an infinite but
Dedekind-finite set D, let S be the set of all finite one-to-one
sequences in D, and let T be obtained from S by removing the empty
sequence. Clearly, since T is a subset of S we have |T|<=|S|, whence
|T|<=*|S| by (*). Moreover, since the set S is also Dedekind-finite
(exercise 5, p. 161) we must have the strict inequality |T|<|S|: that is
to say, |T| \neq |S|.

On the other hand, we also have |S|<=*|T| via the map T->S which deletes
the last entry of each nonempty sequence.