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

Prinsip Keterbilangan

Salah satu fakta dasar yang dipelajari diperkuliahan analisis real adalah bahwa banyaknya unsur di himpunan bilangan rasional {\mathbb{Q}} “sama banyak” dengan banyaknya unsur di himpunan bilangan asli {\mathbb{Q}}. Sebagian besar bukti-bukti yang diberikan di buku teks adalah dengan menggunakan argumen diagonalisasi.

Berikut ini adalah metoda yang saya pelajari dari artikelnya Robert Kantrowitz pada Mathematics Magazine, Februari 2000. Argumen ini sangat sederhana tapi powerful dan dengan metoda ini kita dapat menentukan keterbilangan beberapa himpunan. Tulisan ini adalah salah satu upaya agar metoda Kantrowits ini dikenal lebih luas.

Sebelum menerangkan tentang metoda Kantrowitz ini, pertama kita akan mengulas beberapa definisi.

Definition 1 Suatu himpunan {H} dikatakan terbilang jika terdapat korespondesi satu-satu antara {H} dengan suatu subhimpunan dari {\mathbb{N}}.

Definisi ini agak berbeda dengan definisi yang biasanya pada buku teks, akan tetapi bisa ditunjukkan bahwa mereka ekivalen. Sebagai contoh jika himpunan {H} merupakan himpunan berhingga, sebut anggotanya {h_1,\ldots, h_n}, maka kita punya korespondensi satu-satu antara {\{1,2,\ldots, n\}\subseteq \mathbb{N}} dengan {H}. Dengan demikian himpunan hingga otomatis merupakan himpunan yang terbilang.

Definition 2 Barisan hingga dari unsur-unsur di {A} kita sebut sebagai kata-kata dengan alfabet berasal dari {A}. Suatu kata-kata dari {A} dengan {n} huruf adalah barisan unsur-unsur di {A} dengan {n} anggota.

Sebagai contoh, kata-kata yang kita kenal sehari-hari adalah kata-kata dengan alfabet berasal dari himpunan {A:=\{a,b,c,\ldots,z\}}.

Sekarang kita akan berikan prinsip keterbilangna dari Kantrowitz

Theorem 3 {Prinsip Keterbilangan} Himpunan semua kata-kata yang berasal dengan alfabet himpunan hingga {A} merupakan himpunan terbilang.

Proof: Misalkan {A} terdiri dari {r} unsur. Misalkan {K_s} merupakan himpunan kata-kata dari {A} yang terdiri dari {s} huruf. Ada terdapat {r} kata-kata yang mungkin dari {A} yang hanya terdiri dari satu huruf. Kita bisa membuat korespondensi satu-satu {f_1} antara himpunan {K_1} dengan {\{1,2,\ldots, r\}}. Kemudian, banyaknya unsur di {K_2} adalah {r^2} dan kita bisa membuat korespondensi satu-satu {f_2} antara himpunan {K_2} dengan {\{1+r,\ldots, r+r^2\}}. Berikutnya {f_3} adalah korespondensi satu-satu antara {K_3} dengan {\{1+r+r^2,\ldots, r+r^2+r^3\}}. Secara umum kita bisa mendefinisikan korespondensi satu-satu {f_n} antara himpunan {K_n} dengan {\{1+r+\cdots+r^{n-1},\ldots, r+r^2+\cdots+r^{-1}+r^n\}}.

Perhatikan bahwa himpunan semua kata-kata yang mungkin dari alfabet {A} adalah {K:=\bigcup_{n} K_n}. Definisikan pemetaan {f: K\rightarrow \mathbb{N}} melalui {f(k)=f_n(k)} jika {k\in K_n} dan cukup jelas bahwa pemetaan ini merupakan korespondensi satu-satu. \Box

Berikut beberapa aplikasi dari prinsip keterbilangan ini. Kita akan menggunakan lema berikut dalam contoh-contoh kita.

Lemma 4 Himpunan bagian dari suatu himpunan yang terbilang juga terbilang.

Proof: Bukti diserahkan kepada pembaca. \Box

Example 1

  1. Himpunan bilangan rasional {\mathbb{Q}} merupakan himpunan terbilang. Hal ini dikarenakan setiap unsur di {\mathbb{Q}} bisa kita tinjau sebagai kata-kata yang berasal dari alfabet {A=\{0,1,2,3,4,5,6,7,8,9,/,-\}}. Sebagai contoh bilangan rasional {\frac{-10934}{25346}} bisa kita lihat sebagai kata {-10934/25436}. Karena {A} hingga maka menurut prinsip keterbilangan {\mathbb{Q}} juga hingga.
  2. Himpunan semua polinom dengan koefisien bulat {\mathbb{Z}[x]} merupakan himpunan terbilang. Setiap polinom di {\mathbb{Z}[x]} dapat kita lihat sebagai kata-kata dari himpunan alfabet {\{0,1,\ldots, 9,+,-,x\}}. Sebagai contoh polinom {23x^{123}-99x^{5}+1} dapat kita tulis sebagai kata {23x1-99x5+1}. Akibatnya menurut prinsip keterbilangan {\mathbb{Z}[x]} merupakan himpunan yang terbilang. Dengan menambahkan “/” pada himpunan {A}, dengan argumen yang serupa himpunan {\mathbb{Q}[x]} juga merupakan himpunan terbilang.

Selain penggunaannya pada contoh-contoh di atas, prinsip keterbilangan ini juga mempunyai aplikasi secara teoretis seperti yang terlihat pada hasil berikut.

Theorem 5 Misalkan {H_1,H_2,H_3,\ldots} merupakan barisan himpunan yang terbilang.

  1. {H_1\times H_2\times \cdots \times H_s} merupakan himpunan terbilang.
  2. {\bigcup_{n\geq 1} H_n} merupakan himpunan terbilang.

Proof: Misalkan {f_i} merupakan korespondensi satu-satu antara {\mathbb{N}} (atau himpunan bagian dari {\mathbb{N}}) dengan {H_i}

  1. Anggota dari {H_1\times \cdots \times H_s} bisa kita tuliskan sebagai {(f_i(n_1),f_2(n_2),\ldots, f_s(n_s))} yang bisa kita identifikasi sebagai suatu kata yang berasal dari alfabet {\{0,1,\ldots, 9, f, (,),,\}} (perhatikan bahwa “,” adalah salah satu anggota himpunan alfabet ini).
  2. Setiap unsur di {\bigcup_{n\geq 1} H_n} berbentuk {f_i(n)} untuk suatu bilangan asli {i} dan {n}. Dengan demikian setiap anggota dari {\bigcup_{n\geq 1} H_n} dapat diidentifikasi sebagai suatu kata dari alfabet {\{0,1,\ldots, 9, f, (,)\}}.

\Box

Anda Boleh Berbohong Sekali!

Permainan Menebak Angka

Wati dan Budi memainkan permainan tebak angka. Wati meminta Budi untuk memikirkan suatu angka dari 0 sampai dengan 15. Untuk bisa menebak angka ini, Budi diminta menjawab tujuh pertanyaan berikut dengan jawaban ya atau tidak. Budi diperbolehkan berbohong paling banyak satu kali ketika menjawab.

Tujuh pertanyaan yang Wati ajukan, semuanya berbentuk: apakah bilangan yang kamu pikirkan ada dihimpunan {A} ? dengan himpunan {A} berturut-turut adalah ketujuh himpunan berikut:

  1. {\{8,9,10,11,12,13,14,15\}}
  2. {\{4,5,6,7,12,13,14,15\}}
  3. {\{2,3,6,7,10,11,14,15\}}
  4. {\{1,3,5,7,9,11,13,15\}}
  5. {\{1,2,5,6,8,11,12,15\}}
  6. {\{1,2,4,7,9,10,12,15\}}
  7. {\{1,3,4,6,8,10,13,15\}}

Jawaban Budi dari ketujuh pertanyaan di atas adalah: ya, ya, ya, ya, tidak, tidak, ya. Setelah mencoret-coret sesuatu di kertas, satu menit berikutnya Wati mengumumkan bahwa Budi telah berbohong ketika menjawab pertanyaan ketiga dan angka yang dipikirkan Budi adalah 13! Budi membenarkan apa yang dikatakan Wati.

Karena merasa penasaran Budi ingin mencobanya sekali lagi. Setelah memikirkan suatu angka, berikut adalah jawaban Budi atas pertanyaan-pertanyaan yang sama seperti pada permainan yang pertama: tidak, ya, tidak, tidak, ya, tidak, tidak. Bisakah anda membantu Wati untuk menebak apa angka yang dipikirkan Budi?

Solusi Wati

Berikut adalah cara Wati untuk menentukan bilangan apa yang dipikirkan Budi. Untuk setiap jawaban Budi, Wati menuliskan angka 1 jika Budi menjawab ya dan 0 jika Budi menjawab tidak. Ketujuh kombinasi angka 1 dan 0 tersebut ditempatkan kedalam daerah-daerah yang dipisahkan oleh tiga buah lingkaran seperti yang terlihat pada gambar berikut

circles

dengan bilangan 1 sampai dengan 7 menunjukkan didaerah mana angka 1 atau 0 harus ditempatkan ketika Wati mendengar jawaban Budi. Sebagai contoh, pada permainan pertama Budi menjawab ya, ya, ya, ya, tidak, tidak, ya yang berarti Wati memperoleh barisan bilangan 1,1,1,1,0,0,1 yang akan ditempatkan sesuai pada gambar di atas. Setelah ditempatkan sesuai pada tempatnya diperoleh sebagai berikut

circle2

Jika Budi tidak berkata bohong, angka 1 pada setiap lingkaran muncul sebanyak genap kali. Pada gambar di atas lingkaran sebelah kanan memuat 1 sebanyak 4 kali (genap), sedangkan lingkaran kiri dan bawah muncul sebanyak ganjil kali. Ini menandakan Budi bohong pada pertanyaan yang sekaligus termuat di lingkaran kiri dan lingkaran bawah tapi tidak termuat di lingkaran kanan, yakni pertanyaan nomor 3! Dengan demikian jika Budi jujur maka Budi harus menjawab tidak pada pertanyaan ketiga sehingga angka 1 harus digantikan dengan angka 0 pada daerah untuk pertanyaan nomor 3. Sekarang untuk mengetahui bilangna Budi yang sebenarnya, Wati cukup membaca empat angka pertama pada lingkaran, yakni 1101 dan mengubahnya dari biner ke desimal untuk mendapatkan 13.

Bagaimana Metode Ini Bisa Jalan?

Misalkan Budi memberi jawaban {x_1x_2\cdots x_7} dengan masing-masing {x_i} bisa bernilai 0 atau 1 untuk setiap {1\leq i\leq 7}. Jika Budi tidak bohong maka berdasarkan gambar lingkaran yang paling atas, himpunan-himpunan {\{x_1,x_2,x_4,x_7\},\{x_1,x_3,x_4,x_5\},\{x_2,x_3,x_4,x_6\}} masing-masingnya memiliki angka 1 sebanyak genap kali. Kondisi ini kita bisa tuliskan sebagai

    \begin{align*} x_1+x_3+x_4+x_5&=0\\ x_2+x_3+x_4+x_6&=0\\ x_1+x_2+x_4+x_7&=0 \end{align*}

dimana persamaan ini kita tinjau sebagai persamaan di lapangan {\mathbb{F}_2} yang memiliki dua unsur 0 dan 1. Ingat bahwa di {\mathbb{F}_2} penjumlahan bersifat komutatif dan {0+0=0,0+1=1} dan {1+1=0}.

Sistem persamaan di atas dapat kita tinjau sebagai persamaan matriks

\displaystyle H\begin{pmatrix}x_1\\x_2\\x_3\\x_4\\x_5\\x_6\\x_7\end{pmatrix}=0

dengan {H=\begin{pmatrix}1&0&1&1&1&0&0\\0&1&1&1&0&1&0\\1&1&0&1&0&0&1\end{pmatrix}}. Dari sini kita lihat bahwa “himpunan jawaban jujur” adalah kernel dari {H} dan merupakan subruang dari {\mathbb{F}_2^7}. Karena setiap ruang vektor memiliki basis, kita bisa menanyakan berapa dimensinya dan apa basisnya. Perhatikan bahwa ketiga kolom terakhir dari {H} bebas linier. Dengan demikian {\text{rank } H=3} dan akibatnya kernel dari {H} berdimensi {7-3=4}.

Perhatikan bahwa matriks {H} dapat dilihat sebagai blok-blok matriks {H=[A\mid I_3]} untuk suatu matriks {A}. Untuk {G=[I_4\mid -A^T]}, perhatikan bahwa

\displaystyle HG^T=AI_4-I_3A=0.

Dengan demikian baris-baris dari {G} merupakan bagian dari jawaban-jawan jujur. Akan tetapi karena

\displaystyle G=\begin{pmatrix}1&0&0&0&1&0&1\\0&1&0&0&0&1&1\\0&0&1&0&1&1&0\\0&0&0&1&1&1&1\end{pmatrix}

dan empat kolom pertama dari {G} bebas linier. Dengan demikian ruang baris dari G, juga berdimensi 4. Ini menunjukan bahwa himpunan semua jawaban jujur adalah semua kombinasi linier dari baris-baris {G}.

Dari sini kita bisa melihat bahwa bilangan-bilangan 0 sampai dengan 15 harus kita “sandikan” sebagai unsur di ruang baris {G} dengan tambahan syarat bahwa meskipun telah disandikan kita masih mengenalinya dengan mudah sebagai bilangan 0 sampai dengan 15. Cara yang kita lakukan sebagai berikut: untuk setiap bilangan dari 0 sampai dengan 15 tersebut, pertama kita tuliskan sebagai bilangan biner dengan panjang 4, katakan {a_1a_2a_3a_4}. Kemudian kita sandikan ia sebagai {\begin{pmatrix}a_1&a_2&a_3&a_4\end{pmatrix}G}. Sebagai contoh, untuk bilangan 5, dalam bilangan biner dengan panjang 4 ia bisa kita tuliskan sebagai {0101}. Sehingga 5 kita sandikan menjadi

\displaystyle \begin{pmatrix}0&1&0&1\end{pmatrix}\begin{pmatrix}1&0&0&0&1&0&1\\0&1&0&0&0&1&1\\0&0&1&0&1&1&0\\0&0&0&1&1&1&1\end{pmatrix}=\begin{pmatrix}0&1&0&1&1&0&0\end{pmatrix}

Dengan melakukan hal serupa seperti di atas untuk semua bilangan 0 sampai dengan 15 kita peroleh tabel berikut:

\displaystyle \begin{matrix} 0=0000000&4=0100011&8=1000101&12=1100110\\ 1=0001111&5=0101100&9=1001010&13=1101001\\ 2=0010110&6=0110101&10=1010011&14=1110000\\ 3=0011001&7=0111010&11=1011100&15=1111111 \end{matrix}

Kemudian pertanyaan Wati yang ke-i bernilai sama dengan menanyakan apakah digit ke-i pada bilangan yang telah disandikan merupakan angka 1. Sebagai contoh pertanyaan kedua Wati senilai dengan menanyakan apakah bilangan yang telah disandikan digit keduanya 1. Dari tabel di atas kita lihat bahwa bilangan-bilangan yang digit ke-2 nya 1 adalah bilangan-bilangan di himpunan {\{4,5,6,7,12,13,14,15\}}. Dengan melakukan hal serupa untuk pertanyaan pertama sampai ketujuh maka kita peroleh semua pertanyaan Wati yang diberikan pada bagian pertama tulisan ini.

Masih ada pertanyaan yang tersisa. Darimana kita tahu bahwa dengan melakukan semua hal di atas Wati pasti selalu bisa menebak angka Budi asalkan Budi berbohong tidak lebih dari satu kali? Kita katakan dua string berjarak {k} jika mereka berbeda di {k} buah posisi. Jika kita lihat setiap string dengan 7 digit pada tabel di atas, setiap dua string sedikitnya berjarak 3. Sebagai contoh, string untuk 8 dan 12 yakni 1000101 dan 1100110 berjarak 3 karena mereka berbeda dalam 3 posisi, yakni pada posisi ke 2,6 dan 7. Misalkan Budi memberikan string {x} dengan panjang 7 sebagai jawaban dari Wati. Jika Budi berbohong maka {x} ini didapat dari suatu string {y} dari tabel yang salah satu digitnya diubah (dari 0 ke 1 atau sebaliknya). Wati bisa menyimpulkan bahwa si {x} ini berasal dari {y} jika dan hanya jika {y} adalah satu-satunya string di tabel yang berjarak 1 dari {x}. Jika ada dua string {y_1,y_2} di tabel yang berjarak 1 terhadap {x} maka {y_1,y_2} paling banyak berjarak 2. Tapi ini tidak mungkin karena tadi sudah kita lihat bahwa setiap dua string di tabel berbeda sedikitnya berjarak 3!. Dari sini disimpulkan bahwa apapun angka Budi, asalkan ia tidak berbohong lebih dari satu kali, Wati pasti bisa menebaknya.

Bisa kita lihat jarak minimum memegang peranan yang sangat penting dalam solusi permasalahan ini. Secara teoretis, jika kita mempunyai himpunan yang jarak minumumnya {d} maka Budi boleh berbohong spaling banyak {\lfloor \frac{d-1}{2}\rfloor} kali agar Wati masih bisa menebak angka Budi. Bagaimana mengkonstruksi himpunan dengan jarak {d} yang besar dapat dipelajari lebih lanjut di buku-buku yang membahas tentang error correcting codes.