January 2017 – A Mathematician Impostor

January 25, 2017

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$

January 25, 2017

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}$

January 20, 2017January 20, 2017

Kuis 1

Soal
Tentukan semua $a,b,c$ rasional sehingga $f:\mathbb{Z}\to \mathbb{Z}$ yang didefinisikan melalui $f(x)=ax^2+bx+c$ merupakan suatu pemetaan.
Jawaban
Klaim bahwa $a,b,c$ haruslah $a,b,c$ semuanya bulat atau $a=\frac{s}{2}, b=\frac{t}{2}$ dengan $s,t$ bulat ganjil dan $c$ bulat.

Perhatikan bahwa jika $a,b,c$ semuanya bulat jelas bahwa $f(x)$ bulat untuk setiap $x$ bulat.

Untuk kasus kedua, $f(x)=\frac{sx^2+tx}{2}+c$ . Karena $s,t$ ganjil, jika $x$ ganjil maka $sx^2$ dan $tx$ ganjil akibatnya $sx^2+tx$ genap. Demikian juga jika $x$ genap maka $sx^2+tx$ genap. Pada kedua kasus kita bisa tuliskan $sx^2+tx=2k$ untuk suatu $k$ bulat. Jadi $f(x)=\frac{2k}{2}+c=k+c$ bulat untuk setiap $x$ bulat.

Sekarang akan kita tunjukkan bahwa tidak ada nilai $a,b,c$ lain yang memenuhi selain yang disebutkan di atas.

Misalkan $a,b,c$ bilangan rasional sehingga $f(x)$ bulat. Perhatikan bahwa $c=f(0)$ bulat. Demikian juga $f(1)=a+b+c$ dan $f(-1)=a-b+c$ bulat. Karena $c$ bulat maka $a+b$ dan $a-b$ bulat. Dengan meninjau penjumlahan keduanya dan juga selisih keduanya kita peroleh bahwa $2a$ dan $2b$ bulat.

Jika $2a$ bulat genap, maka $a$ bulat. Karena $a+b$ bulat, ini berakibat $b$ bulat. Jadi dalam kasus ini $a,b,c$ semuanya bulat.

Jika $2a$ ganjil, maka $a=\frac{s}{2}$ untuk suatu bilangan ganjil $s$ . Karena $a+b$ bulat, tulis $a+b=u$ dengan $u$ bulat. Akibatnya, $s+2b=2a+2b=2u$ . Karena $2u$ genap dan $s$ ganjil, maka haruslah $2b=t$ ganjil. Jadi $b=\frac{t}{2}$ untuk suatu bilangan ganjil $t$ . Jadi dalam kasus ini $a=\frac{s}{2},b=\frac{t}{2}$ dengan $t$ ganjil dan $c$ bulat.

Pemikiran di balik layar

Pada soal ini kita diminta untuk mencari kondisi untuk $a,b,c$ agar $f$ merupakan suatu pemetaan. Yang menjadi permasalahan di sini adalah jika $a,b,c$ nya tidak kita pilih dengan baik maka $f(x)$ nya mungkin bukan bilangan bulat. Sebagai contoh jika $a=b=0$ dan $c=\frac{1}{2}$ maka $f(x)=\frac{1}{2}$ dan akibatnya $f$ bukan suatu pemetaan. Berarti kita harus mencari $a,b,c$ rasional sehingga $f(x)$ bulat untuk semua $x$ bulat.

Kita bisa mencoba-coba kombinasi nilai $a,b,c$ yang mungkin memenuhi, tapi terlalu banyak pilihan bilangan rasional $a,b,c$ . Untuk mencoba membatasi pilihan nilai $a,b,c$ , kita bisa menanyakan kalau $f(x)$ bulat untuk setiap $x$ apa akibatnya terhadap si $a,b, c$ ini?

Misalkan $f(x)=ax^2+bx+c$ bulat untuk setiap $x$ bulat. Kita bisa mencoba memasukkan nilai-nilai $x$ tertentu untuk bisa mengetahui lebih banyak tentang $a,b,c$ . Jika kita masukkan $x=0$ yang merupakan bilangan bulat, maka kita dapatkan $f(0)=c$ bulat. Dengan demikian mau tidak mau, agar $f(x)$ bulat “paling tidak” nilai $c$ haruslah bulat.

Berturut-turut kita substitusikan $x=1$ dan $x=-1$ kita peroleh $a+b+c$ dan $a-b+c$ bulat. Tapi karena kita sudah tahu bahwa $c$ bulat maka haruslah $a+b$ bulat dan $a-b$ bulat. Dengan menjumlahkan dan mengurangkan keduanya, kita juga peroleh bahwa $2a=(a+b)+(a-b)$ dan $2b=(a+b)-(a-b)$ bulat.

Bisakah sekarang kita menyimpulkan bahwa jawaban atas persoalan kita adalah semua bilangan rasional $a,b,c$ dengan $c,2a,2b$ bulat?

Belum! Di atas kita hanya menunjukkan bahwa jika $f(x)$ bulat maka haruslah $c,2a,2b$ bulat. Kita belum menunjukkan bahwa jika $a,b,c$ kita adalah bilangan rasional sedemikian sehingga $c,2a,2b$ bulat maka $f(x)$ bulat untuk setiap $x$ . Tapi paling tidak sekarang pilihan kita terbatas. Tadinya kita harus meninjau semua bilangan rasional $a,b,c$ . Sekarang kita cukup meninjau bilangan rasional $a,b,c$ yang membuat $2a,2b,c$ bulat.

Ok sekarang kita tinjau $a$ rasional sehingga $2a$ bulat. Jika $2a$ bilangan bulat genap, maka $a$ bulat. Jika $2a$ ganjil, maka $a=\frac{s}{2}$ untuk suatu bilangan ganjil $s$ .

Kita tinjau dua kasus

1) $a$ bulat.

Karena $a+b$ bulat, maka haruslah $b$ bulat. Dalam kasus ini $a,b,c$ semuanya bulat.

2) $a=\frac{s}{2}$ dengan $s$ bulat ganjil.

Kita tahu $2b$ juga bulat. Maka seperti argumen untuk $a$ diatas, kita tahu bahwa $b$ bulat atau $b=\frac{t}{2}$ untuk suatu bilangan bulat ganjil $t$ . Tapi tidak mungkin $b$ bulat, bersama-sama dengan $a+b$ bulat ia mengakibatkan $a$ bulat. Jadi haruslah $b=\frac{t}{2}$ .

[collapse]