Tagged: paradox

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.

Advertisements

Nothing Contains Everything: My Tiny Thought about Russel’s Paradox

Indonesian. 😀

Posting ini akan membahas suatu fakta matematis, yang pertama kali diperkenalkan oleh salah satu Bapak “Modern Set Theory”, Bertrand Russel. Bagi saya, fakta ini sangat mencengangkan; bahkan di luar akal sehat saya. Sangat menarik, dan membuat saya berpikir bahwa memang tidak pernah ada science yang pernah cukup rigorous dan detail untuk menjelaskan bagaimana alam bekerja. Memang perkembangan science dunia selalu berkembang, namun tingkat perkembangannya tidak pernah mencapai kesempurnaan, seperti grafik asimpotik; kita sudah sangat dekat dengan kesempurnaan, namun tidak pernah mencapainya. Bukan stagnan, tapi converge. Pembahasan ini saya ambilkan dari sebuah buku yang sangat baik, “Naive Set Theory”, karangan Paul R. Halmos; salah satu matematikawan yang paling berpengaruh di abad 20. A very recommended book. Yah, siapalah saya, saya hanya ingin membagikan what do I feel about this paradox. Hopefully, you may enjoy every single words of my writing. 🙂

Well, secara sekilas, fakta ini mengatakan bahwa tidak ada himpunan yang memuat semua himpunan; tidak dengan pengertian himpunan yang kita kenal dalam matematika sehari-hari. Karena jika seandainya ada, maka himpunan ini akan menemui kontradiksi dengan definisinya sendiri. How can it be? Baiklah, pertama-tama, I’ll present you one of the major principle of set theory. Prinsip ini terkenal dengan nama Aussonderungaxiom, atau dalam bahasa Indonesia, Aksioma spesifikasi. Prinsip ini berbunyi demikian:

Untuk sembarang himpunan A dan kondisi S(x) selalu terdapat sebuah himpunan B sedemikian sehingga setiap anggotanya merupakan anggota A dan memenuhi kondisi S(x).

Ah, aksioma yang terlalu trivial! Yah, saya yakin kita semua akan dengan cepat setuju dengan peryataan di atas. Ya memang begitu kan? Yes, That’s why we called it major principle. Penerapan aksioma di atas sesederhana penggunaan konsep himpunan dalam matematika sehari-hari. Bahkan anak-anak SD pun menggunakan aksioma ini tanpa halangan yang berarti. Sangat sederhana! Misalkan A merupakan himpunan semua wanita di dunia, dan S(x) adalah kondisi di mana x merupakan mahasiwa matematika. Berdasarkan dua hal di atas, kita dapat “memilah-milah” anggota himpunan A yang juga memiliki kondisi S(x), dan selanjutnya jika kita himpun semuanya, kita akan dapatkan himpunan B=\{ x\in A:S(x)\} =\{ x\in A:x mahasiswa matematika \} yang memenuhi sifat seperti yang dikemukanan pada aksioma di atas. Dengan demikian B merupakan himpunan semua mahasiswa matematika wanita.

Mudah! Namun mari kita lihat, jika kita pilih kondisinya S(x) sebagai berikut: “x\notin x“. Sebelum kita lanjut, ada baiknya supaya kita dapat membedakan notasi “\in” dengan “\subset“. Notasi yang pertama menunjukkan notasi keanggotaan, sementara yang terakhir merujuk pada keterhimpunan. (Detail mengenai 2 relasi ini dapat dicari di Google :p). Oke, lalu ambillah sembarang himpunan A. Berdasar aksioma di atas, kita dapat definisikan himpunan B=\{ x\in A:x\notin x\}. Well, per definisi kita tahu bahwa B\subseteq A. Tapi, pertanyaan yang mungkin menarik adalah, dapatkah kita menyimpulkan bahwa B\in A? Jawabannya adalah TIDAK. Pernyataan tersebut adalah SALAH.

Mengapa demikian? Andaikan pernyataan tersebut benar, yaitu B\in A. Maka dengan mempertimbangkan B sebagai subhimpunan A, kita memiliki dua pilihan, yaitu B\in B atau B\notin B. Oke kita bahas satu-satu. Pilihan pertama tidaklah mungkin. Karena jika B\in B, maka berdasar definisi B=\{ x\in A:x\notin x\}, haruslah B\notin B dan ini kontradiksi. Selanjutnya kita tinjau pilihan kedua. Jika B\notin B benar, maka per definisi B=\{ x\in A:x\notin x\}, B memenuhi syarat keanggotaan B sendiri, dan dengan demikian B\in B. Kontradiksi lagi. Karena itu kesimpulannya, haruslah B\notin A. (Paragraf ini mungkin paragraf yang paling sulit dipahami; saya sarankan Anda membaca paragraf ini berulang kali sebelum akhirnya Anda melanjutkan ke paragraf berikutnya)

Oke, perhatikan bahwa proses tersebut terjadi untuk sembarang himpunan. Jadi dengan demikian, untuk setiap himpunan, subhimpunannya yang dispesifikasi dengan kondisi S(x) tidak akan pernah menjadi anggota himpunan tersebut. Ini menunjukan bahwa untuk setiap himpunan A terdapat suatu himpunan B sehingga B\notin A. Dan dengan demikian, kita membuktikan bahwa tidak ada himpunan yang memuat semua himpunan. Bahkan kita dapat katakan bahwa tidak ada himpunan yang semua subhimpunannya merupakan anggota dari himpunan tersebut. (harap dapat dibedakan antara keterhimpunan dan keanggotaan) Dengan gayanya yang dramatis, Halmos mengungkapkan bahwa “Nothing contains Everything” –dengan tambahan dari saya pribadi- “,not in nowadays’ concept of set”.

Tidak masuk akal! Tidak ada himpunan yang memuat semua himpunan! Ini bertentangan dengan konsep himpunan yang selama ini saya pahami. Jika kita ingin membuat himpunan yang memuat semua himpunan, yah tinggal kumpulkan saja semua jenis himpunan yang ada di semesta ini. Kumpulan yang tadi sudah kita kumpulkan tentunya menjadi himpunan yang memuat semua himpunan. Namun himpunan yang memuat semua himpunan itu juga merupakan himpunan, apakah himpunan tersebut juga sudah termuat di dalamnya? Oh tidak! Proses ini berlangsung terus sampai kita bisa dibuatnya gila!

Jadi apa itu kumpulan semua himpunan? Tidak ada yang tahu. Saya percaya konsep itu ada, dan bukannya kontradiksi dengan pemikiran kita. Itulah sebabnya, fakta ini dinamakan Russel’s paradox; bukan Russel’s contradiction. Lalu bagaimana menjelaskan fenomena itu? Tidak ada yang tahu. Ini sama misteriusnya dengan pertanyaan “Dari mana asal manusia?”. Tidak untuk masa sekarang. Belum cukup instrumen yang dimiliki masyarakat sains untuk dapat mendefinisikan dengan rigorous fenomena ini. Haruslah ada definisi mengenai himpunan yang lebih besar, lebih kuat, lebih divine; untuk membantu umat manusia mendalami peristiwa ini. Yang seperti apakah itu? Itu adalah pertanyaan kita semua, umat manusia.

 

Jadi apakah itu himpunan? Jawaban yang mungkin paling memuaskan, adalah “Himpunan tidak didefinisikan”.