Hindman's theorem does not code $\emptyset^{(\omega)}$ in one application

तकनीकी सारांश: "हिंडमैन का प्रमेय एक अनुप्रयोग में $\emptyset^{(\omega)}$ को कोड नहीं करता है"

समस्या विवरण
यह शोध पत्र हिंडमैन के प्रमेय (HT) की गणनात्मक-सैद्धांतिक जटिलता (computability-theoretic complexity) को संबोधित करता है, विशेष रूप से इनपुट कलरिंग के सापेक्ष इसके द्वारा उत्पन्न समाधानों की शक्ति के संबंध में। हिंडमैन का प्रमेय बताता है कि प्राकृतिक संख्याओं $\mathbb{N}$ के प्रत्येक परिमित रंग (finite coloring) के लिए, एक अनंत समुच्चय $H$ मौजूद होता है, ऐसा कि $H$ के अलग-अलग तत्वों के सभी गैर-रिक्त परिमित योगों (जिसे $FS(H)$ द्वारा दर्शाया जाता है) का सेट एक ही रंग का (monochromatic) होता है।

पूर्व कार्य ने निम्नलिखित सीमाएँ स्थापित की थीं:

1. ऊपरी सीमा (Upper Bound): ब्लास, हर्स्ट और सिम्पसन (1987) ने सिद्ध किया कि प्रत्येक गणनीय (computable) कलरिंग के लिए, एक ऐसा समाधान मौजूद होता है जो खाली सेट के $\omega$-जंप, $\emptyset^{(\omega)}$, से गणनीय है।
2. निचली सीमा (Lower Bound): उन्हीं लेखकों ने सिद्ध किया कि कुछ गणनीय कलरिंग्स के लिए, प्रत्येक समाधान हैल्टिंग सेट $\emptyset'$ को कंप्यूट करता है। बाद में, लियाओ (2026) ने इसे सुधारते हुए दिखाया कि कुछ गणनीय कलरिंग्स के लिए, कोई $\Pi^0_3$ समाधान मौजूद नहीं होता है।

यह शोध पत्र जिस केंद्रीय खुले प्रश्न को संबोधित करता है, वह यह है कि क्या हिंडमैन के प्रमेय का एक एकल अनुप्रयोग के लिए $\emptyset^{(\omega)}$ का ऊपरी स्तर इष्टतम (optimal) है। विशेष रूप से, क्या हिंडमैन के प्रमेय का प्रत्येक अंकगणितीय (arithmetic) उदाहरण एक ऐसा समाधान प्रदान करता है जो $\emptyset^{(\omega)}$ को कंप्यूट नहीं करता है?

कार्यप्रणाली (Methodology)
लेखक टोស្នर (Towsner) के हिंडमैन के प्रमेय के कॉम्बिनेटोरियल प्रमाण से अनुकूलित एक फोर्सिंग तकनीक (forcing technique) का उपयोग करते हैं। कार्यप्रणाली में निम्नलिखित घटक शामिल हैं:

1. पुनर्गठन (Reformulation): समस्या को 'फाइनाइट यूनियन थ्योरम' (FUT) की भाषा में अनुवादित किया जाता है, जो HT के गणनीय रूप से समतुल्य है। इसमें $\mathbb{N}$ के गैर-रिक्त परिमित उपसमुच्चयों, $P_{fin}(\mathbb{N})$, के कलरिंग और एक अनंत ब्लॉक अनुक्रम $H$ की खोज शामिल है ताकि परिमित संघों (finite unions) का सेट $FU(H)$ एक ही रंग का हो।
2. टोស្នर ट्रीज़ और मैचिंग (Towsner Trees and Matching): लेखक टोស្នर की "हाफ-मैच" (half-match) और "फुल-मैच" (full-match) की अवधारणाओं का उपयोग करते हैं। एक परिमित सेट $F$, एक अनंत ब्लॉक अनुक्रम $X$ के साथ हाफ-मैच करता है यदि प्रत्येक परिमित संघ $b \in FU(X)$ के लिए, एक $a \in F$ मौजूद है ताकि $f(a \cup b) = f(b)$ हो। एक फुल-मैच के लिए $f(a) = f(a \cup b) = f(b)$ की आवश्यकता होती है।
   • वे एक "टोស្នर अनुक्रम" का निर्माण करते हैं, जो एक नेस्टेड हाफ-मैच अनुक्रम है जो एक ट्री संरचना (टोស្នर ट्री) को प्रेरित करता है।
   • वे स्थापित करते हैं कि एक अंकगणितीय कलरिंग $f$ के लिए, एक $f''$-गणनीय टोស្នर अनुक्रम मौजूद होता है।
3. फोर्सिंग नोशन (Forcing Notion): "P-कंडीशन्स" का उपयोग करके एक नया फोर्सिंग नोशन परिभाषित किया गया है, जो ब्लॉक अनुक्रमों के एक परिमित सेट $I$ और एक अनंत रिज़र्वोइर $X$ के युग्म हैं। एक कंडीशन "f-मैचिंग" तब होती है जब वह कलरिंग से संबंधित एक विशिष्ट विस्तार गुण को संतुष्ट करती है।
4. प्रथम-जंप नियंत्रण (First-Jump Control): मुख्य नवाचार एक विशिष्ट परिभाषित गुणों वाले "फोर्सिंग प्रश्न" का डिज़ाइन है। यह एक ऐसा जेनेरिक फिल्टर बनाने की अनुमति देता है जहाँ परिणामी समाधान $G$ एक विशिष्ट गैर-अंकगणितीय सेट $C$ को कंप्यूट करने से बचता है। फोर्सिंग संबंध को समाधान के प्रथम जंप को नियंत्रित करने के लिए डिज़ाइन किया गया है, यह सुनिश्चित करते हुए कि समाधान इनपुट के सापेक्ष एक विशिष्ट अंकगणितीय डिग्री के भीतर रहे, जबकि लक्षित शंकु (target cone) से बचता रहे।
5. विकर्षण (Diagonalization): यह सुनिश्चित करने के लिए कि $C \not\leq_T G$, लेखक आवश्यकताओं $R^C_e: W^G_e \neq C$ को संतुष्ट करते हैं। $\Sigma^0_1$ सूत्रों के लिए फोर्सिंग प्रश्न का विश्लेषण करके, वे प्रदर्शित करते हैं कि किसी भी गैर-अंकगणितीय सेट $C$ और अंकगणितीय कलरिंग के लिए, एक स्थिति को विस्तारित किया जा सकता है ताकि $G$ किसी तत्व पर $C$ से भिन्न हो जाए।

प्रमुख योगदान और परिणाम

1. मुख्य प्रमेय (कोन अवॉयडेंस - Cone Avoidance): प्राथमिक परिणाम (मुख्य प्रमेय 1.5) कहता है: मान लीजिए $C$ एक गैर-अंकगणितीय डिग्री वाला सेट है। प्रत्येक $\ell \geq 1$ और प्रत्येक अंकगणितीय डिग्री वाली कलरिंग $f: \mathbb{N} \to \ell$ (या $P_{fin}(\mathbb{N}) \to \ell$) के लिए, एक अनंत सेट $H$ मौजूद है ताकि $FS(H)$एक$f$-मोनोक्रोमैटिक हो और$C \not\leq_T H$ हो।

   • उपसंहार (Corollary): $C = \emptyset^{(\omega)}$ सेट करके, लेखक सिद्ध करते हैं कि हिंडमैन के प्रमेय का प्रत्येक अंकगणितीय उदाहरण एक ऐसा समाधान प्रदान करता है जो $\emptyset^{(\omega)}$ को कंप्यूट नहीं करता है। यह दर्शाता है कि हिंडमैन के प्रमेय के लिए $\emptyset^{(\omega)}$ का कंप्यूटेशनल ऊपरी स्तर एकल अनुप्रयोग के लिए इष्टतम नहीं है।

2. पुनरावृत्ति की सीमाएँ (Limitations of Iteration): लेखक स्पष्ट करते हैं कि यह परिणाम यह संकेत नहीं देता कि हिंडमैन का प्रमेय $\text{ACA}^+_0$ से कमजोर है। कोन अवॉयडेंस ट्यूरिंग रिड्यूसिबिलिटी ($C \not\leq_T H$) के लिए तो लागू होता है, लेकिन आवश्यक रूप से अंकगणितीय रिड्यूसिबिलिटी के लिए नहीं। इसलिए, इस प्रमेय को $\emptyset^{(\omega)}$ को बाहर करने वाला $\omega$-मॉडल बनाने के लिए पुनरावृत्त (iterate) नहीं किया जा सकता है।

3. सरल कलरिंग्स (Simple Colorings): शोध पत्र "सरल कलरिंग्स" (ऐसी कलरिंग्स जहाँ यूनियन का रंग घटकों के रंग और उनकी सापेक्ष स्थिति पर निर्भर करता है) तक HT के प्रतिबंधों की जांच करता है।

   • वे सिद्ध करते हैं कि सरल कलरिंग्स के लिए फाइनाइट यूनियन थ्योरम का प्रतिबंध $\text{RCA}_0$ पर $\text{ACA}_0$ के समतुल्य है।
   • वे दिखाते हैं कि ब्लास, हर्स्ट और सिम्पसन द्वारा निचली सीमा सिद्ध करने के लिए उपयोग की गई विशिष्ट कलरिंग (जो "बहुत छोटे अंतराल" पर आधारित है) एक सरल कलरिंग है।

4. टोស្នर ट्रीज़ की जटिलता: वे सिद्ध करते हैं (प्रपोजिशन 2.24) कि ब्लास, हर्स्ट और सिम्पसन द्वारा निर्मित विशिष्ट कलरिंग के लिए, प्रत्येक टोស្នर अनुक्रम $\emptyset'$ को कंप्यूट करता है। यह सुझाव देता है कि जबकि टोស្នर ट्रीज़ शक्तिशाली उपकरण हैं, उनके अस्तित्व में कुछ गणनीय कलरिंग्स के लिए महत्वपूर्ण कंप्यूटेशनल शक्ति अंतर्निहित रूप से एनकोड होती है, हालांकि यह अन्य प्रमाणों या फुल-मैच के अस्तित्व को खारिज नहीं करता है जो इन ट्रीज़ पर निर्भर नहीं करते हैं।

महत्व
यह शोध पत्र इस प्रश्न को हल करता है कि क्या हिंडमैन के प्रमेय के एकल अनुप्रयोग के लिए $\emptyset^{(\omega)}$ की ऊपरी सीमा सटीक है। यह सिद्ध करके कि गैर-अंकगणितीय शंकुओं (cones) से बचा जा सकता है, लेखक दिखाते हैं कि हिंडमैन का प्रमेय अंकगणितीय इनपुट के लिए समाधान उत्पन्न करने हेतु स्वाभाविक रूप से $\omega$-जंप की पूरी शक्ति की आवश्यकता नहीं रखता है। यह प्रमेय के कंप्यूटेशनल कंटेंट की समझ को परिष्कृत करता है, जो एक समाधान खोजने की जटिलता और विशिष्ट उच्च-डिग्री सेटों को कंप्यूट करने वाले समाधान को खोजने की जटिलता के बीच अंतर करता है। यह कार्य कॉम्बिनेटोरियल प्रमाणों (टोស្នर के) को फोर्सिंग तकनीकों के साथ जोड़कर समाधानों के ट्यूरिंग डिग्री पर सटीक नियंत्रण प्राप्त करता है।