सामान्य फ्रेम

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

परिभाषा

एक मॉडल सामान्य फ्रेम एक ट्रिपल है $\mathbf {F} =\langle F,R,V\rangle$, कहाँ $\langle F,R\rangle$ क्रिप्के फ़्रेम है (अर्थात, $R$ सेट पर एक द्विआधारी संबंध है $F$), और $V$ के उपसमुच्चय का समुच्चय है $F$ जो निम्नलिखित के तहत बंद है:

• (द्विआधारी) प्रतिच्छेदन (सेट सिद्धांत), संघ (सेट सिद्धांत), और पूरक (सेट सिद्धांत) के बूलियन संचालन,
• संचालन $\Box$, द्वारा परिभाषित $\Box A=\{x\in F\mid \forall y\in F\,(x\,R\,y\to y\in A)\}$.

वे इस प्रकार सेट के क्षेत्र का एक विशेष मामला हैं # अतिरिक्त संरचना के साथ सेट के क्षेत्र। उद्देश्य से $V$ फ्रेम में अनुमत मूल्यांकन को प्रतिबंधित करना है: एक मॉडल $\langle F,R,\Vdash \rangle$ क्रिप्के फ्रेम पर आधारित है $\langle F,R\rangle$ सामान्य ढांचे में स्वीकार्य है $\mathbf {F}$, अगर

$\{x\in F\mid x\Vdash p\}\in V$ प्रत्येक प्रस्तावक चर के लिए $p$.

बंद करने की स्थिति चालू है $V$ तो सुनिश्चित करें $\{x\in F\mid x\Vdash A\}$ से संबंधित $V$ प्रत्येक सूत्र के लिए $A$ (न केवल एक चर)।

एक सूत्र $A$ में मान्य है $\mathbf {F}$, अगर $x\Vdash A$ सभी स्वीकार्य मूल्यांकन के लिए $\Vdash$, और सभी बिंदु $x\in F$. एक सामान्य मॉडल तर्क $L$ फ्रेम में मान्य है $\mathbf {F}$, यदि सभी अभिगृहीत (या समतुल्य, सभी प्रमेय (तर्क) हैं $L$ में मान्य हैं $\mathbf {F}$. ऐसे में हम कॉल करते हैं $\mathbf {F}$ एक $L$-चौखटा।

एक क्रिपके फ्रेम $\langle F,R\rangle$ एक सामान्य ढांचे के साथ पहचाना जा सकता है जिसमें सभी मूल्यांकन स्वीकार्य हैं: यानी, $\langle F,R,{\mathcal {P}}(F)\rangle$, कहाँ ${\mathcal {P}}(F)$ के सत्ता स्थापित को दर्शाता है $F$.

फ्रेम के प्रकार

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

चौखटा $\mathbf {F} =\langle F,R,V\rangle$ कहा जाता है

• विभेदित, अगर $\forall A\in V\,(x\in A\Leftrightarrow y\in A)$ तात्पर्य $x=y$,
• तंग, अगर $\forall A\in V\,(x\in \Box A\Rightarrow y\in A)$ तात्पर्य $x\,R\,y$,
• कॉम्पैक्ट, यदि का प्रत्येक उपसमुच्चय $V$ परिमित चौराहा संपत्ति के साथ एक गैर-खाली चौराहा है,
• परमाणु, अगर $V$ सभी सिंगलटन शामिल हैं,
• परिष्कृत, अगर यह विभेदित और तंग है,
• वर्णनात्मक, अगर यह परिष्कृत और कॉम्पैक्ट है।

क्रिप्के फ्रेम परिष्कृत और परमाणु हैं। हालाँकि, अनंत क्रिपके फ्रेम कभी भी कॉम्पैक्ट नहीं होते हैं। प्रत्येक परिमित विभेदित या परमाणु फ्रेम एक क्रिपके फ्रेम है।

द्वैत सिद्धांत के कारण वर्णनात्मक फ्रेम फ्रेम का सबसे महत्वपूर्ण वर्ग है (नीचे देखें)। वर्णनात्मक और क्रिपके फ्रेम के सामान्य सामान्यीकरण के रूप में परिष्कृत फ्रेम उपयोगी होते हैं।

फ्रेम पर संचालन और morphisms

हर क्रिपके मॉडल $\langle F,R,{\Vdash }\rangle$ सामान्य ढांचे को प्रेरित करता है $\langle F,R,V\rangle$, कहाँ $V$ परिभाषित किया जाता है

$V={\big \{}\{x\in F\mid x\Vdash A\}\mid A{\hbox{ is a formula}}{\big \}}.$

जनरेट किए गए सबफ़्रेम, Kripke_semantics#Model_constructions|p-मॉर्फिक इमेज, और Kripke फ़्रेम के असंयुक्त संघों के मौलिक सत्य-संरक्षण संचालन में सामान्य फ़्रेम पर एनालॉग होते हैं। चौखटा $\mathbf {G} =\langle G,S,W\rangle$ एक फ्रेम का एक उत्पन्न सबफ्रेम है $\mathbf {F} =\langle F,R,V\rangle$, अगर क्रिप्के फ्रेम $\langle G,S\rangle$ क्रिप्के फ्रेम का एक उत्पन्न सबफ्रेम है $\langle F,R\rangle$ (अर्थात।, $G$ का उपसमुच्चय है $F$ के नीचे ऊपर की ओर बंद है $R$, और $S=R\cap G\times G$), और

$W=\{A\cap G\mid A\in V\}.$

एक पी-मोर्फिज्म (या बाउंड मॉर्फिज्म) $f\colon \mathbf {F} \to \mathbf {G}$ से एक समारोह है $F$ को $G$ यह क्रिपके फ्रेम का पी-मोर्फिज्म है $\langle F,R\rangle$ और $\langle G,S\rangle$, और अतिरिक्त बाधा को संतुष्ट करता है

$f^{-1}[A]\in V$ हरएक के लिए $A\in W$.

फ़्रेम के अनुक्रमित सेट का असंयुक्त संघ $\mathbf {F} _{i}=\langle F_{i},R_{i},V_{i}\rangle$, $i\in I$, फ्रेम है $\mathbf {F} =\langle F,R,V\rangle$, कहाँ $F$ का असंयुक्त संघ है $\{F_{i}\mid i\in I\}$, $R$ का संघ है $\{R_{i}\mid i\in I\}$, और

$V=\{A\subseteq F\mid \forall i\in I\,(A\cap F_{i}\in V_{i})\}.$

एक फ्रेम का शोधन $\mathbf {F} =\langle F,R,V\rangle$ एक परिष्कृत ढांचा है $\mathbf {G} =\langle G,S,W\rangle$ निम्नानुसार परिभाषित किया गया है। हम तुल्यता संबंध पर विचार करते हैं

$x\sim y\iff \forall A\in V\,(x\in A\Leftrightarrow y\in A),$

और जाने $G=F/{\sim }$ के तुल्यता वर्गों का समुच्चय हो $\sim$. फिर हम डालते हैं

$\langle x/{\sim },y/{\sim }\rangle \in S\iff \forall A\in V\,(x\in \Box A\Rightarrow y\in A),$

$A/{\sim }\in W\iff A\in V.$

संपूर्णता

क्रिपके फ्रेम के विपरीत, हर सामान्य मोडल लॉजिक $L$ सामान्य फ़्रेमों के एक वर्ग के संबंध में पूर्ण है। यह इस बात का परिणाम है कि $L$ क्रिप्के मॉडलों के एक वर्ग के संबंध में पूर्ण है $\langle F,R,{\Vdash }\rangle$: जैसा $L$ प्रतिस्थापन के तहत बंद है, द्वारा प्रेरित सामान्य फ्रेम $\langle F,R,{\Vdash }\rangle$ एक $L$-चौखटा। इसके अलावा, हर तर्क $L$ एक वर्णनात्मक फ्रेम के संबंध में पूर्ण है। वास्तव में, $L$ अपने कैनोनिकल मॉडल के संबंध में पूर्ण है, और कैनोनिकल मॉडल द्वारा प्रेरित सामान्य फ्रेम (कैनोनिकल फ्रेम कहा जाता है) $L$) वर्णनात्मक है।

जॉनसन-तर्स्की द्वैत

Error creating thumbnail:

द रिगर-निशिमुरा सीढ़ी: एक 1-सार्वभौमिक अंतर्ज्ञानवादी क्रिपके फ्रेम।

Error creating thumbnail:

इसका दोहरा हेयटिंग बीजगणित, रीगर-निशिमुरा जालक। यह 1 जेनरेटर पर मुफ्त हेटिंग बीजगणित है।

सामान्य फ्रेम मॉडल बीजगणित के साथ घनिष्ठ संबंध रखते हैं। होने देना $\mathbf {F} =\langle F,R,V\rangle$ एक सामान्य फ्रेम बनें। सेट $V$ बूलियन संचालन के तहत बंद है, इसलिए यह पावर सेट बूलियन बीजगणित (संरचना) का एक subalgebra है $\langle {\mathcal {P}}(F),\cap ,\cup ,-\rangle$. इसमें एक अतिरिक्त यूनरी ऑपरेशन भी होता है, $\Box$. संयुक्त संरचना $\langle V,\cap ,\cup ,-,\Box \rangle$ एक मॉडल बीजगणित है, जिसे का दोहरा बीजगणित कहा जाता है $\mathbf {F}$, और द्वारा दर्शाया गया $\mathbf {F} ^{+}$.

विपरीत दिशा में, दोहरे फ्रेम का निर्माण संभव है $\mathbf {A} _{+}=\langle F,R,V\rangle$ किसी भी मॉडल बीजगणित के लिए $\mathbf {A} =\langle A,\wedge ,\vee ,-,\Box \rangle$. बूलियन बीजगणित $\langle A,\wedge ,\vee ,-\rangle$ एक पत्थर की जगह है, जिसका अंतर्निहित सेट $F$ के सभी ultrafilter का सेट है $\mathbf {A}$. सेट $V$ स्वीकार्य मूल्यांकन में $\mathbf {A} _{+}$ के क्लोपेन सेट के सबसेट होते हैं $F$, और अभिगम्यता संबंध $R$ द्वारा परिभाषित किया गया है

$x\,R\,y\iff \forall a\in A\,(\Box a\in x\Rightarrow a\in y)$

सभी अल्ट्राफिल्टर के लिए $x$ और $y$.

एक फ्रेम और उसके दोहरे एक ही सूत्र को मान्य करते हैं, इसलिए सामान्य फ्रेम शब्दार्थ और बीजगणितीय शब्दार्थ एक अर्थ में समकक्ष हैं। डबल द्वैत $(\mathbf {A} _{+})^{+}$ किसी भी मॉडल बीजगणित का आइसोमोर्फिक है $\mathbf {A}$ अपने आप। यह फ्रेम के दोहरे दोहरे के लिए सामान्य रूप से सही नहीं है, क्योंकि प्रत्येक बीजगणित का दोहरा वर्णनात्मक है। वास्तव में, एक फ्रेम $\mathbf {F}$ वर्णनात्मक है अगर और केवल अगर यह अपने दोहरे दोहरे के लिए आइसोमोर्फिक है $(\mathbf {F} ^{+})_{+}$.

एक तरफ पी-मॉर्फिज्म के द्वैत को परिभाषित करना भी संभव है, और दूसरी तरफ मोडल बीजगणित समरूपता। ऐसे में ऑपरेटर्स $(\cdot )^{+}$ और $(\cdot )_{+}$ सामान्य फ़्रेमों की श्रेणी (गणित) और मॉडल बीजगणित की श्रेणी के बीच प्रतिपरिवर्ती फ़ैक्टरों की एक जोड़ी बनें। ये मजदूर वर्णनात्मक फ्रेम की श्रेणियों और मॉडल बीजगणित के बीच श्रेणियों की समानता प्रदान करते हैं (बर्जनी जोन्ससन और अल्फ्रेड टार्स्की के बाद जोन्सन-टार्स्की द्वंद्व कहा जाता है)। यह समुच्चय#जटिल बीजगणित के क्षेत्र और संबंधपरक संरचनाओं पर समुच्चय के क्षेत्र के बीच एक अधिक सामान्य द्वैत का एक विशेष मामला है।

अंतर्ज्ञानवादी फ्रेम

इंट्यूशनिस्टिक और इंटरमीडिएट लॉजिक्स के लिए फ्रेम सिमेंटिक्स को मोडल लॉजिक्स के सिमेंटिक्स के समानांतर विकसित किया जा सकता है। एक अंतर्ज्ञानवादी सामान्य फ्रेम एक ट्रिपल है $\langle F,\leq ,V\rangle$, कहाँ $\leq$ पर आंशिक आदेश है $F$, और $V$ के ऊपरी सेट (शंकु) का एक सेट है $F$ जिसमें खाली सेट है, और नीचे बंद है

• चौराहा और मिलन,
• संचालन $A\to B=\Box (-A\cup B)$.

स्वीकार्य वैल्यूएशन के सेट के कमजोर समापन गुणों को समायोजित करने के लिए आवश्यक कुछ बदलावों के साथ वैधता और अन्य अवधारणाओं को मॉडल फ्रेम के समान पेश किया जाता है। विशेष रूप से, एक अंतर्ज्ञानवादी फ्रेम $\mathbf {F} =\langle F,\leq ,V\rangle$ कहा जाता है

• तंग, अगर $\forall A\in V\,(x\in A\Leftrightarrow y\in A)$ तात्पर्य $x\leq y$,
• कॉम्पैक्ट, यदि का प्रत्येक उपसमुच्चय $V\cup \{F-A\mid A\in V\}$ परिमित चौराहा संपत्ति के साथ एक गैर-खाली चौराहा है।

तंग अंतर्ज्ञानवादी फ्रेम स्वचालित रूप से विभेदित होते हैं, इसलिए परिष्कृत होते हैं।

एक अंतर्ज्ञानवादी फ्रेम का दोहरा $\mathbf {F} =\langle F,\leq ,V\rangle$ हेटिंग बीजगणित है $\mathbf {F} ^{+}=\langle V,\cap ,\cup ,\to ,\emptyset \rangle$. एक हेटिंग बीजगणित का दोहरा $\mathbf {A} =\langle A,\wedge ,\vee ,\to ,0\rangle$ अंतर्ज्ञानवादी ढांचा है $\mathbf {A} _{+}=\langle F,\leq ,V\rangle$, कहाँ $F$ के सभी प्रधान फिल्टर का सेट है $\mathbf {A}$, आदेश $\leq$ समावेशन (सेट सिद्धांत) है, और $V$ के सभी उपसमुच्चय होते हैं $F$ फार्म का

$\{x\in F\mid a\in x\},$

कहाँ $a\in A$. जैसा कि मोडल मामले में है, $(\cdot )^{+}$ और $(\cdot )_{+}$ प्रतिपरिवर्ती फ़ैक्टरों की एक जोड़ी है, जो हेटिंग बीजगणित की श्रेणी को वर्णनात्मक अंतर्ज्ञानवादी फ़्रेमों की श्रेणी के बराबर बनाते हैं।

सकर्मक रिफ्लेक्सिव मोडल फ्रेम से अंतर्ज्ञानवादी सामान्य फ्रेम बनाना संभव है और इसके विपरीत, मोडल साथी देखें।

संदर्भ

• Alexander Chagrov and Michael Zakharyaschev, Modal Logic, vol. 35 of Oxford Logic Guides, Oxford University Press, 1997.
• Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal Logic, vol. 53 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 2001.