Schröder Bernstein Theorem: Proof

Let A and B be two nonempty sets; and let there be, in addition, two one-one functions f:AB and g:BA. We propose to show that A and B are equinumerous i.e., they are in one to one correspondence.

Consider the notation:

g-1(x), if xg(B)
f-1(g-1(x)), if g-1(x)f(A)
g-1(f-1(g-1(x))), if f-1(g-1(x))g(B)

Define, for each xA, the order of it, denoted by (x), to be the number of such preimageMathworldPlanetmath(s) which exist. In a similer way, we’d be able to define the order of an element yB, i.e., by considering the sequence f-1(y),g-1(f-1(y)),.

Now define, for each xA,

ϕ(x): = f(x),(x)=
= f(x),(x)=2n, for some nω
= b,(x)=2n+1,i.e.,bB:g(b)=x

Notice that if the order is infiniteMathworldPlanetmath, ϕ(x)=f(x) is also infinite. Because, otherwise x would have to have a finite order. On the other hand, if yB and (y) is infinite, then f-1(y) exists and has an infinite order; call the latter one x. This means, ϕ maps the infinite order elements of A bijectively onto the infinite order elements of B.

Next, if (x)=2n, then the order of f(x) is sheer 2n+1. Similer to the above para, if for yB, the order is 2n+1, as the order is non-zero, f-1(y) exists and it must have order 2n. To formally show it you need a tedious inductive reasoning!

Last, if (x)=2n+1, then the order is 1, and so, g-1(x) exists and the order of g-1(x) is sheer 2n(looking upon g-1(x) as an element of B). Conversely, similer to above, if there is an element y of order 2n in B, take x=g(y) and the order of x is indeed 2n+1. All that you need to convince a sceptic is a long, tedious, involved inductionMathworldPlanetmath!!

What we learn from what precedes is that the one-one function ϕ maps the infinite order elements onto infinite order elements, odd order onto odd order, and even order onto even order; a simple set theory reveals that ϕ is a one-one map from A onto B. This completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof.

Title Schröder Bernstein Theorem: Proof
Canonical name SchroderBernsteinTheoremProof
Date of creation 2013-03-22 16:40:36
Last modified on 2013-03-22 16:40:36
Owner sauravbhaumik (15615)
Last modified by sauravbhaumik (15615)
Numerical id 10
Author sauravbhaumik (15615)
Entry type Proof
Classification msc 03E20