Barra – A Mathematician Impostor

February 11, 2017February 11, 2017

Deret Harmonik dan Pecahan Mesir

Pecahan berbentuk ${\dfrac{1}{n}}$ dengan ${n}$ bilangan asli kita sebut sebagai pecahan satuan. Apakah penjumlahan sejumlah pecahan satuan yang pertama dapat menghasilkan bilangan bulat? Dengan kata lain, adakah bilangan asli ${N}$ sehingga

$\displaystyle H_N:=\frac11+\frac12+\frac13+\frac14+\cdots +\frac{1}{N-1}+\frac{1}{N}$

merupakan bilangan bulat?

Ternyata hasilnya negatif, seperti tertulis dalam teorma berikut.

Teorema 1 Untuk setiap bilangan asli ${N}$ bilangan ${H_N}$ tidak pernah merupakan bilangan bulat.

Proof: Andaikan ${H_N}$ merupakan bilangan bulat untuk suatu bilangan asli ${N}$ . Misalkan ${k}$ adalah bilangan asli sehingga ${2^k\leq N<2^{k+1}}$ (mengapa ada ${k}$ yang demikian?). Kalikan ${H_N}$ dengan ${2^{k-1}}$ untuk mendapatkan

$\begin{align*} 2^{k-1}H_N&= 2^{k-1}\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{2^k-1}+\frac{1}{2^k}+\frac{1}{2^k+1}+\cdots +\frac{1}{N}\right)\\ &=\frac{2^{k-1}}{1}+\frac{2^{k-2}}{1}+\frac{2^{k-1}}{3}+\cdots + \frac{2^{k-1}}{2^k-1}+\frac{1}{2}+\frac{2^{k-1}}{2^k+1}+\cdots +\frac{2^{k-1}}{N}. \end{align*}$

Pindah ruaskan ${2^{k-1}H_N}$ dan ${\frac{1}{2}}$ , didapat

$\displaystyle -\frac12=-\frac{2^{k-1}H_N}{1}+\left(\frac{2^{k-1}}{1}+\frac{2^{k-2}}{1}+\frac{2^{k-1}}{3}+\cdots + \frac{2^{k-1}}{2^k-1}\right)+\left(\frac{2^{k-1}}{2^k+1}+\cdots +\frac{2^{k-1}}{N}\right)$

Masing-masing suku disebelah kanan merupakan bilangan rasional dalam bentuk yang paling sederhana dengan penyebut ganjil. Ketika mereka semua kita jumlahkan dan sederhanakan maka tetap diperoleh suatu bilangan rasional ${\frac pq}$ dengan ${q}$ ganjil. Akibatnya tidak mungkin ${\frac{p}{q}=-\frac{1}{2}}$ (kontradiksi!). $\Box$

Pertanyaan berikutnya adalah bagaimana kalau kita tidak mensyaratkan pecahan satuannya harus berurutan? Apakah bisa kita menyatakan suatu bilangan bulat sebagai jumlahan pecahan-pecahan satuan yang berbeda?

Definisi 2 Suatu bilangan rasional disebut pecahan Mesir jika ia dapat dinyatakan sebagai jumlahan pecahan-pecahan satuan yang berbeda.

Ternyata dapat dibuktikan bahwa tidak hanya ada bilangan bulat yang merupakan pecahan Mesir, tapi lebih kuat dari itu, setiap bilangan rasional positif merupakan pecahan Mesir. Untuk membuktikannya pertama kita perlukan lema berikut.

Lema 3 Misalkan ${\frac{p}{q}}$ bilangan rasional dengan ${\frac{1}{s}\leq \frac{p}{q}< \frac{1}{s-1}}$ untuk suatu bilangan asli ${s}$ . Maka ${\frac{p}{q}}$ merupakan pecahan Mesir.

Proof: Perhatikan bahwa

$\displaystyle \frac{p}{q}-\frac{1}{s}=\frac{ps-q}{qs}$

Karena ${\frac{p}{q}<\frac{1}{s-1}}$ , maka ${p(s-1)<q\Leftrightarrow ps-q<p}$ . Tulis ${p_1=p(s-1)}$ dan ${q_1=qs}$ , maka ${\frac{p}{q}-\frac{1}{s}=\frac{p_1}{q_1}}$ dengan ${p_1<p}$ . Jika ${p_1=0}$ , maka ${\frac{p}{q}=\frac{1}{s}}$ dan kita selesai. Jika ${p_1>0}$ , maka terdapat bilangan asli ${s_1 >s}$ (mengapa?) sehingga ${\frac{1}{s_1}<\frac{p_1}{q_1}<\frac{1}{s_1-1}}$ . Dengan cara serupa kita dapatkan ${\frac{p_1}{q_1}-\frac{1}{s_1}=\frac{p_2}{q_2}}$ dengan ${p>p_1>p_2}$ . Jika kita lakukan terus menerus maka akan diperoleh barisan bilangan asli yang turun ${p>p_1>p_2>\ldots}$ yang tentunya pada suatu saat kita peroleh ${p_{n+1}=0}$ . Ketika hal ini terjadi maka kita peroleh

$\displaystyle \frac{p}{q}-\frac{1}{s}-\frac{1}{s_1}-\cdots -\frac{1}{s_{n}}=\frac{p_{n+1}}{q_{n+1}}=0.$

Jadi ${\frac{p}{q}}$ merupakan pecahan mesir. $\Box$

Sekarang kita siap membuktikan hasil utama kita.

Teorema 4 Setiap bilangan rasional positif merupakan pecahan Mesir.

Proof: Ambil sebarang bilangan rasional positif ${\frac{u}{v}}$ . Ingat bahwa deret harmonik $\sum_{n=1}^\infty \frac{1}{n}$ merupakan deret yang divergen. Jika $H_N=\sum_{n=1}^N \frac{1}{n}$ , maka terdapat suatu ${m}$ sehingga ${H_m\leq \frac{u}{v}<H_{m+1}=H_m+\frac{1}{m+1}}$ . Akibatnya ${0<\frac{u}{v}-H_m<\frac{1}{m+1}<1}$ dan tentunya terdapat ${s>m+1}$ asli sehingga ${\frac{1}{s}\leq \frac{u}{v}-H_m<\frac{1}{s-1}}$ . Dengan menggunakan lema di atas, kita peroleh

$\displaystyle \frac{u}{v}-H_m=\frac{1}{s}+\frac{1}{s_1}+\cdots +\frac{1}{s_n}$

dengan ${m+1<s<s_1<\cdots<s_n}$ . Dengan demikian

$\displaystyle \frac{u}{v}=H_m+\frac{1}{s}+\frac{1}{s_1}+\cdots+\frac{1}{s_n}$

merupakan pecahan Mesir. $\Box$

February 7, 2017February 7, 2017

Deret Harmonik yang Konvergen ?

Di kelas telah ditunjukkan bahwa deret harmonik $\sum_{n=1}^\infty \frac{1}{n}$ merupakan deret yang divergen. Berikut adalah bukti yang sedikit berbeda dengan yang telah ditunjukkan di kelas.

Teorema 1 Deret harmonik divergen.
Bukti: Andakan deret harmonik konvergen, tulis jumlahnya sebagai ${S}$ . Maka

$\begin{align*} S &= 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\cdots \\ &> \left(\frac{1}{2}+\frac12\right)+\left(\frac14+\frac14\right)+\left(\frac16+\frac16\right)+\cdots\\ &=S \end{align*}$

dan ${S>S}$ tidak mungkin terjadi (kontradiksi!) $\Box$

Pernyataan berikutnya bisakah kita membuang beberapa suku dari deret harmonik sehingga dihasilkan deret yang konvergen? Kita mengetahui bahwa jawabannya bisa, karena kita mengetahui bahwa deret $\sum_{n=1}^\infty \frac{1}{n^2}$ merupakan deret yang konvergen. Bisakah kita melakukannya dengan lebih baik yakni dengan membuang suku-suku dari deret harmonik lebih sedikit?

Berikut akan ditunjukkan bahwa jika kita kita membuang suku-suku ${\frac{1}{n}}$ pada deret harmonik untuk semua ${n}$ yang digit-digitnya mengandung minimal sebuah angka 9, maka deret yang dihasilkan merupakan deret yang konvergen.

Teorema 2 Deret ${\displaystyle\sum_{9 \text{ bukan digit }n} \frac{1}{n}}$ konvergen.
Bukti: Misalkan ${a_1=1+\frac{1}{2}+\cdots +\frac{1}{8}, a_2=\frac{1}{10}+\frac{1}{11}+\cdots +\cdots+\frac{1}{88}}$ dan secara umum ${a_m=\frac{1}{10^{m-1}}+\cdots +\frac{1}{\underbrace{8\cdots 88}_m}}$ adalah jumlah semua bentuk ${\frac{1}{n}}$ dengan ${n}$ bilangan dengan ${m}$ digit yang tidak mengandung angka 9. Perhatikan bahwa jika kita memiliki suatu bilangan dengan ${m}$ digit dan dia tidak mengandung 9, maka untuk digit pertamanya kita punya 8 pilihan, yakni semua digit kecuali 0 atau 9. Sedangkan untuk digit kedua sampai dengan digit ke- ${m}$ kita bisa menggunakan semua digit kecuali digit 9. Dengan demikian pada ${a_m}$ kita menjumlahkan ${8\cdot 9^{m-1}}$ bilangan. Karena suku tekecil di ${a_m}$ adalah ${\frac{1}{10^{m-1}}}$ maka ${a_m< 8\cdot \frac{9^{m-1}}{10^{m-1}}}$ . Akibatnya

$\displaystyle \sum_{9 \text{ bukan digit }n} \frac{1}{n}=\sum_{m=1}^\infty a_m<\sum_{m=1}^\infty 8\cdot \left(\frac{9}{10}\right)^{m-1}=80$

jelas merupakan deret konvergen. $\Box$
Berikutnya adalah tantangan buat para pembaca

Problem Jika kita membuang semua suku ${\frac{1}{n}}$ pada deret harmonik untuk semua ${n}$ yang mengandung paling sedikit 2017 buah angka 9 pada digit-digitnya, apakah deret yang dihasilkan akan konvergen?

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

October 16, 2016October 18, 2016

The Conway’s Way

1. Lagi-lagi Keirasionalan ${\sqrt{2}}$

Berikut bukti keirasionalan ${\sqrt{2}}$ dari Conway yang sangat ringkas:
Andaikan ${\sqrt{2}=\frac{p}{q}}$ dengan ${p,q}$ bulat dan dalam bentuk yang paling sederhana. Maka ${2q^2=p^2}$ . Tuliskan persamaan ini dalam bentuk

$\displaystyle \frac{2q}{p}=\frac{p}{q}.$

Untuk bilangan real ${x}$ nyatakan dengan ${\{x\}}$ sebagai bagian ${x}$ yang tidak bulat. Sebagai contoh ${\{123,456\}=0,456}$ , ${\{7\frac{1}{3}\}=\frac{1}{3}}$ . Dari persamaan di atas kita peroleh

$\displaystyle \left\{\frac{2q}{p}\right\}=\left\{\frac{p}{q}\right\}$

Perhatikan bahwa jika kita memiliki bilangan rasional ${x=\frac{a}{b}}$ , jelas bahwa ${\{x\}=\frac{c}{b}}$ untuk suatu ${0\leq c<b}$ . Dengan demikian dari persamaan di atas kita peroleh

$\displaystyle \frac{s}{p}=\frac{t}{q}\Leftrightarrow \frac{s}{t}=\frac{p}{q}$

untuk suatu ${0\leq s< p}$ dan ${0\leq t<q}$ . Tapi ini mustahil terjadi karena tadi kita sudah menuliskan ${\frac{p}{q}}$ dalam bentuk yang paling sederhana.

June 13, 2016

Kekonvergenan Suatu Deret

Salah satu soal menarik pada soal tutorial kalkulus 2A adalah tentang kekonvergenan deret

$\displaystyle \sum_{n=2}^\infty \frac{1}{(\ln n)^4}.$

Untuk dapat memahami intuisi penyelesaian di atas kita akan melakukan lomba marathon yang pesertanya adalah fungsi-fungsi ${e^x,x^k}$ dan ${\ln x}$ . Ini merupakan lomba marathon dalam artian kita hanya peduli untuk ${x}$ yang cukup besar.

Untuk dapat membandingkan, misalnya siapa diantara ${ê^x}$ dan ${x^k}$ yang menang kita bisa hitung nilai $\lim_{x\rightarrow\infty}\frac{x^k}{e^x}$ . Perhatikan bahwa ini merupakan bentuk tak tentu ${\frac{\infty}{\infty}}$ yang mengakibatkan kita bisa melakukan aturan L’Hospital. t Perhatikan bahwa setiap kali kita menurunkan pembilang, derajatnya berkurang satu, akan tetapi penyebutnya meskipun diturunkan tetap ${e^x}$ seperti semula. Hal ini menunjukkan bahwa pada akhirnya nilai limit di atas adalah nol. Ini berarti untuk ${x}$ yang cukup besar ${e^x}$ lebih cepat dibanding ${x^k}$ untuk ${k}$ yang manapun (meski ${k=10^6}$ misalnya).

Dengan melakukan pendekatan yang sama kita bisa tunjukkan bahwa ${x^k}$ eventually akan lebih cepat dibanding ${\ln x}$ meski ${k}$ nya kecil, misalnya ${0<k<1}$ .

Apa untungnya pengamatan di atas? Dari pengamatan di atas kita tahu bahwa

$\displaystyle n^{1/4} >\ln n \Leftrightarrow n> (\ln n)^4\Leftrightarrow \frac{1}{n}<\frac{1}{(\ln n)^4}$

untuk ${n}$ yang cukup besar. Karena deret ${\sum_{n=2}^\infty \frac{1}{n}}$ merupakan deret yang divergen (deret harmonik), maka menurut uji banding langsung, demikian pula deret $\sum_{i=2}^n \frac{1}{(\ln n)^4}$ merupakan deret yang divergen.

Agar buktinya lebih ketat, kita masih berhutang untuk menunjukkan bahwa

$\displaystyle n^{1/4}-\ln n > 0 \ \ \ \ \ (1)$

untuk ${n}$ yang besar. Pertanyaannya untuk ${n}$ yang mana? Saya serahkan kepada pembaca untuk membuktikan bahwa ketaksamaan di atas benar untuk ${n\geq e^{16}}$ . Perlu di ingat juga bilangan ${e^{16}}$ ini tidak benar-benar penting dalam menentukan kedivergenan deret kita dan boleh kita ganti dengan bilangan lain yang mengakibatkan ketaksamaan 1 benar.

June 10, 2016June 10, 2016

Perluasan Aljabarik

5. Perluasan Aljabarik

Pada pembahasan sebelumnya kita melihat bahwa ketika ${\alpha}$ aljabarik atas ${K}$ maka semua unsur di ${K(\alpha)}$ juga aljabarik atas ${K}$ . Kita akan memerlukan suatu istilah untuk menangkap konsep ini.

Definition 14 Suatu perluasan ${L/K}$ dikatakan perluasan aljabarik jika semua unsur di ${L}$ merupakan unsur aljabarik atas ${K}$ .

Dengan definisi ini, apa yang kita sampaikan sebelumnya bisa kita nyatakan sebagai berikut.

Proposition 15 Jika ${\alpha}$ aljabarik atas ${K}$ maka ${K(\alpha)/K}$ merupakan perluasan aljabarik.

Seringkali kita akan menggunakan argumen dimensi untuk memperlihatkan bahwa suatu perluasan bersifat aljabarik. Karenanya seringkali kita akan menggunakan definisi alternatif berikut. Kedua definisi ekivalen dikarenakan Teorema 12.

Definition 16 Suatu perluasan ${L/K}$ dikatakan perluasan aljabarik jika untuk setiap ${\alpha\in L}$ berlaku ${[K(\alpha):K]<\infty}$ .

Perhatikan bahwa ${\sqrt{2}}$ dan bilangan rasio emas ${\phi=\frac{1+\sqrt{5}}{2}}$ keduanya merupakan bilangan aljabarik atas ${\mathbb{Q}}$ karena yang pertama merupakan akar dari ${x^2-2}$ sedangkan yang kedua adalah akar dari ${x^2-x-1}$ . Apakah ${\sqrt{2}+\phi}$ dan ${\sqrt{2}\phi}$ aljabarik atas ${\mathbb{Q}}$ ? Kami berikan petunjuk bahwa keduanya aljabarik dan kami minta pembaca untuk mencari polinom minimalnya pada soal latihan berikut.

Exercise 10 Tentukan polinom minimal atas ${\mathbb{Q}}$ dari ${\sqrt{2}+\phi}$ dan ${\sqrt{2}\phi}$ .

Jika anda mencoba latihan di atas anda akan menyadari bahwa soal latihan tersebut tidaklah mudah. Jika diberikan ${\alpha,\beta}$ aljabarik, tidaklah mudah untuk mencari polinom minimal dari ${\alpha+\beta}$ dan ${\alpha\beta}$ . Akan tetapi teorema 12 berikut membantu kita memahami bahwa unsur-unsur aljabarik tertutup terhadap beberapa operasi.

Theorem 17 Misalkan ${L/K}$ suatu perluasan. Jika ${\alpha,\beta \in L}$ dengan ${\alpha\pm \beta, \alpha\cdot \beta}$ juga aljabarik atas ${K}$ . Hal yang sama juga berlaku untuk ${\alpha/\beta}$ untuk ${\beta\neq 0}$ . Himpunan semua unsur di ${L}$ yang aljabarik atas ${K}$ kita notasikan dengan ${L_A}$ . Himpunan ${L_A}$ membentuk suatu lapangan dan ${L\supset L_A\supset K}$ .

Proof: Perhatikan bahwa ${\alpha\pm \beta, \alpha\beta, \alpha/\beta \in K(\alpha,\beta)}$ . Ini berakibat ${K(\alpha\beta)\subseteq K(\alpha,beta)}$ . Akibatnya dengan menggunakan Proposisi 13 didapat

$\displaystyle [K(\alpha\beta): K]\leq [K(\alpha,\beta)]:K]\leq [K(\alpha):K][K(\beta):K] <\infty$

dengan ketaksamaan terakhir terjadi karena ${\alpha}$ dan ${\beta}$ aljabarik atas ${K}$ . Jadi ${\alpha\beta}$ aljabarik. Dengan cara yang serup kita juga bisa tunjukkan bahwa ${\alpha\pm \beta}$ dan ${\alpha/\beta}$ aljabarik. Khususnya operasi penjumlahan dan perkalian di tertutup di ${L_A}$ sehingga ${L_A}$ menjadi subgelanggang dari ${R}$ . Perhatikan juga setiap unsur aljabarik ${\beta\neq 0}$ memiliki invers ${1/\beta}$ yang juga aljabarik (kenapa?). Jadi ${L_A}$ suatu lapangan. $\Box$

Berikutnya kita mencoba memperumum hasil pada Proposisi 15.

Theorem 18 Misalkan ${L/K}$ suatu perluasan dan ${S\subseteq L}$ sedemikian sehingga setiap unsur di ${S}$ aljabarik atas ${K}$ . Maka ${K(S)/K}$ adalah perluasan aljabarik.

Proof: Kita akan menggunakan deskripsi unsur di ${K(S)}$ yang dituliskan pada Teorema 3. Karena unsur aljabarik tertutup terhadap perkalian dan semua unsur di ${S}$ aljabarik, maka jelas setiap unsur di ${W_S}$ juga aljabarik. Unsur generik di ${K(S)}$ berbentuk ${\frac{\sum_{i=1}^m s_iu_i}{\sum_{i=1}^n t_iv_i}}$ . Masing-masing ${s_i,t_i}$ aljabarik kerena merupakan unsur di ${K}$ . Demikian pula dengan ${u_i,v_i}$ yang merupakan unsur di ${W_S}$ . Karena ${\alpha}$ diperoleh dengan menggunakan operasi penjumlahan, perkalian dan pembagian pada unsur-unsul aljabarik, maka ${\alpha}$ juga aljabarik. $\Box$

Berikutnya kita akan mencoba melihat kaitan antara perluasan hingga dengan perluasan aljabarik. Terlebih dulu kita buktikan hasil penting berikut.

Theorem 19 ${L/K}$ merupakan perluasan hingga jika dan hanya jika terdapat ${\alpha_1,\ldots, \alpha_n}$ unsur aljabarik atas ${K}$ sehingga ${L=K(\alpha_1,\ldots, \alpha_n)}$ .

Proof: ${(\Rightarrow)}$ Karena ${[L:K]<\infty}$ , kita bisa misalkan ${\alpha_1,\ldots, \alpha_n}$ adalah basis bagi ruang vektor ${L/K}$ . Setiap unsur ${\alpha\in L}$ merupakan kombinasi linier dari ${\alpha_1,\ldots,\alpha_n}$ . Dengan demikian ${L\subseteq L(\alpha_1,\ldots,\alpha_n)}$ . Inklusi sebaliknya jelas berlaku. Dengan demikian ${L=K(\alpha_1,\ldots,\alpha_n)}$ . Untuk masing-masing ${\alpha_i}$ himpunan ${\{1,\alpha,\ldots, \alpha^n\}}$ merupakan himpunan yang bergantung linear. Dengan demikian masing-masing ${\alpha_i}$ unsur aljabarik atas ${K}$ .

${(\Leftarrow)}$ Perhatikan bahwa karena ${K\subseteq K(\alpha_1,\ldots, \alpha_i)}$ dan ${\alpha_{i+1}}$ aljabarik atas ${K}$ , maka minimal polinom dari ${\alpha_{i+1}}$ dapat dianggap sebagai polinom di ${K(\alpha_1,\ldots, \alpha_i)[x]}$ . Dengan demikian ${\alpha_{i+1}}$ aljabarik atas ${K(\alpha_1,\ldots, \alpha_i)}$ dan khususnya kita punyai ${[K(\alpha_1,\ldots, \alpha_i)(\alpha_{i+1}):K(\alpha_1,\ldots, \alpha_i)]<\infty}$ untuk setiap ${i}$ . Untuk mempersingkat notasi kita tuliskan ${K(\alpha_1,\ldots, \alpha_i)=F_i}$ dan ${[F_{i+1}:F_i]=[F_i(\alpha_{i+1}):F_i]<\infty}$ . Jika ${L=K(\alpha_1,\ldots,\alpha_n)}$ dengan masing-masing ${\alpha_j}$ aljabarik maka

$\begin{align*} [L:K]&=[F_n:K]\\ &=[F_n:F_{n-1}][F_{n-1}:F_{n-2}]\cdots [F_2:F_1][K(\alpha_1):K]\\ &< \infty. \end{align*}$

$\Box$

Corollary 20 Jika ${[L:K]<\infty}$ maka ${L/K}$ adalah perluasan aljabarik.

Proof: Dengan Teorema 19 terdapat ${\alpha_1,\ldots,\alpha_n}$ aljabarik atas ${K}$ sehingga ${L=K(\alpha_1,\ldots,\alpha_n)}$ . Dengan Teorema 18 ini berakibat ${L/K}$ perluasan aljabarik. $\Box$

Remark 1 Perlu diperhatikan bahwa arah sebaliknya tidak berlaku. Ada contoh suatu perluasan aljabarik yang merupakan perluasan takhingga.

Untuk memberikan contoh perluasan aljabarik yang takberhingga kita ingatkan pembaca pada Lemma Eisenstein berikut.

Lemma 21 (Eisenstein) Misalkan ${P(x)=a_nx^n+a_{n-1}x^{n-1}+a_1x+a_0\in \mathbb{Z}[x]}$ dengan sifat: terdapat ${p}$ prima sedemikian sehingga ${p}$ membagi semua ${a_i}$ kecuali untuk ${i=n}$ dan ${p^2}$ tidak membagi ${a_0}$ . Maka ${P(X)}$ taktereduksi di ${\mathbb{Q}[x]}$ .

Example 5 Dengan menggunakan kriteria Eisenstein ini kita dapat melihat bahwa untuk ${n\geq 2}$ kita dapatkan ${P_n(x)=x^n-2}$ merupakan polinom taktereduksi di ${\mathbb{Q}[x]}$ berderajat ${n}$ . Misalkan ${\alpha_n}$ adalah salah satu akar kompleks dari ${P_n}$ . Definisikan ${S=\{\alpha_n : n\geq 2\}}$ . Karena setiap unsur di ${S}$ aljabarik atas ${\mathbb{Q}}$ maka ${\mathbb{Q}(S)}$ merupakan perluasan aljabarik (lihat Teorema 18). Di lain pihak untuk setiap bilangan asli ${M}$ kita peroleh bahwa

$\displaystyle [\mathbb{Q}(S):\mathbb{Q}]\geq [\mathbb{Q}(\alpha_M):\mathbb{Q}]=\deg P_M(x)=M,$

maka haruslah ${[\mathbb{Q}(S):\mathbb{Q}]=\infty}$ .

June 9, 2016June 9, 2016

Teorema Cauchy dan Kesederhanaan A5

Pada artikel ini kita akan buktikan Teorema Cauchy dan kemudian kita gunakan aplikasi sederhananya untuk menunjukkan bahwa grup alternating ${A_5}$ sederhana. Bukti yang akan di berikan mengikuti buktinya McKay. Beliau membuktikan lemma yang lebih kuat berikut.

Lemma 1 (Mckay) Misalkan ${G}$ suatu grup berorde ${n}$ dan ${p}$ adalah bilangan prima pembagi ${n}$ . Maka banyaknya solusi dari ${x^p=e}$ di ${G}$ ada sebanyak ${kp}$ untuk suatu ${K\neq 0}$ .

Proof: Tinjau himpunan ${S=\{(a_1,\ldots,a_p) : a_i\in G \text{ dan } a_1\cdots a_p=e\}}$ . Definisikan operator ${\sigma}$ , operator pergeseran melingkar, melalui ${\sigma(a_1,a_2,\ldots, a_p)=(a_p,a_1,\ldots, a_{p-1})}$ . Definisikan relasi ekivalen di ${S}$ , dua tupel ekivalen jika kita bisa menerapkan operator ${\sigma}$ beberapa kali kepada tupel yang satu untuk mendapatkan tupel yang lain. Perhatikan bahwa jika semua ${a_1=\cdots=a_p}$ maka kelas ekivalen dari ${(a_1,\ldots, a_p)}$ hanya berisi satu unsur. Jika ada dua komponen yang berbeda, yakni ${a_i\neq a_j}$ untuk suatu ${i,j}$ , setiap menerapkan operator ${\sigma}$ kita akan memperoleh tupel yang baru. Baru setelah menerapkan ${\sigma}$ sebanyak ${p}$ kali kita kembali ke tupel semula. Dengan demikian dalam situasi ada dua komponen yang berbeda, kelas ekivalennya mengandung ${p}$ unsur.

Sekarang perhatikan bahwa agar ${a_1\cdots a_p=1}$ kita bisa memilih ${a_1,\ldots, a_{p-1}}$ sembarang dan kemudian ${a_p}$ ditentukan oleh pemilihan dari ${a_1,\ldots, a_{p-1}}$ kita, yakni ${a_p=(a_1\cdots a_{p-1})^{-1}}$ . Dengan demikian banyaknya anggota di ${S}$ adalah sama dengan banyaknya cara memilih ${a_1,\ldots, a_{p-1}}$ yakni sebanyak ${n^{p-1}}$ .

Kelas-kelas ekivalen dari relasi ekivalen di atas mempartisi ${S}$ . Misalkan ada ${r}$ kelas ekivalen yang beranggotakan 1 unsur dan ${t}$ kelas ekivalen yang beranggotakan ${p}$ unsur. Akibatnya ${r+tp=n^{p-1}}$ . Perhatikan bahwa menurut Teorema Little Fermat berlaku ${n^{p-1}\equiv n {\pmod p}}$ . Karena ${p}$ membagi ${n}$ maka ${p}$ membagi ${n^{p-1}}$ . Akibatnya ${p}$ juga membagi ${r}$ . Perhatikan bahwa $\{(e,e,\ldots,e)\}$ merupakan salah satu kelas ekivalen yang beranggotakan satu unsur. Dengan demikian ${r\neq 0}$ dan ${r=kp}$ dengan ${k\neq 0}$ . $\Box$

Theorem 2 (Cauchy) Misalkan ${G}$ grup dengan orde ${n}$ dan ${p}$ bilangan prima yang membagi ${n}$ . Maka ada unsur di ${G}$ yang berorde ${p}$ .

Proof: Dari bukti Lemma McKay di atas kita melihat bahwa banyaknya solusi ${x^p}$ dengan ${x\neq e}$ ada sebanyak ${kp-1\neq 0}$ . $\Box$

Dalam tulisan ini kita akan membuktikan bahwa ${A_5}$ , grup yang memuat semua permutasi genap di ${S_5}$ , merupakan grup yang simple.

Untuk bukti kesederhanaan ${A_5}$ kita menggunakan argumen di bukunya Martin Isaacs Algebra. Dalam bukti ini akan dihindari penggunaan teorema Sylow yang biasanya belum diperoleh pada kuliah teori grup di tingkat sarjana.

Kita akan menggunakan lema berikut dalam pembuktian

Lemma 3 Dua unsur di ${S_n}$ saling konjugat jika dan hanya jika keduanya mempunyai struktur putaran (cycle) yang sama.

Theorem 4 ${A_5}$ merupakan grup yang sederhana.

Proof: Unsur-unsur di ${A_5}$ mempunyai struktur putaran salah satu diantara struktur: ${1^5, 1\cdot 2^2, 1^2\cdot 3, 5}$ . Masing-masingnya terdapat ${1,15,20,24}$ unsur di ${A_5}$ dengan struktur putaran tersebut.

Misalkan ${N}$ adalah subgrup normal dari ${A_5}$ dengan ${N\neq {1}}$ dan ${N\neq A_5}$ . Perhatikan bahwa ${|A_5|=60=2^2\cdot 3\cdot 5}$ . Akibatnya faktor prima dari ${|N|}$ adalah 2,3 atau 5.

Jika ${3\mid |N|}$ maka menurut teorema Cauchy, ada unsur berorde 3 yang merupakan unsur di ${N}$ . Unsur tersebut jelas adalah unsur yang mempunyai struktur putaran ${1^2\cdot 3}$ . Berdasarkan lema semua unsur yang mempunyai struktur putaran ini saling konjugat satu sama lain. Karena subgrup normal ${N}$ tertutup secara konjugasi maka ${N}$ memuat semua unsur yang memiliki struktur putaran ${1^2\cdot 3}$ . Khususnya ${|N|>20}$ . Karena ${|N|}$ membagi 60, maka haruslah ${|N|=30}$ .

Jika ${5\mid |N|}$ , kembali dengan teorema Cauchy, ${N}$ memiliki unsur berorde 5 dan haruslah unsur dengan struktur putaran 5. Dengan kenormalan ${N}$ maka ke 24 unsur yang memiliki struktur putaran 5 semuanya termuat di ${N}$ . Jadi ${|N|>24}$ dan karena ${|N|}$ membagi ${60}$ maka haruslah ${|N|=30}$ .

Dengan demikian jika ${3\mid |N|}$ atau ${5\mid |N|}$ maka ${|N|=30}$ yang mengakibatkan ${3}$ dan ${5}$ keduanya membagi ${|N|}$ . Akan tetapi ini berarti semua unsur dengan struktur putaran ${1^2\cdot 3}$ dan ${5}$ termuat di ${N}$ . Jadi ${|N|>20+24=44}$ yang tidak mungkin karena ${|N|=30}$ .

Sekarang misalkan ${2\mid |N|}$ , maka dengan argumen yang serupa semua unsur dengan struktur putaran ${1\cdot 2^2}$ semuanya terkandung di ${N}$ . Jadi ${|N|>15}$ . Ini berakibat ${|N|=30}$ Tapi sudah kita tunjukkan di atas hal tersebut tidak mungkin. $\Box$

Rendered by QuickLaTeX.com

June 8, 2016June 8, 2016

Mewarnai Kalung dengan Cauchy-Frobenius

1. Formula Cauchy-Frobenius

Misalkan grup ${G}$ beraksi pada himpunan ${\Omega}$ . Kita hendak menghitung banyaknya orbit dari aksi ini. Untuk setiap ${g\in G}$ definisikan ${\text{Fix}(g):=\{\alpha \in \Omega \mid \alpha\cdot g=\alpha\}}$ dan untuk setiap ${\alpha \in \Omega}$ definisikan ${G_\alpha:=\{g\in G\mid \alpha\cdot g=\alpha\}}$ .

Untuk menghitung banyaknya orbit dari aksi, pertama kita tinjau himpunan

$\displaystyle \mathcal{S}:=\{(\alpha,g)\mid \alpha\cdot g=\alpha\}$

Kita akan menghitung banyaknya kardinalitas dari ${\mathcal{S}}$ . Misalkan unsur-unsur di ${\Omega}$ adalah ${\alpha_1,\ldots, \alpha_s}$ dan unsur-unsur di ${G}$ adalah ${g_1,\ldots, g_t}$ . Definisikan matriks ${M=(m_{ij})}$ dengan

$\displaystyle m_{ij}:=\begin{cases}1& \text{ jika } (\alpha_i,g_j)\in \mathcal{S}\\ 0&\text{ jika } (\alpha_i,g_j)\not\in \mathcal{S} \end{cases}$

Banyaknya angka 1 pada baris ke- ${i}$ adalah banyaknya ${g\in G}$ sehingga ${\alpha_i\cdot g=\alpha_i}$ , yakni ${|G_{\alpha_i}|}$ . Sehingga banyaknya total angka 1 yang terdapat pada matriks ${M}$ adalah

$\displaystyle \sum_{i=1}^s |G_{\alpha_i}|=\sum_{\alpha \in \Omega} |G_\alpha|.$

Di lain pihak kita bisa menghitung banyaknya angka 1 pada ${M}$ kolom-demi kolom. Banyaknya angka 1 pada kolom ke- ${j}$ sama dengan banyaknya ${i=1,\ldots,s}$ sehingga ${(\alpha_i,g_j)\in S}$ , yakni sebesar ${|\text{Fix}(g_i)|}$ . Dengan demikian banyaknya total angka 1 pada matriks ${M}$ adalah

$\displaystyle \sum_{j=1}^t |\text{Fix}(g_j)|=\sum_{g\in G} |\text{Fix}(g)|.$

Karena kedua hal di atas menghitung dua objek yang sama, maka

$\displaystyle \sum_{g\in G} |\text{Fix}(g)|=\sum_{\alpha \in \Omega} |G_\alpha|$

Bagi kedua ruas dengan ${|G|}$ kita peroleh

$\begin{align*} \frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|&=\sum_{\alpha \in \Omega} \frac{|G_\alpha|}{|G|}\\ &=\sum_{\alpha \in \Omega} \frac{1}{|O_\alpha|} \end{align*}$

Misalkan ${O_1,O_2,\ldots, O_k}$ adalah orbit-orbit yang mempartisi ${\Omega}$ . Maka

$\begin{align*} \sum_{\alpha \in \Omega} \frac{1}{|O_\alpha|}&=\sum_{i=1}^k \sum_{\alpha \in O_i} \frac{1}{|O_\alpha|}\\ &= \sum_{i=1}^k \frac{|O_i|}{|O_i|}\\ &=k\\ &= \text{banyaknya orbit} \end{align*}$

Dengan demikian

$\displaystyle \text{banyaknya orbit }=\frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|.$

Berikut contoh aplikasi sederhana dari Teorema Cauchy-Frobenius yang dikenal juga sebagai Teorema Frobenius yang menurut beberapa matematikawan merupakan pengatributan yang keliru kepada Burnside.

Example 1 Misalkan kita ingin membuat kalung manik-manik yang terdiri dari 6 butiran manik-manik. Jenis manik-manik yang tersedia ada 2 warna, berwarna hitam dan putih. Kita ingin menghitung banyaknya cara membuat manik-manik seperti itu. Perhatikan bahwa dua kalung manik-manik kita anggap sama jika kita bisa merotasi kalung yang satu untuk mendapatkan konfigurasi manik-manik pada kalung kedua.

Kita tinjau himpunan semua warna kalung sebagai himpunan

$\displaystyle C=\{(c_1,c_2,\ldots, c_6)\mid c_i=1 \text{ atau } c_i=0\}$

dengan ${c_i=1}$ jika manik-manik ${i}$ berwarna hitam dan ${c_i=0}$ jika manik-manik ${i}$ berwarna putih. Himpunan semua rotasi pada 6 buah manik-manik bisa kita nyatakan sebagai grup ${G=\langle \tau \rangle}$ dengan ${\tau}$ adalah putaran ${(1\,2\,3\,4\,5\,6)}$ . Perhatikan bahwa ${G=\{\text{id},\tau,\tau^2\tau^3,\tau^4,\tau^5\}}$ dengan ${\tau}$ bisa kita anggap juga sebagai rotasi sebesar ${60^\circ}$ searah jarum jam.

Disini kita melihat bahwa ${G}$ beraksi pada ${C}$ dengan rotasi. Misalkan diberikan kalung dengan konfigurasi ${c=(1,1,0,1,0,0)}$ maka semua hasil rotasi dari ${c}$ dianggap sebagai konfigurasi kalung yang sama atau dengan kata lain mereka semua tinggal dalam satu orbit. Pewarnaan kalung yang berbeda menyatakan orbit yang lain. Dengan demikian yang kita cari adalah banyaknya orbit dari aksi ${\langle \tau\rangle}$ terhadap ${C}$ .

Kita akan menghitung banyaknya orbit ini dengan menggunakan Teorema Cauchy-Frobenius dengan cara menghitung ${|\text{Fix}(\tau^i)|}$ untuk ${i=0,1,2,3,4,5}$ .

Pertama kita akan menghitung banyaknya unsur di ${\text{Fix (id)}}$ . Oleh pemetaan ${\text{id}}$ setiap ${c\in C}$ dipetakan ke dirinya sendiri. Semua konfigurasi kalung yang mungkin merupakan anggota ${\text{Fix(id)}}$ . Dengan ${|\text{Fix (id)}|=|C|=2^6}$ .
Oleh ${\tau}$ konfigurasi ${(c_1,c_2,c_3,c_4,c_5,c_6)}$ dibawa ke konfigurasi ${(c_6,c_1,c_2,c_3,c_4,c_5)}$ . Dengan demikian ${(c_1,\ldots,c_6)\in \text{Fix}(\tau)}$ jika ${c_6=c_1}$ kemudian ${c_1=c_2}$ dan seterusnya sehingga berturut-turut kita memiliki ${c_6=c_1=c_2=c_3=c_4=c_5}$ . Dengan demikian pewarnaan kalung bergantung pada salah satu manik-manik saja, misal ${c_1}$ . Banyaknya cara untuk mewarnai ${c_1}$ dengan dua warna adalah ${2^1}$ cara. Jadi ${|\text{Fix}(\tau)|=2^1}$ . Dengan cara yang serupa, karena ${\tau^5=\tau^{-1}}$ adalah rotasi 60 derajat berlawanan arah kita dapatkan pula ${|\text{Fix}(\tau^5)|=2^1}$ .
Jika ${c\in \text{Fix}(\tau)}$ maka konfigurasi ${(c_1,c_2,c_3,c_4,c_5,c_6)}$ haruslah sama dengan ${(c_5,c_6,c_1,c_2,c_3,c_4)}$ dengan demikian ${c_1=c_5=c_3}$ dan ${c_2=c_4=c_6}$ . Jadi pewarnaan kalung ditentukan oleh warna ${c_1}$ dan ${c_2}$ . Ada ${2^2}$ cara untuk mewarnai ${c_1}$ dan ${c_2}$ . Dengan demikian ${|\text{Fix}(\tau^2)|=2^2}$ . Dengan cara yang sama ${|\text{Fix}(\tau^4)|=|\text{Fix}(\tau^{-2})|=2^2}$ .
Oleh ${\tau^3}$ , ${(c_1,c_2,c_3,c_4,c_5,c_6)}$ di petakan menjadi ${(c_4,c_5,c_6,c_1,c_2,c_3)}$ . Jadi haruslah ${c_1=c_4,c_2=c_5}$ dan ${c_3=c_6}$ . Pewarnaan kalung ditentukan oleh pewarnaan ${c_1,c_2,c_3}$ , Jadi ${|\text{Fix}(\tau^3)|=2^3}$ .

Sekarang menurut Teorema Cauchy-Frobenius banyaknya pewarnaan kalung adalah

$\frac{1}{6}\left(2^6+2^1+2^1+2^2+2^2+2^3\right)=14.$

Jadi ada 14 konfigurasi kalung yang mungkin.

June 7, 2016June 7, 2016

Teori Galois 2 – Perluasan Sebagai Ruang Vektor

4. Struktur Ruang Vektor dari Perluasan

Jika ${\alpha}$ aljabarik atas ${K}$ maka menurut Teorema (5) kita miliki

$\displaystyle K(\alpha)=\left\{k_0+k_1\alpha+\cdots k_{n-1}\alpha^{n-1}\mid k_i\in K\right\}.$

Himpunan ${K(\alpha)}$ bisa kita tinjau sebagai himpunan semua ${K}$ -kombinasi linear dari ${\{1,\alpha,\ldots, \alpha^{n-1}\}}$ . Hal ini mendorong kita untuk melihat struktur ruang vektor pada perluasan lapangan.

Lebih umum misalkan ${L/K}$ suatu perluasan. Karena ${L}$ lapangan jelas ${(L,+)}$ merupakan grup komutatif. Definisikan perkalian skalar ${k\cdot u=ku}$ untuk setiap ${k\in K}$ dan ${u\in L}$ . Kami serahkan kepada pembaca bahwa dengan pendefinisian ini penjumlahan dan perkalian skalar di ${L}$ memenuhi aksioma-aksioma ruang vektor. Lebih umum kita mempunyai proposisi berikut yang buktinya diserahkan kepada pembaca.

Proposition 6 Misalkan ${R}$ daerah integral yang memuat lapangan ${K}$ . Dengan penjumlahan dan perkalian skalar seperti di atas ${R}$ merupakan ruang vektor atas ${K}$ .

Exercise 7 Bagaiman jika ${R}$ pada proposisi di atas hanya merupakan gelanggang ? Apakah ${R}$ masih tetap merupakan ruang vektor atas ${K}$ ?

Proposition 7 Misalkan ${\alpha}$ aljabarik atas ${K}$ dengan derajat ${m_\alpha}$ adalah ${n}$ . Maka ${\{1,\alpha,\ldots, \alpha^{n-1}\}}$ adalah basis bagi ruang vektor ${K(\alpha)}$ atas ${K}$ .

Proof: Menurut deskripsi ${K(\alpha)}$ pada Teorema 5 jelas bahwa ${\{1,\alpha,\ldots, \alpha^{n-1}\}}$ membangun ${K}$ . Sekarang kita tunjukkan bahwa ia bebas linear. Misalkan ${t_0+t_1\alpha+\cdots +t_{n-1}\alpha^{n-1}=0}$ . Jika ${t_0,\ldots,t_{n-1}}$ tidak semuanya nol, maka polinom ${f(x)=t_0+t_1x+\cdots+t_{-1}x^{n-1}\in K[x]}$ merupakan polinom berderajat ${\leq n-1}$ yang memenuhi ${f(\alpha)=0}$ . Ini bertentangan dengan keminimalan ${m_\alpha}$ . Dengan demikian ${t_1=t_2=\cdots=t_{n-1}=0}$ dan ${\{1,\alpha,\ldots, \alpha^{n-1}\}}$ bebas linear. $\Box$

Definition 8 Misalkan ${L}$ adalah gelanggang yang memuat lapangan ${K}$ . Dimensi dari ${L}$ sebagai ruang vektor atas ${K}$ kita nyatakan sebagai ${[L:K]}$ .

Berdasarkan definisi ini dan Proposisi 7 kita peroleh

Proposition 9 Jika ${\alpha}$ aljabarik atas ${K}$ maka ${[K(\alpha):K]=\deg m_\alpha}$ dengan ${\deg m_\alpha}$ adalah derajat dari minimal polinomial dari ${\alpha}$ .

Definition 10 Misalkan ${L/K}$ adalah suatu perluasan. Jika ${[L:K]}$ berhingga kita katakan ${L/K}$ adalah perluasan hingga dan ketika ${[L:K]=\infty}$ kita katakan ${L/K}$ perluasan takhingga.

Example 3 Kita akan tunjukkan bahwa ${\mathbb{R}/\mathbb{Q}}$ merupakan perluasan takhingga. Misalkan ${p_k}$ adalah bilangan prima ke- ${k}$ . Kita akan tunjukkan bahwa di ${\mathbb{R}}$ sebagai ruang vektor atas ${\mathbb{Q}}$ himpunan ${\{\log p_1,\log p_2,\ldots, \log p_k,\ldots\}}$ merupakan himpunan yang bebas linier. Dengan menunjukkan hal ini kita mendapatkan takberhingga banyaknya unsur yang bebas linear di ${\mathbb{Q}}$ . Dari sini kita simpulkan ${[\mathbb{R}:\mathbb{Q}]=\infty}$ . Jika ${q_1,\ldots, q_n\in \mathbb{Q}}$ memenuhi ${q_1\log p_1+\cdots +q_n\log p_n=0}$ maka dengan mengambil exponential dari masing-masing ruas kita dapatkan ${p_1^{q_1}p_2^{q_2}\cdots p_n^{q_n}=1}$ . Ini mengakibatkan ${q_1=q_2=\cdots =q_n=0}$ dan kita simpulkan ${\{\log p_1,\log p_2,\ldots, \log p_k,\ldots\}}$ bebas linear.

Theorem 11 Misalkan ${K\subset L\subset M}$ adalah suatu perluasan. Maka berlaku ${[M:K]=[M:L][L:K]}$ .

Proof: Perhatikan bahwa ${L/K}$ adalah subruang dari ${M/L}$ . Jika ${[L:K]=\infty}$ maka demikian pula ${[M:K]}$ . Unsur-unsur di ${M}$ yang bebas linear di ${M/L}$ tentu saja bebas linear di ${M/K}$ . Dengan demikian jika ${[L:K]}$ takhingga, demikian pula dengan ${[M:K]}$ .

Berikutnya bisa kita asumsikan bahwa ${[M:L]=m}$ dan ${[L:K]=n}$ . Misalkan ${\{x_1,\ldots, x_m\}}$ adalah basis bagi ${M/L}$ dan ${\{y_1,\ldots, y_n\}}$ basis bagi ${L/K}$ . Jika persamaan yang ingin kita buktikan benar, kita berharap bahwa ${[M:K]=mn}$ . Dari mana kita bisa mendapatkan ${mn}$ unsur basis bagi ${M}$ ? Dalam kotak penyimpanan kita kita mempunyai ${m}$ unsur basis bagi ${M/L}$ dan ${n}$ unsur basis bagi ${L/K}$ ? Tentunya alamiah kita meninjau himpunan ${S=\{x_iy_j \mid i=1\ldots m, j=1,\ldots, n\}}$ dan berharap ${S}$ merupakan basis bagi ${M/K}$ .

Ambil ${m\in M}$ . Karena ${\{x_1,\ldots, x_m\}}$ basis bagi ${M/L}$ kita bisa tuliskan ${m=\sum_{i=1}^m \ell_i x_i}$ untuk suatu ${\ell_i\in L}$ . Sekarang masing masing ${\ell_i}$ bisa kita tuliskan sebagai ${\ell_i=\sum_{j=1}^n k_{ij}y_j}$ untuk suatu ${k_{ij}\in K}$ . Dengan demikian ${m=\sum_{i=1}^m\sum_{j=1}^n k_{ij} x_iy_j}$ merupakan kombinasi linier unsur-unsur di ${S}$ atau dengan kata lain ${\text{span } S=M}$ .

Jika ${k_{i,j}\in K}$ sehingga ${0=\sum_{i=1}^m\sum_{i=1}^n k_{i,j}x_iy_i=0=\sum_{i=1}^m\left(\sum_{j=1}^n k_{i,j}y_j\right)x_i}$ maka dengan kebebas linearan ${\{x_1,\ldots, x_m\}}$ kita peroleh ${\sum_{j=1}^n k_{i,j}y_j=0}$ untuk setiap ${i=1,\ldots,m}$ . Kemudian dengan kebebas linearan ${\{y_1,\ldots,y_n\}}$ didapat ${k_{i,j}=0}$ untuk setiap ${i}$ dan ${j}$ . Jadi ${S}$ bebas linear dan merupakan basis dari ${M/K}$ . $\Box$

Hasil berikutnya merupakan hasil yang cukup penting dimana kita bisa mengenali kapan suatu unsur aljabarik lewat dimensi lapangan perluasannya.

Proposition 12 Unsur ${\alpha}$ aljabarik atas ${K}$ jika dan hanya jika ${[K(\alpha):K]<\infty}$

Proof: Untuk arah ke kanan jelas dari Proposisi 7. Untuk sebaliknya misalkan ${[K(\alpha):K]=n <\infty}$ . di ${K(\alpha)}$ . Karena dimensi menyatakan banyaknya unsur maksimum yang bisa bebas linier maka haruslah ke ${n+1}$ buah unsur ${1,\alpha,\ldots, \alpha^{n+1}}$ bergantung linear. Jadi terdapat ${k_0,\ldots, k_n}$ yang tidak semuanya nol sehingga ${\sum_{i=0}^n k_i\alpha^i=0}$ . Jadi ${\alpha}$ aljabarik karena merupakan akar dari polinom ${f(x)=\sum_{i=0}^n k_ix^n}$ . $\Box$

Misalkan ${\alpha}$ aljabarik atas ${K}$ dan misalkan ${f(x)\in K[x]}$ memenuhi ${f(\alpha)=0}$ . Perhatikan bahwa bukan perkara yang mudah untuk melihat bahwa jika ${\beta\in K(\alpha)}$ maka ${\beta}$ juga aljabarik. Jika kita diminta untuk mencari suatu polinom eksplisit ${g(x)\in K[x]}$ yang memenuhi ${g(\beta)=0}$ , kita akan kesulitan karena kita hanya mempunyai informasi ${f(x)}$ . Artinya kita harus menyatakan ${g(x)}$ kita dalam ${f(x)}$ .

Akan tetapi dengan menggunakan Teorema 12, menunjukkan ${\beta}$ juga aljabarik atas ${K}$ adalah hal yang mudah, kita cukup menunjukkan bahwa ${[K(\beta):K]<\infty}$ . Untuk melihat hal tersebut tinjau ${\{1,\beta,\ldots, \beta^{n}\}}$ yang merupakan ${n+1}$ unsur di ruang vektor ${K(\alpha)}$ berdimensi ${n}$ . Akibatnya ${\{1,\beta,\ldots, \beta^{n}\}}$ bergantung linear dan terdapat ${k_0,\ldots, k_n\in K}$ sehingga ${\sum_{i=0}^n k_i\beta^i=0}$ . Kita akan melihat hasil yang lebih umum dari ini pada subbab berikutnya.

Proposition 13 ${[K(\alpha,\beta):K]\leq [K(\alpha):K][K(\beta):K]}$

Proof: Jika ${[K(\alpha):K]=\infty}$ atau ${[K(\beta):K]}$ merupakan perluasan takhingga maka jelas bahwa ${[K(\alpha,\beta):K]}$ mengingat ${K(\alpha)\cup K(\beta)\subseteq K(\alpha,\beta)}$ .

Untuk selanjutnya kita asumsikan ${[K(\alpha):K],[K(\beta):K]<\infty}$ . Kita akan tunjukkan bahwa ${[K(\beta)(\alpha):K(\alpha)]\leq [K(\alpha):K]}$ . Misalkan ${m_\alpha(x)}$ adalah polinom minimal dari ${\alpha}$ atas ${K}$ . Karena ${K\subset K(\beta)}$ maka polinom ${m_\alpha(x)}$ bisa kita tinjau sebagai polinom monik di ${K(\beta)[x]}$ yang mempunyai akar ${\alpha}$ . Di lain pihak ${[K(\beta)(\alpha):K]}$ adalah derajat terkecil dari polinom di ${K(\beta)[x]}$ yang memiliki ${\alpha}$ sebagai akarnya. Dari keminimalan ini kita peroleh ${[K(\beta)(\alpha):K(\beta)]\leq \deg m_\alpha(x)=[K(\alpha):K]}$ . Akibatnya

$\displaystyle [K(\alpha,\beta):K]=[K(\beta)(\alpha)):K(\beta)][K(\beta):K]\leq [K(\alpha):K][K(\beta):K].$

$\Box$

Hasil yang lebih umum ini juga berlaku dan kita serahkan kepada pembaca.

Exercise 8 Misalkan ${S,T}$ adalah dua lapangan diantara lapangan ${K\subset L}$ . Kita akan membuktikan bahwa

$\displaystyle [K(S\cup T):K]\leq [S:K][T:K]$

Tunjukkan bahwa jika salah satu diantara ${[S:K]}$ atau ${[T:K]}$ merupakan perluasan takhingga maka demikian juga dengan ${[K(S\cup T):K]}$ .
Definisikan ${R=\left\{\sum_{i=1}^n a_ib_i\,\bigg|\, n\in \mathbb{N}, a_i\in S, b_i\in T\right\}}$ . Tunjukkan bahwa ${R}$ adalah subring dari ${L}$ yang memuat ${S}$ dan ${T}$ .
Tunjukkan bahwa ${R}$ ruang vektor atas ${K}$ dan ${[R:K(T)]\leq [K(S):K]}$ .
Buktikan bahwa ${R}$ lapangan dan ${R=K(S\cup T)}$ , kemudian buktikan ketaksamaan yang diminta.

Berikutnya kita akan melihat bagaimana analisis dimensi memberikan suatu teknik yang berguna untuk melihat kapan dua perluasan merupakan lapangan yang sama.

Example 4 Pada Latihan 5 kita diminta untuk memeriksa apakah ada diantara ${\mathbb{Q}(\sqrt{2}+\sqrt{3}), \mathbb{Q}(\sqrt{6}), \mathbb{Q}(\sqrt{2},\sqrt{3})}$ yang merupakan himpunan yang sama. Dengan analisis dimensi kita akan menunjukkan bahwa ${\mathbb{Q}(\sqrt{2}+\sqrt{3})=\mathbb{Q}(\sqrt{2},\sqrt{3})}$ . Perhatikan jelas bahwa ${\mathbb{Q}(\sqrt{2}+\sqrt{3}) \subseteq \mathbb{Q}(\sqrt{2},\sqrt{3})}$ . Dengan cukup kreatifitas sebetulnya kita bisa menunjukkan bahwa ${\sqrt{2},\sqrt{3}\in \mathbb{Q}(\sqrt{2}+\sqrt{3})}$ sehingga kedua perluasan merupakan himpunan yang sama.

Exercise 9 Fakta-fakta berikut akan kita pergunakan untuk menyelesaikan soal di Contoh 4 akan tetapi sangat baik untuk dijadikan latihan.

Buktikan bahwa

${x^2-2}$ dan ${x^2-3}$ berturut-turut adalah polinom minimal dari ${\sqrt{2}}$ dan ${\sqrt{3}}$ di ${\mathbb{Q}[x]}$ .
${\sqrt{3}\not \in \mathbb{Q}(\sqrt{2})}$ . Tunjukkan bahwa ini berakibat ${x^2-3}$ adalah polinom minimal dari ${\sqrt{3}}$ di ${\mathbb{Q}(\sqrt{2})[x]}$
Tunjukkan bahwa polinom minimal dari ${\sqrt{2}+\sqrt{3}}$ atas ${\mathbb{Q}}$ berderajat ${4}$ .

Dari Latihan 9 di atas kita peroleh

$\begin{align*} [\mathbb{Q}(\sqrt{2},\sqrt{3}):\mathbb{Q}]&=[\mathbb{Q}(\sqrt{2})(\sqrt{3}):\mathbb{Q}(\sqrt{2})][\mathbb{Q}(\sqrt{2}):\mathbb{Q}]\\ &= \deg (x^2-3)\cdot \deg (x^2-2)\\ &=4\\ &=\deg (\text{ polinom minimal dari } \sqrt{2}+\sqrt{3})\\ &=[\mathbb{Q}(\sqrt{2}+\sqrt{3}):\mathbb{Q}] \end{align*}$

Berarti ${\mathbb{Q}(\sqrt{2}+\sqrt{3})\subseteq \mathbb{Q}(\sqrt{2},\sqrt{3})}$ keduanya merupakan ruang vektor atas ${\mathbb{Q}}$ yang berdimensi 4. Karena juga ruang vektor yang satu termuat di yang lain, maka haruslah keduanya merupakan ruang vektor yang sama.