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.

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.

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

Domain + Finiteness = Field

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

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

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

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

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

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

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

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

\Box

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

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

Bukti

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

[collapse]

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

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

Bukti

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

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

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

[collapse]

Dua Soal Struktur Aljabar ONMIPA 2016

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

Soal Hari Pertama

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

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

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

Cara lain yang lebih teoretis adalah dengan pertama membuktikan lemma berikut

Bukti Lain

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

[collapse]

Soal tentang struktur aljabar berikutnya adalah sebagai berikut:

Soal Hari Kedua

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

Bukti 1

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

[collapse]
Bukti 2

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

[collapse]

 

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

 

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

Prima berbentuk p=a^2+b^2.

Dalam tulisan ini akan ditunjukkan jika {p} adalah bilangan prima berbentuk {p=4k+1} jika dan hanya jika {p} dapat dituliskan sebagai penjumlahan dua bilangan kuadrat. Pembuktian di artikel ini akan memanfaatkan sifat bahwa {\mathbb{Z}[i]} merupakan suatu Unique Factorization Domain (UFD).

Pertama kita akan memerlukan teorema Wilson

Theorem 1 (Wilson)

\displaystyle  (p-1)!\equiv -1 {\pmod p}.

Proof: Pertama akan kita tunjukkan bahwa unsur taknol di {\mathbb{Z}_p} yang inversnya adalah dirinya sendiri hanyalah {1} dan {-1}. Jika {x^2=1} di {\mathbb{Z}_p}, maka {(x+1)(x-1)=0} dan karena {\mathbb{Z}_p} lapangan maka {x=1} atau {x=-1}. Dengan demikian semua unsur {1,2,\ldots, p-1} di {\mathbb{Z}_p} dapat dipasang-pasangkan dengan inversnya kecuali 1 dan -1. Dengan demikian {(p-1)!=-1} di {\mathbb{Z}_p}. \Box

Lemma 2 Jika {p=4k+1} maka terdapat {m\in \mathbb{Z}} sehingga {p} membagi {m^2+1}.

Proof: Perhatikan bahwa

\displaystyle  -1=(p-1)!=1\cdot 2\cdots 2k\cdot (-2k)\cdots (-2)= (-1)^{2k}\left(1\cdot 2\cdots 2k\right)^2

di {\mathbb{Z}_p}. Dengan demikian untuk {m=(2k)!} kita peroleh bahwa {p} membagi {m^2+1}. \Box

Theorem 3 (Fermat) Bilangan prima ganjil {p} berbentuk {p=4k+1} jika dan hanya jika terdapat {a,b} sehingga {p=a^2+b^2}.

Proof: Dari lemma di atas kita punyai {p} membagi {m^2+1=(m+i)(m-i)\in \mathbb{Z}[i]}. Perhatikan bahwa {p} tidak membagi baik {m+i} ataupun {m-i} karena jika misalnya {p(c+di)=m+i} maka {pd=1} yang jelas mustahil. Dengan demikian {p} tidak membagi {m+i}. Dengan cara serupa {p} tidak membagi {m-i}. Ini menunjukkan bahwa {p} bukan unsur prima di {\mathbb{Z}[i]}. Karena unsur taktereduksi adalah unsur prima di UFD maka {p} juga bukat unsur taktereduksi. Artinya ada {a+bi, c+di \in \mathbb{Z}[i]} sehingga {(a+bi)(c+di)=p}. Sekarang {N(a+bi)N(c+di)=N(p)=p^2}. Karena {a+bi,c+di} bukan unit maka {N(a+bi)} dan {N(c+di)} tidak sama dengan 1. Jadi haruslah {N(a+bi)=N(c+di)=p}. Akibatnya {a^2+b^2=N(a+bi)=p}.

Sebaliknya misalkan {p=a^2+b^2} untuk suatu bilangan bulat {a,b}. Karena {p} ganjil maka {a,b} tidak mungkin keduanya genap dan juga tidak mungkin keduanya ganjil. Tanpa mengurangi keumuman misalkan {a=2k} dan {b=2l+1}. Akibatnya {p=4k^2+4l^2+4l+1=4(k^2+l^2+l)+1}. \Box

Aturan Perkalian

Metode standard yang dipergunakan untuk menunjukkan aturan perkalian dalam penghitungan turunan adalah dengan menggunakan definisi turunan yang diterapkan kepada fungsi f(x)g(x). Menurut definisi

    \begin{align*} (fg)'(x)=\lim_{h\to 0}\frac{f(x+h)g(x+h)-f(x)g(x)}{h}. \end{align*}

Selanjutnya kita gunakan trik mengurangkan dan menambahkan f(x+h)g(x) kepada pembilang sehingga kita bisa menuliskan

    \begin{align*} \lim_{h\to 0} &\frac{f(x+h)\left(g(x+h)-g(x)\right)+ g(x)\left(g(x+h)-g(x)\right)}{h} \end{align*}

yang kemudian dipecah menjadi dua limit yang setelah dihitung limitnya menghasilkan f(x)g'(x)+f'(x)g(x).

Berikut adalah cara lain untuk mendapatkan aturan perkalian tersebut dengan pertama-tama meninjau kasus khusus dari aturan perkalian dimana kedua fungsi yang dikalikan merupakan fungsi yang sama.

Lemma
Jika u(x) punya turunan maka (u^2)'(x)=2u(x)u'(x).

Bukti.

    \begin{align*} (u^2)'(x)&=\lim_{h\to 0} \frac{u^2(x+h)-u^2(x)}{h}\\&=\lim_{h\to 0}\left(u(x+h)+u(x)\right)\frac{u(x+h)-u(x)}{h}\\ &=2u(x)u'(x). \quad \box \end{align*}

Sekarang kita kembali ingin menghasilkan turunan dari perkalian f(x)g(x). Kita akan menurunkan (f+g)^2 dalam dua cara. Pertama menurut lemma kita peroleh

    \[ \left((f+g)^2\right)'=2(f+g)(f'+g')=2(ff'+gg'+fg'+gf'). \]

Sekarang dengan mengekspansi (f+g)^2 terlebih dahulu menjadi f^2+g^2+2fg. Maka

    \[ \left((f+g)^2\right)'=(f^2+g^2+2fg)'=2ff'+2gg'+2(fg)'. \]

Dengan membadingkan kedua ekspresi di atas diperoleh (fg)'=fg'+f'g.

Cara penurunan aturan perkalian diatas diambil dari artikel pendek berikut.

Rendered by QuickLaTeX.com

Teorema Sylow

Theorem 1 (Sylow) Misalkan {G} grup hingga dan |G|=p^am dengan {p} tidak membagi {m}. Maka terdapat {H} subgrup dari {G} sehingga {|H|=p^a}.

Sebelum kita membuktikan teorema di atas kita memerlukan lemma berikut.

Lemma 2

\displaystyle  {p^am\choose p^a}\equiv m {\pmod p}.

Proof: Dapat dibuktikan dengan induksi bahwa {(x+1)^{p^a}\equiv x^{p^a}+1{\pmod p}}. Akibatnya

\displaystyle  (x+1)^{p^am}=\left((x+1)^{p^a}\right)^m\equiv (x^{p^a}+1)^m {\pmod m}.

Sekarang dengan melihat koefisien dari {x^{p^a}} dari kedua sisi kita peroleh

\displaystyle  {p^am\choose p^a}\equiv {m\choose 1}=m {\pmod p}.

\Box

Sekarang kita siap untuk membuktikan teorema Sylow. Bukti ini merupakan bukti yang diberikan oleh Wielandt.

Proof: Tinjau himpunan {\Omega:=\{X\subseteq G\mid |X|=p^a\}}. Perhatikan bahwa {|\Omega|={p^am\choose p^a}}, sehingga menurut lemma di atas, {\|\Omega|\equiv m {\pmod p}}. Karena {p\nmid m}, maka khususnya {p\nmid |\Omega|}.

Sekarang {G} beraksi pada {\Omega} lewat perkalian kanan. Karena {\Omega} merupakan gabungan dari orbit-orbit, maka kita bisa mempelajari {|\Omega|} lewat kardinalitas orbit-orbit aksi. Jika {p\mid |\mathcal{O}|} untuk setiap orbit {\mathcal{O}} maka otomatis {p\mid |\Omega|} yang bertentanga dengan apa yang sebelumnya kita dapatkan bahwa {p} tidak membagi {|\Omega|}. Dengan demikian ada {\mathcal{O}_X} yang memuat {X} sehingga {p\nmid |\mathcal{O}_X}.

Menurut teorema orbit-stabiliser, {|G_X||\mathcal{O}_X|=|G|} dengan {G_X} adalah stabiliser dari {X} di {G}. Karena {p^a\mid |G|} tapi {p\nmid |\mathcal{O}_X|} maka haruslah {p^a\mid |G_X|}. Khususnya {p^a\leq |G_X|}.

Berikutnya akan kita tunjukkan bahwa kardinalitas dari grup {H:=G_X} adalah tepat sebanyak {p^a}. Untuk setiap {x\in X} dan {h\in H} perhatikan bahwa

\displaystyle  xh\in Xh=X\cdot h=X (\text{ karena }h\in G_X).

Ini berarti bahwa {xH\subseteq X}. Akibatnya {|H|=|xH|\leq |X|=p^a} dan dari ketaksamaan sebelumnya kita simpulkan bahwa {|H|=p^a}. \Box