💻 computer science

Unifying Sequent Systems for Gödel-Löb Provability Logic via Syntactic Transformations

यह शोध पत्र एक रैखिकीकरण तकनीक (linearization technique) और एक सामान्य रूप (normal form) सहित नवीन वाक्यात्मक रूपांतरणों को प्रस्तुत करके प्रूफ़ थ्योरी (proof theory) में एक खुली समस्या का समाधान करता है, जिससे गोडेल-लोब (Gödel-Löb) प्रूवेबिलिटी लॉजिक के छह प्रमुख सीक्वेंट-आधारित औपचारिक प्रणालियों के बीच पूर्ण रचनात्मक प्रमाण पत्राचार (constructive proof correspondences) स्थापित करने के लिए संरचनात्मक और चक्रीय प्रणालियों को एकीकृत किया जाता है और इस तर्क के लिए प्रथम कट-फ्री लीनियर नेस्टेड सीक्वेंट कैलकुलस (cut-free linear nested sequent calculus) प्राप्त किया जाता है।

मूल लेखक: Tim S. Lyon

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

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

CC BY 4.0

मूल लेखक: Tim S. Lyon

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

कल्पना कीजिए कि आप एक बहुत ही जटिल पहेली को हल करने की कोशिश कर रहे हैं। तर्क (logic) की दुनिया में, यह पहेली यह सिद्ध करने की कोशिश है कि एक विशिष्ट कथन गोडेल-लोब लॉजिक (Gödel-Löb logic), जिसे अक्सर GL कहा जाता है, के भीतर सत्य है। इस तर्क का उपयोग "प्रमाणिकता" (provability) के बारे में तर्क करने के लिए किया जाता है—अनिवार्य रूप से, यह पूछना कि "क्या यह सिद्ध करना संभव है कि यह कथन सत्य है?"

दशकों से, गणितज्ञों ने इन पहेलियों को हल करने के लिए अलग-अलग "कार्यशालाएं" (जिन्हें सीक्वेंट सिस्टम/sequent systems कहा जाता है) बनाई हैं। प्रत्येक कार्यशाला के अपने अद्वितीय उपकरण, नियम और ब्लूप्रिंट होते हैं। कुछ कार्यशालाएं सपाट तालिकाओं का उपयोग करती हैं, कुछ 3D पेड़ों का, और कुछ अनंत लूपों का।

समस्या क्या है? किसी को ठीक से यह नहीं पता था कि एक कार्यशाला में मिले समाधान को दूसरी कार्यशाला की भाषा में कैसे अनुवादित किया जाए। यदि आपने "ट्री वर्कशॉप" (Tree Workshop) में एक पहेली हल की, तो क्या आप इसे "लूप वर्कशॉप" (Loop Workshop) में सिद्ध कर सकते थे? अब तक, यह एक रहस्य था।

टिम एस. लियोन का यह शोध पत्र एक सार्वभौमिक अनुवादक (universal translator) और एक निर्माण मार्गदर्शिका (construction guide) के रूप में कार्य करता है जो इन सभी विभिन्न कार्यशालाओं को जोड़ता है। यह कैसे काम करता है, इसे सरल उपमाओं के माध्यम से यहाँ समझाया गया है:

1. पाँच अलग-अलग कार्यशालाएँ

यह शोध पत्र GL में चीजें सिद्ध करने के पाँच विशिष्ट तरीकों पर ध्यान केंद्रित करता है:

द फ्लैट वर्कशॉप (GLseq): क्लासिक, पारंपरिक तरीका। इसे एक साधारण, सीधी रेखा के पाठ के रूप में सोचें।
द लूप वर्कशॉप (GLcirc और GL∞): ये अनुमति देते हैं कि प्रमाण अपने आप में वापस घूम सकें (जैसे अपनी ही पूंछ खाता हुआ सांप) या एक संरचित तरीके से अनंत काल तक चलें।
द ट्री वर्कशॉप (CSGL∗): यहाँ, प्रमाण पारिवारिक वृक्षों (family trees) की तरह दिखते हैं। एक मुख्य कथन उप-कथनों में विभाजित होता है, जो आगे और अधिक शाखाओं में विभाजित होते हैं।
द ग्राफ वर्कशॉप (G3KGL): यह एक जटिल मानचित्र की तरह है जिसमें नोड्स और उन्हें जोड़ने वाली सड़कें हैं।
द न्यू वर्कशॉप (LNGL): यह शोध पत्र इसका आविष्कार करता है। यह एक "लीनियर नेस्टेड" (Linear Nested) सिस्टम है, जो पारदर्शी शीटों के एक ढेर की तरह है, जहाँ प्रत्येक शीट में पाठ की एक साधारण रेखा होती है, लेकिन वे एक दूसरे के ऊपर रखी जाती हैं।

2. बड़ी चुनौती: संरचना को "छोड़ना" (Shedding the Structure)

सबसे कठिन हिस्सा ट्री वर्कशॉप (CSGL∗) से फ्लैट वर्कशॉप (GLseq) की ओर बढ़ना है।

उपमा: कल्पना करें कि आपके पास एक मूर्ति है जो एक जटिल, शाखाओं वाले पेड़ से बनी है। आप इसे एक साधारण, सपाट कागज की शीट में बदलना चाहते हैं बिना किसी जानकारी को खोए।
समस्या: आप एक पेड़ को केवल सपाट नहीं कर सकते; उसकी शाखाएं उलझ जाएंगी।
समाधान (चरण 1: एंड-एक्टिव/End-Active): लेखक पहले पेड़ को पुनर्गठित करता है ताकि सारा "एक्शन" (महत्वपूर्ण नियम) केवल शाखाओं के बिल्कुल सिरों (पत्तियों) पर हो। यह एक बोन्साई पेड़ को छांटने जैसा है ताकि सारी वृद्धि केवल सिरों पर हो।
समाधान (चरण 2: लीनियरलाइजेशन/Linearization): एक बार जब पेड़ को छांट दिया जाता है, तो लेखक एक नई तकनीक पेश करता है जिसे लीनियरलाइजेशन कहा जाता है। कल्पना करें कि आप उस छंटे हुए पेड़ को सावधानी से "अनस्पूल" (unspooling) कर रहे हैं। आप जड़ से सिरे तक एक पथ का अनुसरण करते हैं, और जैसे-जैसे आप आगे बढ़ते हैं, आप शाखाओं को एक सीधी रेखा में बिछाते जाते हैं।
परिणाम: यह LNGL सिस्टम बनाता है। यह प्रमाणों को लिखने का एक नया तरीका है जो सरल रेखाओं के ढेर जैसा दिखता है। यह शोध पत्र का पहला बड़ा आविष्कार है: जटिल पेड़ों को सरल रेखाओं में बदलने का एक नया उपकरण।

3. "नॉर्मल फॉर्म" का नृत्य

एक बार जब प्रमाण इस नए "रेखाओं के ढेर" वाले प्रारूप (LNGL) में आ जाता है, तो लेखक इसे एक विशिष्ट लय में व्यवस्थित करने का तरीका दिखाता है, जिसे नॉर्मल फॉर्म (Normal Form) कहा जाता है।

उपमा: एक डांस रूटीन के बारे में सोचें। प्रमाण बेतरतीब ढंग से नहीं कूदता। यह चरणों में चलता है:
1. पहले, यह सभी "लोकल" (स्थानीय) चालें करता है (सरल तर्क जैसे "और" या "या" से निपटना)।
2. फिर, यह "प्रोपैगेशन" (प्रसार) चालें करता है (सूचना को रेखा में नीचे फैलाना)।
3. अंत में, यह "मोडल" (modal) चालें करता है (जटिल "प्रोवेबिलिटी बॉक्स" से निपटना)।
प्रमाण को इस विशिष्ट क्रम में नचाने से, इसे पुराने, क्लासिक "फ्लैट वर्कशॉप" (GLseq) में अनुवादित करना आसान हो जाता है।

4. लूप को बंद करना

यह शोध पत्र वहीं नहीं रुकता। यह बिंदुओं को जोड़ता है:

यह ट्री प्रमाणों को न्यू स्टैक (New Stack) प्रमाणों में बदलना दिखाता है।
यह दिखाता है कि कैसे न्यू स्टैक प्रमाणों को क्लासिक फ्लैट प्रमाणों में बदला जाता है।
यह दिखाता है कि कैसे क्लासिक फ्लैट प्रमाणों को ग्राफ प्रमाणों में बदला जाता है।
यह हमें याद दिलाता है कि लूप प्रमाण पहले से ही क्लासिक फ्लैट प्रमाणों से जुड़े हुए हैं (शामकानो के पिछले कार्य के कारण)।

अंतिम निष्कर्ष

इन पुलों का निर्माण करके, लेखक ने गोडेल-लोब लॉजिक के परिदृश्य का एक पूर्ण मानचित्र तैयार किया है।

पहले: यदि आपके पास ट्री वर्कशॉप में एक प्रमाण था, तो आप लूप वर्कशॉप के उपकरणों का आसानी से उपयोग नहीं कर सकते थे।
अब: आप इनमें से किसी भी छह प्रणालियों में से किसी भी प्रमाण को ले सकते हैं, उसे किसी भी अन्य प्रणाली में अनुवादित कर सकते हैं, और जान सकते हैं कि वह अभी भी एक वैध प्रमाण है।

यह शोध पत्र मूल रूप से कहता है: "हमने एक सार्वभौमिक एडेप्टर बनाया है। चाहे आप तर्क की कौन सी भी भाषा बोलते हों, अब आप इस परिवार की किसी भी अन्य भाषा के प्रमाणों को समझ सकते हैं और उपयोग कर सकते हैं।" यह गणितज्ञों को किसी विशिष्ट कार्य के लिए सबसे सुविधाजनक उपकरण चुनने और फिर उस परिणाम को उस उपकरण में अनुवादित करने की अनुमति देता है जिसकी उन्हें अंतिम उत्तर के लिए आवश्यकता है, बिना सब कुछ फिर से सिद्ध किए।

तकनीकी सारांश: गोडेल-लोब प्रवेबिलिटी लॉजिक के लिए सक्वेंट सिस्टम्स का एकीकरण

समस्या विवरण
यह शोध पत्र गोडेल-लोब प्रवेबिलिटी लॉजिक (GL) के प्रूफ़ थ्योरी में एक महत्वपूर्ण अंतराल को संबोधित करता है। यद्यपि GL के पास विविध प्रकार के कट-फ्री (cut-free) सक्वेंट-शैली के फॉर्मलिज्म मौजूद हैं, उनके बीच के संबंधों को पूरी तरह से स्थापित नहीं किया गया था। विशेष रूप से, पूर्व कार्यों ने निम्नलिखित के बीच प्रूफ़-थ्योरेटिक पत्राचार (correspondences) स्थापित किए थे:

स्ट्रक्चरल सिस्टम्स: नेग्री का लेबल युक्त सक्वेंट सिस्टम ($G3KGL $) और पॉगियोलेस का ट्री-हाइपरसिक्वेंट सिस्टम ($ CSGL^*$), गोर और रामानायके के माध्यम से।
प्रूफ़-स्ट्रक्चर जनरलाइजेशन: साम्बिन और वेलेंटिनी का जेंट्ज़ेन सिस्टम ( $GL_{seq}$ ), शामकानों का नॉन-वेलफाउंडेड सिस्टम ( $GL_\infty$ ), और शामकानों का साइक्लिक सिस्टम ( $GL_{circ}$ ), शामकानों के माध्यम से।

हालाँकि, स्ट्रक्चरल सिस्टम्स ($G3KGL$, $CSGL^*$ ) और प्रूफ़-स्ट्रक्चर जनरलाइजेशन ( $GL_{seq}$ , $GL_\infty$ , $GL_{circ}$ ) के बीच प्रमाणों की अंतर-परिवर्तनीयता (inter-translatability) एक खुला प्रश्न बना हुआ था। अंतर्निहित कठिनाई इन जटिल स्ट्रक्चरल सक्वेंट्स (ग्राफ या जेंट्ज़ेन सक्वेंट्स के पेड़) का उपयोग करने वाले प्रमाणों को मानक जेंट्ज़ेन सक्वेंट्स का उपयोग करने वाले प्रमाणों में बदलने की प्रक्रिया में निहित है, जिसके लिए इस अतिरिक्त स्ट्रक्चरल डेटा को "त्यागने" (shedding) की आवश्यकता होती है।

कार्यप्रणाली
लेखक, टिम एस. लियोन, इन भिन्न फॉर्मलिज्मों के बीच की खाई को पाटने के लिए सिंटैक्टिक प्रूफ़ ट्रांसफॉर्मेशन की एक श्रृंखला का निर्माण करके इस खुले प्रश्न को हल करते हैं। कार्यप्रणाली तीन प्राथमिक चरणों में आगे बढ़ती है:

एंड-एक्टिव फॉर्म में पुनर्गठन: शोध पत्र पहले यह प्रदर्शित करता है कि ट्री-हाइपरसिक्वेंट सिस्टम $CSGL^*$ के प्रमाणों को "एंड-एक्टिव" (end-active) रूप में कैसे पुनर्गठित किया जाए। एक एंड-एक्टिव प्रमाण में, इन्फरेंस रूल्स के प्रिंसिपल और ऑक्सिलरी फॉर्मुला केवल ट्री-सिक्वेंट संरचना के (प्री-)लीव्स (leaves) पर होते हैं। इसे $CSGL^*$ में नियमों की हाइट-प्रिजर्विंग इनवर्टीबिलिटी (height-preserving invertibility) का लाभ उठाते हुए, नॉन-एंड-एक्टिव नियमों को प्रमाण वृक्ष (proof tree) के माध्यम से नीचे की ओर जाने (permuting downward) द्वारा प्राप्त किया जाता है।
लीनियराइजेशन (Linearization): एक नवीन "लीनियराइजेशन तकनीक" पेश की गई है जो इन एंड-एक्टिव ट्री-सिक्वेंट प्रमाणों को लीनियर नेस्टेड सक्वेंट्स का उपयोग करने वाले प्रमाणों में बदलने के लिए है। इस तकनीक में ट्री-सिक्वेंट में रूट से लीफ तक के विशिष्ट पथों की पहचान करना और ट्री-सब-स्ट्रक्चर को "प्रून" (pruning) करना शामिल है, जो प्रभावी रूप से ट्री संरचना को जेंट्ज़ेन सक्वेंट्स के एक लीनियर सीक्वेंस में सिकोड़ देता है। यह प्रक्रिया एक नया कैलकुलस, LNGL (GL के लिए लीनियर नेस्टेड सक्वेंट कैलकुलस) उत्पन्न करती है।
नॉर्मल फॉर्म और जेंट्ज़ेन में अनुवाद: शोध पत्र यह दिखाता है कि LNGL में प्रमाणों को एक विशिष्ट नॉर्मल फॉर्म में बदला जा सकता है। इस रूप में, प्रमाण पुनरावृत्ति चरणों में चलते हैं: स्थानीय नियम (local rules), उसके बाद प्रोपेगेशन नियम ( $4L$ और $\Box L$ ), और अंत में मोडल नियम ( $\Box R$ )। इस संरचित प्रमाण को फिर साम्बिन और वेलेंटिनी के जेंट्ज़ेन सिस्टम ( $GL_{seq}$ ) में अनुवादित किया जाता है। अंत में, मानक रूपांतरण $GL_{seq}$ प्रमाणों को वापस लेबल युक्त सिस्टम $G3KGL $और साइक्लिक/नॉन-वेलफाउंडेड सिस्टम ($ GL_{circ}$, $GL_\infty$ ) में मैप करते हैं।

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

नया कैलकुलस (LNGL): शोध पत्र गोडेल-लोब लॉजिक के लिए पहले कट-फ्री लीनियर नेस्टेड सक्वेंट कैलकुलस, LNGL को पेश करता है। यह सिस्टम जेंट्ज़ेन सक्वेंट्स की लाइनों पर कार्य करता है और इनवर्टीबिलिटी और कट-एडमिसिबिलिटी जैसी मौलिक गुणों को बनाए रखता है।
नवीन लीनियराइजेशन तकनीक: लेखक ट्री-हाइपरसिक्वेंट सिस्टम से लीनियर नेस्टेड सक्वेंट सिस्टम निकालने के लिए एक सामान्य विधि प्रस्तुत करते हैं। यह तकनीक अन्य मोडल और संबंधित लॉजिक्स के लिए नए लीनियर नेस्टेड सिस्टम उत्पन्न करने हेतु अन्य लॉजिक्स के लिए भी लागू होने की संभावना है।
पूर्ण प्रूफ़-थ्योरेटिक पत्राचार: शोध पत्र निम्नलिखित सिस्टमों के बीच एक पूर्ण, छह-तरफा सिंटैक्टिक पत्राचार स्थापित करता है: $G3KGL$, $CSGL^*$ , $LNGL$, $GL_{seq}$ , $GL_\infty$ , और $GL_{circ}$ ।
कंस्ट्रक्टिव मैपिंग्स: यह कार्य स्ट्रक्चरल सिस्टम्स (लेबल युक्त, ट्री-हाइपरसिक्वेंट, लीनियर नेस्टेड) और साइक्लिक प्रमाण सिस्टम ( $GL_{circ}$ ) के बीच प्रथम कंस्ट्रक्टिव मैपिंग प्रदान करता है।

परिणाम
प्राथमिक परिणाम यह प्रदर्शन करना है कि GL के छह प्रमुख सकेंट सिस्टमों में से किसी में भी प्रमाणों को दूसरे में सिंटैक्टिक रूप से रूपांतरित किया जा सकता है। विशेष रूप से:

$CSGL^*$ के प्रमाणों को एंड-एक्टिव प्रमाणों में बदला जा सकता है, फिर LNGL में लीनियर किया जा सकता है।
LNGL के प्रमाणों को नॉर्मलाइज किया जा सकता है और $GL_{seq}$ में रूपांतरित किया जा सकता है।
$GL_{seq}$ के प्रमाणों को $G3KGL $और साइक्लिक सिस्टम ($ GL_{circ}$, $GL_\infty$ ) में रूपांतरित किया जा सकता है।
शोध पत्र पुष्टि करता है कि $LNGL$, GL के लिए साउंड और कम्प्लीट है, और $LNGL$ के प्रमाणों को एक नॉर्मल फॉर्म में रखा जा सकता है जहाँ मोडल और लोकल नियम चरणों में दोहराए जाते हैं।

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

1. पाँच अलग-अलग कार्यशालाएँ

2. बड़ी चुनौती: संरचना को "छोड़ना" (Shedding the Structure)

3. "नॉर्मल फॉर्म" का नृत्य

4. लूप को बंद करना

अंतिम निष्कर्ष

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