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

Leave a Reply

Your email address will not be published. Required fields are marked *