PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof of Schroeder-Bernstein theorem (Proof)

We first prove as a lemma that for any $B\subset A$ , if there is an injection $f:A\to B$ , then there is also a bijection $h:A\to B$ .

Inductively define a sequence $(C_n)$ of subsets of $A$ by $C_0=A\setminus B$ and $C_{n+1}=f(C_n)$ . Now let $C=\bigcup_{k=0}^\infty C_k$ , and define $h:A\rightarrow B$ by

$\displaystyle h(z)=\begin{cases} f(z), & z\in C \ z, & z\notin C \end{cases} $
If $z\in C$ , then $h(z)=f(z)\in B$ . But if $z\notin C$ , then $z\in B$ , and so $h(z)\in B$ . Hence $h$ is well-defined; $h$ is injective by construction. Let $b\in B$ . If $b\notin C$ , then $h(b)=b$ . Otherwise, $b\in C_k=f(C_{k-1})$ for some $k>0$ , and so there is some $a\in C_{k-1}$ such that $h(a)=f(a)=b$ . Thus $h$ is bijective; in particular, if $B=A$ , then $h$ is simply the identity map on $A$ .

To prove the theorem, suppose $f:S\to T$ and $g:T\to S$ are injective. Then the composition $gf:S\to g(T)$ is also injective. By the lemma, there is a bijection $h':S\to g(T)$ . The injectivity of $g$ implies that $g^{-1}:g(T)\to T$ exists and is bijective. Define $h:S\to T$ by $h(z)=g^{-1}h'(z)$ ; this map is a bijection, and so $S$ and $T$ have the same cardinality.




Anyone with an account can edit this entry. Please help improve it!

"proof of Schroeder-Bernstein theorem" is owned by mps.
(view preamble | get metadata)

View style:

See Also: an injection between two finite sets of the same cardinality is bijective

Other names:  proof of Cantor-Bernstein theorem, proof of Cantor-Schroeder-Bernstein theorem
Keywords:  cardinality, bijection, injection

This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: cardinality, map, implies, composition, theorem, identity map, bijective, injective, well-defined, subsets, sequence, bijection, injection

This is version 16 of proof of Schroeder-Bernstein theorem, born on 2002-07-05, modified 2005-07-11.
Object id is 3156, canonical name is ProofOfSchroederBernsteinTheorem.
Accessed 17675 times total.

Classification:
AMS MSC03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers)

Pending Errata and Addenda
None.
[ View all 6 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)