|
|
|
Viewing Version
4
of
'proof of Schroeder-Bernstein theorem'
|
[ view 'proof of Schroeder-Bernstein theorem'
|
back to history
]
| Title of object: |
proof of Schroeder-Bernstein theorem |
| Canonical Name: |
ProofOfSchroederBernsteinTheorem |
| Type: |
Proof |
| Created on: |
2002-07-05 20:22:42.682661-04 |
| Modified on: |
2002-07-05 20:33:59.965383-04 |
| Classification: |
msc:03E10 |
| Keywords: |
cardinality, bijection, injection |
| Synonyms: |
proof of Schroeder-Bernstein theorem=proof of Cantor-Bernstein theorem
proof of Schroeder-Bernstein theorem=proof of Cantor-Schroeder-Bernstein theorem |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
We first prove as a lemma that for any set $A$ and subset $B$, if there is an
injection $f:A\rightarrow B$, then there is also a bijection $h:A\rightarrow B$. We may assume that $B$ is a proper subset of $A$.
Define a sequence $\{C_k\}_{k=0}^\infty$ of subsets of $A$ by $C_0=A-B$, $C_{k+1}=f(C_k)$. Assume that there exist integers $j<k$ such that
$C_j\cap C_k\ne\emptyset$; we may take $j$ to be minimal. Because $C_0\not\subset B$ but $C_k\subset B$ for $k>0$, $j>0$. Thus $C_j=f(C_{j-1})$ and $C_k=f(C_{k-1})$. Since $f$ is injective, $C_{j-1}\cap C_{k-1}\ne\emptyset$, contradicting the minimality of $j$. Hence the $C_k$ are pairwise disjoint.
Now let $C=\bigcup_{k=0}^\infty C_k$, and define $h:A\rightarrow B$ by
\[h(z)=\left\{\begin{array}{ll}
f(z), & z\in C \\
z, & z\not\in C
\end{array}\right. .\]
If $z\not\in C$, $z\in B$, so $h$ is well-defined; $h$ is injective by construction.
Let $b\in B$. If $b\not\in C$, then $h(b)=b$. Otherwise, $b\in C_k=f(C_{k-1})$ for some $k>1$, and so
there is some $a\in C_{k-1}$ such that $h(a)=b$. Thus $h$ is bijective.
To prove the theorem, suppose $f:S\rightarrow T$ and $g:T\rightarrow S$ are injections. Then $gf:S\rightarrow g(T)$ is a composition of injections and so injective. By the lemma, there is a bijection $h':S\rightarrow g(T)$. Because $g$ is injective, $g:T\rightarrow g(T)$ is a bijection, and thus so is $g^{-1}:g(T)\rightarrow T$. Then $h:S\rightarrow T$ defined by $h(z)=g^{-1}h'(z)$ is a bijection. Since there is such a bijection, $S$ and
$T$ have the same cardinality. |
|
|
|
|
|
