अनंत के विचित्र गणित और कंप्यूटर साइंस को जोड़ने वाला नया पुल

• अनंत समुच्चयों की संरचना का अध्ययन करने वाला क्षेत्र descriptive set theory अब एल्गोरिद्मिक भाषा में फिर से व्याख्यायित किया जा सकता है
• गणितज्ञ Anton Bernshteyn ने साबित किया कि अनंत ग्राफ की समस्याओं को कंप्यूटर नेटवर्क में संचार समस्याओं के रूप में फिर से लिखा जा सकता है
• यह संबंध measurability और distributed algorithms की efficiency के बीच एक correspondence दिखाता है
• शोधकर्ता इस पुल के ज़रिये दोनों क्षेत्रों के प्रमेयों और समस्याओं को परस्पर रूपांतरित करते हुए नए नतीजे निकाल रहे हैं
• यह खोज अनंत और computation की सीमा को फिर से परिभाषित करती है और गणित व कंप्यूटर साइंस के सहयोग की संभावनाओं का विस्तार करती है

---

परिचय: समुच्चय सिद्धांत और अनंत की दुनिया

• आधुनिक गणित की नींव समुच्चय सिद्धांत पर आधारित है, और अधिकांश गणितज्ञ इसी को आधार मानकर समस्याओं पर काम करते हैं
• लेकिन descriptive set theorists अनंत समुच्चयों के स्वभाव की लगातार पड़ताल करने वाला अपेक्षाकृत छोटा शोधकर्ता समुदाय है
• 2023 में Anton Bernshteyn ने descriptive set theory और कंप्यूटर साइंस के बीच एक गहरा संबंध खोजा
  • उन्होंने दिखाया कि कुछ अनंत समुच्चयों से जुड़ी समस्याओं को कंप्यूटर नेटवर्क की संचार समस्याओं में बदला जा सकता है
• इस नतीजे को तर्क और एल्गोरिद्म, अनंत और सीमित जैसी विपरीत भाषाओं को जोड़ने वाले पुल के रूप में देखा जा रहा है

descriptive set theory की पृष्ठभूमि

• समुच्चय सिद्धांत की शुरुआत Georg Cantor के काम से हुई, जिन्होंने अलग-अलग अनंतताओं के आकार होने का प्रमाण दिया
• समुच्चयों के आकार को दर्शाने वाले विचारों में cardinality और measure शामिल हैं
  • उदाहरण: 0~1 अंतराल के वास्तविक संख्याओं का समुच्चय और 0~10 अंतराल के वास्तविक संख्याओं का समुच्चय cardinality में समान हैं, लेकिन उनका measure क्रमशः 1 और 10 है
• descriptive set theory मापने योग्य समुच्चयों और अमाप्य समुच्चयों के बीच अंतर करती है और उन्हें complexity hierarchy में वर्गीकृत करती है
• यह hierarchy गणित के दूसरे क्षेत्रों (जैसे probability theory, dynamical systems, group theory) में उपयुक्त टूल चुनने के मानदंड के रूप में काम करती है

अनंत ग्राफ और coloring समस्या

• Bernshteyn ने अनंत ग्राफ का अध्ययन करते हुए, हर ग्राफ के nodes और edges को अनंत रूप से जुड़े ढांचे के रूप में मॉडल किया
• उदाहरण: अगर वृत्त पर बिंदुओं को एक निश्चित दूरी पर जोड़ा जाए, तो परिमेय दूरी होने पर बंद चक्र बनता है, जबकि अपरिमेय दूरी होने पर अनंत जुड़ी संरचना बनती है
• जब ग्राफ के nodes को दो रंगों से रंगने की बात आती है, तो axiom of choice का उपयोग करने पर यह संभव है, लेकिन इससे अमाप्य समुच्चय बनता है
• इसके विपरीत, सतत coloring पद्धति अपनाने पर तीन रंगों की ज़रूरत पड़ती है, लेकिन मापने योग्य समुच्चय मिलता है
• यह अंतर समुच्चय-सिद्धांत आधारित complexity hierarchy में उसकी स्थिति तय करने वाला अहम तत्व बनता है

distributed algorithms से मुलाकात

• 2019 में Bernshteyn ने distributed algorithms पर कंप्यूटर साइंस का एक व्याख्यान सुना और उसमें समानता देखी
  • उदाहरण: Wi-Fi routers को इस तरह frequency (रंग) चुनना कि वे एक-दूसरे में हस्तक्षेप न करें
• हर node केवल पड़ोसी nodes से संचार करते हुए रंग तय करने वाला local algorithm इस्तेमाल करता है
• दो रंगों के साथ समाधान अक्षम रहता है, लेकिन तीन रंगों की अनुमति देने पर समस्या का कुशल समाधान संभव हो जाता है
• Bernshteyn ने पहचाना कि रंगों की संख्या का threshold descriptive set theory की मापने योग्य coloring समस्या के threshold से मेल खाता है

दो दुनियाओं की समतुल्यता का प्रमाण

• Bernshteyn ने कुशल local algorithm ↔ मापने योग्य coloring पद्धति के बीच समतुल्यता को गणितीय रूप से सिद्ध किया
• सीमित ग्राफ में हर node को एक unique number दिया जा सकता है, लेकिन अगणनीय अनंत ग्राफ में यह संभव नहीं है
• उन्होंने सटे हुए nodes के बीच दोहराव-रहित labeling पद्धति तैयार की, जिससे एल्गोरिद्म को अनंत ग्राफ तक बढ़ाया जा सका
• नतीजतन यह सिद्ध हुआ कि “हर local algorithm descriptive set theory की मापने योग्य coloring पद्धति के अनुरूप होता है”
• यह computability और definability के बीच गहरे गणितीय संबंध को दिखाता है

शोध का विस्तार और उपयोग

• Václav Rozhoň और अन्य शोधकर्ताओं ने इस संबंध का उपयोग करके tree graph coloring समस्या हल की और dynamical systems के अध्ययन के टूल निकाले
• दूसरी ओर, समुच्चय सिद्धांत की विधियों का उपयोग कर समस्याओं की कठिनाई के आकलन को बेहतर बनाने वाला शोध भी हो रहा है
• यह पुल केवल समस्या-समाधान का साधन नहीं, बल्कि समुच्चय सिद्धांत की वर्गीकरण प्रणाली के पुनर्गठन में भी योगदान दे रहा है
• descriptive set theorists अब कंप्यूटर साइंस की व्यवस्थित classification पद्धतियों का सहारा लेकर अब तक अवर्गीकृत समस्याओं को व्यवस्थित कर सकते हैं
• Bernshteyn को उम्मीद है कि यह शोध अनंत की अवधारणा को व्यावहारिक गणित के हिस्से के रूप में स्थापित करने का अवसर बनेगा

[GN⁺]

Hacker News राय

• जिज्ञासा है कि क्या ऐसे नतीजे distributed computing जैसे वास्तविक क्षेत्रों में लागू हो सकते हैं, या यह सिर्फ़ शुद्ध गणितीय रुचि की चीज़ है

  • यह बिल्कुल भी बेवकूफ़ी भरा सवाल नहीं है। ऐसी technical insight से distributed algorithms या computational complexity theory में नए impossibility theorems निकल सकते हैं। mesh networking जैसे applications भी रोचक लगते हैं

• “सारी आधुनिक गणित set theory पर खड़ी है” कहना कुछ ज़्यादा ही निर्णायक है। Lean और Rocq जैसे आधुनिक गणितीय tools formalized mathematics पर आधारित होकर विकसित हो रहे हैं, और यह type theory पर खड़ा है

  • मैं गणितज्ञ नहीं हूँ, लेकिन मुझे लगता है कि ZFC अब भी एक वैध foundational system है। dependent types theorem proving को manage करने में उपयोगी हैं, लेकिन वे आपको ज़्यादा theorems prove करने नहीं देते। Lawrence Paulson का Isabelle/HOL type-based नहीं है, फिर भी वह ज़्यादातर गणित prove कर सकता है
  • लेकिन असली गणितज्ञ formalized mathematics का लगभग उपयोग नहीं करते। जानते हों तब भी उसकी असुविधा की वजह से उसे foundational language की तरह नहीं अपनाते
  • गणित की language और उस language के बारे में proofs करने वाली formal language को गड़बड़ नहीं करना चाहिए। पहली लगभग पूरी तरह sets का उपयोग करती है, दूसरी अनिवार्य रूप से types का
  • ज़्यादा सटीक रूप से कहें तो, गणित की foundations पर आया संकट set theory की formalization से फिलहाल सुलझा माना जा सकता है

• “cons’es all the way down” एक मज़ाकिया अभिव्यक्ति है, जो recursive structure पर व्यंग्य करती है

• “आख़िरकार हम infinity की गणना कर सकते हैं” सुनकर उत्साह हुआ

  • अगले महीने Bay Area में The Dillinger Escape Plan का Calculating Infinity टूर है। कॉन्सर्ट लिंक. लगा कि गणित, hacking, और mathcore के fans का overlap होगा, इसलिए साझा कर रहा हूँ
  • “infinity की गणना” पर जवाब आता है, “और उससे भी आगे!”, और मज़ाक आगे बढ़ता है
  • Haskell में let x = x in x की एक लाइन से countable infinity दिखाया जा सकता है
  • “Chuck Norris ने 1 से infinity तक दो बार गिना” वाला meme भी जोड़ा गया
  • “इसमें तो सच में बहुत समय लग गया /s” कहकर व्यंग्यात्मक टिप्पणी की गई

• “computer science सिर्फ़ finite चीज़ों से डील करती है” इस दावे से सहमत नहीं हूँ। असल में computer science का infinity से गहरा संबंध है

  • Quanta का इस तरह पेश करना आम बात है। popular science शैली में वह लोगों-केंद्रित कहानी पर ज़ोर देता है और details छोड़ देता है
  • हाँ, computer science का uncountable infinity में कम interest है। measure theory ज़्यादातर उसी से जुड़ी होती है
  • मैंने भी पहले सोचा था कि “CS infinity को approximate करती है”, लेकिन वास्तव में approximation ही मुख्य शब्द है। हम हमेशा finite boundaries के भीतर काम करते हैं। ब्रह्मांड अनंत हो तब भी हमारी observable range प्रकाश की गति से सीमित है
  • “computer science logic का उपयोग नहीं करती” जैसे वाक्य बहुत आलसी किस्म के कथन हैं। Boolean logic इसका सीधा सबूत है

• मैंने लंबे समय तक गणित पढ़ी है, और अब मुझे विश्वास होने लगा है कि infinity जैसी कोई चीज़ नहीं होती। शायद गणित उसके बिना बेहतर हो सकती है

  • मैंने भी सिर्फ़ engineering-level mathematics पढ़ी है, लेकिन मुझे लगता है कि infinity संख्या नहीं बल्कि एक process है। {1, 2, 3, ...} में “...” एक अंतहीन विस्तार की प्रक्रिया को दर्शाता है। अनंतवाँ अभाज्य जैसा कुछ नहीं, सिर्फ़ एक generative rule है कि हमेशा उससे बड़ा prime मौजूद होगा
  • लेकिन infinity को हटा दें तो गणित भयानक रूप से जटिल हो जाती है। अगर natural numbers को अंतहीन रूप से बढ़ता न मानें, तो calculation बहुत असुविधाजनक हो जाएगी
  • गणित का सरोकार अस्तित्व से ज़्यादा conceptual usefulness से है। circle भी वास्तविक दुनिया में मौजूद नहीं होता, फिर भी उपयोगी है। अगर infinity न हो, तो अंततः हमें “जब x बहुत बहुत बड़े number की ओर जाए तब limit” जैसी चीज़ फिर से गढ़नी पड़ेगी
  • “8 पर रुक जाओ” वाला मज़ाक infinity की अनावश्यकता पर व्यंग्य करता है
  • infinity बस उस नाम की तरह है जो कभी खत्म न होने वाली प्रक्रिया को दिया गया है। कुछ प्रक्रियाएँ दूसरों से तेज़ बढ़ती हैं, इसलिए बड़ी infinities भी होती हैं। मुझे व्यक्तिगत रूप से Riemann sphere model में infinity की अवधारणा पसंद है

• यह मज़ाक भी आया कि “node_modules” ने मेरे file system में infinity की गणित जोड़ दी है, यानी dependency explosion पर व्यंग्य

• “सारी आधुनिक गणित set theory पर आधारित है” इस वाक्य का विरोध करते हुए किसी ने कहा कि Type Theory भी है

  • Type Theory, ZFC से ज़्यादा शक्तिशाली axiomatic system है। संबंधित व्याख्या के लिए MathOverflow उत्तर देखें
  • लेकिन ZF या ZFC जितना प्रभावशाली कोई type-theoretic axiom set अभी नहीं है
  • तकनीकी रूप से descriptive set theory foundational set theory से अलग है। इसे type और space की अवधारणाओं से आसानी से दोबारा बनाया जा सकता है, और कई बार यह ज़्यादा फायदेमंद होता है। गणितीय infinity को computational perspective से दोबारा समझना कोई नई कोशिश नहीं है
  • “abstract objects के set को व्यवस्थित करने वाला discipline” कहना set theory का बहुत सरलीकृत वर्णन है। फिर भी यह सच है कि अधिकांश गणित अब भी set-theoretic axioms से परिभाषित होती है