🤖 AI

First-Order Modal Logic in HOL: Deep and Shallow Embeddings with Automated Faithfulness (Extended Preprint)

यह शोध पत्र तीन विशिष्ट एम्बेडिंग्स प्रदान करके, क्वांटिफायर के लिए आवश्यक प्रतिस्थापन तंत्र विकसित करके, और पूर्ण डोमेन पर डीप वैलिडिटी को मिनिमल-शैलो व्याख्याओं के साथ सुसंगत बनाने के लिए डाउनवर्ड लोवेनहाइम-स्कोलेम प्रमेय को मैकेनाइज करके, इसाबेल/एचओएल (Isabelle/HOL) के भीतर प्रपोजिशनल से फर्स्ट-ऑर्डर मोडल लॉजिक तक डीप-एंड-शैलो एम्बेडिंग कार्यप्रणाली का विस्तार करता है।

मूल लेखक: Christoph Benzmüller, Daniel Kirchner

प्रकाशित 2026-07-14

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

CC BY 4.0

मूल लेखक: Christoph Benzmüller, Daniel Kirchner

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

कल्पना कीजिए कि आप एक सुपर-स्मार्ट रोबोट, जिसे हम "इसाबेल" (Isabelle) कह सकते हैं, को यह सिखाने की कोशिश कर रहे हैं कि एक ऐसी दुनिया के बारे में कैसे सोचा जाए जहाँ चीजें कुछ जगहों पर सच हो सकती हैं और कुछ जगहों पर झूठ, और जहाँ आप उन जगहों पर "हर कोई" या "कोई एक" के बारे में बात कर सकते हैं। यह फर्स्ट-ऑर्डर मोडल लॉजिक (FML) की दुनिया है। यह "क्या होगा अगर?" के खेल और हर संभावित व्यक्ति की उपस्थिति दर्ज करने जैसा है।

समस्या यह है कि इसाबेल एक बहुत ही सटीक, उच्च-स्तरीय भाषा बोलती है जिसे हायर-ऑर्डर लॉजिक (HOL) कहा जाता है। उसे हमारे "क्या होगा अगर?" वाले खेल को समझाने के लिए, लेखकों को हमारे तर्क (logic) को उसकी भाषा में अनुवाद करने के लिए तीन अलग-अलग पुल (embeddings) बनाने पड़े।

तीन पुल

द डीप ब्रिज (द ब्लूप्रिंट - गहरा पुल/ब्लूप्रिंट): यह लॉजिक का एक वास्तविक, भौतिक मॉडल लेगो (Lego) ईंटों से बनाने जैसा है। हर एक नियम, हर "और" (and), हर "नहीं" (not), और हर "सभी के लिए" (for all) एक विशाल संरचना में एक अलग ईंट है। यह भारी और विस्तृत है, जो लॉजिक के आकार का अध्ययन करने के लिए तो उत्तम है, लेकिन रोबोट के लिए इस पर तेज़ी से चलना कठिन है।
द हेवीवेट शैलो ब्रिज (द फुल-सर्विस होटल - भारी उथला पुल/पूर्ण-सेवा होटल): यह पुल एक लग्जरी होटल की तरह है जहाँ हर अतिथि (हर फॉर्मूला) को अपना कमरा मिलता है, और उस कमरे के साथ दुनिया का अपना नक्शा, सभी संभावित लोगों की एक सूची और एक विशिष्ट मार्गदर्शक भी आता है। यह सब कुछ स्पष्ट रूप से अपने साथ लेकर चलता है। यह बहुत स्पष्ट है, लेकिन इसे साथ लेकर चलना थोड़ा बोझिल है।
द लाइटवेट शैलो ब्रिज (द मिनिमलिस्ट टेंट - हल्का उथला पुल/न्यूनतम तंबू): यह पेपर का मुख्य आकर्षण है। यह एक छोटा, पोर्टेबल तंबू है। एक पूर्ण नक्शा और लोगों की पूरी सूची ले जाने के बजाय, यह केवल एक "दुनिया" और एक "मार्गदर्शक" (guide) लेकर चलता है। यह मान लेता है कि बाकी फर्नीचर पहले से ही वहाँ मौजूद है। यह इतना हल्का है कि रोबलेट अपने स्वचालित तर्क साधनों (जैसे "स्लेजहैमर" और "निटपिक") को इस पर अविश्वसनीय रूप से तेज़ी से चला सकता है।

बड़ी बाधा: द सरजेक्टिविटी प्रॉब्लम (Surjectivity Problem)

यहाँ कहानी पेचीदा हो जाती है। लेखक चाहते थे कि लाइटवेट टेंट और डीप ब्लूप्रिंट वास्तव में एक ही बात कह रहे हों। वे यह दिखाना चाहते थे कि यदि कोई कथन ब्लूप्रिंट में सत्य है, तो वह टेंट में भी सत्य है, और इसके विपरीत भी।

लेकिन एक अड़चन आई। लाइटवेट टेंट एक ऐसा मार्गदर्शक (variable assignment) उपयोग करता है जो केवल लोगों की एक गणनीय (countable) संख्या (जैसे प्राकृतिक संख्याएँ: 1, 2, 3...) की ओर संकेत कर सकता है। हालाँकि, डीप ब्लूप्रिंट एक ऐसे ब्रह्मांड की अनुमति देता है जहाँ लोगों की संख्या अगणनीय (uncountable) हो सकती है (जैसे एक रेखा पर सभी वास्तविक संख्याएँ)।

यदि ब्रह्मांड बहुत विशाल और अगणनीय है, तो एक मार्गदर्शक जो केवल गणनीय लोगों की सूची तक ही सीमित है, वह हर किसी तक नहीं पहुँच सकता। यह एक स्टेडियम के अरबों लोगों की हाजिरी लगाने के लिए केवल एक हज़ार नामों वाली सूची का उपयोग करने जैसा है। लेखक समझ गए कि यदि उन्होंने मार्गदर्शक को अगणनीय ब्रह्मांड में हर किसी तक पहुँचने के लिए मजबूर किया, तो प्रमाण टूट जाएगा।

जादुई समाधान: द डाउनवर्ड लोवेनहाइम-स्कोलेम थ्योरम (Downward Löwenheim–Skolem Theorem)

इसे ठीक करने के लिए, लेखकों ने अगणनीय भीड़ तक पहुँचने की कोशिश नहीं की। इसके बजाय, उन्होंने डाउनवर्ड लोवेनहाइम-स्कोलेम थ्योरम नामक एक गणितीय जादू का उपयोग किया।

इसे इस तरह सोचिए: लेखकों ने सिद्ध किया कि किसी भी विशाल, अगणनीय ब्रह्मांड के लिए, एक छोटा, गणable (countable) "छाया" ब्रह्मांड मौजूद होता है जो हमारे लॉजिक के लिए बिल्कुल वैसा ही व्यवहार करता है जैसा असली ब्रह्मांड करता है। यह एक विशाल शहर के सटीक, लघु मॉडल को खोजने जैसा है जहाँ हर सड़क का कोना और हर इमारत असली चीज़ की तरह ही व्यवहार करती है, लेकिन मॉडल इतना छोटा है कि वह डेस्क पर भी समा सके।

उन्होंने दिखाया कि भले ही वास्तविक दुनिया अगणनीय रूप से विशाल हो, हम हमेशा इसे इस गणable छाया में सिकोड़ सकते हैं। चूंकि हमारे लाइटवेट टेंट का मार्गदर्शक इस गणable छाया में मौजूद सभी तक पहुँच सकता है, इसलिए टेंट और ब्लूप्रिंट के बीच का पुल फिर से मजबूत हो जाता है। लेखकों ने सिद्ध किया कि यह काम करता है, जिसका अर्थ है कि उन्होंने केवल अनुमान या सिमुलेशन नहीं लगाया; उन्होंने इसाबेल के भीतर एक कठोर गणितीय तर्क का निर्माण किया।

वे क्या नहीं करते (The "No" List)

यह जानना महत्वपूर्ण है कि यह पेपर क्या नहीं करता, ताकि हमें गलत धारणा न हो:

नो वैरीइंग डोमेन (बदलते डोमेन नहीं): उन्होंने उस समस्या को हल नहीं किया जहाँ दुनिया से दुनिया में लोगों की सूची बदल जाती है (जैसे कुछ साइंस-फिक्शन कहानियों में जहाँ विभिन्न आयामों के बीच लोग पैदा होते या मरते हैं)। वे एक स्थिर डोमेन (constant domain) पर टिके रहे, जिसका अर्थ है कि प्रत्येक संभावित दुनिया में लोगों का एक ही सेट मौजूद है।
नो इक्वैलिटी (समानता नहीं): उन्होंने अपने लॉजिक में एक विशेष "बराबर" ( $=$ ) चिह्न शामिल नहीं किया। उन्होंने चीजों के बीच संबंधों पर ध्यान केंद्रित किया, न कि इस पर कि दो चीजें एक समान हैं या नहीं।
नो इनफिनिट वर्ल्ड्स (अभी अनंत दुनिया नहीं): अपने गणable छाया को काम करने के लिए, उन्हें यह मानना पड़ा कि दुनियाओं की संख्या भी गणable है। उन्होंने स्वीकार किया कि दुनियाओं की अगणनीय संख्या को संभालना भविष्य के कार्य के लिए है।

परिणाम: एक सत्यापित संबंध

लेखकों ने केवल यह सुझाव नहीं दिया कि यह काम करता है; उन्होंने इसे इसाबेल के भीतर मैकेनाइज (mechanize) किया। उन्होंने प्रतिस्थापन मशीनरी (variables को बिना तोड़े बदलने के उपकरण) बनाई और सिद्ध किया कि:

डीप ब्लूप्रिंट और लाइटवेट टेंट एक-दूसरे के प्रति वफादार (faithful) हैं।
आप तेज़, हल्के टेंट में चीजें सिद्ध कर सकते हैं, और वे प्रमाण गारंटी के साथ भारी, विस्तृत ब्लूप्रिंट में भी सत्य होंगे।
उन्होंने प्रसिद्ध लॉजिक नियमों (जैसे K-एक्सिओम और बारकन फॉर्मूला) की जाँच करके इसकी पुष्टि की और पुष्टि की कि वे कायम रहते हैं।

संक्षेप में, लेखकों ने एक अत्यंत कुशल, हल्का तरीका बनाया जिससे कंप्यूटर जटिल "क्या होगा अगर?" वाले परिदृश्यों के बारे में तर्क कर सके, और उन्होंने गणितीय रूप से सिद्ध किया कि यह शॉर्टकट कोई भी महत्वपूर्ण विवरण नहीं छोड़ता है, भले ही संभावनाओं का ब्रह्मांड अनंत रूप से बड़ा क्यों न हो। उन्होंने एक संभावित मृत-अंत (अगणनीय डोमेन की समस्या) को एक चतुर गणितीय संकुचन तकनीक का उपयोग करके एक हल किए गए पहेली में बदल दिया।

तकनीकी सारांश: HOL में प्रथम-क्रम मोडल लॉजिक: स्वचालित निष्ठा के साथ गहन और उथले एम्बेडिंग (Deep and Shallow Embeddings)

समस्या विवरण
प्रथम-क्रम मोडल लॉजिक (FML), क्वांटिफिकेशन (quantification) की अभिव्यक्ति शक्ति को मोडैलिटी (modality) के साथ जोड़ता है, जो कृत्रिम बुद्धिमत्ता, कंप्यूटर विज्ञान और दर्शनशास्त्र में अनुप्रयोगों के लिए एक महत्वपूर्ण ढांचा है। जबकि प्रोपोज़िशनल मोडल लॉजिक (PML) के क्लासिकल हायर-ऑर्डर लॉजिक (HOL) में एम्बेडिंग को सफलतापूर्वक स्वचालित किया गया है, FML तक इन तकनीकों का विस्तार करना महत्वपूर्ण जटिलता पेश करता है। विशेष रूप से, FML को वेरिएबल बाइंडिंग, सब्स्टीट्यूशन (substitution) और अनगिनत (uncountable) डोमेन पर क्वांटिफिकेशन को संभालने की आवश्यकता होती है। पूर्ववर्ती कार्य [5] ने PML के लिए एक डीप-एंड-शैलो एम्बेडिंग कार्यप्रणाली स्थापित की थी, लेकिन उन्होंने सब्स्टीट्यूशन मशीनरी या फर्स्ट-ऑर्डर क्वांटिफिकेशन में निहित सर्जिविटी (surjectivity) के मुद्दों को संबोधित नहीं किया था। चुनौती एक साथ एक डीप एम्बेडिंग (सिंटैक्टिक रीजनिंग के लिए) और शैलो एम्बेडिंग (स्वचालित प्रमाण खोज के लिए) प्रदान करने और उनकी पारस्परिक निष्ठा (faithfulness) को सिद्ध करने में निहित है, विशेष रूप से तब जब व्यक्तियों का डोमेन अनगिनत हो और शैलो एम्बेडिंग में वेरिएबल असाइनमेंट एक गणनीय (countable) सेट (जैसे, प्राकृतिक संख्याएँ) तक सीमित हो।

कार्यप्रणाली
लेखक कॉन्स्टेंट-डोमेन क्रिप्के सिमेंटिक्स के तहत FML का समर्थन करने के लिए Isabelle/HOL वातावरण का विस्तार करते हैं। यह कार्यप्रणाली तीन समानांतर एम्बेडिंग का उपयोग करती है:

डीप एम्बेडिंग (Deep Embedding): फॉर्मुलों को एक इंडक्टिव डेटाटाइप $\mathcal{F}$ के रूप में दर्शाया जाता है। सत्य (Truth) को एक मॉडल $\langle W, R, I, D \rangle$ , एक असाइनमेंट $g$ , और एक विश्व $w$ पर पुनरावर्ती (recursively) रूप से परिभाषित किया जाता है। वैधता ($ValD $) सभी मॉडलों, डोमेन$ D$ का सम्मान करने वाले असाइनमेंट्स, और विश्व पर सार्वभौमिक रूप से क्वांटिफाई करती है।
मैक्सिमल शैलो एम्बेडिंग (Maximal Shallow Embedding): फॉर्मुलों को सभी मॉडल मापदंडों ( $W, R, I, D, g, w$ ) पर स्पष्ट रूप से एब्स्ट्रैक्ट करने वाले $\lambda$ -टर्म्स में ऊपर उठाया जाता है। यह सीधे Isabelle के ऑटोमेशन के उपयोग की अनुमति देता है लेकिन जटिल प्रकार (types) उत्पन्न करता है।
मिनिमल शैलो एम्बेडिंग (Minimal Shallow Embedding): इसे एक Isabelle/HOL locale (MinS) के रूप में लागू किया गया है, यह दृष्टिकोण स्थिर मापदंडों ( $W, R, I, g$ ) को लोकेल आर्गुमेंट्स में बढ़ावा देता है, जिससे फॉर्मूला का प्रकार $w \Rightarrow bool$ में बदल जाता है। महत्वपूर्ण रूप से, अस्तित्वगत क्वांटिफायर (existential quantifier) को Isabelle के नेटिव मेटा-लेवल बाइंडर का उपयोग करके एनकोड किया जाता है, जबकि मोडल ऑपरेटर विश्व पैरामीटर को शिफ्ट करता है।

डीप और मिनिमल-शैलो एम्बेडिंग के बीच के अंतर को पाटने के लिए, लेखक एक व्यापक सब्स्टीट्यूशन मशीनरी (फ्री/बाउंड वेरिएबल प्रेडिकेट्स, कैप्चर-अवॉइडिंग सब्स्टीट्यूशन, अल्फाबेटिक रीनेमिंग) विकसित करते हैं, जो फर्स्ट-ऑर्डर क्वांटिफायर्स को संभालने के लिए आवश्यक है, जो पूर्ववर्ती प्रोपोज़िशनल कार्य में अनुपस्थित थी।

एक केंद्रीय तकनीकी नवाचार गणनीय डाउनवर्ड लोवेनहाइम-स्कोलेम प्रमेय (countable downward Löwenheim–Skolem theorem) का मशीनीकरण है। यह प्रमेय गारंटी देता है कि किसी भी मॉडल और किसी भी गणनीय प्रारंभिक उप-डोमेन $D_0$ के लिए, एक गणनीय प्रारंभिक उप-डोमेन $\mathcal{N}$ मौजूद होता है जो सत्य को संरक्षित करता है। इसका उपयोग सर्जिविटी समस्या को हल करने के लिए किया जाता है: चूंकि मिनिमल-शैलो असाइनमेंट $g: V \to D$ (जहाँ $V = \mathbb{N}$ ) $D$ पर अनगिनत डोमेन पर सर्जिव नहीं हो सकता है, इसलिए सीधा निष्ठा (faithfulness) विफल हो जाता है। एक गणनीय प्रारंभिक उप-डोमेन $\mathcal{N}$ का निर्माण करके जिस पर $g$ सर्जिव हो सके, और यह सिद्ध करके कि $D$ में सत्य $\mathcal{N}$ में सत्य के साथ मेल खाता है, लेखक पूर्ण डोमेन पर निष्ठा को पुनः प्राप्त करते हैं।

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

MinFMLinHOL विकास: बाइनरी रिलेशनल एटम्स, प्रोपोज़िशनल कनेक्टिव्स, अस्तित्वगत क्वांटिफिकेशन और कॉन्स्टेंट-डोमेन सिमेंटिक्स के तहत बॉक्स मोडैलिटी के साथ FML को कवर करने वाला एक पूर्ण Isabelle/HOL सिद्धांत।
तीन एम्बेडिंग: एक डीप एम्बेडिंग, एक मैक्सिमल शैलो एम्बेडिंग, और एक लाइटवेट मिनिमल शैलो एम्बेडिंग (लोकेल के रूप में पैकेज किया गया) का प्रावधान।
ग्लोबल फेथफुलनेस थ्योरम: MinS लोकेल का परिचय, जो एक मजबूत ग्लोबल थ्योरम, FaithfulMS_all प्रदान करता है, जो बताता है कि सभी मिनिमल-शैलो इंटरप्रिटेशन पर क्वांटिफाई करने से ठीक वही डीप वैलिडिटी प्राप्त होती है।
सब्स्टीट्यूशन मशीनरी: डीप एम्बेडिंग के लिए आवश्यक सिंथैक्टिक टूल्स (सब्स्टीट्यूशन लेम्मा, रीनेमिंग, साइज-बेस्ड इंडक्शन) का विकास, जो पूर्ववर्ती प्रोपोज़िशनल कार्य का विस्तार करता है।
मशीनाइज्ड लोवेनहाइम-स्कोलेम थ्योरम: कॉन्स्टेंट-डोमेन क्रिप्के सिमेंटिक्स के लिए डाउनवर्ड लोवेनहाइम-स्कोलेम प्रमेय का औपचारिक रूप (formalization), जो डीप और मिनिमल-शैलो एम्बेडिंग के बीच निष्ठा प्रमाण के स्वचालन को आधार प्रदान करता है।
सर्जिविटी समाधान: एक परिष्कृत लोकेल MinS_surj का डिज़ाइन जो यह मानता है कि असाइनमेंट एक प्रारंभिक उप-डोमेन पर सर्जिव है, जिससे असाइनमेंट के रेंज से पूर्ण डोमेन $D$ तक निष्ठा को बढ़ाया जा सके।

परिणाम
विकास को कई प्रयोगों के माध्यम से मान्य किया जाता है:

एक्सिओमैटिक वेरिफिकेशन (Axiomatic Verification): K-एक्सिओम, नेसेसिटेशन नियम (necessitation rule), और बारकन (Barcan) एवं कन्वर्स बारकन (converse Barcan) फॉर्मुलों की वैधता की पुष्टि (जो कॉन्स्टेंट-डोमेन सिमेंटिक्स के तहत मान्य हैं)।
फ्रेम कॉरेस्पोंडेंस (Frame Correspondences): रिफ्लेक्सिव, ट्रांजिटिव और सिमेट्रिक फ्रेम्स के बीच T, 4, और B एक्सिओम स्कीमा के कॉरेस्पोंडेंस का स्वचालित सत्यापन।
ऑटोमेशन: sledgehammer और nitpick टूल्स का उपयोग प्रदर्शित किया गया है। मिनिमल-शैलो एम्बेडिंग sledgehammer को फर्स्ट-ऑर्डर मोडल लक्ष्यों को साधारण HOL लक्ष्यों के रूप में मानने की अनुमति देता है, जबकि nitpick डोमेन टाइप को छोटा करके काउंटर-एग्जांपलल ढूंढ सकता है, जो प्रभावी रूप से स्पष्ट डोमेन गार्ड्स को बायपास करता है।

महत्व
यह पत्र दावा करता है कि यह कार्य पूर्ववर्ती प्रोपोज़िशनल एम्बेडिंग पद्धतियों के प्रथम-क्रम मामले में स्वाभाविक विस्तार है। इसका प्राथमिक महत्व यह प्रदर्शित करने में है कि डीप और शैलो एम्बेडिंग एक ही HOL सिद्धांत में स्वचालित निष्ठा प्रमाणों (automated faithfulness proofs) के साथ सह-अस्तित्व में रह सकते हैं, भले ही फर्स्ट-ऑर्डर क्वांटिफिकेशन और अनगिनत डोमेन की उपस्थिति हो। लोवेल मैकेनिज्म और लोवेनहाइम-स्कोलेम प्रमेय का लाभ उठाकर, लेखक वेरिएबल असाइनमेंट सर्जिविटी की तकनीकी बाधा को दूर करते हैं, जिससे कठोर डीप सिंटैक्टिक रिप्रेजेंटेशन की शुद्धता से समझौता किए बिना फर्स्ट-ऑर्डर मोडल लॉजिक के लिए शक्तिशाली HOL ऑटोमेशन टूल्स का उपयोग संभव हो जाता है। यह कार्य भविष्य के विस्तार, जैसे कि वैरीइंग-डोमेन सिमेंटिक्स या समानता (equality) के समावेश के लिए एक आधार स्थापित करता है, जबकि वर्तमान में यह न्यूनतम कॉन्स्टेंट-डोमेन फ्रैगमेंट पर केंद्रित है।

तीन पुल

बड़ी बाधा: द सरजेक्टिविटी प्रॉब्लम (Surjectivity Problem)

जादुई समाधान: द डाउनवर्ड लोवेनहाइम-स्कोलेम थ्योरम (Downward Löwenheim–Skolem Theorem)

वे क्या नहीं करते (The "No" List)

परिणाम: एक सत्यापित संबंध

इसी तरह के और पेपर