Category: mathematics

Misteri Imanensi Bilangan Transenden: suatu refleksi posisi diri di hadapan Sang Transenden

Untuk memulai diskusi, ada baiknya penulis menjelaskan makna judul artikel ini agar pembaca dapat menangkap kesan paradoks yang muncul dalam judul tersebut. Sesuatu yang transenden berarti bahwa sesuatu tersebut eksis namun berada sangat jauh dari kesadaran realitas sehari-hari. Sementara itu, suatu yang imanen berarti kita memiliki akses yang sangat mudah untuk bertemu dengan hal tersebut. Sebagai contoh kecil, kita dapat mengatakan cincin es Saturnus bersifat transenden, sementara es batu dalam kulkas rumah kita bersifat imanen. Berdasarkan kedua definisi singkat ini, dapat kita tangkap bahwa jika suatu hal transenden, maka ia tidak seharusnya imanen; demikian pula sebaliknya. Dengan demikian, jika suatu bilangan yang dikatakan transenden, ternyata memiliki imanensi, maka fenomena ini adalah suatu misteri yang sangat menarik. Apa maksudnya suatu bilangan begitu jauh namun juga sekaligus begitu dekat?

Pertama-tama, kita akan melihat beberapa klasifikasi bilangan. Dalam artikel ini, penulis tidak mendefinisikan bilangan nyata (real numbers) dan mengasumsikan pembaca memiliki ide dasar mengenai hal ini. Salah satu himpunan bilangan yang paling elementer adalah bilangan bulat, yaitu bilangan yang tidak memuat pecahan, dinotasikan

\mathbb{Z} =\{ 0, \pm 1, \pm 2, \dots \}.

Selanjutnya, kita definisikan bilangan rasional, yaitu bilangan yang dapat dinyatakan sebagai rasio dari dua bilangan bulat, dinotasikan

\mathbb{Q} = \{ \frac{p}{q} : p,q\in \mathbb{Z}; q\neq 0\}

Bilangan nyata yang bukan merupakan bilangan rasional disebut bilangan irasional. Sebagai contoh, bilangan 0.125 merupakan bilangan rasional karena 0.125 = 1/8. Sementara itu \sqrt{2} merupakan bilangan irasional (bukti pernyataan ini adalah contoh yang sangat populer untuk metode pembuktian dengan kontradiksi; sebagai referensi, lihat https://id.wikipedia.org/wiki/Pembuktian_melalui_kontradiksi).

Dalam artikel ini, kita akan membahas secara khusus tentang bilangan irasional. Dalam tulisan ini, kita membagi bilangan irasional menjadi 2 kelompok: bilangan aljabar dan bilangan transenden. Suatu bilangan irasional x dikatakan sebagai bilangan aljabar jika ada suatu polinom rasional (polinom dengan koefisien bilangan rasional) P(\cdot) sehingga P(x)=0. Sementara itu, bilangan irasional yang tidak dapat dinyatakan sebagai akar dari suatu polinom disebut bilangan transenden. Sebagai contoh, \sqrt{2} adalah bilangan aljabar karena \sqrt{2} merupakan akar dari polinom rasional P(x)=x^2-2. Di sisi lain, konstanta \pi adalah bilangan transenden. Bukti bahwa \pi transenden tidak terlalu elementer, dan ini adalah implikasi dari dari sifat bilangan transenden. Dalam bagian selanjutnya kita akan melihat bahwa sedikit sekali pengetahuan kita tentang bilangan transenden.

Bilangan-bilangan yang bukan merupakan akar dari polinomial apapun disebut transenden karena beberapa alasan. Alasan teoretis adalah karena bilangan ini tidak dapat diaproksimasi perilakunya melalui suatu polinomial. Polinom merupakan salah satu alat yang dipakai matematikawan zaman Yunani kuno untuk menemukan suatu tipikal bilangan “jenis baru”, yaitu bilangan irasional. Bilangan bulat dan pecahan mungkin dapat dikenal secara umum karena ada banyak hal dalam kehidupan sehari-hari yang memunculkan bilangan-bilangan tersebut secara natural. Namun demikian, para matematikawan Yunani kuno memperhatikan bahwa mereka tidak pernah dapat mengukur panjang sisi miring segitiga sama kaki dengan panjang kaki 1 cm dengan akurat (dengan teorema pythagoras kita tahu bahwa sisi ini memiliki panjang \sqrt{2}, yang adalah bilangan irasional). Meskipun mereka mengaproksimasi panjang sisi tersebut dengan pecahan ataupun desimal yang sangat panjang, mereka mendapati bahwa aproksimasi tersebut tidak pernah benar-benar memenuhi bilangan yang dicari. Hal ini memimpin mereka menemukan fakta bahwa memang ada bilangan yang tidak dapat dinyatakan sebagai rasio dua buah bilangan bulat. Mencari akar suatu polinom menjadi suatu jalan untuk menemukan bilangan-bilangan “baru” yang tersembunyi, yang jarang muncul dalam dunia keseharian. Namun seiring perkembangan matematika modern, para matematikawan kembali menemukan bahwa ada bilangan-bilangan irasional tertentu yang lebih “jauh” dibanding dengan bilangan irasional yang lain, yaitu bilangan transenden. Meskipun dengan metode polinom, matematikawan sanggup menemukan jenis bilangan baru di zaman itu, rupanya masih ada bilangan yang belum terjamah di antaranya!

Alasan lain yang lebih realistis, adalah bahwa hanya ada sedikit sekali pengetahuan umat manusia yang terkumpul selama berabad-abad mengenai bilangan ini. Tidak lebih dari 20 kelas bilangan yang sejauh ini berhasil dikonfirmasi sebagai bilangan transenden. Ada banyak bilangan yang dipercaya sebagai bilangan transenden, namun tidak pernah ada yang dapat memberi bukti formal mengenai hal tersebut (matematikawan tidak pernah menemukan suatu polinomial yang mengaproksimasi bilangan tersebut; namun belum dapat membuktikan bahwa memang tidak mungkin ada polinom yang seperti demikian). Sebagai referensi, pembaca dapat meninjau https://en.wikipedia.org/wiki/Transcendental_number#Numbers_proven_to_be_transcendental . Fakta bahwa puluhan ribu matematikawan dari segala abad menemukan kebuntuan untuk memahami perilaku bilangan ini, menjadi alasan utama mengapa bilangan transenden begitu jauh dari kehidupan kita sehari-hari. Begitu jauhnya pemahaman umat manusia akan hal ini hingga beberapa matematikawan eksentrik memutuskan untuk tidak mempercayai eksistensi bilangan ini, dan bahkan menuduh bahwa bilangan nyata sebetulnya hanyalah ilusi.

Namun demikian, bilangan yang pemahamannya begitu melampaui pengertian kita ini sebetulnya ada banyak sekali di sepanjang garis bilangan, bahkan lebih banyak dan melimpah dibanding bilangan aljabar! Inilah yang penulis maksudkan dengan imanensi bilangan transenden.

Untuk memahami fenomena ini, kita akan melihat beberapa pengertian mengenai bagaimana kita mengukur suatu himpunan memiliki anggota yang lebih banyak dibanding himpunan lain. Sebagai contoh, dengan mudah kita dapat menyimpulkan bahwa himpunan bilangan bulat positif kurang dari satu milyar memiliki anggota lebih sedikit dibanding himpunan semua bilangan bulat positif. Namun apa yang dapat kita katakan tentang himpunan bilangan ganjil dan himpunan bilangan genap? Mana yang lebih banyak? Secara intuitif mungkin kita dapat katakan sama banyak. Lalu mana yang lebih banyak, himpunan bilangan prima atau himpunan bilangan bulat kelipatan 5? Bagaimana kita membandingkannya?

Dalam teori himpunan, kardinalitas suatu himpunan A , dinotasikan |A| menyatakan ukuran seberapa banyak anggota himpunan tersebut. Dua buah himpunan A dan B dikatakan berkardinalitas sama, yaitu |A|=|B|, jika kita dapat memasangkan setiap anggota A dengan tepat satu anggota B dan tidak ada anggota B yang tidak punya pasangan. Sebagai contoh, misal A dan B secara berturut-turut menyatakan himpunan bilangan bulat positif dan bilangan genap. Maka untuk setiap bilangan positif a\in A, kita dapat memasangkan a dengan 2a, yang merupakan anggota B. Selain itu jika kita ambil sebarangan bilangan genap b\in B, dengan cepat kita tahu bahwa b/2 pasti bilangan bulat positif di A yang dipasangkan dengan b. Artinya, himpunan bilangan bulat positif berkadinalitas sama dengan himpunan bilangan genap, atau dengan kata lain, banyaknya bilangan genap sama dengan banyaknya bilangan bulat positif. Secara sekilas, argumen ini memang counter-intuitive, namun inilah kenyataannya. Banyak hal aneh dan lucu terjadi saat kita melibatkan ketakberhinggan dalam bermatematika.

Pertanyaan selanjutnya: manakah yang lebih banyak, bilangan bulat atau bilangan rasional? Georg Cantor, seorang matematikawan Jerman abad 19, membuktikan bahwa bilangan bulat sama banyaknya dengan bilangan rasional. Argumen yang mendasari hal ini adalah argumen diagonalisasi Cantor yang sangat terkenal. Kita dapat memasangkan bilangan bulat secara berurutan dari 1 dan seterusnya dengan bilangan-bilangan rasional dengan cara mengikuti arah anak panah sebagaimana tertera pada gambar di bawah.

sv74l75a

Hal ini merupakan sesuatu yang mengejutkan! Seharusnya bilangan rasional jauh lebih banyak dibanding bilangan bulat, karena bahkan di antara dua bilangan bulat saja, ada tak berhingga banyaknya bilangan rasional pecahan di antaranya. Bagaimana mungkin keduanya memiliki kardinalitas yang sama? Inilah keindahan dan keagungan matematika. Untuk penjelasan lebih dalam, pembaca dapat melihat https://bermatematika.net/2016/06/20/paradoks-hotel-hilbert/. Untuk selanjutnya, semua himpunan yang berkardinalitas sama dengan bilangan bulat akan kita sebut sebagai himpunan tercacah (countable set).

Lebih lanjut lagi, Cantor juga membuktikan bahwa perkalian kartesian dari dua himpunan tercacah, juga merupakan himpunan tercacah. Lebih jauh lagi, perkalian kartesian dari sejumlah tercacah kumpulan himpunan tercacah juga masih merupakan himpunan tercacah. Fakta ini mengimplikasikan fakta bahwa himpunan semua bilangan aljabar adalah himpunan tercacah.

Namun demikian, Cantor memberi bukti bahwa bahwa himpunan bilangan nyata bukan himpunan tercacah. Bukti pernyataan ini cukup sederhana. Seandainya, bilangan nyata tercacah, maka kita dapat memasangkan semua bilangan bulat dengan tepat satu bilangan nyata dan semua bilangan nyata memiliki pasangan bilangan bulat. Misalkan k adalah bilangan bulat dan S_k merupakan bilangan nyata pasangannya. Kita akan melihat representasi desimal bagian pecahan S_k, misalkan S_k= 0.a_{k0}a_{k1}a_{k2}\dots. Lalu, definisikan bilangan nyata s=0.a_{11}a_{22}a_{33}\dots, yaitu bagian diagonal dari enumerasi representasi desimal bilangan nyata tersebut. Dengan mendefinisikan bilangan nyata lain r=0.b_{11}b_{22}b_{33}\dots dan memilih b_{ii}\neq a_{ii} untuk setiap i, kita dapat yakin bahwa tidak ada satupun bilangan bulat yang dipasangkan dengan r, suatu kontradiksi. Dengan demikian, himpunan bilangan nyata tidak tercacah.
annot2292bFakta ini sangat penting, karena ini menunjukkan bahwa bilangan nyata secara signifikan jauh lebih banyak dibanding bilangan bulat. Namun demikian, karena kita tahu bahwa bilangan aljabar juga tercacah, maka bilangan nyata jauh lebih banyak dibanding bilangan aljabar.

Fakta ini kemudian berakibat bahwa bilangan transenden haruslah jauh lebih banyak ketimbang bilangan aljabar. Mengapa demikian? Karena himpunan semua bilangan transenden tidak tercacah. Perhatikan bahwa gabungan dua himpunan tercacah haruslah tercacah pula. Seandainya bilangan transenden tercacah, maka himpunan bilangan irasional (yang adalah gabungan bilangan transenden dan bilangan aljabar) juga tercacah. Lalu, karena bilangan rasional tercacah, seharusnya bilangan real (yang adalah gabungan bilangan rasional dan bilangan irasional) juga tercacah, suatu kontradiksi!

Fakta bahwa bilangan transendental begitu melimpah dan banyak sekali ditemukan di sepanjang garis bilangan nyata semakin membuat realitas mengenai sedikitnya bilangan transenden yang ditemukan sepanjang sejarah menjadi misteri yang semakin jaya. Ada tak berhingga banyaknya bilangan transenden. Meskipun ada tak berhingga banyaknya bilangan bulat, ketakberhinggaan banyaknya bilangan transenden memiliki derajat yang lebih besar lagi. Jika kita tidak dapat bayangkan bagaimana ujung dari pencacahan bilangan bulat, dapatkah kita bayangkan bagaimana cara untuk mencacah bilangan transenden? Namun demikian, tidak sampai 20 keluarga bilangan yang terkonfirmasi merupakan bilangan transendental di sepanjang basis data pengetahuan peradaban manusia sepanjang sejarah! Di manakah jutaan, atau milyaran, atau apalah itu bilangan transenden yang lain? Kita tidak tahu! Dapatkah kita membayangkan seberapa tersembunyinya bilangan-bilangan itu dalam pengertian kita? Yang kita ketahui hanyalah ada banyak sekali bilangan transenden, namun kita tidak pernah benar-benar tahu yang mana sajakah bilangan itu.

Secara teoretis, jika kita mengambil sembarang bilangan nyata secara murni acak, maka dengan peluang nyaris mendekati 100%, kita akan dapatkan sebuah bilangan transenden. Namun betulkah demikian? Secara realitas, tanyakan kepada sembarang orang yang lewat agar mereka menyebut suatu bilangan nyata secara acak. Dengan peluang nyaris mendekati 0% orang tersebut menyebut suatu bilangan transenden. Bagaimana mungkin ini terjadi? Karena pengetahuan manusia tentang bilangan begitu sempit dan kecil. Beribu-ribu tahun umat manusia berestafet mengejar ujung ilmu pengetahuan, namun hasil penyelidikan manusia begitu memutuskan harapan. Sejak zaman prasejarah, manusia sudah mengenal bilangan, namun setelah ribuan tahun, pengetahuan kita tentang bilangan hanya bertambah sekitar 0% dari semua bilangan yang sebetulnya sudah eksis sejak kekekalan. (proporsi kardinalitas himpunan tercacah dibanding kardinalitas himpunan tidak tercacah, jika dihitung dengan teori ukuran, adalah betul-betul nol)

Inilah imanensi bilangan transenden! Bilangan transenden begitu berlimpah-limpah. Jika kita mengukur lebar suatu pita, kemungkinan besar kita akan mendapati bilangan transenden tanpa sebenarnya kita mengenal seperti apakah bilangan itu. Jika kita mengukur volume pewangi ruangan, hampir pasti volume cairan itu adalah bilangan transenden yang kita kira adalah bilangan bulat. Bilangan transenden ada di mana-mana! Mereka mengepung kita. Kita melihat mereka setiap hari namun bahkan tidak pernah sadar bahwa mereka ada. Bagaimana mungkin? Inilah misteri imanensi yang transenden. Inilah mengagumkannya transendensi yang imanen.

Tidak perlu kita melancong ke antariksa sejauh jutaan tahun cahaya untuk menyadari seberapa kecil kita di tengah raksasa transendensi yang menenggelamkan kita. Bahkan di tengah pengetahuan paling mendasar dalam benak kita, tersimpan misteri besar yang tidak pernah kita pedulikan. Maka benarlah perkataan Sokrates yang mengatakan bahwa bijaksana tertinggi adalah menyadari diri tidak mengerti apapun. Jika Anda masih merasa bahwa Andalah pusat semesta, Anda betul-betul belum keluar dari tempurung Anda. Kita jelas bukan pusat dari semesta ini. Namun ketika kita beroleh hidup dan pengertian, bukankah ini keajaiban yang lain? Selayaknya kah kita yang begitu tak berarti di tengah samuderan transendesi menerima pengertian? Kekuatan macam manakah yang memampukan kita sejauh ini?

Peluang kecelakaan Satu di antara Sejuta: Jika 999.999 selamat dan Anda orang ke-sejuta, Masihkah Anda Melanjukan?

Seorang sahabat pernah menceletukkan pikiran isengnya yang sangat legitimate untuk dipertanyakan: misalnya kecelakaan suatu maskapai penerbangan adalah 1 dibanding 1.000.000. Seandainya kita tahu bahwa 999.999 penerbangan sebelumnya selamat, dan kita akan memasuki penerbangan yang ke 1.000.000. Beranikah kita masuk ke dalam pesawat itu? Pastikah terjadi kecelakaan di penerbangan tersebut?

Ini adalah pertanyaan yang sangat menarik! Jika ternyata penerbangan itu tidak mengalami kecelakaan, bukankah ini berarti bahwa peluang kecelakaannya tidak lagi satu dibanding sejuta (karena dari 1 juta penerbangan, tidak ada satupun yang kecelakaan)? Lalu jika memang “selalu” ada 1 dari sejuta penerbangan yang mengalami kecelakaan, apa itu berarti penerbangan ke-sejuta kita pasti kecelakaan?

Untuk meluruskan kebingungan ini, kita perlu mendefinisikan ulang apa makna peluang suatu kejadian dan distribusinya. Pertama-tama, perlu kita pahami bahwa biasanya, statistik yang diberikan media tentang suatu kejadian (katakanlah kecelakaan pesawat) adalah estimasi berdasarkan data historis. Artinya, nilai proporsi ini bukan nilai yang sesungguhnya, tapi dengan selang kepercayaan tertentu, kita dapat yakin estimasi ini cukup “dekat” dengan proporsi dalam dunia nyata. Lebih jauh lagi, nilai estimasi ini sangat bergantung pada data historis yang dimiliki sebelumnya. Hal ini akan semakin jelas setelah kita diskusikan bagian berikut.

Untuk memahami fenomena ini, kita akan memakai model yang jauh lebih umum dan lebih mudah untuk dianalisis. Misalkan ada n (pilih n cukup besar nanti, minimal sejuta lah) buah apel dalam keranjang dan hanya ada 1 buah yang busuk di antaranya. Maka, dengan cepat kita dapat simpulkan bahwa ketika kita ambil sebuah apel secara acak, peluang kita peroleh apel busuk adalah satu dibanding n. Perhatikan bahwa nilai peluang dalam kasus ini adalah nilai eksak dan bukan estimasi. Peluang mendapatkan apel busuk adalah betul-betul 1/n. Lalu jika kita lakukan pengambilan buah secara acak (dan setelah diambil, buah dikembalikan lagi) sebanyak n-1 kali dan selalu diperoleh apel yang baik, berapa peluang apel ke sejuta busuk? Perhatikan bahwa jika semua pengambilan selalu disertai dengan pengembalian, maka pemilihan buah dalam suatu percobaan tidak bergantung pada pemilihan buah dalam percobaan yang lain. Dalam bahasa statistik, setiap pengambilan buah saling bebas satu sama lain. Dengan demikian, jika kita diberi informasi bahwa n-1 pengambilan pertama tidak memberikan apel busuk, informasi itu tidak memberi pengaruh apapun dalam perhitungan peluang apel ke-sejuta. Dengan kata lain, peluang busuknya apel kesejuta sama dengan peluang busuknya apel pertama, yang tidak lain adalah 1/n. Anehkah? Jika kita tetapkan n=6, maka kasus ini akan sama dengan kasus melempar dadu. Peluang kita peroleh angka 1 adalah 1/6. Lalu, jika kita melempar dadu sebanyak 5 kali dan kita tidak peroleh angka 1, berapa peluang dadu keenam bermata 1? Tentu 1/6 bukan, sama seperti pelemparan yang lain? Ya, tidak ada yang aneh dari semua perhitungan ini.

Namun demikian, kita dapat kembali mempertanyakan hal ini dengan cara yang berbeda. Bukankah peluang pengambilan apel busuk satu dibanding n berarti bahwa dalam n kali pengambilan, ada satu diantaranya yang busuk? Jadi apa hal ini menjamin dalam n kali pengambilan, pasti ada 1 apel busuk? Jawabannya adalah TIDAK. Kita akan buktikan secara matematis. Dalam sekali pengambilan, peluang terambil apel sehat adalah \left(1-\dfrac{1}{n}\right). Maka, peluang tidak ditemukan apel busuk dalam n kali pengambilan adalah \left(1-\dfrac{1}{n}\right)^n, yang konvergen menuju 1/e\approx 0.3679 ketika n\rightarrow \infty. Perhatikan bahwa nilai ini berbeda dengan nilai peluang yang kita analisis di paragraf sebelumnya (di sini, tidak ada syarat/kondisi yang diberikan). Jadi, perhitungan kita mengatakan bahwa TIDAK PASTI bahwa selalu ditemukan satu apel busuk dalam n kali pengambilan; lebih tepatnya kejadian ini terjadi dengan peluang sekitar 36.79%, suatu angka yang lebih kecil dari 100%.

Sekarang, mari kembali ke cerita pesawat kita. Dalam kasus ini, nilai peluang satu dibanding sejuta bukanlah nilai peluang secara eksak, karena kita tidak bisa membuktikan secara matematis bahwa proporsi kecelakaan pesawat secara apriori memang betul-betul tepat 1 dibanding sejuta. Lalu bagaimana kita dapat mengklaim nilai peluang ini? Kemungkinan besar nilai ini diperoleh dari estimatornya, yang didapat dari pengolahan data sebelumnya. Tentu perhitungan estimator ini mengasumsikan distribusi terjadinya kecelakaan saat ini sama dengan di waktu yang lampau dan kejadian kecelakaan setiap penerbangan saling bebas satu sama lain. Tentu karena perhitungan kita adalah estimasi, maka kita akan selalu memiliki error. Menariknya, kejadian yang terjadi saat ini dapat mengubah nilai estimator menjadi lebih akurat, padahal di saat yang sama nilai estimator tersebut dalam prakteknya digunakan untuk memprediksi realisasi kejadian tersebut. Dengan kata lain, ketika seseorang dapat menyimpulkan peluang kecelakaan adalah 1 banding sejuta, maka sebetulnya sudah ada cukup banyak penerbangan yang sudah diambil data sampelnya (minimal sejuta). Dan sebaliknya, jika kita hanya mengetahui data 999.999 penerbangan saja, kita belum dapat menyimpulkan bahwa estimator peluang kecelakaan adalah 1 banding sejuta. Dengan demikian, cerita yang menjadi pokok permasalahan kita kurang realistis dan mengasumsikan proposisi yang kurang tepat.

Namun demikian, sekalipun kita dapat memperoleh nilai peluang secara eksak (seperti dalam cerita apel busuk), toh BELUM PASTI bahwa selalui ada sebuah kecelakaan dalam sejuta kali penerbangan. Jadi, kepastian yang kita peroleh bahwa penerbangan ke-sejuta tidak pasti mengalami kecelakaan, datang dari dua hal: suku error dari estimator kita dan perhitungan peluang teoretik kita. Dengan demikian, ketika Anda tahu bahwa Anda adalah penumpang ke-sejuta, jangan panik dan buang-buang tiket Anda. Anda hanya perlu melihat angka statistik ini dari perspektif lain dan menyadarinya bahwa itu hanya tipuan belaka. 🙂

Berulang Tahun di Tanggal yang Sama, Kebetulankah?

Pernahkah Anda mengenal seseorang yang berulangtahun di tanggal yang sama dengan ulang tahun Anda? Mungkin Anda mengenal satu atau dua orang. Tentu saja tidak mungkin semua orang berulang tahun di hari yang sama dengan ulang tahun Anda. Ada 365 (atau 366 jika 29 Februari terhitung) kemungkinan tanggal ulang tahun yang dapat dimiliki oleh seseorang yang baru Anda kenal. Dengan demikian, peluang orang tersebut memiliki ulang tahun yang sama dengan Anda adalah 1 dibanding 365. Suatu proporsi yang cukup kecil, yang berarti bahwa Anda dapat berharap hanya ada 1 orang yang berulangtahun di hari ulang tahun Anda untuk setiap 365 orang yang baru Anda kenal. Berangkat dari pengamatan ini, Anda mungkin berpikir bahwa dua orang yang memiliki ulang tahun yang sama adalah kejadian yang tidak terlalu sering terjadi dalam skala yang cukup kecil. Namun benarkah hal ini?

Anda dapat menanyakan pada seorang guru kelas atau pegawai rumah sakit yang menyimpan data diri sejumlah murid atau pasien. Walaupun hanya ada cukup sedikit murid dalam suatu kelas, atau pasien yang masuk dalam satu hari, kerap sekali mereka menemukan setidaknya ada 2 orang yang berulangtahun di hari yang sama. Tentu saja, jika kita mengumpulkan data diri 366 orang, kita dapat memastikan adanya suatu tanggal yang menjadi ulang tahun 2 orang atau lebih, karena hanya ada 365 kemungkinan tanggal lahir (hal ini sering juga disebut prinsip sangkar merpati dalam matematika diskrit). Namun demikian, Anda boleh membuktikan melalui pengamatan pribadi Anda, bahwa Anda tidak perlu mengumpulkan sampai ratusan orang hanya untuk menemukan dua orang berulang tahun di tanggal yang sama. Bahkan, hanya dengan mengumpulkan data diri 25 orang saja, Anda mungkin akan menemukan fenomena ini dengan peluang yang cukup tinggi.

Secara sekilas, pernyataan di atas mungkin terdengar mengherankan, karena jika kita hanya memiliki 25 data yang secara acak yang terambil dari 365 kemungkinan yang ada, data tersebut seharusnya “terpencar-pencar” ke seluruh kemungkinan tanggal yang ada dan tidak seharusnya saling “bertabrakan” karena masih ada banyak “tanggal kosong” yang belum terpakai. Namun demikian, fakta matematis dapat menunjukkan bahwa memang peluang terjadinya fenomena ini cukup tinggi, yaitu 56,87%. Lebih jauh lagi, jika kita menambah data menjadi 58 orang, kita sudah memiliki peluang sebesar 99%!

Bagaimana kita dapat memperoleh angka ini? Kita akan mengasumsikan bahwa tidak ada orang yang berulang tahun di 29 Februari, sehingga hanya ada 365 kemungkinan tanggal. Juga kita asumsikan bahwa proporsi tanggal kelahiran seluruh umat manusia berdistribusi seragam, artinya tidak ada satu tanggal yang bertendensi untuk memiliki lebih banyak orang yang lahir di tanggal tersebut, dibanding dengan tanggal yang lain.

Katakanlah kita mempunyai k\le 365 buah data. Perhitungannya cukup sederhana. Kita akan menghitung peluang kejadian komplemennya, yaitu peluang setiap orang memiliki ulang tahun yang berbeda. Kita akan menghitung peluang tidak adanya ulang tahun bersama selangkah demi selangkah. Ketika kita menginput data pertama, tentu tidak mungkin kita menemukan ulang tahun bersama, karena hanya ada 1 buah data yang kita miliki. Untuk memastikan tanggal inputan kedua berbeda dengan tanggal data pertama, hanya ada 364 kemungkinan dari 365 kemungkinan yang dimiliki oleh data kedua tersebut (karena 1 tanggal sudah dipakai oleh data pertama). Demikian seterusnya sampai data ke-k dimasukkan, hanya ada 365-k+1 kemungkinan dari 365 kemungkinan yang ada. Dengan demikian, peluang kejadian yang kita harapkan adalah perkalian dari peluang kejadian tidak adanya ulang tahun bersama yang sudah kita uraikan selangkah demi selangkah, yaitu

\dfrac{365}{365}.\dfrac{364}{365}.\dfrac{363}{365}\dots\dfrac{365-k+1}{365}

Perkalian bilangan-bilangan ini dapat dengan mudah kita hitung menggunakan aplikasi spreadsheet. Ingat bahwa nilai yang kita hitung adalah kejadian komplemennya. Dengan demikian, peluang adanya ulang tahun bersama adalah 1 dikurang nilai peluang komplemen tersebut. Berikut merupakan screenshot perhitungan dalam spreadsheet.

25      58

Mengejutkan! Tanpa perlu menampung data yang terlalu banyak, kita hampir selalu dapat menemukan orang-orang yang berulangtahun di hari yang sama!

Jika kita melihat lebih dalam, fenomena ini dapat diperumum ke dalam konteks yang lebih luas. Seandainya terdapat n buah kemungkinan tanggal (pada kenyataannya memang hanya ada 365 tanggal, tapi kita akan sedikit bermain-main untuk melihat hal menarik lainnya). Maka pertanyaan yang menarik adalah seberapa sedikit data yang perlu kita kumpulkan untuk memastikan bahwa ada data yang memiliki ulang tahun bersama dengan peluang yang cukup besar?

Pertama, kita akan sedikit memperjelas definisi matematis pertanyaan ini. Seberapa “besar” kah peluang yang “cukup besar” yang ingin kita capai? Pertanyaan ini akan kita jawab secara asimtotik, yaitu bagaimana nilai peluang ini berperilaku ketika nilai n sangat besar. Secara matematis, kita akan mencari nilai limit peluang tersebut ketika n\rightarrow \infty. Mengapa membicarakan suatu nilai yang sangat besar menjadi menarik? Karena jika nilai n berhingga, yaitu suatu konstanta saja, kita dapat melakukan komputasi dengan cukup mudah melalui bantuan komputer. Dan, ketika kita dapat memahami apa yang terjadi di suatu nilai yang sangat besar, kita dapat memahami apa yang terjadi di nilai yang lebih kecil dengan lebih mudah. Dengan demikian, kita definisikan suatu kejadian dikatakan terjadi “dengan peluang cukup besar” jika limit peluang kejadian tersebut mendekati 1 ketika n\rightarrow \infty.

Dengan demikian, pertanyaan di atas dapat diformulasikan sebagai berikut: Carilah suatu fungsi k(n) terkecil (secara asimtotik), sehingga ketika kita mengumpulkan k(n) data tanggal lahir, ada setidaknya 2 data yang memiliki ulang tahun yang sama dengan peluang cukup besar. Dengan cara yang sama, kita akan mencoba untuk menghitung peluang kejadian komplemennya. Dengan kata lain, kita mencari k(n) terkecil sehingga peluang tidak adanya ulang tahun bersama di antara k(n) data menuju 0. Katakanlah p_k merupakan nilai peluang tersebut. Maka

p_k=\dfrac{n}{n}.\dfrac{n-1}{n}\dots\dfrac{n-k+1}{n}=\left(1-\dfrac{0}{n}\right) . \left(1-\dfrac{1}{n}\right)\dots \left(1-\dfrac{k-1}{n}\right)=\prod\limits_{i=0}^{k-1} \left(1-\dfrac{i}{n}\right)

Kita akan mengaproksimasi nilai ini melalui ketidaksamaan (1-x)\le e^{-x}, yang berlaku untuk semua bilangan real x (dapat dibuktikan dengan kalkulus sederhana). Dengan demikian, kita dapatkan

p_k \le \prod\limits_{i=0}^{k-1} e^{-i/n} = \exp\left(-\sum\limits_{i=0}^{k-1} \frac{i}{n}\right) = \exp\left(-\dfrac{O(k^2)}{n}\right)

di mana kesamaan terakhir diperoleh dari rumus deret aritmatika. Dengan demikian, jika kita memilih k(n) sehingga k^2/n merupakan barisan yang menuju tak berhingga saat n\rightarrow \infty, kita akan mendapati p_k \rightarrow 0. Dengan demikian, fungsi apapun yang “lebih besar” dari \sqrt{n} akan membuat p_k \rightarrow 0. Secara matematis, kita dapat menulisnya sebagai berikut, k(n)=\sqrt{\omega n} untuk sembarang \omega=\omega(n), barisan yang divergen selambat apapun itu (arbitrarily slowly). Jadi, ketika k(n)= \sqrt{\omega n}, kita akan menemukan ulang tahun bersama “dengan peluang cukup besar”.

Di sisi lain, ketika kita memiliki k(n)=\Theta(\sqrt{n}), kita akan dapati bahwa p_k=e^{O(1)}, artinya p_k konvergen ke suatu nilai peluang yang positif. Artinya ketika \Theta(\sqrt{n}), kita tidak akan menemukan ulang tahun bersama “dengan peluang cukup besar”. Dengan demikian, simpulan atas penyelidikan kita adalah: \Theta(\sqrt{n}) ada fungsi terbesar sehingga kita tidak akan menemukan ulang tahun bersama “dengan peluang cukup besar” dengan k(n) buah data.

Sebagai contoh, jika kita ambil k(n)=\sqrt{n\log n}, maka p_k\le O(1/n). Ini berarti bahwa ketika kita memiliki \sqrt{n\log n} data, peluang kita tidak mendapati ulangtahun bersama hanya kira-kira sebesar 1/n, suatu nilai yang sangat kecil, bahkan semakin kecil ketika n membesar. Dari n kemungkinan, hanya diperlukan \sqrt{n\log n} data saja untuk mendapatkan ulang tahun bersama “dengan peluang cukup besar”. \sqrt{n\log n} adalah suatu nilai yang sangat kecil dibanding n. Sebagai perbandingan, jika n=10000, maka \sqrt{n\log n} \approx 303,48, suatu nilai yang secara signifikan jauh lebih kecil! Secara sekilas tidak terlihat masuk akal, namun perhitungan matematis membuktikannya!

Jadi, apakah memiliki ulang tahun bersama adalah suatu hal yang jarang? Tentu ya jika Anda membandingkan dengan ulang tahun Anda secara spesifik. Tapi ketika Anda mengumpulkan sedikit data namun dengan cepat menemukan sekelompok orang yang memiliki tanggal ulang tahun yang sama, itu bukan suatu kebetulan. Ada suatu realitas di luar sana yang mengatur bahwa hal semacam ini adalah memang wajar adanya, kendatipun intuisi kita tidak selalu sinkron dengannya. Ada suatu paradox yang mengejutkan, yang tersembunyi secara anggun di balik kesederhanaan yang universal.

Pintu Rahasia Teorema Graf Ekstremal: sebuah pendekatan probabilistik

Teori graf ekstremal merupakan salah satu cabang ilmu teori graf yang berkembang paling pesat pada masanya. Pada dasarnya, bidang ini menyelidiki batasan-batasan parameter dari suatu graf ketika kepadanya kita terapkan suatu sifat tertentu (extremal property). Disiplin ilmu ini pertama kali dipopulerkan oleh Paul Turán, seorang matematikawan terkemuka Hungaria, dengan melontarkan sebuah pertanyaan yang pada akhirnya menjadi suatu penyelidikan yang sangat menarik di kalangan kaum akademisi pada saat itu.

Pertanyaan tersebut adalah: jika diketahui sebuah graf G dengan orde (banyak titik) n tidak memiliki K_q sebagai subgraf, berapakah ukuran (banyak sisi) maksimum yang mungkin untuk G? Jika q=3, maka pertanyaan tersebut akan mencari ukuran terbesar suatu graf yang tidak memuat segitiga. Dengan cepat mungkin kita akan membayangkan graf bipartit sebagai graf tanpa segitiga. Untuk menampung sebanyak mungkin sisi, kita buat bipartit ini menjadi bipartit lengkap dengan ukuran kelas partisi serata mungkin. Tentu semua graf bipartit tidak memuat segitiga, namun apakah kita yakin bahwa tidak ada struktur graf lain yang sama-sama tidak memuat segitiga, namun bisa lebih padat dari bipartit lengkap? Jauh sebelum Turán, pada tahun 1907 Mantel telah membuktikan bahwa jawaban atas pertanyaan tadi adalah ya. Masalah yang menjadi titik perhatian Turán adalah perumuman masalah Mantel. Menariknya, solusi masalah tersebut rupanya juga merupakan perumuman langsung dari solusi Mantel.

Dalam graf (q-1)-ary lengkap, yaitu graf dengan q-1 kelas partisi titik dan ada sisi di antara dua titik jika dan hanya jika kedua titik berada di kelas yang berbeda, kita dapat yakin bahwa di dalamnya tidak mungkin termuat subgraf lengkap dengan q titik. Namun demikian, Turán juga menyatakan bahwa tidak ada graf lain yang lebih padat dari graf (q-1)-ary yang memiliki sifat yang sedang kita cari. Temuan Turán ini menjadi dasar yang mengukuhkan teori graf ekstremal dan untuk mengapresiasi mahakaryanya, graf ektremal ini dinamai atas nama keluarganya. Graf Turán dengan n titik adalah graf (q-1)-ary lengkap dengan kelas partisi dengan kardinalitas n_1,n_2,\dots,n_{q-1} di mana |n_i-n_j|\le 1 untuk setiap i\neq j. Atau dengan kata lain, kita membagi n titik dalam graf tersebut ke dalam q-1 kelas serata mungkin dan membangkitkan sisi dari sembarang titik dari dua kelas yang berbeda. Berapakah ukuran graf Turán? Jika n habis dibagi q-1, maka kita dapat memilih ukuran kelas partisi yang uniform, yaitu n_i=n/(q-1) dan kemudian graf tersebut akan memiliki sisi sebanyak {q-1 \choose 2} (n/(q-1))^2=(1-1/(q-1))n^2/2. Ini merupakan nilai ekstremal dari ukuran graf tanpa subgraf lengkap K_q. Secara formal, Teorema Turán berkata sebagai berikut.

Jika G graf dengan n titik tidak memiliki K_q sebagai subgraf (q\ge 2), maka

|E(G)| \le \left(1-\dfrac{1}{q-1}\right) \dfrac{n^2}{2}

Turán membuktikan teoremanya dengan argumen induksi, yang (mengejutkannya) cukup sederhana. Namun demikian, yang membuatnya makin menarik adalah bukti probabilistik yang diberikan oleh Noga Alon, kombinatorikawan Israel dan Joel Spencer, kombinatorikawan Amerika Serikat dalam buku mereka, “The Probabilistic Methods”. Aigner dan Ziegler mempertimbangkan bukti Alon & Spencer sebagai bukti yang “berasal dari sang buku” (proof from the book), suatu legenda mengenai kumpulan bukti & argumen matematika yang ‘cantik’ yang dipopulerkan oleh Paul Erdos.

Walaupun sampai saat ini pembuktikan masalah kombinatorik dengan teknik probabilistik sudah sangat populer, bukti Alon & Spencer ini masih cukup mengejutkan, karena argumen mereka berangkat dari suatu titik yang sama sekali tidak terlihat ada kaitannya dengan masalah ekstremal ini. Dan karenanya, bukti ini layak untuk meraih gelar “berasal dari sang buku”. Pada dasarnya, bukti ini akan menggunakan sifat linearitas ekspektasi, ketidaksamaan Cauchy-Schwarz, dan lema jabat tangan teori graf. Berikut merupakan bukti Alon-Spencer untuk teorema Turán.

Bukti:

Pertama, kita definisikan bilangan clique dari suatu graf G, dinotasikan \omega(G), yaitu bilangan bulat positif q terbesar sehingga K_q merupakan subgraf dari G. Misalkan G graf dengan himpunan titik \{v_1,\dots,v_n\} dan titik v_i memiliki derajat d_i. Kita akan terlebih dahulu membuktikan suatu klaim, yaitu

\omega(G) \ge \sum\limits_{k=1}^n \dfrac{1}{n-d_i}

Untuk membuktikan klaim ini, kita akan membangun suatu ruang peluang. Misalkan \sigma adalah suatu n-permutasi acak yang dipilih secara uniform, artinya setiap n-permutasi muncul dengan peluang 1/n!. Kemudian, kita definisikan himpunan (acak) A_\sigma di mana titik v_{\sigma (j)}\in A_\sigma jika dan hanya jika v_{\sigma (j)} bertetangga dengan v_{\sigma (i)} untuk semua i<j. Berdasarkan definisi ini, titik-titik di A_\sigma membentuk subgraf lengkap di G. Selanjutnya, kita akan mencari rata-rata kardinalitas A_\sigma. Misalkan X merupakan peubah acak kardinalitas A_\sigma dan X_i adalah peubah acak indikator v_i \in A_\sigma. Ekspektasi X_i bernilai sama dengan peluang kejadian v_i \in A_\sigma. Perhatikan bahwa v_i \in A_\sigma jika dan hanya jika dalam \sigma, v_i muncul sebelum semua titik yang tidak bertetangga dengannya (ada n-1-d_i titik). Untuk memilih urutan posisi d_i tetangga v_i, ada [n]_{d_i} cara. Setelah itu, kita posisikan v_i pada posisi pertama yang belum ditempati oleh tetangga-tetangga v_i. Baru setelah itu, kita dapat dengan bebas mengatur posisi n-1-d_i titik sisanya dan terdapat (n-1-d_i)! cara untuk mengaturnya. Ini berarti bahwa \mathbb{E}X_i= [n]_{d_i} (n-1-d_i)! /n! = 1/(n-d_i). Selanjutnya, berdasarkan sifat linearitas ekspektasi, kita dapat simpulkan bahwa

\mathbb{E}X=\sum\limits_{k=1}^n \mathbb{E} X_i =\sum\limits_{k=1}^n \dfrac{1}{n-d_i}

Fakta ini menunjukkan bahwa kejadian A_\sigma berkardinalitas setidaknya \mathbb{E}X memiliki peluang tak nol. Artinya, haruslah ada suatu himpunan (deterministik) A dengan |A|\geq \mathbb{E}X dan titik-titik di A membentuk subgraf lengkap. Dengan demikian, kita sudah membuktikan klaim kita.

Selanjutnya kita akan menggunakan ketidaksamaan Cauchy-Schwarz sebagai berikut.

\left( \sum\limits_{k=1}^n a_k b_k \right) ^2 \leq \left( \sum\limits_{k=1}^n a_k^2\right) \left( \sum\limits_{k=1}^n b_k^2\right)

Sekarang, kita tetapkan a_k=\sqrt{n-d_k} dan b_k=1/\sqrt{n-d_k}. Kita lihat bahwa ruas kiri menjadi n^2, sementara ruas kanan menjadi

\left(\sum\limits_{k=1}^n (n-d_i)\right) \left(\sum\limits_{k=1}^n \dfrac{1}{n-d_i} \right) \le \omega(G) \left(\sum\limits_{k=1}^n (n-d_i)\right)

Selanjutnya, karena G tidak memiliki K_q sebagai subgraf, maka \omega(G)\le q-1. Selain itu, dengan menggunakan lema jabat tangan (\sum\limits_{k=1}^n d_i=2|E(G)|), kita bisa memperoleh \left(\sum\limits_{k=1}^n (n-d_i)\right) = n^2-2|E(G)|. Dengan demikian, kita mempunyai

n^2 \le (q-1)(n^2-2|E(G)|)

dan ketidaksamaan ini tidak lain adalah pernyataan teorema Turán itu sendiri.

Komentar:

Bagaimana kita dapat mengapresiasi keindahan teorema dan bukti ini? Teorema ini berdasar dari suatu permasalahan yang cukup sederhana untuk dinyatakan (tidak perlu pendefinisian berbagai terminologi yang rumit). Lebih jauh lagi, solusi yang ditawarkan untuk menjadi kandidat struktur ekstrem yang Turán tawarkan begitu naif dan sederhana. Jika Anda mencoba untuk mencari bukti Anda sendiri tanpa mempelajari argumen-argumen di atas, saya cukup yakin Anda akan memikirkan struktur graf Turán dalam percobaan induktif Anda. Namun demikian, kandidat solusi ini sepertinya terlalu naif untuk menjadi struktur ekstrem yang kita cari. Kenyataannya, pembuktiannya memang tidak terlalu straightforward. Hal yang membuatnya makin indah adalah ide liar Spencer dan Alon untuk mengikutsertakan unsur keacakan pada ruang peluang yang tidak terduga, yaitu pemilihan elemen secara uniform acak di ruang permutasi, sesuatu yang sangat tidak natural untuk muncul dalam intuisi matematis orang pada umumnya. Pada kenyataannya, klaim sampingan pada bukti di atas sebetulnya tidak hanya memberi manfaat besar untuk kebutuhan kita. Kita lihat ketika klaim ini kita terapkan pada komplemen graf G, maka kita akan peroleh batas bawah untuk bilangan kebebasan (indepence number) dari suatu graf, yang akan sangat berguna untuk kasus yang lain. Ketidaksamaan ini kemudian dipadukan dengan begitu cerdik dengan ketidaksamaan terkenal Cauchy-Schwarz untuk menghasilkan pintu masuk rahasia kepada Teorema Turán. Pendekatan ini begitu tak terduga dan diatur dengan sangat dramatis untuk memperoleh efek ketakjuban yang sangat memuaskan gairah bermatematika. Itulah sebab bukti ini sangat layak untuk masuk dalam segelintir koleksi bukti matematika terindah sepanjang zaman, sebagaimana Aigner dan Zieglier mengabadikannya dalam museum bukti matematis mahakarya mereka, “Proofs from the Book”.

Dual Space – The dual of the dual is itself

Good morning, Jakarta. (FYI, I’m on Jakarta now, preparing for our Chinese New Year family celebration :D)

Recently, I found some interesting algebraic properties of a vector space. Some kind of abstract object, however the term is popular among other areas of mathematics. Comments are pleased for correction & other additional information.

First, to make familiar with the ‘muggles’ (#orang awam matematik), let us define some terms:

A field F (+,\times ) is a set, such that for each a,b,c \in F the following is hold:

  • a+b = b+a
  • (a+b)+c = a+(b+c)
  • There exist 0 \in F such that 0+a=a+0=a
  • There exist \ -a \in F such that -a+a=a+(-a)=0
  • a\times b = b\times a
  • (a\times b)\times c = a\times (b\times c)
  • There exist 1 \in F such that 1\times a=a \times 1=a
  • There exist a^{-1} \in F-\{0\} such that $latex a^{-1} \times a=1$
  • a\times (b+c) = (a\times b) + (a\times c)
  • (b+c)\times a = (b\times a) + (c\times a)

A vector space V over a field F is a set, such that for each u,v,w \in V and a,b \in F the following is hold:

  • u+v = v+u
  • (u+v)+w = u+(v+w)
  • There exist 0 \in V such that 0+u=u+0=u
  • There exist \ -u \in V such that -u+u=u+(-u)=0
  • a(u+v)=au+av
  • (a+b)u=au+bu
  • a(bu)=(ab)u
  • There exist 1 \in F such that 1\times v=v \times 1=v

An isomorphism from a set A to B is a bijection from A to B in which the operations involved in each sets are preserved. Naively, to operate first then transform is the same as to transform first then operate.

A homomorphism from a set A to B is a mapping from A to B in which the operations involved in each sets are preserved. (no need the mapping to be a bijection)

The set A is said to be isomorphic to B if we can find any isomorphism from A to B.

Now let the magic begin. Suppose we have a vector space V over a field F. Then we can find some homomorphism from V to F. Moreover, if we collect every single homomorphisms and gather them in a set, namely S:=\{\varphi \mid \varphi homomorphism from V to F \} . Then we can make an operation + : S \times S \rightarrow S such that S is a vector space under operation +. Next, as we always construct a vector space S from arbitrary vector space V, we may define S as the dual space of V.

Well, we now have the structure of dual space. Now, let we have a vector space V and its dual V'. As the V' is also a vector space, we can construct its dual, let say V''. Magically, one had proven that V'' is then isomorphic to V. 2 isomorphic sets means that the two sets are algebraically equivalent. Then, we can conclude that every vector space is equivalent to the dual of its dual.

What a properties..

Moreover, the concept of duality is not only exist in linear algebra. You may check that the duality may appear on linear programming, graph theory, and so on. I believe that the concept of these things are not different. In abstract they are ‘isomorphic’, but somehow I have not discovered how the may come together as one.  That’s all guys. May the magical properties of algebra fulfil your heart. Thanks for your attention. 😀

Enjoy algebra!