2025-11-16T01:34:12.228023

Provability Models

Mojtahedi, Miranda
In this paper, we study a new Kripke-style semantics for classical modal logic, named as provability models. We study provability models for the propositional modal logics K, K4, S4 GL, GLP and the interpretability logic ILM. Provability models combine features of Kripke models with the assignment of logics to individual worlds. Originally introduced in [Mojtahedi, 2022], these models allowed the first author to establish arithmetical completeness for intuitionistic provability logic. Interestingly, we show that the ILM is complete for the same provability models of GL. We improve provability models to predicative and decidable provability models in the case of GL and ILM. Furthermore, we prove a soundness and completeness of GLP for provability models.
academic

प्रमाणीयता मॉडल

मूल जानकारी

  • पेपर ID: 2510.06696
  • शीर्षक: प्रमाणीयता मॉडल (Provability Models)
  • लेखक: मोजताबा मोजताहेदी (घेंट विश्वविद्यालय), बोर्जा सिएरा मिरांडा (बर्न विश्वविद्यालय)
  • वर्गीकरण: math.LO (गणितीय तर्कशास्त्र)
  • प्रकाशन समय: 15 अक्टूबर, 2025
  • पेपर लिंक: https://arxiv.org/abs/2510.06696

सारांश

यह पेपर शास्त्रीय मोडल तर्कशास्त्र के लिए एक नई कृपके-शैली की शब्दार्थ—प्रमाणीयता मॉडल (provability models)—का अध्ययन करता है। अनुसंधान प्रस्तावनात्मक मोडल तर्कशास्त्र K, K4, S4, GL, GLP और व्याख्यात्मक तर्कशास्त्र ILM की प्रमाणीयता मॉडल को कवर करता है। प्रमाणीयता मॉडल कृपके मॉडल की विशेषताओं को व्यक्तिगत दुनियाओं को तर्कशास्त्र प्रदान करने की विधि के साथ जोड़ते हैं। यह मॉडल मूलतः मोजताहेदी द्वारा 2022 में अंतर्ज्ञानवादी प्रमाणीयता तर्कशास्त्र की अंकगणितीय पूर्णता स्थापित करने के लिए प्रस्तुत किया गया था। दिलचस्प बात यह है कि यह पेपर सिद्ध करता है कि ILM GL के समान प्रमाणीयता मॉडल के लिए पूर्ण है। GL और ILM के मामले में, यह पेपर प्रमाणीयता मॉडल को पूर्वानुमानित और निर्णायक प्रमाणीयता मॉडल में सुधारता है, और GLP की प्रमाणीयता मॉडल के लिए सुदृढ़ता और पूर्णता सिद्ध करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

मूल समस्या

पारंपरिक प्रमाणीयता तर्कशास्त्र अनुसंधान में, मोडल ऑपरेटर को आमतौर पर किसी प्रथम-क्रम अंकगणित या समुच्चय सिद्धांत प्रणाली में प्रमाणीयता विधेय के रूप में व्याख्यायित किया जाता है। हालांकि, □A को L ⊢ A के रूप में व्याख्यायित किया जा सकता है (दिए गए प्रस्तावनात्मक सिद्धांत L के लिए)। यद्यपि GL युक्त किसी भी तर्कशास्त्र L के लिए, GL को L-व्याख्या के लिए सुदृढ़ दिखाया जा सकता है, लेकिन कोई भी L-व्याख्या GL की पूर्णता नहीं दे सकती।

समस्या की महत्ता

यह विफलता PA-व्याख्या के साथ विपरीत है, मुख्य रूप से इसलिए कि तर्कशास्त्र L कृपके मॉडल का अनुकरण नहीं कर सकता, जबकि पीनो अंकगणित अपनी कृपके मॉडल का अनुकरण करने की क्षमता का लाभ उठा सकता है (जैसा कि सोलोवे द्वारा प्रदर्शित किया गया है)। इसलिए, GL को एकल प्रस्तावनात्मक तर्कशास्त्र की प्रमाणीयता तर्कशास्त्र के रूप में अपेक्षा नहीं की जा सकती।

मौजूदा दृष्टिकोण की सीमाएं

  1. मानक कृपके मॉडल की प्रतिबंध: प्रमाणीयता तर्कशास्त्र की अंकगणितीय व्याख्या को सीधे संभालने में असमर्थ
  2. प्रस्तावनात्मक प्रमाणीयता व्याख्या की अपूर्णता: एकल प्रस्तावनात्मक तर्कशास्त्र GL की पूर्णता प्रदान नहीं कर सकता
  3. जटिल ढांचे के गुण: जैसे Iemhoff शब्दार्थ में जटिल ढांचे के गुण अंकगणितीय पूर्णता प्रमेय स्थापित करना कठिन बनाते हैं

अनुसंधान प्रेरणा

यह पेपर कृपके ढांचे को स्पष्ट रूप से प्रस्तावनात्मक तर्कशास्त्र में एकीकृत करके इस सीमा को दूर करता है, मानक कृपके मॉडल पर विचार करता है, जहां प्रत्येक दुनिया w को एक तर्कशास्त्र Lw से सुसज्जित किया जाता है, और अंतर्निहित पहुंच संबंध के आधार पर इन सिद्धांतों के बीच पहुंच संबंध लागू किए जाते हैं।

मूल योगदान

  1. प्रमाणीयता मॉडल ढांचा प्रस्तुत करना: शास्त्रीय मोडल तर्कशास्त्र के लिए नई कृपके-शैली की शब्दार्थ प्रस्तुत की
  2. कई मोडल तर्कशास्त्र की पूर्णता स्थापित करना: K, K4, S4, GL की प्रमाणीयता मॉडल के लिए सुदृढ़ता और पूर्णता सिद्ध की
  3. स्वतंत्र प्रमाणीयता मॉडल का निर्माण: विशेष रूप से GL और ILM के लिए, मानक कृपके मॉडल से स्वतंत्र प्रमाणीयता मॉडल का निर्माण कैसे करें यह दिखाया
  4. निर्णायकता को लागू करना: GL और ILM के मामले में, निर्णायक प्रमाणीयता मॉडल का निर्माण किया
  5. बहु-मोडल तर्कशास्त्र तक विस्तार: GLP (बहु-मोडल प्रमाणीयता तर्कशास्त्र) की प्रमाणीयता मॉडल के लिए सुदृढ़ता और पूर्णता सिद्ध की
  6. ILM की पूर्णता स्थापित करना: सिद्ध किया कि व्याख्यात्मक तर्कशास्त्र ILM GL के समान प्रमाणीयता मॉडल के लिए पूर्ण है

विधि विवरण

कार्य परिभाषा

प्रमाणीयता मॉडल को मोडल तर्कशास्त्र की शब्दार्थ के रूप में अनुसंधान करना, जहां:

  • इनपुट: मोडल तर्कशास्त्र सूत्र और प्रमाणीयता मॉडल
  • आउटपुट: मॉडल में सूत्र की वैधता का निर्णय
  • बाधा: मॉडल को विशिष्ट तार्किक गुणों और ढांचे की शर्तों को संतुष्ट करना चाहिए

मॉडल आर्किटेक्चर

प्रमाणीयता पूर्व-मॉडल परिभाषा

प्रमाणीयता पूर्व-मॉडल P = (W, <, {Lw}w∈W, V) में शामिल हैं:

  • W: गैर-खाली दुनिया का समुच्चय
  • <: W पर द्विआधारी संबंध
  • Lw: प्रत्येक <-पहुंच योग्य दुनिया w के लिए तर्कशास्त्र
  • V: परमाणु प्रस्तावों का मूल्यांकन संबंध

वैधता परिभाषा

सूत्र A के लिए, P, w |= A को आगमन द्वारा परिभाषित करें:

  • बूलियन संयोजकों के साथ विनिमेय
  • P, w |= □A यदि और केवल यदि ∀u ⪯ w (⊢u A)

प्रमाणीयता मॉडल शर्तें

प्रमाणीयता पूर्व-मॉडल प्रमाणीयता मॉडल बनने के लिए संतुष्ट करना चाहिए:

  • मोडल पूर्णता: प्रत्येक शुद्ध मोडल सूत्र A के लिए, यदि P, w |=+ A तो ⊢w A

तकनीकी नवाचार बिंदु

1. ढांचे की शर्तों का तार्किकीकरण

प्रमाणीयता मॉडल ढांचे की शर्तों को व्यक्तिगत दुनियाओं को प्रदान किए गए तर्कशास्त्र के अनुमान नियमों के रूप में अवशोषित कर सकते हैं:

  • संक्रामकता को आवश्यकता नियम द्वारा प्रतिस्थापित किया जा सकता है
  • प्रतिलोम सुस्थापितता को लोब नियम द्वारा प्रतिस्थापित किया जा सकता है

2. निर्माणात्मक विधि

GL और ILM के लिए, प्रमाणीयता मॉडल बनाने के लिए निर्माणात्मक विधि प्रदान की जाती है:

प्रमेय 4.4: प्रत्येक प्रतिलोम सुस्थापित वृक्ष प्रमाणीयता पूर्व-मॉडल P के लिए, आवश्यकता के साथ एक प्रमाणीयता मॉडल P̄ मौजूद है, जैसे कि:

  • P̄ में आवश्यकता है
  • P ⊆ P̄
  • P̄ P युक्त न्यूनतम प्रमाणीयता मॉडल है

3. निर्णायकता गारंटी

यदि P द्विसीमित है, तो P̄ निर्णायक है, जहां द्विसीमित का अर्थ है कि W और प्रत्येक w∈W के लिए Axiom(Lw) दोनों सीमित हैं।

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन ढांचा

यह पेपर मुख्य रूप से सैद्धांतिक प्रमाण प्रदान करता है, सत्यापन ढांचा शामिल है:

1. सुदृढ़ता प्रमाण

विभिन्न मोडल तर्कशास्त्र के लिए, सिद्ध करना कि यदि तर्कशास्त्र ⊢ A, तो P |= A सभी संबंधित प्रमाणीयता मॉडल P के लिए सत्य है।

2. पूर्णता प्रमाण

सिद्ध करना कि यदि P |= A सभी संबंधित प्रमाणीयता मॉडल P के लिए सत्य है, तो तर्कशास्त्र ⊢ A।

3. प्रबल पूर्णता

विशेष रूप से GL के लिए, प्रबल पूर्णता सिद्ध की: Γ |=P A का अर्थ Γ ⊢GL A है।

निर्माण विधि सत्यापन

ठोस निर्माण द्वारा सत्यापित:

  • सीमित प्रमाणीयता मॉडल का अस्तित्व
  • निर्णायकता का कार्यान्वयन
  • स्वतंत्रता (मानक कृपके मॉडल पर निर्भर नहीं)

प्रायोगिक परिणाम

मुख्य परिणाम

1. मूल मोडल तर्कशास्त्र की पूर्णता

  • K: प्रमाणीयता मॉडल के लिए सुदृढ़ और पूर्ण (प्रमेय 3.6, 3.7)
  • K4: आवश्यकता या संक्रामकता वाले प्रमाणीयता मॉडल के लिए सुदृढ़ और पूर्ण (प्रमेय 3.8, 3.9)
  • S4: प्रतिबिंबी, संक्रामक, आवश्यकता और स्थानीय पूर्णता वाले प्रमाणीयता मॉडल के लिए सुदृढ़ और पूर्ण (प्रमेय 3.11, 3.12)

2. प्रमाणीयता तर्कशास्त्र GL के परिणाम

  • सुदृढ़ता: GL प्रतिलोम सुस्थापित प्रमाणीयता मॉडल के लिए आवश्यकता और लोब नियम के साथ सुदृढ़ है (प्रमेय 3.14)
  • पूर्णता: GL सीमित संक्रामक गैर-प्रतिबिंबी प्रमाणीयता मॉडल के लिए पूर्ण है (प्रमेय 3.17)
  • प्रबल पूर्णता: GL आवश्यकता और लोब नियम वाले प्रमाणीयता मॉडल के लिए प्रबल पूर्ण है (प्रमेय 3.18)
  • सीमितता पूर्णता: GL सीमितता प्रमाणीयता मॉडल के लिए पूर्ण है (प्रमेय 4.6)

3. व्याख्यात्मक तर्कशास्त्र ILM के परिणाम

  • सुदृढ़ता: ILM प्रतिलोम सुस्थापित प्रमाणीयता मॉडल के लिए आवश्यकता के साथ सुदृढ़ है (प्रमेय 5.6)
  • पूर्णता: ILM सीमित वृक्ष प्रतिलोम सुस्थापित प्रमाणीयता मॉडल के लिए आवश्यकता के साथ पूर्ण है (प्रमेय 5.10)
  • सीमितता पूर्णता: ILM सीमितता प्रमाणीयता मॉडल के लिए पूर्ण है (प्रमेय 5.13)

4. बहु-मोडल प्रमाणीयता तर्कशास्त्र GLP के परिणाम

  • सुदृढ़ता और पूर्णता: GLP बहु-प्रमाणीयता GLP-मॉडल के लिए सुदृढ़ और प्रबल पूर्ण है (प्रमेय 6.2, 6.3)

निर्माणात्मक परिणाम

मानक कृपके मॉडल से स्वतंत्र प्रमाणीयता मॉडल का सफल निर्माण, विशेष रूप से:

  • किसी भी प्रतिलोम सुस्थापित वृक्ष ढांचे और नोड्स को सूत्र समुच्चय के किसी भी असाइनमेंट के लिए, न्यूनतम प्रमाणीयता मॉडल का निर्माण कर सकते हैं
  • द्विसीमित मामले में, निर्मित मॉडल निर्णायक है

संबंधित कार्य

प्रमाणीयता तर्कशास्त्र परंपरागत अनुसंधान

  • सोलोवे (1976): PA की प्रमाणीयता तर्कशास्त्र स्थापित की
  • बूलोस (1995), स्मोरिंस्की (1985): प्रमाणीयता तर्कशास्त्र की शास्त्रीय पाठ्यपुस्तकें
  • आर्टेमोव और बेकलेमिशेव (2004): व्यापक सर्वेक्षण

शब्दार्थ विधि

  • मानक कृपके शब्दार्थ: विभिन्न मोडल तर्कशास्त्र के लिए
  • वेल्टमैन मॉडल: व्याख्यात्मक तर्कशास्त्र ILM के लिए
  • स्थलीय शब्दार्थ: GLP के लिए पूर्णता प्रदान करता है

अंतर्ज्ञानवादी प्रमाणीयता तर्कशास्त्र

  • Iemhoff (2001-2003): Iemhoff शब्दार्थ प्रस्तुत किया
  • मोजताहेदी (2022): पहली बार प्रमाणीयता मॉडल का उपयोग अंतर्ज्ञानवादी प्रमाणीयता तर्कशास्त्र की अंकगणितीय पूर्णता स्थापित करने के लिए किया

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. एकीकृत ढांचा: प्रमाणीयता मॉडल कई मोडल तर्कशास्त्र के लिए एकीकृत शब्दार्थ ढांचा प्रदान करते हैं
  2. निर्माणात्मकता: विशेष रूप से GL और ILM के लिए, स्वतंत्र प्रमाणीयता मॉडल निर्माणात्मक रूप से स्थापित किए जा सकते हैं
  3. निर्णायकता: उपयुक्त शर्तों के तहत, प्रमाणीयता मॉडल निर्णायक हैं
  4. लचीलापन: ढांचे की शर्तें तार्किक गुणों द्वारा प्रतिस्थापित की जा सकती हैं, अधिक लचीलापन प्रदान करती हैं

सीमाएं

  1. GLP की प्रतिबंध: GLP के लिए, अभी तक निर्णायक प्रमाणीयता मॉडल वर्ग नहीं मिला है
  2. निर्माण की जटिलता: कुछ निर्माण (जैसे GLP का विहित मॉडल) निर्माणात्मक नहीं हो सकते हैं
  3. प्रयोज्य सीमा: मुख्य रूप से प्रमाणीयता गुणों वाले तर्कशास्त्र पर लागू

भविष्य की दिशाएं

पेपर स्पष्ट रूप से कई खुली समस्याएं प्रस्तुत करता है:

  1. प्रमाण तर्कशास्त्र का विस्तार: प्रमाण तर्कशास्त्र LP और JGL के लिए प्रमाणीयता-शैली मॉडल परिभाषित करना
  2. अंतर्ज्ञानवादी मोडल तर्कशास्त्र: दो मोडल ऑपरेटर □ और ◇ वाले अंतर्ज्ञानवादी मोडल तर्कशास्त्र के लिए प्रमाणीयता मॉडल परिभाषित करना
  3. GLP का निर्णायक मॉडल: GLP के निर्णायक प्रमाणीयता मॉडल वर्ग खोजना
  4. अंकगणितीय पूर्णता का सरलीकरण: यह अन्वेषण करना कि क्या प्रमाणीयता मॉडल के माध्यम से ILM की अंकगणितीय पूर्णता प्रमाण को सरल किया जा सकता है

गहन मूल्यांकन

लाभ

  1. सैद्धांतिक नवाचार: पूरी तरह से नई शब्दार्थ ढांचा प्रस्तुत की, कई मोडल तर्कशास्त्र के उपचार को एकीकृत किया
  2. तकनीकी गहराई: विस्तृत गणितीय प्रमाण और निर्माण विधि प्रदान की
  3. व्यावहारिक मूल्य: विशेष रूप से निर्णायकता पहलू में सुधार महत्वपूर्ण है
  4. व्यवस्थितता: मूल मोडल तर्कशास्त्र से जटिल प्रमाणीयता तर्कशास्त्र तक विभिन्न मामलों को व्यवस्थित रूप से संभाला

कमियां

  1. जटिलता: कुछ निर्माण (विशेष रूप से GLP) की जटिलता इसके व्यावहारिक अनुप्रयोग को सीमित कर सकती है
  2. खुली समस्याएं: अभी भी महत्वपूर्ण खुली समस्याएं हैं जो अनसुलझी हैं, जैसे GLP का निर्णायक मॉडल
  3. अनुप्रयोग सीमा: मुख्य रूप से सैद्धांतिक अनुसंधान तक सीमित, व्यावहारिक अनुप्रयोग मूल्य को आगे की खोज की आवश्यकता है

प्रभाव

  1. सैद्धांतिक योगदान: मोडल तर्कशास्त्र शब्दार्थ के लिए नई अनुसंधान दिशा प्रदान करता है
  2. पद्धति मूल्य: ढांचे की शर्तों का तार्किकीकरण विधि सार्वभौमिक महत्व रखती है
  3. अनुवर्ती अनुसंधान: अंतर्ज्ञानवादी तर्कशास्त्र, प्रमाण तर्कशास्त्र आदि क्षेत्रों में अनुसंधान के लिए नए उपकरण प्रदान करता है

प्रयोज्य परिदृश्य

  1. प्रमाणीयता तर्कशास्त्र अनुसंधान: विशेष रूप से अंकगणितीय पूर्णता की आवश्यकता वाले अनुसंधान के लिए उपयुक्त
  2. मोडल तर्कशास्त्र शब्दार्थ: जटिल मोडल तर्कशास्त्र के लिए नई शब्दार्थ विधि प्रदान करता है
  3. कम्प्यूटेशनल तर्कशास्त्र: निर्णायकता की आवश्यकता वाले अनुप्रयोगों में संभावित मूल्य

संदर्भ

पेपर समृद्ध संबंधित साहित्य का हवाला देता है, जिसमें शामिल हैं:

  • प्रमाणीयता तर्कशास्त्र की शास्त्रीय साहित्य (बूलोस, स्मोरिंस्की, सोलोवे आदि)
  • मोडल तर्कशास्त्र शब्दार्थ का महत्वपूर्ण कार्य (ब्लैकबर्न आदि)
  • व्याख्यात्मक तर्कशास्त्र का मुख्य अनुसंधान (बेरार्डुची, शावरुकोव आदि)
  • अंतर्ज्ञानवादी प्रमाणीयता तर्कशास्त्र का संबंधित कार्य (Iemhoff आदि)

यह पेपर मोडल तर्कशास्त्र शब्दार्थ के क्षेत्र में महत्वपूर्ण सैद्धांतिक योगदान देता है, विभिन्न प्रमाणीयता तर्कशास्त्र को संभालने के लिए एक नई एकीकृत ढांचा प्रदान करता है, जबकि निर्माणात्मकता और निर्णायकता पहलुओं में उल्लेखनीय प्रगति प्राप्त करता है। यद्यपि कुछ खुली समस्याएं अभी भी बनी हुई हैं, यह कार्य अनुवर्ती अनुसंधान के लिए एक मजबूत आधार स्थापित करता है।