Jembatan Baru yang Menghubungkan Matematika Aneh tentang Tak Hingga dan Ilmu Komputer

• Terungkap bahwa teori himpunan deskriptif, bidang teknis yang meneliti struktur himpunan tak hingga, dapat ditafsirkan ulang dalam bahasa algoritme
• Matematikawan Anton Bernshteyn membuktikan bahwa masalah pada graf tak hingga dapat ditulis ulang sebagai masalah komunikasi pada jaringan komputer
• Keterkaitan ini menunjukkan hubungan korespondensi antara measurability dan efisiensi algoritme terdistribusi
• Para peneliti kini menggunakan jembatan ini untuk saling mengonversi teorema dan masalah dari kedua bidang dan menghasilkan temuan baru
• Penemuan ini mendefinisikan ulang batas antara tak hingga dan komputasi, serta memperluas kemungkinan kolaborasi antara matematika dan ilmu komputer

---

Pendahuluan: teori himpunan dan dunia tak hingga

• Fondasi matematika modern bertumpu pada teori himpunan, dan sebagian besar matematikawan menangani masalah dengan asumsi tersebut
• Namun, ahli teori himpunan deskriptif (descriptive set theorists) adalah kelompok kecil peneliti yang terus mengeksplorasi hakikat himpunan tak hingga
• Pada 2023, Anton Bernshteyn menemukan keterkaitan mendalam antara teori himpunan deskriptif dan ilmu komputer
  • Ia menunjukkan bahwa persoalan pada himpunan tak hingga tertentu dapat diubah menjadi masalah komunikasi pada jaringan komputer
• Hasil ini dinilai sebagai jembatan yang menghubungkan bahasa yang tampak berlawanan: logika dan algoritme, serta tak hingga dan hingga

Latar belakang teori himpunan deskriptif

• Asal-usul teori himpunan bermula dari penelitian Georg Cantor, yang membuktikan adanya ukuran tak hingga yang berbeda-beda
• Konsep untuk menyatakan ukuran himpunan mencakup kardinalitas (cardinality) dan ukuran (measure)
  • Contoh: himpunan bilangan real pada interval 0~1 dan himpunan bilangan real pada interval 0~10 memiliki kardinalitas yang sama, tetapi ukurannya masing-masing 1 dan 10
• Teori himpunan deskriptif membedakan himpunan terukur dan himpunan tak terukur, lalu mengelompokkannya ke dalam hierarki kompleksitas (hierarchy)
• Hierarki ini menjadi patokan untuk memilih alat yang tepat di bidang matematika lain, seperti teori probabilitas, sistem dinamis, dan teori grup

Graf tak hingga dan masalah pewarnaan

• Bernshteyn meneliti graf tak hingga, dengan memodelkan node dan sisi setiap graf sebagai struktur yang terhubung tanpa batas
• Contoh: jika titik-titik pada lingkaran dihubungkan dengan jarak tertentu, maka pada jarak rasional akan terbentuk loop tertutup, sedangkan pada jarak irasional akan terbentuk struktur terhubung tak hingga
• Ketika node graf diwarnai dengan dua warna, hal itu bisa dilakukan menggunakan aksioma pilihan (axiom of choice), tetapi menghasilkan himpunan tak terukur
• Sebaliknya, jika menggunakan metode pewarnaan kontinu, dibutuhkan tiga warna tetapi diperoleh himpunan terukur
• Perbedaan ini berperan sebagai faktor kunci yang menentukan posisi dalam hierarki kompleksitas teori himpunan

Pertemuan dengan algoritme terdistribusi

• Pada 2019, Bernshteyn menghadiri kuliah ilmu komputer tentang algoritme terdistribusi (distributed algorithms) dan menemukan kemiripan
  • Contoh: masalah memilih frekuensi (warna) yang berbeda agar router Wi-Fi tidak saling mengganggu
• Setiap node menentukan warnanya dengan algoritme lokal (local algorithm) yang hanya berkomunikasi dengan node tetangga
• Dua warna tidak efisien, tetapi jika tiga warna diizinkan, masalah dapat diselesaikan secara efisien
• Bernshteyn menyadari bahwa ambang jumlah warna (threshold) ini identik dengan ambang pada masalah pewarnaan terukur dalam teori himpunan deskriptif

Bukti kesetaraan dua dunia

• Bernshteyn secara matematis membuktikan kesetaraan antara algoritme lokal yang efisien ↔ metode pewarnaan terukur
• Pada graf berhingga, setiap node dapat diberi nomor unik, tetapi pada graf tak hingga tak terhitung (uncountable) hal itu tidak mungkin
• Ia merancang metode pelabelan yang tidak bertumpang tindih antar node bertetangga, sehingga algoritme dapat diperluas ke graf tak hingga
• Hasilnya, terbukti bahwa “setiap algoritme lokal berkorespondensi dengan metode pewarnaan terukur dalam teori himpunan deskriptif”
• Ini menunjukkan keterkaitan matematis yang mendalam antara komputabilitas dan keterdefinisian (definability)

Perluasan riset dan penerapan

• Václav Rozhoň dan lainnya menggunakan keterkaitan ini untuk menyelesaikan masalah pewarnaan graf pohon (tree) dan menurunkan alat penelitian untuk sistem dinamis
• Sebaliknya, ada pula riset yang memakai metode teori himpunan untuk meningkatkan estimasi tingkat kesulitan masalah
• Jembatan ini melampaui sekadar alat penyelesaian masalah, dan turut berkontribusi pada penataan ulang sistem klasifikasi teori himpunan
• Para ahli teori himpunan deskriptif kini dapat merapikan masalah yang belum terklasifikasi dengan merujuk pada cara klasifikasi sistematis dalam ilmu komputer
• Bernshteyn berharap riset ini menjadi momentum untuk membuat konsep tak hingga dipandang sebagai bagian nyata dari matematika praktis

[GN⁺]

Opini Hacker News

• Penasaran apakah hasil seperti ini bisa diterapkan ke bidang nyata seperti komputasi terdistribusi. Atau apakah ini hanya menarik sebagai minat matematika murni

  • Itu sama sekali bukan pertanyaan bodoh. Wawasan teknis semacam ini bisa mengarah pada teorema ketidakmungkinan baru dalam algoritme terdistribusi atau teori kompleksitas komputasi. Potensi penerapan seperti mesh networking juga menarik

• Pernyataan “semua matematika modern dibangun di atas teori himpunan” terlalu mutlak. Alat matematika modern seperti Lean atau Rocq berkembang di atas matematika terformalisasi (formalized mathematics), yang dibangun di atas teori tipe (type theory)

  • Saya bukan matematikawan, tetapi menurut saya ZFC masih merupakan sistem fondasi yang valid. Tipe dependen (dependent types) berguna untuk mengelola pembuktian teorema, tetapi tidak membuat kita bisa membuktikan lebih banyak teorema. Isabelle/HOL milik Lawrence Paulson tidak berbasis tipe, tetapi dapat membuktikan sebagian besar matematika
  • Namun matematikawan sungguhan hampir tidak pernah menggunakan matematika terformalisasi. Kalaupun tahu, mereka tidak menulis dalam bahasa fondasional itu karena tidak praktis
  • Jangan mencampuradukkan bahasa matematika dengan bahasa formal yang digunakan untuk membuktikan hal-hal tentang bahasa itu. Yang pertama hampir sepenuhnya memakai himpunan, yang kedua niscaya memakai tipe
  • Lebih tepatnya, krisis fondasi matematika dianggap mereda dengan formalisasi teori himpunan

• Ungkapan bercanda “cons’es all the way down” menyindir struktur rekursif

• Terharu dengan kalimat “akhirnya kita bisa menghitung tak hingga”

  • Bulan depan di Bay Area akan ada tur Calculating Infinity dari The Dillinger Escape Plan. Tautan acara. Saya bagikan karena sepertinya ada irisan penggemar matematika, hacking, dan mathcore
  • Menanggapi kalimat “menghitung tak hingga” dengan lelucon, “dan melampauinya!”
  • Di Haskell, katanya tak hingga terhitung (countable infinity) bisa dinyatakan hanya dengan satu baris: let x = x in x
  • Menambahkan humor dengan meme “Chuck Norris menghitung dari 1 sampai tak hingga dua kali”
  • Menambahkan sindiran dengan “ini memang butuh waktu lama /s”

• Tidak setuju dengan klaim bahwa “ilmu komputer hanya berurusan dengan hal-hal yang hingga”. Faktanya, ilmu komputer sangat berkaitan dengan tak hingga

  • Quanta memang sering membahas hal seperti ini dengan gaya begitu. Mereka cenderung memakai narasi sains populer yang berfokus pada tokoh dan menghilangkan detail
  • Namun ilmu komputer memang kurang tertarik pada tak hingga tak terhitung (uncountable infinity). Teori ukuran (measure theory) lebih banyak berurusan dengan itu
  • Awalnya saya juga mengira “CS mengaproksimasi tak hingga”, tetapi sebenarnya kata kuncinya adalah aproksimasi. Kita selalu bekerja hanya dalam batas hingga. Bahkan jika alam semesta tak hingga, jangkauan yang bisa kita amati tetap dibatasi oleh kecepatan cahaya
  • Kalimat seperti “ilmu komputer tidak menggunakan logika” terlalu malas. Logika Boolean adalah buktinya

• Saya sudah lama belajar matematika, dan akhirnya percaya bahwa tak hingga (infinity) itu tidak ada. Mungkin matematika akan lebih baik tanpa tak hingga

  • Saya juga hanya belajar matematika tingkat teknik, tetapi saya menganggap tak hingga bukan angka, melainkan proses. Tanda “...” dalam {1, 2, 3, ...} berarti proses perluasan yang tidak pernah selesai. Tidak ada yang namanya bilangan prima ke-takhingga-an, yang ada hanya aturan generatif bahwa selalu ada bilangan prima yang lebih besar
  • Namun jika tak hingga dihapus, matematika menjadi sangat rumit. Jika bilangan asli tidak boleh diperluas tanpa akhir, perhitungan menjadi sangat tidak nyaman
  • Matematika lebih peduli pada kegunaan konseptual daripada keberadaan nyata. Lingkaran juga tidak ada secara fisik, tetapi berguna. Tanpa tak hingga, pada akhirnya kita akan menemukannya lagi dalam bentuk seperti “limit ketika x menuju bilangan yang sangat, sangat besar”
  • Lelucon “cukup berhenti di 8” menyindir ketidakperluan tak hingga
  • Tak hingga hanyalah nama untuk proses yang tidak pernah selesai. Beberapa proses bertumbuh lebih cepat, sehingga ada tak hingga yang lebih besar. Secara pribadi saya menyukai konsep tak hingga dalam model bola Riemann

• Lelucon bahwa “node_modules” telah menghubungkan matematika tak hingga ke sistem file saya, menyindir ledakan dependensi

• Menyanggah kalimat “semua matematika modern dibangun di atas teori himpunan” dengan menunjukkan bahwa ada juga Type Theory

  • Type Theory adalah sistem aksioma yang lebih kuat daripada ZFC. Lihat penjelasan terkait di jawaban MathOverflow
  • Tetapi belum ada kumpulan aksioma teori tipe yang seberpengaruh ZF atau ZFC
  • Secara teknis, descriptive set theory terpisah dari teori himpunan fondasional. Bidang itu bisa dengan mudah direkonstruksi dengan konsep tipe dan ruang, dan itu sering kali lebih menguntungkan. Menafsirkan ulang tak hingga matematis dari sudut pandang komputasional bukanlah upaya baru
  • Penjelasan “disiplin yang mengatur himpunan objek abstrak” terlalu menyederhanakan teori himpunan. Meski begitu, tetap benar bahwa sebagian besar matematika masih didefinisikan dari aksioma himpunan