Posted on

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 {\displaystyle \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 {\displaystyle \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.

Posted on

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

Posted on

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

Posted on

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

  1. 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}.
  2. 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}.
  3. 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}.
  4. 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.

Posted on

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]

  1. Tunjukkan bahwa jika salah satu diantara {[S:K]} atau {[T:K]} merupakan perluasan takhingga maka demikian juga dengan {[K(S\cup T):K]}.
  2. 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}.
  3. Tunjukkan bahwa {R} ruang vektor atas {K} dan {[R:K(T)]\leq [K(S):K]}.
  4. 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

  1. {x^2-2} dan {x^2-3} berturut-turut adalah polinom minimal dari {\sqrt{2}} dan {\sqrt{3}} di {\mathbb{Q}[x]}.
  2. {\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]}
  3. 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.

Posted on

Teori Galois 1 – Lapangan Perluasan

1. Akar Polinom

Misalkan {f(x)} merupakan polinom dengan koefisien real. Kita mengetahui bahwa tidak setiap polinom dengan koefisien real mempunyai akar real. Sebagai contoh {f(x)=x^2+1} tidak mempunyai akar real karena untuk setiap {r\in \mathbb{R}} berlaku {f(r)=r^2+1\geq 1>0}. Dilain pihak kita mengetahui bahwa {f(x)=x^2+1} memiliki akar kompleks {\pm i}. Faktanya menurut Teorema Dasar Aljabar setiap polinom dengan koefisien real berderajat {n} memiliki {n} buah akar kompleks (dihitung beserta multiplistitasnya).

Dengan kata lain kita membuat persamaan {x^2+1=0} menjadi memiliki solusi dengan mengizinkan {x} merupakan unsur dari lapangan yang lebih luas {\mathbb{C}}. Perhatikan bahwa jika {K} adalah lapangan lain yang mengandung {\mathbb{R}} dan memuat {\pm i} (akar dari {x^2+1}), maka {K} memuat semua ekspresi {a+ib} untuk setiap {a,b\in \mathbb{R}}. Ini berarti bahwa {K} juga memuat {\mathbb{C}}. Di sini kita bisa melihat bahwa {\mathbb{C}} adalah lapangan terkecil yang memuat {\mathbb{R}} dan sekaligus membuat persamaan {x^2+1=0} mempunyai solusi.

2. Lapangan Perluasan

Misalkan {K} suatu lapangan. Jika {L} merupakan lapangan dan {L\supset K}, kita katakan bahwa {L} merupakan lapangan perluasan dari {K}. Untuk selanjutnya ketika konteksnya jelas kita akan mengatakan bahwa {L} adalah perluasan dari {K} dan secara singkat bisa kita ungkapkan dengan mengatakan {L/K} adalah suatu perluasan. Perhatikan bahwa {\mathbb{C}} merupakan perluasan dari {\mathbb{R}} yang mengandung {\pm i} (akar-akar dari {x^2+1}). Jika {F/\mathbb{R}} adalah lapangan perluasan yang juga memuat {\pm i}, maka dari sifat lapangan {F} memuat semua unsur berbentuk {a+bi} dengan {a,b\in \mathbb{R}}. Dengan kata lain {F} memuat {\mathbb{C}}. Dengan demikian kita bisa melihat {\mathbb{C}} sebagai perluasan terkecil dari {\mathbb{R}} yang memuat {\pm i}.

Definition 1 Misalkan {L/K} suatu perluasan dan {S\subseteq L}. Himpunan {K(S)} didefinisikan sebagai perluasan terkecil dari {K} yang memuat {S}.

Tentunya kita bertanya-tanya apakah {K(S)} selalu ada? Perhatikan koleksi {\mathcal{F}} dari perluasan {F/K} yang memuat {S}, yakni {\mathcal{F}=\{F : F/K \text{ perluasan dan } F\supseteq S\} }. Koleksi ini tidak hampa karena {L\in \mathcal{F}}. Tinjau himpunan {\bigcap _{F\in \mathcal{F}} F}. Sebagai latihan pembaca disarankan untuk mengerjakan latihan berikut yang menunjukkan eksistensi dari {K(S)}.

Exercise 1 Tunjukkan bahwa {\bigcap _{F\in \mathcal{F}} F =K(S)} dengan menunjukkan bahwa {\bigcap _{F\in \mathcal{F}} F} merupakan lapangan perluasan dari {K} terkecil yang memuat {S}.

Menurut pendefinisian {K(S)}, himpunan {S} selalu diasumsikan termuat di suatu perluasan {L/K}. Akan tetapi berikutnya kita mungkin tidak akan secara eksplisit menyebutkan lapangan {L} yang memuat {S}. Kita katakan bahwa {K(S)} adalah perluasan yang diperoleh dengan menempelkan {S} ke {K}.

Exercise 2 Buktikan bahwa {K(S \cup T)=K(S)(T).}

Untuk memperjelas soal latihan di atas, notasi {K(S\cup T)} menyatakan perluasan dari {K} dengan menempelkan {S\cup T} sedangkan {K(S)(T)} berarti kita pertam menempelkan {S} pada {K} untuk mendapatkan {K(S)} kemudian kita lanjutkan dengan menempelkan {T} ke {K(S)} untuk mendapatkan {K(S)(T)}.

Berikutnya kita ingin mendapatkan pemahaman yang lebih dalam mengenai {K(S)} kita ingin mengenali bagaimana bentuk unsur-unsur di {K(S)}. Pertama kita definisikan himpunan {W_S} sebagai himpunan yang unsur-unsurnya adalah himpunan semua kata berhingga yang huruf-hurufnya berasal dari {S}. Dengan definisi kita anggap {1} sebagai perkalian dari nol buah unsur di {S} sehingga dengan kesepakatan ini {1} merupakan unsur di {W_S}. Sebagai contoh jika {S=\{\alpha, \beta\}} maka {\alpha\alpha \beta \alpha=\alpha^2\beta\alpha} dan {\beta\alpha \beta\beta \beta=\beta\alpha\beta^3} adalah beberapa contoh unsur-unsur di {W_S}. Kemudian definisikan

\displaystyle R_S=\left\{\sum_{i=1}^n k_iw_i \,\bigg |\, n \text{ suatu bilangan asli }, k_i\in K, w_i\in W_S\right\}.

Berdasarkan definisi dari {R_S}, jelas {R_S} tertutup terhadap operasi penjumlahan. Untuk operasi perkalian pertama perhatikan bahwa jika {u,v\in W_S} maka {uv} juga merupakan suatu kata di {W_S}. Dengan sifat distributi bisa kita tunjukkan bahwa untuk setiap {\sum_{i=1}^m s_iu_i, \sum_{i=1}^n t_iv_i\in R_S} kita peroleh perkalian keduanya juga di {R_S}. Dengan kata lain {R_S} tertutup terhadap operasi perkalian. Ini menunjukkan bahwa {R_S} suatu subring dari {L}. Karena {L} lapangan maka {R_S} suatu daerah integral.

Sebelum kita lanjutkan kita akan mengingatkan pembaca akan fakta berikut.

Theorem 2 Misalkan {D} suatu daerah integral. Maka

\displaystyle T(D):=\{a/b \,|\, a,b\in D, b\neq 0\}

adalah suatu lapangan dan merupakan lapangan terkecil yang memuat {D}. Lapangan {T(D)} disebut sebagai field of fraction dari {D}.

{T(D)} merupakan himpunan kelas ekivalen dengan {\frac{a}{b}=\frac{c}{d}} jika dan hanya jika {ad=bc}. Penjumlahan dan perkalian di {T(D)} didefinisikan melalui

    \begin{align*} \frac{a}{b}+\frac{c}{d}&:=\frac{ad+bc}{bd}\\ \frac{a}{b}\cdot\frac{c}{d}&:=\frac{ac}{bd}. \end{align*}

Exercise 3 Tunjukkan bahwa unsur di {T(R_S)} berbentuk

\displaystyle \frac{\sum_{i=1}^m s_iu_i}{\sum_{i=1}^n t_iv_i}

dengan {m,n\in \mathbb{N}, s_i,t_i\in K} dan {u_i,v_i\in W_S} ({t_i} tidak semuanya nol).

Dari daerah integral {R_S} kita memperoleh lapangan {T(R_S)}. Kita ingin membandingkan antara lapangan {T(R_S)} dan {K(S)}. Perhatikan karena {1\in W_s} maka {k\cdot 1\in R_S} untuk setiap {k\in K}. Ini menunjukkan bahwa juga {T(R_S)/K} merupakan lapangan perluasan. Dari definisi {R_S} jelas bahwa {S} termuat di {T(R_S)}. Karena keminimalan {K(S)} maka kita simpulkan {K(S)\subseteq T(R_S)}. Sebaliknya dari definisi {W_S} jelas bahwa {W_S\subseteq K(S)}. Akibatnya {R_S\subseteq K(S)}. Berdasarkan keminimalan {T(R_S)} maka {T(R_S)\subseteq K(S)}.

Dari apa yang kita lakukan di atas kita simpulkan sebagai berikut.

Theorem 3

    \[K(S)=T(R_S)=\left\{\frac{\sum_{i=1}^m s_iu_i}{\sum_{i=1}^n t_iv_i} \,\bigg |\, \sum_{i=1}^m s_iu_i, \sum_{i=1}^n t_iv_i \in R_s \exists i \ni t_i\neq 0\right\}.\]

Ketika {S} suatu singleton {S=\{\alpha\}}, {K(S)} kita tuliskan sebagai {K(\alpha)} dan kita sebut sebagai perluasan dari {K} yang diperoleh dengan menempelkan {\alpha}. Dalam kasus ini {W_S=W_\alpha =\{1,\alpha, \alpha^2,\ldots \}}. Kemudian berturut-turut

\displaystyle R_\alpha =\{k_0+k_1\alpha+k_2\alpha^2+\cdots +k_n\alpha^n\,|\, n\in \mathbb{N}, k_i\in K\}

dan

    \begin{align*} K(\alpha)&=\left\{\frac{k_o+k_1\alpha+\cdots +k_n\alpha^n}{t_o+t_1\alpha+\ldots+t_m\alpha^m} \,\bigg|\, k_i,t_i\in K, \text{ penyebut taknol }\right\} \\ &=\left\{\frac{f(\alpha)}{g(\alpha)}\,\bigg |\, f(x),g(x)\in K[x] \text{ dengan } f(x)\neq 0\right\} . \end{align*}

Example 1 Unsur di {\mathbb{Q}(\pi)} berbentuk pecahan {\displaystyle\frac{f(\pi)}{g(\pi)}} dengan {f(x),g(x)} polinom dengan koefisen rasional dan {g(x)\neq 0}.

Example 2 Tinjau {\mathbb{Q}(\alpha)} dengan {\alpha=\sqrt{2}}. Perhatikan bahwa {\alpha^2=2} dan akibatnya {\alpha^{2k}=2^k\in \mathbb{Q}}, yakni {\alpha^i\in \mathbb{Q}} untuk {i} genap. Dengan menggunakan informasi ini untuk {k_i\in\mathbb{Q}} kita peroleh

\displaystyle k_o+k_1\alpha+\cdots +k_n\alpha^n=\left(\sum_{i \text{ genap }} k_i\alpha^i\right) +\left(\sum_{i \text{ ganjil}} k_i\alpha^{i-1}\right) \alpha=a+b\alpha

untuk suatu {a,b\in \mathbb{Q}}. Dengan demikian

\displaystyle \mathbb{Q}(\alpha)=\left\{\frac{a+b\alpha}{c+d\alpha}\,\bigg |\, a,b,c,d\in \mathbb{Q} \text{ dengan } c,d \text{ tidak keduanya nol}\right\}.

Kita bisa menyederhanakan {\mathbb{Q}(\alpha)} lebih lanjut. Perhatikan bahwa

\displaystyle \frac{a+b\alpha}{c+d\alpha}=\frac{a+b\alpha}{c+d\alpha}\cdot \frac{c-d\alpha}{c-d\alpha}=\frac{(ac+dbd)+(ad+bc)\alpha}{c^2-2d^2}.

Karena {c^2-d^2\in \mathbb{Q}} maka {\frac{(ac+dbd)+(ad+bc)\alpha}{c^2-2d^2}} dapat dituliskan ke dalam bentuk {p+q\alpha} dengan {p,q} rasional. Jadi kita dapatkan deskripsi paling sederhana dari {\mathbb{Q}(\alpha)} yakni

\displaystyle \mathbb{Q}(\sqrt{2})=\{p+q\sqrt{2}\mid p,q\in \mathbb{Q}\}.

Exercise 4 Nyatkan bentuk paling sederhana dari unsur-unsur di {\mathbb{Q}(\beta)} dengan {\beta=\sqrt{2-\sqrt{3}}}.

Exercise 5 Urutkan ketiga perluasan {\mathbb{Q}(\sqrt{2}+\sqrt{3}), \mathbb{Q}(\sqrt{2},\sqrt{3})} dan {\mathbb{Q}(\sqrt{6})} dari yang terkecil sampai yang terbesar. Apakah diantara ketiganya ada yang merupakan himpunan yang sama?

3. Unsur Aljabarik

Definition 4 Misalkan {L/K} suatu perluasan. Unsur {\alpha\in L} dikatakan aljabarik atas {K} jika terdapat polinom {f(x)\in K[x]} sehingga {f(\alpha)=0}. Unsur yang tidak aljabarik dikatakan transenden.

Unsur-unsur di {K} tentunya aljabarik atas {K} karena untuk setiap {\alpha\in K} polinom {f(x)=x-k\in K[x]} memenuhi {f(\alpha)=0}. Unsur-unsur berikut merupakan beberapa contoh unsur aljabarik atas {\mathbb{Q}}: {\sqrt{2}, \sqrt{2-\sqrt{3}}, \sqrt{2}+\sqrt{3}}. Telah dibuktikan oleh Hermite (1834) bahwa {\pi} dan {e} keduanya transenden atas {\mathbb{Q}}. Akan tetapi masih merupakan masalah terbukan tentang apakah {\pi+e} merupakan unsur aljabarik atau transenden atas {\mathbb{Q}}.

Dalam subbab ini kita akan menunjukkan, seperti halnya yang kita lihat di contoh pada {\mathbb{Q}(\sqrt{2})}, bahwa ketika {\alpha } aljabarik atas {K} maka {K(\alpha)} mempunyai deskripsi sederhana. Untuk menunjukkan hal tersebut kita memerlukan beberapa persiapan yang kita jadikan sebagai soal latihan.

Exercise 6 Misalkan {L/K} suatu perluasan dan {\alpha\in L} aljabarik atas {K}.

  1. Tunjukkan bahwa himpunan {I:=\{f(x)\in K[x]\mid f(\alpha)=0 \}} merupakan suatu ideal.
  2. Tunjukkan bahwa {I} ideal utama yang dibangun oleh suatu polinom monik tunggal {m_{\alpha}(x)} yang taktereduksi atas {K}. Polinom {m_\alpha(x)} kita sebut sebagai polinom minimal dari {\alpha} atas {K}.
  3. Untuk setiap {g(x)\neq 0 \in K[x]} tunjukkan bahwa terdapat {h(x),p(x)\in K[x]} sehingga {g(x)h(x)+m_\alpha(x)p(x)=1}.

Dari subbab berikutnya kita ingat bahwa

\displaystyle K(\alpha)=\{f(\alpha)/g(\alpha) \mid f(x),g(x)\in K[x] \text{ dengan } g(x)\neq 0\}.

Karena {g(x)h(x)+m_{\alpha}(x)p(x)=1} maka {g(\alpha)h(\alpha)=1}. Ini menunjukkan jika {g(x)} tidak nol maka {g(\alpha)} memiliki invers berbentuk {h(\alpha)} untuk suatu polinom {h(x)}.

Dengan demikian tipikal unsur di {K(\alpha)} berbentuk

\displaystyle \frac{f(\alpha)}{g(\alpha)}=\frac{f(\alpha)h(\alpha)}{1}.

Dengan algoritma Euclide pada {K[x]} terhadap {f(x)h(x)} dan {m_\alpha(x)}, kita bisa tuliskan {f(x)h(x)=q(x)m_\alpha(x)+r(x)} dengan {r(x)=0} atau derajat {r(x)} kurang dari derajat {m_\alpha(x)}. Substitusikan {\alpha} ke persamaan diperoleh {f(\alpha)h(\alpha)=r(\alpha)}. Hasil ini menunjukkan bahwa tipikal unsur di {K(\alpha)} berbentuk {r(\alpha)} dengan {r(x)\in K[x]} berderajat kurang dari derajat {m_\alpha(x)}. Kita simpan hasil ini dalam teorema berikut.

Theorem 5 Misalkan {\alpha} aljabarik atas {K} dan misalkan minimal polinomialnya berderajat {n}. Maka

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

Posted on

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]
Posted on

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]

 

Posted on

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

 

Posted on

Naik Tangga dengan Fibonacci

Barisan Fibonacci adalah barisan {F_n} yang didefinisikan secara rekursif melalui

\displaystyle F_1=1,F_2=1, F_{n+2}=F_n+F_{n+1}.

Barikut adalah interpretasi barisan Fibonacci dengan menggunakan model menaiki tangga.

Diberikan {n} bilangan asli. Definisikan {F_n} sebagai banyaknya cara menaiki tangga dari level 1 ke level {n} dengan setiap langkahnya boleh menaiki satu anak tangga atau dua anak tangga sekaligus. Untuk {F_1} karena dari level 1 ke level 1 tidak ada yang perlu dilakukan, didefinisikan {F_1=1}. Berikutnya {F_2=1} karena hanya ada satu cara naik dari level 1 ke level 2, yakni dengan menaiki satu anak tangga.

Sekarang, agar bisa sampai ke level {n+2} (untuk {n\geq 1}), kita bisa naik sampai ke {n} kemudian naik 2 anak tangga atau naik sampai ke level {n+1} kemudian naik satu anak tangga. Dengan demikian kita peroleh

\displaystyle F_{n+2}=F_{n}+F_{n+1},

dan menunjukkan bahwa model menaiki tangga ini sesuai dengan definisi barisan Fibonacci.

Dengan menggunakan interpretasi menaiki tangga ini kita akan membuktikan beberapa identitas yang melibatkan barisan Fibonacci yang biasanya dilakukan dengan induksi matematika yang seringkali tidak memuaskan karena kita hanya memeriksa kesahihan identitas tersebut secara mekanis tanpa memahami apa yang sebenarnya terjadi.

Theorem 1 {F_1+F_2+\cdots+F_n=F_{n+2}-1}

Proof: Tinjau permasalahan menaiki tangga dari level 1 sampai ke level n+2. Salah satu cara melakukannya adalah dengan setiap saatnya menaiki satu anak tangga. Sekarang {F_{n+2}-1} adalah banyaknya cara menaiki tangga dari level 1 ke level {n+2} sehingga pada suatu saat pernah menaiki dua tangga.

Untuk setiap {k} dengan {1\leq k\leq n} tinjau cara menaiki tangga sehingga naik dari level {k} ke level {k+2} adalah terakhir kalinya naik dua undakan. Dari level ke {k+2} sampai ke {n+2} dilakukan dengan cara yang tunggal yakni naik 1 undakan setiap saatnya. Banyaknya cara untuk menaiki tangga seperti ini adalah jelas {F(k)}. \Box

Theorem 2 {F_1+F_3+\cdots+F_{2n-1}=F_{2n}}

Proof: Tinjau permasalahan naik tangga dari level 1 ke level {2n}. Misalkan {k} adalah level ganjil terakhir yang dikunjungi. Dari level {k} sampai level ke {k+1} naik satu undakan dan dari sana sampai ke level {2n} setiap saat selalu naik dua undakan. \Box

Theorem 3 {F_nF_{n+1}=F_1^2+\cdots +F_n^2}.

Proof: A menaiki tangga dari level 1 ke level {n} dan {B} naik dari level 1 ke level {n+1}. Banyaknya cara keduanya bisal melakukan hal yang demikian adalah {F_nF_{n+1}}. Misalkan {k} adalah level tertinggi yang dikunjungi oleh keduanya. Dari level {k} si A naik {a} undakan sedangkan si {B} naik {b} undakan dengan {a,b\in\{1,2\}}. Berdasarkan definisi {k} haruslah {a\neq b} (jika sama maka {A} dan {B} mengunjungi level {k+a=k+b}). Setelah itu untuk memastikan keduanya tidak pernah mengunjungi level yang sama maka mereka harus selalu naik 2 undakan. Nilai {a} dan {b} juga ditentukan secara tunggal dari syarat bahwa dengan langkah {a,2,2,\ldots,2} si {A} harus sampai ke level {n}.

Berarti dari level 1 sampai dengan level {k} si {A} dan {B} masing-masing mempunyai {F_k} cara dan sisanya dari level {k} ke level {n} dan dari level {k} ke level {n+1} ditentukan secara tunggal. \Box

Theorem 4 {F_n=F_kF_{n+1-k}+F_{k-1}F_{n-k}}.

Proof: Naik dari level 1 ke level {n} bisa dengan mengunjung level {k} terlebih dulu bisa juga tidak. Jika melalui level {k} banyaknya cara untuk melakukan hal tersebut adalah {F_kF_{n+1-k}}. Jika tidak melalui {k} maka haruslah sampai ke level {k-1} terlebih dahulu, kemudian naik dua undakan ke level {k+1} kemudian dari sana bebas melakukan apapun untuk sampai di level {n}. Banyaknya cara melakukan hal ini adalah {F_{k-1}F_{n-k}}. \Box