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.

Lema Gauss dan Keirasionalan Bilangan

Dulu, pertama kali saya melihat bukti bahwa {\sqrt{2}} irasional ketika mengambil mata kuliah Analisis Real di tingkat tiga. Mungkin memang sepertinya sangat terlambat, tapi yang saya ingat saya cukup terkesan melihat bukti tersebut. Agar mahasiswa mengenal hal ini sedini mungkin, saya sudah memberikannya kepada mahasiswa kalkulus saya semester ini.

Hasil keirrasionalan {\sqrt{2}} bisa diperumum. Dapat dibuktikan bahwa asalkan bilangan asli {k} bukanlah merupakan pangkat {n} dari suatu bilangan asli, yakni {k\neq m^n} untuk setiap bilangan asli {m}, maka {\sqrt[n]{k}} merupakan bilangan irasional.

Lebih lanjut jika {P(x)=x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n} merupakan polinom dengan {a_1,\ldots,a_n} merupakan bilangan bulat, maka akar dari {P(x)} adalah bilangan bulat atau bilangan irasional. Hasil ini dikenal dengan Lemma Gauss. Perhatikan bahwa dengan meninjau polinom {x^n-k} dengan {k\neq m^n} untuk sebarang bilangan bulat {m}, maka kita simpulkan bahwa {\sqrt[n]{k}} merupakan bilangan irasional.

Dalam tulisan ini kita akan membuktikan Lemma Gauss dengan argumen baru yang diberikan oleh David Gilat tahun 2012. Argumen baru ini hanya bersandar kepada sifat kelengkapan bilangan asli yang mengatakan bahwa setiap subhimpunan bilangan asli pasti memiliki unsur terkecil. Bukti Lemma Gauss yang standard meskipun sama-sama sederhananya tapi mengasumsikan beberapa pengetahuan dasar tentang sifat bilangan prima.

Theorem 1 (Lemma Gauss) Diberikan polinom {P(x)=x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n} dengan koefisien bulat. Jika {r} adalah akar rasional dari {P(x)}, maka {r} merupakan bilangan bulat.

Bukti Standard

Misalkan r=p/q dengan (p,q)=1 dan f(r)=0. Akibatnya \frac{p^n}{q^n}+\sum_{i=1}^{n-1} a_i \frac{p^{n-1}}{q^{n-1}}=0. Kalikan dengan q^n dan pindah ruas diperoleh p^n=-\sum_{i=1}^{n-1} p^iq^{n-i}. Perhatikan bahwa ruas kanan habis dibagi q. Jika q\neq 1 maka q mempunyai faktor prima t yang membagi q dan menurut persamaan di atas juga membagi p^n. Karena sifat bilangan prima maka t juga membagi p kontradiksi dengan (p,q)=1. Jadi haruslah q=1 dan r bulat.

[collapse]

Proof: Andaikan {r} adalah akar rasional dari {P(x)} yang tidak bulat. Maka terdapat suatu bilangan bulat {q} sedemikian sehingga {q< r< q+1}. Sekarang pandang himpunan

\displaystyle M:=\{m\in \mathbb{N}\mid mr,mr^2,\ldots,mr^{n-1} \text{ merupakan bilangan bulat}\}

Karena {M} merupakan subhimpunan dari bilangan asli, maka {M} mempunyai unsur terkecil, sebut ia {m}. Dari {P(r)=0} kita peroleh {r^n= -a_1r^{n-1}-a_2r^{n-2}+\cdots-a_{n-1}r-a_n}. Dengan mengalikan persamaan ini dengan {m} kita dapatkan

\displaystyle mr^n=-a_1mr^{n-1}-a_2mr^{n-2}+\cdots-a_{n-1}mr-a_n

dan kita simpulkan bahwa {mr^n} merupakan bilangan bulat (mengapa?). Sekarang tinjau bilangan {m':=(r-q)m}. Perhatikan bahwa berdasarkan definisi {m}, kita tahu bahwa {mr} bulat, demikian juga {qm} bulat karena {q} bulat. Dengan demikian {m'} bulat. Perhatikan pula bahwa untuk {i=1,\ldots, n-1} kita peroleh {m'r^i=(r-q)mr^i=mr^{i+1}-qmr^i} yang juga merupakan bilangan bulat arena {Q} bulat dan {mr^j} adalah bilangan bulat untuk {j=1,\ldots, n}. Jadi {m'\in M}. Akan tetapi perhatikan bahwa {0<(r-q)<(q+1)-q=1} yang mengakibatkan {m'=(r-q)m<m}. Ini bertentangan dengan fakta bahwa {m} adalah unsur terkecil di {M}.

Jadi haruslah {r} merupakan bilangan bulat. \Box

Berkaitan dengan keirasionalan bilangan, Lemma Gauss bisa kita baca sebagai berikut: jika {r} bukan bilangan bulat, tapi ia merupakan akar suatu polinom monik dengan koefisien bilangan bulat, maka haruslah {r} merupakan bilangan irasional.

Sebagai contoh jika {p} bilangan prima, jelas {\sqrt{p}} bukan bulat, karena jika bulat maka ia merupakan faktor dari {p}. Akan tetapi {\sqrt{p}} merupakan akar dari polinom monik {x^2-p}. Dengan demikian {\sqrt{p}} merupakan bilangan irasional.

Contoh yang lain, apakah {\sqrt{5}+\sqrt{11}} rasional? Pertama kita periksa apakah ia bulat? jika ia bulat maka demikian pula dengan {(\sqrt{5}+\sqrt{11})^2=16+2\sqrt{55}}. Akibatnya {2\sqrt{55}} bulat. Tapi hal tersebut tidak mungkin karena {14^2< (2\sqrt{55})^2<15^2} sehingga bilangan {2\sqrt{55}} terletak diantara dua bilangan bulat berurutan (14 dan 15) yang mengakibatkan {2\sqrt{55}} tidak bulat. Jadi {\sqrt{5}+\sqrt{11}} tidak bulat. Sekarang perhatikan dari perhitungan di atas kita peroleh

\displaystyle \left((\sqrt{5}+\sqrt{11})^2-16\right)^2=220

atau dengan kata lain {\sqrt{5}+\sqrt{11}} merupakan akar dari polinom monik {(x^2-16)^2-220=x^4-32x^2-24} dan menurut Lemma Gauss haruslah {\sqrt{5}+\sqrt{11}} irasional.