Jembatan Baru Menghubungkan Matematika Aneh dari Ketakterbatasan dengan Ilmu Komputer

Versi aslinya dari cerita ini muncul di Majalah Kuanta.

Semua matematika modern dibangun di atas dasar teori himpunan, studi tentang bagaimana mengatur kumpulan objek yang abstrak. Namun secara umum, ahli matematika riset tidak perlu memikirkannya saat memecahkan masalah mereka. Mereka dapat menerima begitu saja bahwa perangkat berperilaku seperti yang mereka harapkan, dan melanjutkan pekerjaan mereka.

Para ahli teori himpunan deskriptif merupakan pengecualian. Komunitas kecil matematikawan ini tidak pernah berhenti mempelajari sifat dasar himpunan—khususnya himpunan tak hingga yang aneh yang diabaikan oleh matematikawan lain.

Ladang mereka menjadi tidak terlalu sepi. Pada tahun 2023, seorang ahli matematika bernama Anton Bernshteyn diterbitkan a hubungan yang mendalam dan mengejutkan antara batas matematika jarak jauh dari teori himpunan deskriptif dan ilmu komputer modern.

Dia menunjukkan bahwa semua permasalahan tentang himpunan tak hingga tertentu dapat ditulis ulang sebagai permasalahan tentang bagaimana jaringan komputer berkomunikasi. Jembatan yang menghubungkan disiplin ilmu ini mengejutkan para peneliti di kedua sisi. Ahli teori himpunan menggunakan bahasa logika, ilmuwan komputer menggunakan bahasa algoritma. Teori himpunan berhubungan dengan ketidakterbatasan, ilmu komputer dengan keterbatasan. Tidak ada alasan mengapa masalah mereka harus saling berkaitan, apalagi setara.

“Ini adalah sesuatu yang sangat aneh,” kata Václav Rozhonseorang ilmuwan komputer di Universitas Charles di Praha. “Seperti, kamu tidak seharusnya memiliki ini.”

Sejak hasil Bernshteyn, rekan-rekannya telah mengeksplorasi bagaimana bergerak bolak-balik melintasi jembatan untuk membuktikan teorema baru di kedua sisi, dan bagaimana memperluas jembatan itu ke kelas-kelas permasalahan baru. Beberapa ahli teori himpunan deskriptif bahkan mulai menerapkan wawasan dari sisi ilmu komputer untuk menata ulang lanskap seluruh bidangnya, dan memikirkan kembali cara mereka memahami ketidakterbatasan.

“Selama ini kami mengerjakan masalah yang sangat mirip tanpa berbicara langsung satu sama lain,” katanya Clinton Conleyseorang ahli teori himpunan deskriptif di Universitas Carnegie Mellon. “Ini hanya membuka pintu bagi semua kolaborasi baru ini.”

Set Rusak

Bernshteyn masih seorang sarjana ketika dia pertama kali mendengar teori himpunan deskriptif—sebagai contoh bidang yang dulunya penting, kemudian membusuk hingga tidak ada apa-apanya. Lebih dari setahun berlalu sebelum dia mengetahui bahwa profesornya salah.

Pada tahun 2014, sebagai mahasiswa pascasarjana tahun pertama di Universitas Illinois, Bernshteyn mengambil kursus logika dengan Anush Tserunyanyang kemudian menjadi salah satu penasihatnya. Dia mengoreksi kesalahpahaman tersebut. “Dia harus mengambil semua pujian atas keberadaan saya di bidang ini,” katanya. “Dia benar-benar membuatnya tampak bahwa logika dan teori himpunan adalah perekat yang menghubungkan semua bagian matematika yang berbeda.”

Teori himpunan deskriptif berawal dari Georg Cantor, yang membuktikan pada tahun 1874 bahwa ada ukuran tak terhingga yang berbeda. Himpunan bilangan bulat (0, 1, 2, 3,…), misalnya, berukuran sama dengan himpunan semua pecahan, tetapi lebih kecil dari himpunan semua bilangan real.

Pada saat itu, para matematikawan merasa sangat tidak nyaman dengan kumpulan tak terhingga yang berbeda ini. “Sulit untuk memahaminya,” kata Bernshteyn, yang sekarang kuliah di Universitas California, Los Angeles.

Sebagai respons terhadap ketidaknyamanan tersebut, para ahli matematika mengembangkan gagasan lain tentang ukuran—yang menggambarkan, misalnya, berapa panjang, luas, atau volume yang mungkin ditempati suatu himpunan, bukan jumlah elemen yang dikandungnya. Gagasan tentang ukuran ini dikenal sebagai “ukuran” himpunan (berbeda dengan gagasan Cantor tentang ukuran, yang merupakan “kardinalitas” himpunan). Salah satu jenis ukuran yang paling sederhana—ukuran Lebesgue—mengukur panjang suatu himpunan. Meskipun himpunan bilangan real antara nol dan 1 dan himpunan bilangan real antara nol dan 10 keduanya tak berhingga dan mempunyai kardinalitas yang sama, himpunan bilangan real pertama mempunyai ukuran Lebesgue 1 dan himpunan bilangan real kedua mempunyai ukuran Lebesgue 10.

Untuk mempelajari himpunan yang lebih rumit, ahli matematika menggunakan jenis ukuran lain. Semakin jelek suatu himpunan, semakin sedikit cara yang tersedia untuk mengukurnya. Para ahli teori himpunan deskriptif mengajukan pertanyaan tentang himpunan mana yang dapat diukur menurut definisi “ukuran” yang berbeda. Mereka kemudian menyusunnya dalam hierarki berdasarkan jawaban atas pertanyaan-pertanyaan tersebut. Di bagian atas adalah kumpulan yang dapat dibuat dengan mudah dan dipelajari menggunakan gagasan ukuran apa pun yang Anda inginkan. Di bagian bawah terdapat himpunan yang “tidak dapat diukur”, yang sangat rumit sehingga tidak dapat diukur sama sekali. “Kata yang sering digunakan orang adalah ‘patologis’,” kata Bernshteyn. “Perangkat yang tidak dapat diukur benar-benar buruk. Mereka berlawanan dengan intuisi, dan tidak berperilaku baik.”

Hirarki ini tidak hanya membantu para ahli teori memetakan lanskap bidangnya; hal ini juga memberi mereka wawasan tentang alat apa yang dapat mereka gunakan untuk mengatasi masalah yang lebih umum di bidang matematika lainnya. Matematikawan di beberapa bidang, seperti sistem dinamik, teori grup, dan teori probabilitas, memerlukan informasi tentang ukuran himpunan yang mereka gunakan. Posisi suatu kelompok dalam hierarki menentukan alat apa yang dapat mereka gunakan untuk memecahkan masalah mereka.

Oleh karena itu, para ahli teori himpunan deskriptif seperti pustakawan, yang merawat rak buku besar yang berisi berbagai jenis himpunan tak hingga (dan berbagai cara mengukurnya). Tugas mereka adalah mengambil suatu permasalahan, menentukan seberapa rumit suatu himpunan penyelesaian yang diperlukan, dan menempatkannya di rak yang tepat, sehingga matematikawan lain dapat memperhatikannya.

Membuat Pilihan

Bernshteyn termasuk dalam sekelompok pustakawan yang mengurutkan masalah tentang kumpulan node tak terhingga yang dihubungkan oleh sisi, yang disebut grafik. Secara khusus, ia mempelajari grafik yang memiliki banyak bagian terpisah yang tak terhingga banyaknya, masing-masing berisi banyak simpul yang tak terhingga banyaknya. Kebanyakan ahli teori graf tidak mempelajari grafik jenis ini; mereka fokus pada hal-hal yang terbatas. Namun grafik tak terhingga seperti itu dapat mewakili dan memberikan informasi tentang sistem dinamik dan jenis himpunan penting lainnya, menjadikannya bidang minat utama bagi para ahli teori himpunan deskriptif.

Berikut adalah contoh grafik tak hingga yang mungkin dipelajari Bernshteyn dan rekan-rekannya. Mulailah dengan sebuah lingkaran, yang berisi banyak titik tak terhingga. Pilih satu titik: Ini akan menjadi simpul pertama Anda. Kemudian pindahkan jarak tetap di sekitar keliling lingkaran. Ini memberi Anda simpul kedua. Misalnya, Anda dapat bergerak seperlima keliling lingkaran. Hubungkan kedua simpul dengan sebuah tepi. Pindahkan jarak yang sama ke node ketiga, dan hubungkan ke node sebelumnya. Dan sebagainya.

Jika Anda bergerak seperlima keliling lingkaran setiap kali, diperlukan lima langkah untuk kembali ke titik awal. Secara umum, jika Anda memindahkan jarak berapa pun yang dapat ditulis sebagai pecahan, simpul-simpul tersebut akan membentuk lingkaran tertutup. Namun jika jarak tidak bisa dituliskan sebagai pecahan, prosesnya akan berlangsung selamanya. Anda akan mendapatkan node terhubung dalam jumlah tak terbatas.

Namun bukan itu saja: Urutan yang sangat panjang ini hanya membentuk bagian pertama dari grafik Anda. Meskipun berisi banyak titik tak terhingga, ia tidak memuat semua titik pada lingkaran. Untuk menghasilkan potongan grafik lainnya, mulailah dari salah satu titik lainnya. Sekarang pindahkan jarak yang sama pada setiap langkah seperti yang Anda lakukan pada potongan pertama. Anda akhirnya akan membangun rangkaian node terhubung kedua yang tak terbatas, benar-benar terputus dari yang pertama.

Lakukan ini untuk setiap kemungkinan titik awal baru pada lingkaran. Anda akan mendapatkan grafik yang terdiri dari banyak bagian terpisah yang tak terhingga banyaknya, dengan masing-masing bagian terbuat dari jumlah node yang tak terhingga.

Matematikawan kemudian dapat menanyakan apakah mungkin untuk mewarnai simpul dalam grafik ini sehingga mematuhi aturan tertentu. Misalnya, hanya dengan menggunakan dua warna, dapatkah Anda mewarnai setiap simpul dalam grafik sehingga tidak ada dua simpul yang terhubung yang memiliki warna yang sama? Solusinya mungkin terlihat mudah. Lihatlah bagian pertama grafik Anda, pilih sebuah simpul, dan warnai dengan biru. Kemudian warnai sisa simpul dalam pola bergantian: kuning, biru, kuning, biru. Lakukan hal yang sama untuk setiap bagian dalam grafik Anda: Pilih sebuah simpul, warnai dengan biru, lalu ganti warna. Pada akhirnya, Anda hanya akan menggunakan dua warna untuk menyelesaikan tugas Anda.

Namun untuk mencapai pewarnaan ini, Anda harus mengandalkan asumsi tersembunyi yang oleh para ahli teori himpunan disebut aksioma pilihan. Ini adalah salah satu dari sembilan blok bangunan mendasar yang menjadi dasar pembuatan semua pernyataan matematika. Menurut aksioma ini, jika Anda memulai dengan sekumpulan himpunan, Anda dapat memilih satu item dari masing-masing himpunan tersebut untuk membuat himpunan baru—bahkan jika Anda memiliki banyak sekali himpunan yang dapat dipilih. Aksioma ini berguna, karena memungkinkan ahli matematika membuktikan segala macam pernyataan yang menarik. Namun hal ini juga menimbulkan paradoks yang aneh. Para ahli teori himpunan deskriptif menghindarinya.

Grafik Anda memiliki banyak sekali bagian. Ini sama dengan memiliki banyak himpunan yang tak terhingga. Anda memilih satu item dari setiap set—titik pertama yang Anda putuskan untuk diwarnai dengan warna biru di setiap bagian. Semua titik biru itu membentuk satu set baru. Anda menggunakan aksioma pilihan.

Yang menyebabkan masalah saat Anda mewarnai sisa node dengan pola bergantian antara biru dan kuning. Anda telah mewarnai setiap node (yang panjangnya nol) secara terpisah, tanpa pemahaman apa pun tentang bagaimana node berhubungan satu sama lain ketika node tersebut berasal dari bagian grafik yang berbeda. Artinya, Anda tidak dapat mendeskripsikan himpunan semua simpul biru pada grafik, atau himpunan semua simpul kuning, dalam bentuk panjangnya. Dengan kata lain, kumpulan ini tidak dapat diukur. Matematikawan tidak bisa mengatakan sesuatu yang berguna tentangnya.

Bagi para ahli teori himpunan deskriptif, hal ini tidak memuaskan. Jadi mereka ingin mencari cara untuk mewarnai grafik secara berkelanjutan—cara yang tidak menggunakan aksioma pilihan, dan memberikan kumpulan yang dapat diukur.

Untuk melakukan ini, ingat bagaimana Anda membuat bagian pertama dari grafik Anda: Anda mengambil sebuah simpul pada sebuah lingkaran dan menghubungkannya ke simpul kedua yang agak jauh. Sekarang warnai simpul pertama dengan warna biru, simpul kedua dengan warna kuning, dan seluruh busur di antaranya dengan warna biru. Demikian pula, warnai busur antara simpul kedua dan ketiga dengan warna kuning. Warnai busur ketiga dengan warna biru. Dan sebagainya.

Sebentar lagi, Anda akan berhasil membuatnya hampir seluruhnya mengelilingi lingkaran—artinya Anda telah menetapkan warna pada semua simpul dalam grafik Anda kecuali simpul yang termasuk dalam segmen kecil yang tersisa. Katakanlah busur terakhir yang Anda warnai adalah kuning. Bagaimana Anda mewarnai segmen terakhir yang lebih kecil ini? Anda tidak dapat menggunakan warna biru, karena node ini akan terhubung ke node di busur asli yang Anda warnai biru. Tapi Anda juga tidak bisa menggunakan warna kuning, karena node ini terhubung kembali ke node kuning dari arc sebelumnya.

Anda harus menggunakan warna ketiga—misalnya, hijau—untuk melengkapi pewarnaan Anda.

Namun, kumpulan titik biru, kuning, dan hijau yang Anda dapatkan hanyalah potongan dari keliling lingkaran, bukan hamburan titik yang Anda dapatkan saat menggunakan aksioma pilihan. Anda dapat menghitung panjang himpunan ini. Hal ini dapat diukur.

Oleh karena itu, para ahli teori himpunan deskriptif menempatkan versi masalah dua warna pada urutan terbawah dalam hierarkinya (untuk himpunan tak terukur), sedangkan masalah tiga warna berada pada urutan masalah yang jauh lebih tinggi—yaitu di mana banyak gagasan tentang ukuran dapat diterapkan.

Bernshteyn menghabiskan tahun-tahunnya di sekolah pascasarjana mempelajari masalah mewarnai seperti itu, mengesampingkannya satu per satu. Kemudian, tak lama setelah ia menyelesaikan gelarnya, ia menemukan cara potensial untuk mengesampingkan semuanya sekaligus—dan untuk menunjukkan bahwa permasalahan ini memiliki struktur yang jauh lebih dalam dan lebih relevan secara matematis daripada yang disadari siapa pun.

Putaran demi Putaran

Dari waktu ke waktu, Bernshteyn senang menghadiri ceramah ilmu komputer, yang membahas tentang grafik berhingga dan mewakili jaringan komputer.

Pada tahun 2019, salah satu pembicaraan tersebut mengubah arah kariernya. Itu tentang “algoritme terdistribusi”—kumpulan instruksi yang berjalan secara bersamaan di beberapa komputer dalam jaringan untuk menyelesaikan tugas tanpa koordinator pusat.

Katakanlah Anda memiliki banyak router Wi-Fi di sebuah gedung. Router-router terdekat dapat saling mengganggu jika menggunakan saluran frekuensi komunikasi yang sama. Jadi setiap router perlu memilih saluran yang berbeda dari saluran yang digunakan oleh tetangga terdekatnya.

Ilmuwan komputer dapat membingkai ulang hal ini sebagai masalah pewarnaan pada grafik: Merepresentasikan setiap router sebagai sebuah node, dan menghubungkan router terdekat dengan edge. Hanya dengan menggunakan dua warna (mewakili dua saluran frekuensi berbeda), temukan cara untuk mewarnai setiap node sehingga tidak ada dua node yang terhubung memiliki warna yang sama.

Namun ada kendalanya: Node hanya dapat berkomunikasi dengan tetangga terdekatnya, menggunakan apa yang disebut algoritma lokal. Pertama, setiap node menjalankan algoritma yang sama dan memberikan warna pada dirinya sendiri. Ia kemudian berkomunikasi dengan tetangganya untuk mempelajari bagaimana node lain diwarnai di wilayah kecil di sekitarnya. Kemudian algoritma dijalankan lagi untuk memutuskan apakah akan mempertahankan warnanya atau menggantinya. Ini mengulangi langkah ini sampai seluruh jaringan memiliki warna yang tepat.

Ilmuwan komputer ingin mengetahui berapa banyak langkah yang diperlukan suatu algoritma. Misalnya, algoritme lokal apa pun yang dapat menyelesaikan masalah router dengan hanya dua warna pasti sangat tidak efisien, tetapi algoritme lokal yang sangat efisien dapat ditemukan jika Anda diizinkan menggunakan tiga warna.

Pada pembicaraan yang dihadiri Bernshteyn, pembicara membahas ambang batas untuk berbagai jenis masalah. Salah satu ambang batasnya, ia sadari, terdengar sangat mirip dengan ambang batas yang ada dalam dunia teori himpunan deskriptif—tentang jumlah warna yang diperlukan untuk mewarnai grafik tak terhingga tertentu dengan cara yang dapat diukur.

Bagi Bernshteyn, ini terasa lebih dari sekadar kebetulan. Bukan hanya ilmuwan komputer yang juga seperti pustakawan, yang mengesampingkan masalah berdasarkan seberapa efisien algoritma mereka bekerja. Tidak hanya itu, soal-soal tersebut juga dapat ditulis dalam bentuk grafik dan pewarnaan.

Mungkin, pikirnya, kedua rak buku itu punya lebih banyak kesamaan daripada itu. Mungkin hubungan antara kedua bidang ini jauh lebih dalam.

Mungkin semua buku dan raknya sama, hanya ditulis dalam bahasa yang berbeda—dan membutuhkan penerjemah.

Membuka Pintu

Bernshteyn berusaha membuat hubungan ini eksplisit. Dia ingin menunjukkan bahwa setiap algoritme lokal yang efisien dapat diubah menjadi cara terukur Lebesgue untuk mewarnai grafik tak hingga (yang memenuhi beberapa properti penting tambahan). Artinya, salah satu rak paling penting dalam ilmu komputer setara dengan salah satu rak paling penting dalam teori himpunan (yang paling tinggi dalam hierarki).

Dia memulai dengan kelas masalah jaringan dari kuliah ilmu komputer, dengan fokus pada aturan umum masalah tersebut—bahwa algoritma node mana pun hanya menggunakan informasi tentang lingkungan lokalnya, apakah grafik tersebut memiliki seribu atau satu miliar node.

Agar dapat berjalan dengan baik, algoritma hanya perlu memberi label pada setiap node di lingkungan tertentu dengan nomor unik, sehingga dapat mencatat informasi tentang node terdekat dan memberikan instruksi mengenai node tersebut. Itu cukup mudah untuk dilakukan dalam grafik berhingga: Berikan saja nomor yang berbeda pada setiap node dalam grafik.

Jika Bernshteyn dapat menjalankan algoritme yang sama pada grafik tak hingga, itu berarti dia dapat mewarnai grafik dengan cara yang terukur—menyelesaikan pertanyaan tentang pewarnaan grafik pada sisi teori himpunan. Namun ada masalah: Grafik tak terhingga ini “tak terhitung” tak terhingga. Tidak ada cara untuk memberi label unik pada semua nodenya.

Tantangan Bernshteyn adalah menemukan cara yang lebih cerdas untuk memberi label pada grafik.

Dia tahu bahwa dia harus menggunakan kembali labelnya. Tapi itu tidak masalah asalkan node di dekatnya diberi label berbeda. Adakah cara untuk menetapkan label tanpa menggunakannya kembali secara tidak sengaja di lingkungan yang sama?

Bernshteyn menunjukkan bahwa selalu ada jalan—tidak peduli berapa banyak label yang Anda putuskan untuk digunakan, dan tidak peduli berapa banyak node yang dimiliki lingkungan lokal Anda. Artinya, Anda selalu dapat dengan aman memperluas algoritme dari sisi ilmu komputer ke sisi teori himpunan. “Algoritme apa pun dalam pengaturan kami berhubungan dengan cara mewarnai grafik apa pun secara terukur dalam pengaturan teori himpunan deskriptif,” kata Rozhoň.

Buktinya mengejutkan para ahli matematika. Ini menunjukkan hubungan yang mendalam antara komputasi dan keterdefinisian, dan antara algoritma dan kumpulan terukur. Para ahli matematika kini sedang menjajaki cara memanfaatkan penemuan Bernshteyn. Dalam sebuah makalah yang diterbitkan tahun ini, misalnya, Rozhoň dan rekan-rekannya menemukan bahwa hal itu mungkin terjadi mewarnai grafik khusus yang disebut pohon dengan melihat masalah yang sama dalam konteks ilmu komputer. Hasilnya juga menjelaskan alat apa yang mungkin digunakan ahli matematika untuk mempelajari sistem dinamika pohon yang bersesuaian. “Ini adalah pengalaman yang sangat menarik, mencoba membuktikan hasil di bidang yang saya bahkan tidak memahami definisi dasarnya,” kata Rozhoň.

Matematikawan juga telah berupaya menerjemahkan permasalahan ke arah lain. Dalam satu kasus, mereka menggunakan teori himpunan membuktikan perkiraan baru tentang betapa sulitnya memecahkan suatu kelompok masalah tertentu.

Jembatan Bernshteyn bukan hanya tentang memiliki perangkat baru untuk memecahkan masalah individu. Hal ini juga memungkinkan para ahli teori himpunan mendapatkan pandangan yang lebih jelas tentang bidangnya. Ada banyak masalah yang mereka tidak tahu cara mengklasifikasikannya. Dalam banyak kasus, hal tersebut kini telah berubah, karena para ahli teori himpunan memiliki rak buku ilmuwan komputer yang lebih terorganisir untuk memandu mereka.

Bernshteyn berharap bidang penelitian yang berkembang ini akan mengubah cara pandang para ahli matematika dalam mengatur pekerjaan para ahli teori—sehingga mereka tidak lagi melihatnya sebagai hal yang jauh dan terputus dari dunia matematika yang sebenarnya. “Saya mencoba mengubah ini,” katanya. “Saya ingin orang-orang terbiasa memikirkan tentang ketidakterbatasan.”

Cerita asli dicetak ulang dengan izin dari Majalah Kuantasebuah publikasi independen secara editorial dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman masyarakat terhadap sains dengan meliput perkembangan dan tren penelitian di bidang matematika serta ilmu fisika dan kehidupan.