|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
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
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)
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 MSC: | 03E10 (Mathematical logic and foundations :: Set theory :: Ordinal and cardinal numbers) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
