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

PR Strukal dan Teorema Fueter-Polya

Pada PR Struktur Aljabar mahasiswa diminta untuk mengkonstruksi suatu bijeksi f:\mathbb{N}\times \mathbb{N}\to\mathbb{N}.

Mahasiswa diberikan petunjuk bahwa unsur-unsur di \mathbb{N}\times \mathbb{N} dapat disusun ke dalam piramida bilangan sebagai berikut

    \[{\footnotesize     \begin{tabular}{rccccccccc} Baris ke-$1$:\quad\quad&    &    &    &    &  (1,1)\\\noalign{\smallskip\smallskip} Baris ke-$2$:\quad\quad&    &    &    &  (1,2)&    &  (2,1)\\\noalign{\smallskip\smallskip} Baris ke-$3$:\quad\quad&    &    &  (1,3) &    &  (2,2) &    &  (3,1)\\\noalign{\smallskip\smallskip} Baris ke-$4$:\quad\quad&    &  (1,4) &    &  (2,3) &    &  (3,2) &    &  (4,1)\\\noalign{\smallskip\smallskip} Baris ke-$5$:\quad\quad&  (1,5) &    &  (2,4) &    &  (3,3) &    &  (4,2) &    &  (5,1)\\\noalign{\smallskip\smallskip} \end{tabular}  }   \]

dengan aturan bilangan pada baris ke-s berisi semua pasang bilangan (m,n) dengan m+n=s.
Kemudian unsur-unsur di piramidia bilangan tersebut dipetakan ke \mathbb{N} mulai dari baris yang paling atas dan bergerak dari kiri ke kanan. Sebagai contoh f(1,1)=1,f(1,2)=2, f(2,1)=3, f(1,3)=4 dan seterusnya. Mahasiswa diminta untuk menebak rumus eksplisit dari aturan tersebut dan kemudian membuktikan bahwa pemetaan tersebut bijektif.

Setelah saya periksa sepintas, semua pekerjaan mahasiswa yang saya lihat menebak formula pemetaan dengan benar, yaitu f(m,n)=\frac{(m+n-2)(m+n-1)}{2}+m. Kita akan buktikan bahwa f suatu bijeksi. Pertama-tama kita buktikan lema berikut.

Lemma
Notasikan g(k):=\frac{(k-1)k}{2}. Untuk setiap k\in \mathbb{N} berlaku g(k+1)-g(k)=k. Khususnya g(k) monoton naik.
Bukti.
g(k+1)-g(k)=\frac{k}{2}\left((k+1)-(k-1)\right)=k.

Perhatikan bahwa f(m,n)=g(m+n-1)+m dan akan kita tunjukkan bahwa f suatu bijeksi.
Akan kita tunjukkan bahwa f(m,n) injektif. Misalkan (m,n),(a,b)\in \mathbb{N}\times \mathbb{N} sedemikian sehingga f(m,n)=f(a,b). Maka g(m+n-1)+m=g(a+b-1)+a. Andaika m+n\neq a+b dan tanpa mengurangi keumuman misalkan m+n>a+b. Karena g monoton naik maka a-m=g(m+n-1)-g(a+b-1)\geq g(a+b)-g(a+b-1)=a+b-1 (menurut Lema). Ini mengakibatkan -m\geq b-1\geq 0 yang jelas tidak mungkin karena m\in \mathbb{N}. Dengan demikian haruslah m+n=a+b dan akibatnya a-m=g(m+n-1)-g(a+b-1)=0. Jadi a=m dan akibatnya b=n. Jadi f injektif.

Sekarang kita buktikan bahwa f surjektif. Ambil s\in \mathbb{N}. Maka terdapat k\in \mathbb{N} sehingga g(k) < s \leq g(k+1) (mengapa?). Perhatikan bahwa c:=s-g(k)\leq g(k+1)-g(k)=k. Karena c\leq k maka ada d\in \mathbb{N} sehingga c+d-1=k. Sekarang kita dapatkan s=g(k)+c=g(c+d-1)+c=f(c,d). Jadi f surjektif.

Selain polinom f(x,y) di atas, jika kita mendaftarkan unsur-unsur di piramida bilangan dengan urutan dari kanan ke kiri maka kita dapatkan polinom g(x,y)=\frac{1}{2}(x+y-2)(x+y-1)+y yang juga merupakan suatu bijeksi. Polinom f dan g ini dikenal sebagai polinom Cantor, dan Cantor menggunakannya untuk menunjukkan bahwa \mathbb{N}\times \mathbb{N} dan \mathbb{N} mempunyai kardinalitas yang sama.

Terkait dengan kedua polinom ini Cantor menanyakan apakah ada polinom yang lain yang memberikan bijeksi dari \mathbb{N}\times \mathbb{N} ke \mathbb{N}. Fueter dan Polya di tahun 1923 membuktikan teorema berikut.

Teorema Fueter-Polya
Tidak ada Polinom kuadratik lain selain Polinom Cantor yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N}.

Fueter dan Polya membuktikan Teorema di atas dengan menggunakan teknik teori bilangan analitis. Pada tahun 2001 Vserminov memberikan bukti elementer dari Teorema Fueter-Polya di atas.

Paling tidak ada dua hal yang bisa kita pelajari dari Teorema ini. Kita lihat bahwa pembuktian bahwa f merupakan fungsi bijektif merupakan sesuatu yang terlalu sulit yang bahkan masih bisa kita berikan sebagai suatu pekerjaan rumah. Akan tetapi jika kita bersikap kritis dan menanyakan pertanyaan yang tepat, persoalan yang biasa-biasa bisa menjadi objek riset matematika. Dalam hal ini menanyakan apakah ada polinom lain yang memenuhi membuka kesempatan untuk melakukan suatu riset matematika.

Pelajaran kedua yang kita ambil adalah meskipun Fueter dan Polya sudah membuktikan Teorema di atas puluhan tahun yang lalu tidak berarti persoalannya selesai. Dalam matematika kita selalu punya kesempatan untuk memberikan bukti baru dari suatu teorema yang sudah terbukti. Kita bisa menawarkan bukti dari perspektif lain, bukti yang lebih singkat, bukti yang lebih elementer, bukti yang lebih elegan dan sebagainya.

Sedikit demi sedikit kita harus belajar menggeser peran. Kita tidak hanya sekadar menjadi penikmat matematika, dengan mencoba memahami pekerjaan orang lain, tapi juga ikut serta menciptakan matematika. Langkah pertamanya adalah dengan mengajukan banyak pertanyaan terhadap apa yang telah dilakukan orang lain dan berusaha menjawabnya.

Pertanyaan berikutnya yang berkaitan dengan Teorema Fueter-Polya yang alamiah adalah

Apakah ada polinom berderajat lebih dari dua yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N} ke \mathbb{N}?

Para matematikawan meyakini bahwa hanya Polinom Cantor saja yang memenuhi, tapi saat ini belum ada yang bisa memberikan bukti dari konjektur tersebut. Mungkin anda berminat untuk membuktikannya?

Latihan berikut adalah jawaban dari pertanyaan apakah kita bisa mempunyai polinom bijektif seperti di atas untuk dimensi yang lebih tinggi.
Latihan
Berikan polinom yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N}\times \mathbb{N} ke \mathbb{N} dan polinom yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N}\times \mathbb{N} ke \mathbb{N}\times \mathbb{N}

Bijeksi antara Z dan Q

Salah satu hal menarik ketika kita belajar tentang ketakberhinggaan adalah fakta bahwa “banyaknya” bilangan rasional sama dengan banyaknya bilangan bulat. Hal ini sepertinya berlawanan dengan akal sehat mengingat himpunan bilangan bulat termuat di himpunan bilangan rasional.

Kita ingin membuat pemetaan bijektif antara himpunan bilangan bulat {\mathbb{Z}} dengan himpunan bilangan rasional {\mathbb{Q}}. Untuk melakukannya kita cukup membuat pemetaan bijektif antara himpunan bilangan asli {\mathbb{N}} dan himpunan bilangan rasional positif {\mathbb{Q}^+} (why?).

Konstruksi berikut saya baca beberapa hari yang lalu dalam suatu artikel yang dimuat pada American Mathematical Monthly. Pertama akan dikonstruksi pemetaan bijektif antara {\mathbb{N}} dengan {\mathbb{Z}-\{0\}} (himpunan bilangan bulat taknol). Idenya adalah dengan memasangkan setiap bilangan asli genap dengan bilangan bulat positif dan memasangkan bilangan asli ganjil dengan bilangan bulat negatif. Secara eksplisit pemetaan {f:\mathbb{N}\rightarrow \mathbb{Z}-\{0\}} didefinisikan sebagai berikut

    \[ f(n):=\begin{cases}\frac{n}{2}& \text{ jika $n$ genap }\\ -\frac{n+1}{2}&\text{ jika $n$ ganjil }\end{cases} \]

Mudah diperiksa bahwa pemetaan ini bijektif dan kami menyarankan pembaca untuk mengeceknya.

Berikutnya dengan menggunakan pemetaan {f} ini dan faktorisasi prima dari bilangan asli kita definisikan pemetaan {g:\mathbb{N}\rightarrow \mathbb{Q}^+} sebagai berikut. Pertama definisikan {g(1)=1} dan untuk setiap bilangan asli {m>1}, pertama tuliskan faktorisasi prima {m} ke dalam bentuk {m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}} dengan {p_i} bilangan prima yang berbeda untuk masing-masing {i=1,\ldots, k} dan {a_i} adalah bilangan asli. Kita definisikan

\displaystyle g(m)=g(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k})=p_1^{f(a_1)}p_2^{(a_2)}\cdots p_k^{(a_k)}.

Buktinya tidak sulit dan bagus untuk latihan. Anda dapat membandingkan bukti yang anda dapatkan dengan bukti di bawah ini.

Baca Bukti

Kita akan periksa bahwa {g} suatu bijeksi. Misalkan {s=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}} dan {t=q_1^{b_1}q_2^{b_2}\cdots q_n^{b_n}}. Jika {g(s)=g(t)} maka {p_1^{f(a_1)}p_2^{f(a_2)}\cdots p_m^{f(a_m)}=q_1^{f(b_1)}q_2^{f(b_2)}\cdots q_n^{f(b_n)}}. Berdasarkan ketunggalan faktorisasi prima haruslah {m=n} dan semua faktor prima di ruas kiri sama dengan semua faktor prima di ruas kanan. Tanpa mengurangi keumuman kita misalkan {p_i=q_i} untuk setiap {i}. Akibatnya {f(a_i)=f(b_i)} untuk setiap {i}. Karena {f} suatu bijeksi maka {a_i=b_i} untuk setiap {i} dan dari sini kita peroleh bahwa {s=t}. Jadi {g} pemetaan injektif.

Untuk membuktikan bahwa {g} surjektif, ambil sebarang bilangan rasional positif {u/v} dengan {u,v} tidak punya faktor bersama. Tuliskan {u=p_1^{a_1}\cdots p_k^{a_k}} dan {v=p_{k+1}^{a_{k+1}}\cdots p_m^{a_m}}. Perhatikan bahwa

\displaystyle u/v=p_1^{a_1}\cdots p_k^{a_k}p_{k+1}^{-a_{k+1}}\cdots p_m^{-a_m}.

Karena {f} suatu bijeksi ada {c_1,\ldots, c_k,c_{k+1},\ldots, c_m} sehingga {f(c_i)=a_i} untuk {i=1,\ldots, k} dan {f(c_i)=-a_i} untuk {i=k+1,\ldots, m}. Dengan demikian

\displaystyle \frac{u}{v}=p_1^{f(c_1)}\cdots p_k^{f(c_k)}p_{k+1}^{f(c_{k+1})}\cdots p_m^{f(c_m)}=g(p_1^{c_1}\cdots p_k^{c_k}p_{k+1}^{c_{k+1}}\cdots p_m^{c_m}).

dan ini berarti bahwa {g} surjektif.

[collapse]

Rendered by QuickLaTeX.com