[FOM] FW: Schroeder-Bernstein Dual
Epstein, Adam
A.L.Epstein at warwick.ac.uk
Thu Jun 21 20:03:28 EDT 2007
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.
More information about the FOM
mailing list