The bijection in Cantor-Bernstein Theorem
Here we give further clarification on the bijection constructed in the proof of the S-B theorem.
We are given injections f: A ® B and g: B ® A, where A and B are infinite sets.
We will assume that A ¹ g(B), otherwise g will be a surjection and, since g is an injection to start with, g will be a bijection so that we could take g to be the desired bijection we are seeking. Now, since A ¹ g(B) Ì A, g(B) is a proper subset of A. This is shown in the figure below where the big rectangle represents the set A and the rectangle in the upper corner inside the big rectangle represents A\g(B).
Let us look at the set S in the proof.
Consider the second unand, which is (g o f)(A\g(B)).
CLAIM 1: (g o f)(A\g(B)) Ì g(B).
PROOF: If x Î A\g(B), then (g o f)(x) = g(f(x) Î g(B).
So (g o f)(A\g(B)) Ì g(B).
By Claim 1, the sets A\g(B) and (g o f)(A\g(B)) have no elements in common.
So the figure now becomes this.
CLAIM 2: (g o f)n (A\g(B)) Ì g(B), for every positive integer n.
We prove this by induction as follows.
(g o f)(A\g(B)) Ì g(B), by Claim 1.
Suppose (g o f)n(A\g(B)) Ì g(B). (Induction step)
Let x Î (g o f)n+1(A\g(B)) = (g o f)(g o f)n(A\g(B)).
So x = (g o f)(g o f)n(x'), for some x'Î A\g(B).
But (g o f)n(x') Î g(B) (From Induction step).
So x Î(g o f)g(B) = g(f(g(B))) Ì g(f(A)) Ì g(B), proving the claim.
CLAIM 3: The sets (g o f)m(A\g(B)) and (g o f)n(A\g(B)) have no elements in common when m ¹ n.
PROOF: Assume, without loss of generality, that m > n.
Suppose there is an element x that is common to both sets.
Then x = (g o f)m(x') = (g o f)n(x"), where x' and x" are in A\g(B).
Then (g o f)n(g o f)m-n(x') = (g o f)n(x")
Now since g and f are injections, their composition, g o f, is an injection, and the power, (gof)n, is an injection. That is, (gof)n(x1) = (gof)n(x2) implies x1 = x2.
This means (g o f)n(g o f)m-n(x') = (gof)n(x") implies (gof)m-n(x') = x".
But (g o f)m-n(x') is in g(B) by Claim 2, whereas x" is in A\g(B); a contradiction. This proves the claim.
The figure below shows S as a disjoint union of the sets (g o f)n(A\g(B)).
If x is in S, then (g o f)(x) is in S. The elements in a rectangle in S, in our figure, are shifted to elements in the next rectangle on the right, following the action of (g o f).
We are now in a position to better understand the bijection h constructed in the proof of the S-B Theorem.
The bijection, h: A ® B, was defined thus:
It was shown in the proof that h is surjective.
h is identical with f on the set S.
On the set A\S, h is identical with g-1. An element x in A\S is taken by h to an element y in B, where g(y)=x.
The construction of the S could have been presented in a recursive way as follows.
S0 = A\g(B)
Sn+1 = g(f(Sn))
In the proof, the bijection h is constructed out of the given injections. However, the domain of h is described in terms of S which in turn has been defined recursively. This recursion does not allow for S to be obtained explicitly in all situations.
This means the proof is in fact a non-constructive proof. That is, it shows the existence of h but does not construct it in a finite number of steps to be practical in all situations.
MathPath - "BRIGHT AND EARLY"
Send suggestions to firstname.lastname@example.org
Copyright © 2001- MathPath
Last updated - March 20, 2005