Schroeder-Bernstein theorem, proof of

We first prove as a lemma that for any BA, if there is an injection f:AB, then there is also a bijection h:AB.

Inductively define a sequence (Cn) of subsets of A by C0=AB and Cn+1=f(Cn). Now let C=k=0Ck, and define h:AB by


If zC, then h(z)=f(z)B. But if zC, then zB, and so h(z)B. Hence h is well-defined; h is injective by construction. Let bB. If bC, then h(b)=b. Otherwise, bCk=f(Ck-1) for some k>0, and so there is some aCk-1 such that h(a)=f(a)=b. Thus h is bijectiveMathworldPlanetmath; in particular, if B=A, then h is simply the identity map on A.

To prove the theoremMathworldPlanetmath, suppose f:ST and g:TS are injective. Then the compositionMathworldPlanetmathPlanetmath gf:Sg(T) is also injective. By the lemma, there is a bijection h:Sg(T). The injectivity of g implies that g-1:g(T)T exists and is bijective. Define h:ST by h(z)=g-1h(z); this map is a bijection, and so S and T have the same cardinality.

Title Schroeder-Bernstein theorem, proof of
Canonical name SchroederBernsteinTheoremProofOf
Date of creation 2013-03-22 12:49:56
Last modified on 2013-03-22 12:49:56
Owner mps (409)
Last modified by mps (409)
Numerical id 19
Author mps (409)
Entry type Proof
Classification msc 03E10
Synonym proof of Cantor-Bernstein theorem
Synonym proof of Cantor-Schroeder-Bernstein theorem
Related topic AnInjectionBetweenTwoFiniteSetsOfTheSameCardinalityIsBijective