Teorema Schroder-Bernstein

Theorem  (Schröder-Bernstein) Jika terdapat injeksi {f:A\rightarrow B} dan {g:B\rightarrow A} maka {|A|=|B|}.
Bukti yang diberikan akan menggunakan kasus khusus dari Teorema Titik Tetap Knaster-Tarski.

Lemma  (Knaster-Tarski) Misalkan {\Phi:\mathcal{P}(A)\rightarrow \mathcal{P}(A)} sedemikian sehingga {\Phi} monoton, yakni jika {X\subseteq Y} maka {\Phi(X)\subseteq \Phi(Y)}. Maka terdapat {Z\in \mathcal{P}(X)} sehingga {\Phi(Z)=Z}.
Bukti: Tinjau koleksi {\mathcal{C}:=\{X\in \mathcal{P}(X): X\subseteq \Phi(X)\}}. Perhatikan bahwa {\mathcal{C}} paling tidak mengandung {\emptyset}. Sekarang definisikan {Z:=\bigcup_{X\in C} \Phi(X)}. Untuk setiap {X\in \mathcal{C}} kita dapatkan {X\subseteq \Phi(X)\subseteq Z}. Karena {\Phi} monoton, {\Phi(X)\subseteq \Phi(Z)}. Karena ini berlaku untuk setiap {X\in \mathcal{C}}, kita peroleh {Z=\bigcup_{X\in \mathcal{C}} \Phi(X)\subseteq \Phi(Z)}. Berarti {Z\in \mathcal{C}} dan {\Phi(Z)\subseteq \bigcup_{X\in \mathcal{C}} \Phi(X)=Z}. Karena {Z} dan {\Phi(Z)} saling subset, {Z=\Phi(Z)}. \Box

Sekarang kita siap membuktikan Teorema Schröder-Bernstein. Pertama dengan cara yang cerdik, menggunakan pemetaan injektif {f} dan {g} kita akan buat suatu pemetaan monoton {\Phi:\mathcal{P}(A)\rightarrow \mathcal{P}(A)}. Untuk setiap {X\in \mathcal{P}(A)} definisikan {\Phi(X)=g\left(B\backslash f(A\backslash X)\right)}. Untuk {X\subseteq Y} jelas bahwa {f(A\backslash Y)\subseteq f(A\backslash X)}. Akibatnya
\displaystyle \Phi(X)=g(B\backslash f(A\backslash X))\subseteq g(B\backslash (A\backslash Y))=\Phi(Y).
Jadi {\Phi} monoton.

Bukti (Teorema Schröder-Bernstein):
Menurut Lema, kita punyai {Z\in \mathcal{P}(X)} sehingga {Z=\Phi(Z)=g(B\backslash f(A\backslash Z))}. Sekarang kita partisi {A} dan {B} sebagai {A=Z\cup (A\backslash Z)} dan {B=f(A\backslash Z)\cup B\backslash f(A\backslash Z)}. Karena {f} injektif maka {f} juga merupakan bijeksi antara {A\backslash Z} dan {f(A\backslash Z)}. Kemudian karena {g} injektif, maka {g} juga merupakan bijeksi antara {B\backslash f(A\backslash Z)} dan {g(B\backslash f(A\backslash Z))=Z}.

Dari sini mudah ditunjukkan bahwa pemetaan {h:A\rightarrow B} yang didefinisikan melalui

\displaystyle h(x)=\begin{cases} f(x),& x\in A\backslash Z\\ g^{-1}(x),&x\in Z\end{cases}

adalah bijeksi yang kita perlukan untuk menunjukkan bahwa {|A|=|B|}. \Box

Leave a Reply

Your email address will not be published. Required fields are marked *