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}

Domain + Finiteness = Field

Pada artikel ini akan dibahas tentang kondisi keberhinggaan yang memaksa suatu daerah integral menjadi lapangan. Kita mulai dengan dua lemma berikut.

Lemma 1 Jika {A} adalah himpunan berhingga maka {f:A\rightarrow A} injektif jika dan hanya jika {f} surjektif.

Proof: Misalkan {A=\{a_1,a_2,\ldots, a_n\}} dan {f} injektif. Karena {f} injektif maka {f(a_1),\ldots, f(a_n)} adalah {n} buah unsur yang berbeda di {A}. Karena {\{f(a_1),\ldots, f(a_n)\}\subseteq A} dan keduanya mempunyai banyak unsur yang sama, maka haruslah keduanya merupakan himpunan yang sama. Jadi {f} surjektif.

Jika {f} tidak injektif maka ada {a_i,a_j} dua unsur berbeda di {A} sehingga {f(a_i)=f(a_j)}. Dengan demikian {|\{f(a_1),\ldots, f(a_n)\}|\leq n-1}. Akibatnya {\{f(a_1),\ldots, f(a_n)\}\neq A} dan {f} tidak surjektif. \Box

Lema berikutnya adalah mengenai pemetaan linier pada ruang vektor berdimensi hingga.

Lemma 2 Misalkan {V} adalah sebuah ruang vektor berdimensi hingga {n}. Pemetaan linier {T:V\rightarrow V} injektif jika dan hanya jika {T} surjektif.

Proof: Menurut teorema dimensi berlaku {n=\dim(V)=\text{rank }(T)+\text{nolitas }(T)}. Perhatikan bahwa

\displaystyle T \text{ surjektif }\Leftrightarrow\text{rank }(T)=n \Leftrightarrow \text{nolitas }(T)=0 \Leftrightarrow T \text{ injektif}

\Box

Sekarang kita akan lihat dua kondisi keberhinggaan yang memaksa suatu daerah integral menjadi lapangan.

Proposition 3 Setiap daerah integral hingga {R} merupakan suatu lapangan.

Bukti

Proof: kita hanya perlu menunjukkan bahwa setiap unsur taknol di {R} memiliki invers. Ambil {r\neq 0} di {R}. Tinjau pemetaan {f:R\rightarrow R} melalui {f(x)=xr}. Perhatikan bahwa jika {xr=yr} maka {(x-y)r=0}. Karena {R} daerah integral dan {r\neq 0} maka {x=y}. Dengan demikian {f} injektif. Menurut lema di atas ini mengakibatkan {f} juga surjektif. Khususnya terdapat {z\in R} sehingga {1=f(z)=zr}. Karena domain merupakan gelanggang komutatif, maka berlaku juga {zr=1}. Dengan demikian {r} mempunyai invers {z} dan {R} suatu lapangan. \Box

[collapse]

Lemma 4 Setiap daerah integral {R} yang juga merupakan suatu ruang vektor berdimensi hingga atas suatu lapangan {K} adalah suatu lapangan.

Situasi dimana gelanggang {R} merupakan ruang vektor atas {K} bisa terjadi ketika {R} memuat lapangan {K}. Dengan menggunakan unsur di {K} sebagai skalar mudah diperiksa bahwa dengan penjumlahan di {R} dan perkalian skalar merupakan perkalian di gelanggan {R} maka daerah gelanggang {R} merupakan ruang vektor atas {K}.

Bukti

Proof: Ambil {r\neq 0} di {R}. Definisikan pemetaan {T(x)=xr}. Perhatikan bahwa untuk setiap {\alpha,\beta \in K} dan {u,v\in R} berlaku

\displaystyle T(\alpha u+\beta v)=(\alpha u+\beta v)r=\alpha ur+\beta vr=\alpha T(u)+\beta T(v).

Dengan demikian {T} adalah suatu pemetaan linier. {T} juga injektif karena {0=T(x)=xr} mengakibatkan {x=0} yang menunjukkan bahwa {\ker T= 0}. Sekarang dengan menggunakan lemma kita peroleh {T} surjektif dan seperti argumen pada proposisi di atas ini membawa kita kepada eksistensi invers dari {r}. Jadi {R} lapangan. \Box

[collapse]

Dua Soal Struktur Aljabar ONMIPA 2016

Pada tulisan kali ini akan dibahas tentang soal ONMIPA 2016 bidang matematika untuk sub-bidang struktur aljabar.

Soal Hari Pertama

Misalkan {x} pembagi nol kiri dan {y} pembagi nol kanan di suatu ring hingga {R}. Buktikan bahwa {xy} sekaligus merupakan pembagi nol kiri dan kanan.

Beberapa peserta berhasil menyelesaikan masalah ini. Solusi alamiah muncul dari sebuah wishful thinking, kalau saja {y} juga merupakan pembagi nol kiri, yakni ada {u\neq 0} sehingga {yu=0} maka {xy} akan menjadi pembagi nol kiri, karena {xyu=x(yu)=x\cdot 0=0}. Sekarang memangnya kenapa jika {y} bukan pembagi nol kiri ? Jika {y} bukan pembagi nol kiri maka pemetaan {s\mapsto ys} dari {R} ke {R} merupakan pemetaan yang injektif (periksa!). Karena {R} hingga maka pemetaan ini juga surjektif. Karena {x} pembagi nol kiri, maka ada {v\neq 0} sehingga {xv=0}. Karena {s\mapsto ys} surjektif, ada {t\in R} sehingga {yt=v}. Ini mengakibatkan {xyt=xv=0}. Jadi {xy} pembagi nol kiri.

Untuk menunjukkan bahwa {xy} juga merupakan pembagi nol kanan, kami serahkan kepada pembaca.

Cara lain yang lebih teoretis adalah dengan pertama membuktikan lemma berikut

Bukti Lain

Lemma 1 {a\neq 0} merupakan pembagi nol kanan jika dan hanya jika {Ra\subset R} (subset sejati). Proof: Jika {a} bukan pembagi nol kanan, maka pemetaan {u\mapsto ua} tidak injektif dan akibanya tidak surjektif (karena {R}) hingga. dengan demikian {Ra} subset sejati dari {R}. Sebaliknya jika {Ra} subset sejati dari {R} maka {u\mapsto ua} tidak surjektif dan akibatnya tidak injektif. Berarti ada {u\neq v} sehingga {ua=va}, yang berakibat {(u-v)a=0}. Jadi {a} pembagi nol kanan. \Box Untuk pembagi nol kiri kita punya lema yang serupa. Lemma 2 {a\neq 0} merupakan pembagi nol kiri jika dan hanya jika {aR\subset R}. Sekarang jika {x} pembagi nol kiri dan {y} pembagi nol kanan maka {xR\subset R} dan {Ry\subset R}. Karena {(xy)R=x(yR)\subseteq xR\subset R} maka {xy} pembagi nol kiri. Demikian pula karena {R(xy)=(Rx)y\subseteq Ry\subset R} maka {xy} pembagi nol kanan.

[collapse]

Soal tentang struktur aljabar berikutnya adalah sebagai berikut:

Soal Hari Kedua

Misalkan {G} grup berorde {n} dan {p} adalah bilangan prima terkecil sehingga {p} membagi {n}. Jika {H} adalah satu-satunya subgrup dari {G} berorde {p}, tunjukkan bahwa {gh=hg} untuk setiap {g\in G} dan {h\in H}.

Bukti 1

Ambil {g\in G}. Perhatikan bahwa {gHg^{-1}} juga merupakan subgrup berorde {p}. Dari kondisi yang diberikan soal kita peroleh {gHg^{-1}=H}. Akibatnya pemetaan {f:H-\{e\}\rightarrow H-\{e\}} melalui {f(h)=ghg^{-1}} terdefinisi dengan baik. Mudah diperiksa bahwa pemetaan ini merupakan suatu pemetaan bijektif. Karenanya kita bisa melihat {f} sebagai permutasi atas {p-1} unsur, yakni {f\in S_{p-1}}. Karena {|S_{p-1}|=(p-1)!} maka {f^{(p-1)!}= \text{pemetaan identitas }}. Perhatikan bahwa {f^{n}(h)=g^nh(g^{-1})^n=h} (karena {g^n=e} untuk setiap {g\in G}). Dengan demikian orde {f} sekaligus membagi {(p-1)!} dan membagi {n}. Jika orde {f} adalah {t\neq 1} maka {t} mempunyai faktor prima {q}. Karena {t\mid (p-1)!} dan {t\mid n} maka {q\mid n} dan {q\mid (p-1)!} sehingga {q\leq p-1} adalah bilangan prima yang kurang dari {p} yang membagi {n} (kontradiksi!). Jadi haruslah orde {f} adalah 1 atau dengan kata lain {ghg^{-1}=h\Leftrightarrow gh=hg}.

[collapse]
Bukti 2

Cara lain dengan menggunakan aksi grup adalah sebagai berikut. Tinja aksi dari {G} terhadap {H} dengan konjugasi {g\cdot h=ghg^{-1}} untuk setiap {g\in G} dan {h\in H}. Aksi ini terdefinisi dengan baik karena {gHg^{-1}=H}. Ambil {h\neq e} di {H}. Menurut teorema orbit-stabilizer kita peroleh \displaystyle |G|=|\text{orbit}(h)||G_h| dengan {\text{orbit }(h)=\{ghg^{-1}\mid g\in G\}} dan {G_h=\{g\in G\mid ghg^{-1}=h\}}. Karena {h\neq e} maka {ghg^{-1}\neq e} untuk setiap {g\in G} atau dengan kata lain {e\not \in \text{orbit }(h)}. Jadi {|\text{orbit} (h)|\leq p-1}. Jika {|\text{orbit} (h)|> 1} maka ada prima {q} sehingga {q\mid |\text{orbit} (h)| \mid n}. Jadi {q\mid n} dan {q\leq p-1} yang bertentangan dengan fakta bahwa {p} adalah prima terkeil yang membagi {n}. Jadi haruslah {|\text{orbit} (h)|=1}. Karena {h\in \text{orbit} (h)} maka haruslah {ghg^{-1}=h \Leftrightarrow gh=hg} untuk setiap {g\in G}.

[collapse]