From: Erland Gadde <gadde@sm.luth.se>
Subject: Re: Schroeder-Bunstein Theorem
Date: Mon, 11 Sep 2000 16:31:59 +0200
Newsgroups: sci.math
Summary: [missing]

The following simple proof of the Schroeder-Bernstein Theorem has the
advantadge that it doen't use any infinite sequences of sets, and hence
that one doesn't  need to develop the theory of natural numbers to use
it.

Claim:  If there are injections  f : A->B and g : B->A, then there is a
bijection h : A->B.

Let M denote the family of all subsets V of A such that g maps B-f(V)
into A-V. Let U be the union of all sets in M. Take y in B-f(U). For V
in M, y lies in B-f(V), hence g(y) lies in A-V. Since this holds for all
V in M, g(y) lies in A-U. This holds for any y in B-f(U), therefore U
lies in M. Suppose now that (A-U)-g(B-f(U)) is nonempty, and let x be in
this set. Let U' = U union {x}. Then g maps B-f(U) into A-U', and hence
g maps B-f(U') into A-U', which means that U' belongs to M. But U is the
union of all sets in M, so U' is a subset of U, whence x lies in U,
which contradicts our assumption. It follows that (A-U)-g(B-f(U)) is
empty, that is, that g maps B-f(U) onto A-U. Now we can define h : A ->
B by h(x)=f(x) if x in U, and h(x)=g^{-1}(x) if x in A-U. Then the
preceding shows that h is a bijection. Q.E.D.

Unfortunately, i have forgotten who is the originator of this proof is.


Erland Gadde