The Cantor-Shroder-Bernstein Theorem

Ladies and Gentlemen, I present...

The Cantor-Shroder-Bernstein Theorem...

Theorem:
Suppose there are injections f: A -> B, g: B -> A. Then there is a bijection from A to B.

Proof:
Assume A and B are disjoint (A ^ B != null).
If A ^ B = null, make copies A x {0}, B x {1}.
Let C be the range of g. Let D be the range of f.


We may assume D != B otherwise f is a bijection and we’re done!
A string is a sequence a1, a2, … such that:
(1) a1 is an element of B – D (B – D != null)
(2) a2 = g(a1) which is an element of A.
(3) a3 = f(a2) which is an element of D.
(4) a4 = g(a3) which is an element of A.
* g maps B bijectively to C and so we can consider the inverse of g: C -> B.
* Let W = { for some x in A | x = a2n for some string a and n in N }
W is a subset of C.
Define h: A -> B by:
h(x) = { if x is not in W, f(x)
if x is in W, inverse of g(x) }

Claim: h is a bijection.

First, show h is 1 to 1.
Suppose x, y are in A and h(x) = h(y).
Suppose y is in W, x is not in W.
h(x) = f(x)
h(y) = inverse of g(y)
f(x) = inverse of g(y)
g(f(x)) = g(inverse of g(y))
y = g(f(x))
y is in w, so y = a2n for some string a and n in N
a2n = g(a2n-1)
y = g(f(x))
So since g is 1 to 1, f(x) = a2n-1
If n = 1, f(x) = a1 which is in B – D.
f(x) is in the Range of f which is D.
The above two lines contradict!
If n > 1, a2n-1 = f(a2n-2) = f(x)
Since f is 1 to 1, x = a2n-2 which is in W.
The above line is contradictory with our initial supposition (x is not in W).
By symmetry, x in W, y not in W yields the same result.
Either x, y are in W, or x, y are in A – W.
Suppose x, y are in W.
h(x) = inverse of g(x)
h(y) = inverse of g(y)
So x = y since inverse of g is 1 to 1 on all of C.
Supose x, y are in A – W.
h(x) = f(x)
h(y) = f(y)
So x = y since f is a bijection.
Thus h is 1 to 1.

Now, show h is onto.
Let b be in B.
Case 1: g(b) is in W.
Let x = g(b)
h(x) = inverse of g(x)
(g(b)) = inverse of g(g(b)) = b.
(x) = b.
Case 2: g(b) is not in W.
Case 2.a: b is not in D.
o there is a string a with a1 = b.
2 = g(b) which is in W.
The above contradicts with Case 2 statement g(b) is not in W!
Case 2.b: b is in D = Range of f.
There exists some x in A with f(x) = b
Suppose x is in W, then x = a2n for some string a.
f(x) = b = a2n+1 and g(b) = a2n+2 is in W
The above contradicts with Case 2 statement g(b) is not in W!
Hence x is not in W so h(x) = f(x) = b
Thus h is onto.

Thus h is a bijection.

Of course... You could view the PDF version of this which makes things a lot clearer (formatting makes the world happy!).

 

4 Responses to The Cantor-Shroder-Bernstein Theorem

  1. era Says:
    *twitch* ...why....
  2. Mike S. Says:
    mwhaha. Victory to the mathematicians!

    This is math theory at it's finest and serves one purpose: To give people headaches and make them question their sanity.

    But seriously, why? This is rules of cardinality (equality, or some such) and a major portion of set theory (it's not as scary as it sounds). Without them Math (and by relation, many of the things we enjoy in life) would not exist.

    I should mention that this Theorem involves the axiom of choice. If you don't use the axiom of choice then you end up with an infinetly repeating predicament which can't be solved.

    All in all... You don't have to like it, but you do have to accept it. :)
  3. Anonymous Says:
    I'm going to have so many nightmares about that..that diagram will haunt me always.
    I hope your happy Mike. I hope you're happy.

    -tash
  4. Anonymous Says:
    indefinetly repeating predicament which cannot be rationally solved... hmmm, sounds like my life... OOOOH LOOK, A DUCK!!!