🔢 mathematics

Non-Derivability Results in Polymorphic Dependent Type Theory

यह शोध पत्र यह स्थापित करता है कि शुद्ध बहुरूपी आश्रित प्रकार सिद्धांत ( $\lambda$ P2) में, पैरामीट्रिक कोटिएंट प्रकार और सुदृढ़ सह-आगमन सिद्धांत परिभाषित नहीं किए जा सकते हैं, और फंक्शन एक्सटेंशनैलिटी (function extensionality) इंडक्शन सिद्धांतों को सिद्ध करने के लिए सख्ती से आवश्यक है, जो विशिष्ट मॉडलों का निर्माण करके किया गया है जहाँ ये सिद्धांत विफल हो जाते हैं।

मूल लेखक: Herman Geuvers

प्रकाशित 2026-03-05

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Herman Geuvers

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

मुख्य विचार: एक आदर्श लेगो कैसल (Lego Castle) बनाना

कल्पना कीजिए कि आप एक बहुत ही सख्त नियमों के सेट (एक "टाइप थ्योरी" जिसे $\lambda P2$ कहा जाता है) का उपयोग करके एक आदर्श लेगो कैसल बनाने की कोशिश कर रहे हैं एक वास्तुकार (architect) हैं।

इस दुनिया में, आप अद्भुत चीजें बना सकते हैं:

डेटा टाइप्स (Data Types): आप एक "प्राकृतिक संख्या" (Natural Number) ब्लॉक या एक "लिस्ट" (List) ब्लॉक बना सकते हैं।
फंक्शंस (Functions): आप इन ब्लॉक्स का उपयोग करने के निर्देश लिख सकते हैं।
लॉजिक (Logic): आप अपने ब्लॉक्स के बारे में चीजें साबित करने के लिए नियम लिख सकते हैं (जैसे, "यह मीनार स्थिर है")।

यह पेपर एक बहुत ही विशिष्ट प्रश्न पूछता है: क्या हम एक ऐसा "परफेक्ट कैसल" बना सकते हैं जहाँ ब्लॉक्स के व्यवहार के नियम केवल इस आधार पर स्वतः सिद्ध हो जाएं कि हमने उन्हें कैसे बनाया है?

विशेष रूप से, लेखक दो बड़े मुद्दों को देख रहा है:

इंडक्शन (Induction): वह नियम जो कहता है, "यदि मैं पहला कदम बना सकता हूँ, और मैं पिछले कदम से कोई भी अगला कदम बना सकता हूँ, तो मैं पूरी अनंत सीढ़ी बना सकता हूँ।"
को-इंडक्शन और कोटिएंट्स (Co-induction & Quotients): अनंत स्ट्रीम्स (जैसे कि कभी न खत्म होने वाला वीडियो फीड) के नियम और अलग-अलग ब्लॉक्स को आपस में जोड़ने के नियम (कोटिएंट्स)।

लेखक का निष्कर्ष यह है: नहीं, आप केवल बुनियादी नियमों के साथ ऐसा नहीं कर सकते। इसे काम करने के लिए आपको अतिरिक्त "जादुई औजारों" (extensions) को जोड़ना होगा।

समस्या: "स्मार्ट" एनकोडिंग का जाल

$\lambda P2$ की दुनिया में, आप एक नंबर (जैसे 5) को एक कच्चे नंबर के रूप में नहीं, बल्कि एक जटिल निर्देश के रूप में एनकोड करने की कोशिश कर सकते हैं: "मैं वह चीज़ हूँ जो इस क्रिया को 5 बार करती हूँ।"

यह सरल गणित के लिए बहुत अच्छा काम करता है। लेकिन जब आप इंडक्शन प्रिंसिपल (वह नियम जो आपको सभी संख्याओं पर गणित करने की अनुमति देता है) को सिद्ध करने का प्रयास करते हैं, तो सिस्टम विफल हो जाता है। यह कुछ ऐसा है जैसे ब्लूप्रिंट देखकर यह साबित करने की कोशिश करना कि एक पुल सुरक्षित है, लेकिन ब्लूप्रिंट में वास्तव में गुरुत्वाकर्षण के भौतिक विज्ञान (physics of gravity) का कोई उल्लेख नहीं है। सिस्टम जानता है कि नंबर को कैसे बनाना है, लेकिन वह संख्याओं के पूरे क्रम के बारे में तर्क (reasoning) करना नहीं जानता।

लेखक की खोज:
भले ही आप नंबर को परिभाषित करने के लिए हर "स्मार्ट" ट्रिक का उपयोग करें, सिस्टम इंडक्शन प्रिंसिपल को सिद्ध नहीं कर सकता। यह बुनियादी नियमों की एक मौलिक सीमा है।

काउंटर-मॉडेल्स (Counter-Models): "दर्पणों का गलियारा"

लेखक यह कैसे सिद्ध करता है? वह केवल यह नहीं कहता कि "यह कठिन है।" वह एक काउंटर-मॉडल बनाता है।

"दर्पणों के गलियारे" (एक गणितीय मॉडल) की कल्पना करें जहाँ ब्रह्मांड के नियम थोड़े मुड़े हुए हैं।

हमारी सामान्य दुनिया में, यदि दो चीजें एक जैसी दिखती हैं और एक जैसा व्यवहार करती हैं, तो वे एक ही हैं।
इस "दर्पणों के गलियारे" में, आपके पास ऐसी दो चीजें हो सकती हैं जो बिल्कुल एक जैसी दिखती हैं और एक जैसा व्यवहार करती हैं, लेकिन दर्पण कहता है कि वे अलग हैं।

इन विशिष्ट "दर्पणों के गलियारे" वाले ब्रह्मांडों को बनाकर, लेखक दिखाता है:

स्ट्रीम्स के लिए (अनंत वीडियो): आप एक स्ट्रीम टाइप बना सकते हैं, लेकिन आप यह सिद्ध नहीं कर सकते कि दो स्ट्रीम्स एक ही हैं क्योंकि वे हमेशा एक जैसा आउटपुट देती हैं। दर्पण की दुनिया में, वे अलग-अलग वस्तुएं हैं।
कोटिएंट्स के लिए (विलय): आप यह नियम नहीं बना सकते कि "यदि दो चीजें संबंधित हैं, तो उन्हें एक मानें।" दर्पण की दुनिया में, सिस्टम उन्हें मिलाने से इनकार कर देता है, भले ही आप उसे ऐसा करने के लिए कहें।

ये "दर्पण की दुनिया" प्रमाण के रूप में कार्य करती हैं कि बुनियादी नियम इन सिद्धांतों को काम करने के लिए मजबूर करने में बहुत कमजोर हैं।

समाधान: हमें किन औजारों की आवश्यकता है?

चूंकि बुनियादी नियम विफल हो जाते हैं, इसलिए यह पेपर देखता है कि क्या होता है जब हम हमारे लेगो सेट में "जादुई औजार" (Extensions) जोड़ते हैं। शोधकर्ताओं ने पहले इंडक्शन की समस्या को ठीक करने के लिए चार औजार जोड़ने का सुझाव दिया था:

आइडेंटिटी टाइप्स (Identity Types): यह कहने का एक तरीका कि "A, B के समान है।"
UIP (Uniqueness of Identity Proofs): एक नियम जो कहता है कि "A और B के समान होने को सिद्ध करने का केवल एक ही तरीका है।"
$\Sigma$ -Types: दो चीजों को मजबूती से एक साथ बांधने का एक तरीका।
FunExt (Function Extensionality): एक नियम जो कहता है कि "यदि दो फंक्शन्स हर इनपुट के लिए एक ही उत्तर देते हैं, तो वे एक ही फंक्शन हैं।"

बड़ा आश्चर्य:
लेखक इन टूल्स का एक-एक करके परीक्षण करता है। वह एक नया "दर्पणों का गलियारा" बनाता है जहाँ उसके पास आइडेंटिटी टाइप्स, UIP और $\Sigma$ -टाइप्स हैं, लेकिन NO Function Extensionality है।

इस दुनिया में:

सिस्टम बहुत शक्तिशाली है।
इसके पास सभी फैंसी टूल्स हैं।
लेकिन, यह अभी भी प्राकृतिक संख्याओं के लिए इंडक्शन प्रिंसिपल को सिद्ध नहीं कर सकता।

निष्कर्ष:
Function Extensionality (FunExt) ही गायब कड़ी है। इसके बिना, सिस्टम एक ऐसी कार की तरह है जिसमें एक बेहतरीन इंजन, एक परफेक्ट स्टीयरिंग व्हील और एक जीपीएस है, लेकिन पहिए नहीं हैं। यह चल नहीं सकती। इंडक्शन को काम करने के लिए आपको यह नियम चाहिए ही चाहिए कि "समान व्यवहार = समान फंक्शन"।

"कहानी" का सारांश

लक्ष्य: हम एक ऐसा लॉजिकल सिस्टम चाहते हैं जहाँ हम डेटा (जैसे नंबर) को परिभाषित कर सकें और स्वचालित रूप से यह सिद्ध कर सकें कि वे सही ढंग से व्यवहार करते हैं (Induction)।
विफलता: बुनियादी सिस्टम ( $\lambda P2$ ) में, यह असंभव है। आप नंबर को कितनी भी चतुराई से परिभाषित करें, सिस्टम इंडक्शन नियम को सिद्ध नहीं कर सकता।
प्रमाण: लेखक "टेढ़े ब्रह्मांडों" (counter-models) का निर्माण करता है जहाँ नियम तो लागू होते हैं, लेकिन इंडक्शन सिद्धांत विफल हो जाता है। यह सिद्ध करता है कि इंडक्शन सिद्धांत बुनियादी नियमों के भीतर छिपा हुआ नहीं है।
सुधार: हमें सिस्टम में अतिरिक्त नियम जोड़ने की आवश्यकता है।
महत्वपूर्ण घटक: प्रस्तावित सुधारों में से, Function Extensionality सबसे महत्वपूर्ण है। इसके बिना, अन्य सभी फैंसी टूल्स के साथ भी, आप इंडक्शन को सिद्ध नहीं कर सकते।

आपको इसकी परवाह क्यों करनी चाहिए?

यह पेपर एक मैकेनिक द्वारा दी गई सलाह की तरह है: "आप ट्रांसमिशन के बिना कार नहीं चला सकते।" यह अन्य शोधकर्ताओं को ऐसे सिस्टम में इंडक्शन बनाने में समय बर्बाद करने से बचाता है जिसमें बुनियादी तौर पर गियर बनाने की क्षमता ही नहीं है। यह हमें ठीक से बताता है कि हमें अपने लॉजिकल सिस्टम को वास्तविक गणित को संभालने के लिए पर्याप्त शक्तिशाली बनाने के लिए किन "गियर्स" (जैसे Function Extensionality) को जोड़ने की आवश्यकता है।

यहाँ हर्मन गेउवर्स (Herman Geuvers) के शोध पत्र "Non-Derivability Results in Polymorphic Dependent Type Theory" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र $\lambda P2$ (सेकंड-ऑर्डर डिपेंडेंट टाइप थ्योरी) में मौजूद मौलिक सीमाओं को संबोधित करता है, जो कैलकुलस ऑफ कंस्ट्रक्शंस (CC) का एक उप-तंत्र (subsystem) है। यद्यपि $\lambda P2$ इंडक्टिव डेटा टाइप्स (जैसे प्राकृतिक संख्याएँ, सूचियाँ और स्ट्रीम्स) के इम्प्रेडिकेटिव एनकोडिंग की अनुमति देता है और हायर-ऑर्डर लॉजिक का समर्थन करता है, लेकिन इसमें इन प्रकारों के लिए आवश्यक तर्क सिद्धांतों (reasoning principles) को सिद्ध करने की क्षमता का अभाव है।

विशेष रूप से, यह शोध पत्र $\lambda P2$ के निम्नलिखित विस्तारों (extensions) की आवश्यकता के संबंध में खुले प्रश्नों की जांच करता है:

इंडक्शन प्रिंसिपल्स (Induction Principles): क्या शुद्ध $\lambda P2$ में प्राकृतिक संख्याओं (या अन्य इंडक्टिव प्रकारों) के इंडक्शन सिद्धांत को सिद्ध किया जा सकता है?
को-इंडक्शन प्रिंसिपल्स (Coinduction Principles): क्या शुद्ध $\lambda P2$ में को-इंडक्शन सिद्धांत (विशेष रूप से, यह कि परिभाषित स्ट्रीम टाइप एक टर्मिनल को-अल्जेब्रा है) को सिद्ध किया जा सकता है?
क्वोटिएंट टाइप्स (Quotient Types): क्या $\lambda P2$ में पैरामेट्रिक क्वोटिएंट टाइप्स (जहाँ क्वोटिएंट ऑपरेशन पॉलिमोर्फिक है) को परिभाषित किया जा सकता है?
विस्तार की आवश्यकता (Necessity of Extensions): हाल के कार्यों (जैसे, अ्वोडी, फ्रे, स्पीट [1]) ने दिखाया है कि आइडेंटिटी टाइप्स, यूनिकनेस ऑफ आइडेंटिटी प्रूफ्स (UIP), फंक्शन एक्सटेंशनैलिटी (FunExt), और $\Sigma$ -टाइप्स जोड़ने से ये सिद्धांत प्राप्त किए जा सकते हैं। यह शोध पत्र पूछता है: इनमें से कौन से विस्तार अनिवार्य रूप से आवश्यक हैं? क्या FunExt आवश्यक है? क्या $\Sigma$ -टाइप्स आवश्यक हैं?

2. कार्यप्रणाली (Methodology)

लेखक नॉन-डेरिवेबिलिटी (non-derivability) को सिद्ध करने के लिए सिंटैक्टिक विश्लेषण (syntactic analysis) और काउंटर-मॉडेल्स (counter-models) के निर्माण का उपयोग करते हैं।

मॉडल फ्रेमवर्क (Model Framework): शोध पत्र वीकली एक्सटेंशनल कॉम्बिनेटरी अल्जेब्रा (WEKA) पर आधारित पॉलीसेट मॉडल्स (Polyset Models) का उपयोग करता है।
- मानक पैरामेट्रिक मॉडल्स (जहाँ प्रकार्स को पैरामैट्रिसिटी को संतुष्ट करने वाले रियलाइज़र के सेट के रूप में व्याख्यायित किया जाता है) के विपरीत, ये मॉडल्स अनटाइप्ड $\lambda$ -कैलकुलस टर्म्स ( $\beta$ या $\beta\eta$ समानता के मॉड्यूल) पर आधारित हैं।
- ये मॉडल्स "नॉन-पैरामेट्रिक" हैं, जिसका अर्थ है कि ये ऐसे टर्म्स की अनुमति देते हैं जो विशिष्ट टाइप इंस्टेंशिएशन के आधार पर अलग तरह से व्यवहार करते हैं, जिससे वह पैरामैट्रिसिटी टूट जाती है जो आमतौर पर इंडक्शन/को-इंडक्शन को बनाए रखने के लिए मजबूर करती है।
काउंटर-मॉडल निर्माण (Counter-Model Construction): यह सिद्ध करने के लिए कि कोई सिद्धांत व्युत्पन्न (derivable) नहीं है, लेखक एक विशिष्ट मॉडल का निर्माण करते हैं जहाँ:
1. टाइप थ्योरी के नियम सुसंगत (sound) हैं (मॉडल $\lambda P2$ का एक वैध इंटरप्रिटेशन है)।
2. प्रश्नगत सिद्धांत (जैसे, इंडक्शन टाइप का अस्तित्व) असत्य है (टाइप खाली है या आवश्यक टर्म मॉडल में मौजूद नहीं है)।
विस्तार विश्लेषण (Extension Analysis): पद्धति को आइडेंटिटी टाइप्स और $\Sigma$ -टाइप्स को शामिल करने वाले मॉडल्स तक विस्तारित किया गया है ताकि FunExt की आवश्यकता का परीक्षण किया जा सके।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

A. स्ट्रीम्स के लिए को-इंडक्शन की नॉन-डेरिवेबिलिटी (Non-Derivability of Coinduction for Streams)

संदर्भ: स्ट्रीम्स को $\lambda P2$ में अस्तित्व संबंधी प्रकारों (existential types) के रूप में परिभाषित किया जा सकता है (जैसे, $\exists \alpha. \alpha \times (\alpha \to \sigma) \times (\alpha \to \alpha)$ )।
परिणाम: परिभाषित स्ट्रीम टाइप एक टर्मिनल को-अल्जेब्रा नहीं है।
प्रमाण: लेखक दो स्ट्रीम्स, $s_1$ $s_{1}$ और $s_2$ $s_{2}$ का निर्माण करते हैं, जो बिसिमिलर (bisimilar) हैं (वे समान अनंत अवलोकन अनुक्रम उत्पन्न करते हैं) लेकिन मॉडल में वे असमान हैं।
- $\beta\eta$ समानता के मॉड्यूल में अनटाइप्ड $\lambda$ -टर्म्स पर आधारित मॉडल में, $s_1$ और $s_2$ दो अलग-अलग नॉर्मल फॉर्म्स में रिड्यूस होते हैं।
- इसलिए, टाइप $\Pi s, t : \text{Stream}. s \sim t \to s = t$ खाली है।
- यह दर्शाता है कि को-इंडक्शन सिद्धांत (को-रिकरसर की विशिष्टता) विफल हो जाता है।

B. पैरामेट्रिक क्वोटिएंट टाइप्स की नॉन-डेरिवेबिलिटी (Non-Derivability of Parametric Quotient Types)

संदर्भ: एक पैरामेट्रिक क्वोटिएंट टाइप $\sigma/R$ के लिए एक पॉलिमोर्फिक क्लास फंक्शन $cls $और एक रिकरसर$ rec_q $की आवश्यकता होती है जो संबंध$ R$ का सम्मान करता हो।
परिणाम: पैरामेट्रिक क्वोटिएंट टाइप्स (जैसा कि परिभाषा 2.7 में दिया गया है) $\lambda P2$ में परिभाषित नहीं किए जा सकते।
प्रमाण: लेखक दिखाते हैं कि अनटाइप्ड $\lambda$ $λ$ -टर्म्स के WECA पर आधारित मॉडल में, कोई भी टर्म $cls$ जो क्वोटिएंट गुणों को संतुष्ट करता है, उसे मॉडल की प्रकृति के कारण एक कॉन्स्टेंट फंक्शन के रूप में कार्य करना होगा।
- हालाँकि, एक क्वोटिएंट के उपयोगी होने के लिए, $cls $को तत्वों के बीच अंतर करना चाहिए (उदाहरण के लिए, यदि संबंध उन्हें समान नहीं बनाता है, तो$ cls(\text{true}) \neq cls(\text{false})$ होना चाहिए)।
- आवश्यक गैर-स्थिर व्यवहार और मॉडल द्वारा थोपे गए स्थिर व्यवहार के बीच का विरोधाभास नॉन-डेरिवेबिलिटी को सिद्ध करता है।

C. फंक्शन एक्सटेंशनैलिटी (FunExt) की आवश्यकता

संदर्भ: पिछले कार्यों ने स्थापित किया था कि आइडेंटिटी टाइप्स, UIP, और $\Sigma$ -टाइप्स जोड़ने से इंडक्शन की अनुमति मिलती है। प्रश्न यह था: क्या फंक्शन एक्सटेंशनैलिटी (FunExt) अनिवार्य रूप से आवश्यक है?
परिणाम: हाँ। आइडेंटिटी टाइप्स, UIP, और $\Sigma$ -टाइप्स के साथ भी, प्राकृतिक संख्याओं के लिए इंडक्शन सिद्ध नहीं किया जा सकता यदि Funxt मौजूद न हो।
प्रमाण:
- लेखक $\Lambda_{id}$ (आइडेंटिटी टाइप्स के लिए स्थिरांकों के साथ विस्तारित अनटाइप्ड $\lambda$ -कैलकुलस और $\Sigma$ -प्रोजेक्शन्स के साथ) पर आधारित एक मॉडल का निर्माण करते हैं।
- इस मॉडल में:
  - UIP सत्य है: समानता के सभी प्रमाण refl के बराबर हैं।
  - $\Sigma$ -टाइप्स और आइडेंटिटी टाइप्स सुसंगत (sound) हैं।
  - FunExt विफल हो जाता है: ऐसे फलन $f, g$ मौजूद हैं जहाँ $\forall x. f x = g x$ है लेकिन $f \neq g$ है।
  - इंडक्शन विफल हो जाता है: प्राकृतिक संख्याओं के इंडक्शन सिद्धांत के लिए टाइप खाली है।
- यह प्रदर्शित करता है कि FunExt वह महत्वपूर्ण घटक है जो [1] में अध्ययन किए गए विस्तारों में इंडक्शन को सिद्ध करने में सक्षम बनाता है।

4. महत्व (Significance)

टाइप थ्योरी विस्तारों का स्पष्टीकरण: यह शोध पत्र पॉलिमोर्फिक डिपेंडेंट टाइप थ्योरी में क्या प्राप्त किया जा सकता है और क्या नहीं, इसकी एक सटीक सीमा प्रदान करता है। यह पुष्टि करता है कि शुद्ध $\lambda P2$ में डेटा प्रकारों के "स्मार्ट" एनकोडिंग पर्याप्त नहीं हैं।
फंक्शन एक्सटेंशनैलिटी की भूमिका: सबसे महत्वपूर्ण खोज इंडक्शन को सिद्ध करने योग्य बनाने के लिए फंक्शन एक्सटेंशनैलिटी को एक महत्वपूर्ण एक्सियम (axiom) के रूप में अलग करना है। इसके बिना, UIP के साथ भी, सिस्टम मानक इंडक्टिव रीजनिंग का समर्थन करने के लिए बहुत कमजोर रहता है।
इम्प्रेडिकेटिविटी की सीमाएं: परिणाम इस बात को पुख्ता करते हैं कि जबकि इम्प्रेडिकेटिव एनकोडिंग (चर्च एनकोडिंग) डेटा को परिभाषित करने के लिए शक्तिशाली हैं, उनमें अतिरिक्त एक्सियम्स के बिना आंतरिक तर्क सिद्धांतों (जैसे इनिशियल अल्जेब्रा प्रॉपर्टी) को सहारा देने की संरचनात्मक शक्ति की कमी है।
पद्धतिगत योगदान: WECA पर आधारित सिंथेटिक, नॉन-पैरामेट्रिक मॉडल्स का उपयोग टाइप थ्योरी में नकारात्मक परिणाम सिद्ध करने के लिए एक मजबूत उपकरण प्रदान करता है, जो रियलाइज़ेबिलिटी या PER मॉडल्स का एक विकल्प है जो अक्सर इन सिद्धांतों को डिफ़ॉल्ट रूप से मान्य कर देते हैं।

निष्कर्ष (Conclusion)

हर्मन गेउवर्स निष्कर्ष निकालते हैं कि उचित इंडक्शन और को-इंडक्शन सिद्धांतों (जैसे इनिशियल अल्जेब्रा और टर्मिनल को-अल्जेब्रा) के साथ डेटा प्रकारों को परिभाषित करने के लिए, केवल शुद्ध कैलकुलस ऑफ कंस्ट्रक्शंस या $\lambda P2$ पर निर्भर नहीं रहा जा सकता। हमें सिस्टम का विस्तार करना होगा। विशेष रूप से, जबकि आइडेंटिटी टाइप्स, UIP, और $\Sigma$ -टाइप्स आवश्यक हैं, फंक्शन एक्सटेंशनैलिटी (FunExt) निर्णायक कारक है जो इंडक्शन सिद्धांत के व्युत्पन्न को सक्षम बनाता है। इसके बिना, प्राकृतिक संख्याओं के सबसे परिष्कृत एनकोडिंग भी इंडक्शन सिद्धांत को संतुष्ट करने में विफल रहते हैं।