Schroeder-Bernstein Theorem
By Henry Sealey on Wednesday, December 05,
2001 - 05:14 pm:
Could someone explain what the S-B theorem is.
Thanks
Henry
By Kerwin Hui on Wednesday, December 05,
2001 - 08:31 pm:
S-B states that if two sets
,
have the property that
there exists injective functions
and
, then
and
have the same cardinality.
I am not sure how much set theory you have done, but you probably do not
understand 'injective function' or 'cardinality'. We say a function
is injective if and only if we have
whenever
. Likewise, we
say a function
is surjective if every member of
can be written
as
for some
in
. We say a function is bijective if it is both
surjective and injective, i.e. it is one-to-one.
Cardinality is a bit more subtle. We say two sets
,
have the same
cardinality if and only if there exists a bijective function from
to
.
Formally, the cardinality of a set
is defined as a (proper) class of all
sets which bijects with
.
Kerwin
By Henry Sealey on Thursday, December 06,
2001 - 04:39 pm:
Thanks Kerwin
By Kerwin Hui on Thursday, December 06,
2001 - 06:10 pm:
Do you want a proof of this theorem? I will just quickly
outline it here:
Let
,
be our injections. Now for each element
in
,
either it is
for some unique
, or it is not in the image of
.
Similarly, every element
of
is either
for some unique
, or
not in the image of
. Now we construct a backward chain for an element
in
:-
,
,
,
,...
in such a way that
,
,
, chain may
terminate or it may go on forever. Similarly, we construct the chain for each
element of
. Given this chain, can we identify some bijection?
Yes, first, we note the set
can be split into three disjoint subsets -
those with infinite chain, those with finite odd-length chain (i.e. those
terminates at some elements of
), and those with finite even-length chain.
Similarly,
can be split into three subsets. Now we see that an element
of
has odd (even) length chain if and only if
has even (odd) length
chain, and similarly for
. Further,
has infinite chain if and
only if
has infinite chain. Hence we can form a one-one correspondence
between those in
with odd length chain with those in
with even length
chain by bijecting
with
, and bijecting
with
if
has
finite even length chain with
, and for those with infinite chain, we
can have a bijection
with
(or
with
, just be consistent!).
Kerwin