संरचना (गणितीय तर्क): Difference between revisions
No edit summary |
No edit summary |
||
Line 2: | Line 2: | ||
{{not to be confused|गणित का प्रतिरूप}} | {{not to be confused|गणित का प्रतिरूप}} | ||
{{More footnotes|date=April 2010}} | {{More footnotes|date=April 2010}} | ||
[[सार्वभौमिक बीजगणित]] और [[मॉडल सिद्धांत|प्रतिरूप सिद्धांत]] में, '''संरचना''' | [[सार्वभौमिक बीजगणित]] और [[मॉडल सिद्धांत|प्रतिरूप सिद्धांत]] में, '''संरचना''' एक [[सेट (गणित)]] के साथ-साथ [[अंतिम]] संचालन और [[अंतिम संबंध|संबंधों]] का एक संग्रह होता है जो उस पर परिभाषित होता है। | ||
सार्वभौम बीजगणित उन संरचनाओं का अध्ययन करता है जो [[समूह (गणित)|समूह]], वलय, [[क्षेत्र (गणित)|क्षेत्र]] और सदिश स्थान जैसी [[बीजगणितीय संरचना|बीजगणितीय संरचनाओं]] का सामान्यीकरण करती है। सार्वभौम बीजगणित शब्द का उपयोग प्रथम-क्रम के सिद्धांतों की संरचनाओं के लिए किया जाता है, जिसमें कोई [[संबंध प्रतीक]] नहीं होता है।<ref>Some authors refer to structures as "algebras" when generalizing universal algebra to allow [[relation (mathematics)|relations]] as well as functions.</ref> प्रतिरूप सिद्धांत का एक अलग दायरा है जिसमें सेट सिद्धांत के प्रतिरूप जैसे मूलभूत संरचनाओं सहित अधिक मनमाना प्रथम-क्रम [[समुच्चय सिद्धान्त|सिद्धान्त]] सम्मलित है। | सार्वभौम बीजगणित उन संरचनाओं का अध्ययन करता है जो [[समूह (गणित)|समूह]], वलय, [[क्षेत्र (गणित)|क्षेत्र]] और सदिश स्थान जैसी [[बीजगणितीय संरचना|बीजगणितीय संरचनाओं]] का सामान्यीकरण करती है। सार्वभौम बीजगणित शब्द का उपयोग प्रथम-क्रम के सिद्धांतों की संरचनाओं के लिए किया जाता है, जिसमें कोई [[संबंध प्रतीक]] नहीं होता है।<ref>Some authors refer to structures as "algebras" when generalizing universal algebra to allow [[relation (mathematics)|relations]] as well as functions.</ref> प्रतिरूप सिद्धांत का एक अलग दायरा है जिसमें सेट सिद्धांत के प्रतिरूप जैसे मूलभूत संरचनाओं सहित अधिक मनमाना प्रथम-क्रम [[समुच्चय सिद्धान्त|सिद्धान्त]] सम्मलित है। | ||
Line 12: | Line 12: | ||
</ref> जबकि व्याख्या शब्द का सामान्यतः प्रतिरूप सिद्धांत में एक अलग (चूंकि संबंधित) अर्थ होता है, [[व्याख्या (मॉडल सिद्धांत)|व्याख्या (प्रतिरूप सिद्धांत)]] देखें। | </ref> जबकि व्याख्या शब्द का सामान्यतः प्रतिरूप सिद्धांत में एक अलग (चूंकि संबंधित) अर्थ होता है, [[व्याख्या (मॉडल सिद्धांत)|व्याख्या (प्रतिरूप सिद्धांत)]] देखें। | ||
[[डेटाबेस]] सिद्धांत में, बिना किसी | [[डेटाबेस]] सिद्धांत में, बिना किसी कार्य वाली संरचनाओं का [[संबंधपरक मॉडल|संबंधपरक]] डेटाबेस के [[संबंधपरक मॉडल|प्रतिरूप]] के रूप में अध्ययन किया जाता है। | ||
== परिभाषा == | == परिभाषा == | ||
Line 20: | Line 20: | ||
=== डोमेन === | === डोमेन === | ||
संरचना का डोमेन एक मनमाना सेट है, इसे संरचना का अंतर्निहित सेट, वाहक (विशेष रूप से सार्वभौमिक बीजगणित में), ब्रह्मांड (विशेष रूप से प्रतिरूप सिद्धांत) या प्रवचन का डोमेन भी कहा जाता है। मौलिक प्रथम-क्रम तर्क में, संरचना की परिभाषा खाली डोमेन को प्रतिबंधित करती है।<ref>A logical system that allows the empty domain is known as an [[Free logic|inclusive logic]].</ref> | |||
कभी-कभी अंकन <math>\operatorname{dom}(\mathcal A)</math> या <math>|\mathcal A|</math> के डोमेन के लिए प्रयोग किया जाता है <math>\mathcal A,</math> लेकिन अधिकांशतः एक संरचना और उसके डोमेन (अर्थात, एक ही प्रतीक) के बीच कोई सांकेतिक भेद नहीं किया जाता है <math>\mathcal A</math> संरचना और उसके डोमेन दोनों को संदर्भित करता है। | कभी-कभी अंकन <math>\operatorname{dom}(\mathcal A)</math> या <math>|\mathcal A|</math> के डोमेन के लिए प्रयोग किया जाता है <math>\mathcal A,</math> लेकिन अधिकांशतः एक संरचना और उसके डोमेन (अर्थात, एक ही प्रतीक) के बीच कोई सांकेतिक भेद नहीं किया जाता है <math>\mathcal A</math> संरचना और उसके डोमेन दोनों को संदर्भित करता है।<ref>As a consequence of these conventions, the notation <math>|\mathcal A|</math> may also be used to refer to the [[cardinality]] of the domain of <math>\mathcal A.</math> In practice this never leads to confusion.</ref> | ||
===हस्ताक्षर=== | ===हस्ताक्षर=== | ||
Line 28: | Line 28: | ||
हस्ताक्षर (तर्क) <math>\sigma = (S, \operatorname{ar})</math> एक संरचना के होते है: | हस्ताक्षर (तर्क) <math>\sigma = (S, \operatorname{ar})</math> एक संरचना के होते है: | ||
* एक सेट <math>S</math> | * एक सेट <math>S</math> कार्य प्रतीकों और [[संबंध प्रतीक|संबंध प्रतीकों]] के साथ होता है | ||
* एक समारोह <math>\operatorname{ar} : \ S \to \N_0</math> जो प्रत्येक प्रतीक को बताता है <math>s</math> एक [[प्राकृतिक संख्या]] <math>n = \operatorname{ar}(s).</math> प्राकृतिक संख्या <math>n=\operatorname{ar}(s)</math> एक प्रतीक का <math>s</math> की आरती कहलाती है <math>s</math> क्योंकि यह व्याख्या की योग्यता है | * एक समारोह <math>\operatorname{ar} : \ S \to \N_0</math> जो प्रत्येक प्रतीक को बताता है <math>s</math> एक [[प्राकृतिक संख्या]] <math>n = \operatorname{ar}(s).</math> प्राकृतिक संख्या <math>n=\operatorname{ar}(s)</math> एक प्रतीक का <math>s</math> की आरती कहलाती है <math>s</math> क्योंकि यह व्याख्या की योग्यता होती है | ||
चूंकि [[बीजगणित]] में उत्पन्न होने वाले हस्ताक्षरों में अधिकांशतः केवल | चूंकि [[बीजगणित]] में उत्पन्न होने वाले हस्ताक्षरों में अधिकांशतः केवल कार्य प्रतीक होते है, बिना संबंध प्रतीकों वाले हस्ताक्षर को [[बीजगणितीय हस्ताक्षर]] कहा जाता है। ऐसे हस्ताक्षर वाली संरचना को बीजगणित भी कहा जाता है, इसे किसी क्षेत्र पर बीजगणित की धारणा के साथ भ्रमित नहीं होना चाहिए। | ||
=== व्याख्या समारोह === | === व्याख्या समारोह === | ||
{{not to be confused|text=[[व्याख्या (प्रतिरूप सिद्धांत)|एक प्रतिरूप की व्याख्या]] दूसरे प्रतिरूप में}} | {{not to be confused|text=[[व्याख्या (प्रतिरूप सिद्धांत)|एक प्रतिरूप की व्याख्या]] दूसरे प्रतिरूप में}} | ||
व्याख्या कार्य <math>I</math> का <math>\mathcal A</math> हस्ताक्षर के प्रतीकों को कार्य और संबंध प्रदान करता है। प्रत्येक समारोह प्रतीक <math>f</math> दया की <math>n</math> सौंपा गया है <math>n</math>-एरी समारोह <math>f^{\mathcal A} = I(f)</math> डोमेन पर प्रदान करता है। प्रत्येक संबंध प्रतीक <math>R</math> दया की <math>n</math> एक सौंपा गया है <math>n</math>-आर्य संबंध <math>R^{\mathcal A} = I(R)\subseteq A^{\operatorname{ar(R)}}</math> डोमेन पर प्रदान करता है। एक शून्य (<math>= \, 0</math>-आरी) | व्याख्या कार्य <math>I</math> का <math>\mathcal A</math> हस्ताक्षर के प्रतीकों को कार्य और संबंध प्रदान करता है। प्रत्येक समारोह प्रतीक <math>f</math> दया की <math>n</math> सौंपा गया है <math>n</math>-एरी समारोह <math>f^{\mathcal A} = I(f)</math> डोमेन पर प्रदान करता है। प्रत्येक संबंध प्रतीक <math>R</math> दया की <math>n</math> एक सौंपा गया है <math>n</math>-आर्य संबंध <math>R^{\mathcal A} = I(R)\subseteq A^{\operatorname{ar(R)}}</math> डोमेन पर प्रदान करता है। एक शून्य (<math>= \, 0</math>-आरी) कार्य प्रतीक <math>c</math> एक [[स्थिर प्रतीक]] कहा जाता है, क्योंकि इसकी व्याख्या <math>I(c)</math> डोमेन के एक स्थिर तत्व के साथ पहचाना जा सकता है। | ||
जब एक संरचना (और इसलिए एक व्याख्या कार्य) संदर्भ द्वारा दी जाती है, तो प्रतीक | जब एक संरचना (और इसलिए एक व्याख्या कार्य) संदर्भ द्वारा दी जाती है, तो प्रतीक <math>s</math> और इसकी व्याख्या <math>I(s).</math> के बीच कोई सांकेतिक भेद नहीं किया जाता है। उदाहरण के लिए, यदि <math>f</math> का एक बाइनरी कार्य प्रतीक है <math>\mathcal A,</math> एक बस लिखता है <math>f : \mathcal A^2 \to \mathcal A</math> इसके अतिरिक्त <math>f^{\mathcal A} : |\mathcal A|^2 \to |\mathcal A|.</math> | ||
=== उदाहरण === | === उदाहरण === | ||
मानक हस्ताक्षर <math>\sigma_f</math> क्षेत्र (गणित) के लिए दो बाइनरी | मानक हस्ताक्षर <math>\sigma_f</math> क्षेत्र (गणित) के लिए दो बाइनरी कार्य प्रतीक होते है <math>\mathbf{+}</math> और <math>\mathbf{\times}</math> जहां अतिरिक्त प्रतीकों को प्राप्त किया जा सकता है, जैसे कि एकात्मक कार्य प्रतीक <math>\mathbf{-}</math> (विशिष्ट रूप से निर्धारित <math>\mathbf{+}</math>) और दो स्थिर प्रतीक <math>\mathbf{0}</math> और <math>\mathbf{1}</math> (विशिष्ट रूप से निर्धारित <math>\mathbf{+}</math> और <math>\mathbf{\times}</math> क्रमश)। इस प्रकार हस्ताक्षर के लिए एक संरचना (बीजगणित) में तत्वों का एक समूह होता है <math>A</math> साथ में दो बाइनरी फ़ंक्शंस, जिन्हें एक यूनरी कार्य और दो विशिष्ट तत्वों के साथ बढ़ाया जा सकता है, लेकिन इस बात की कोई आवश्यकता नहीं है कि यह किसी भी क्षेत्र के स्वयंसिद्धों को संतुष्ट करे। परिमेय संख्याएँ <math>\Q,</math> [[वास्तविक संख्या]]एँ <math>\Reals</math> और [[जटिल संख्या]]एँ <math>\Complex,</math> किसी अन्य क्षेत्र की तरह माना जा सकता है <math>\sigma</math>-संरचना एक स्पष्ट तरीके से:<math display=block>\begin{alignat}{3} | ||
\mathcal Q &= (\Q, \sigma_f, I_{\mathcal Q}) \\ | \mathcal Q &= (\Q, \sigma_f, I_{\mathcal Q}) \\ | ||
\mathcal R &= (\Reals, \sigma_f, I_{\mathcal R}) \\ | \mathcal R &= (\Reals, \sigma_f, I_{\mathcal R}) \\ | ||
Line 132: | Line 132: | ||
हर [[बाधा संतुष्टि समस्या]] (CSP) का समरूपता समस्या में अनुवाद है।<nowiki><ref></nowiki>{{Citation |last1=Jeavons |first1=Peter |last2=Cohen |first2=David |last3=Pearson |first3=Justin |date=1998 |title=Constraints and universal algebra |journal=Annals of Mathematics and Artificial Intelligence |doi=10.1023/A:1018941030227 |volume=24 |pages=51–67 |s2cid=15244028 |postscript=.}}</ref> इसलिए, [[परिमित मॉडल सिद्धांत|परिमित प्रतिरूप सिद्धांत]] के तरीकों का उपयोग करके बाधा संतुष्टि और समरूपता समस्या की जटिलता का अध्ययन किया जा सकता है। | हर [[बाधा संतुष्टि समस्या]] (CSP) का समरूपता समस्या में अनुवाद है।<nowiki><ref></nowiki>{{Citation |last1=Jeavons |first1=Peter |last2=Cohen |first2=David |last3=Pearson |first3=Justin |date=1998 |title=Constraints and universal algebra |journal=Annals of Mathematics and Artificial Intelligence |doi=10.1023/A:1018941030227 |volume=24 |pages=51–67 |s2cid=15244028 |postscript=.}}</ref> इसलिए, [[परिमित मॉडल सिद्धांत|परिमित प्रतिरूप सिद्धांत]] के तरीकों का उपयोग करके बाधा संतुष्टि और समरूपता समस्या की जटिलता का अध्ययन किया जा सकता है। | ||
एक अन्य अनुप्रयोग डेटाबेस सिद्धांत में है, जहां डेटाबेस का एक संबंध प्रतिरूप अनिवार्य रूप से एक संबंध | एक अन्य अनुप्रयोग डेटाबेस सिद्धांत में है, जहां डेटाबेस का एक संबंध प्रतिरूप अनिवार्य रूप से एक संबंध संरचना के समान होता है। इससे पता चलता है कि डेटाबेस पर एक संयोजन क्वेरी को डेटाबेस प्रतिरूप के समान हस्ताक्षर में किसी अन्य संरचना द्वारा वर्णित किया जा सकता है। संबंधपरक प्रतिरूप से क्वेरी का प्रतिनिधित्व करने वाली संरचना के लिए एक समरूपता क्वेरी के समाधान के समान ही है। इससे पता चलता है कि संयोजक क्वेरी समस्या भी समाकारिता समस्या के समतुल्य है। | ||
== संरचनाएं और प्रथम-क्रम तर्क == | == संरचनाएं और प्रथम-क्रम तर्क == | ||
{{See also| | {{See also|प्रतिरूप सिद्धांत # प्रथम-क्रम तर्क|प्रतिरूप सिद्धांत # निश्चितता}} | ||
संरचनाओं को कभी-कभी | संरचनाओं को कभी-कभी प्रथम-क्रम संरचना के रूप में संदर्भित किया जाता है। यह भ्रामक है, क्योंकि उनकी परिभाषा में कुछ भी उन्हें किसी विशिष्ट तर्क से बांधता नहीं है, और वास्तव में वे शब्दार्थ वस्तुओं के रूप में उपयुक्त है, दोनों पहले क्रम के तर्क के बहुत सीमित अंशों के लिए जैसे कि सार्वभौमिक बीजगणित में उपयोग किया जाता है, और दूसरे क्रम के तर्क के लिए भी उपयोग किया जाता है। प्रथम-क्रम तर्क और प्रतिरूप सिद्धांत के संबंध में, संरचनाओं को अधिकांशतः प्रतिरूप कहा जाता है, तब भी जब प्रश्न किसका प्रतिरूप? होता है तो कोई स्पष्ट उत्तर नहीं होता है। | ||
=== संतुष्टि संबंध === | === संतुष्टि संबंध === | ||
प्रत्येक प्रथम-क्रम संरचना <math>\mathcal{M} = (M, \sigma, I)</math> संतोष सम्बन्ध है <math>\mathcal{M} \vDash \phi</math> सभी सूत्रों के लिए परिभाषित <math>\, \phi</math> की भाषा से मिलकर भाषा में <math>\mathcal{M}</math> के प्रत्येक तत्व के लिए एक स्थिर प्रतीक के साथ <math>M,</math> जिसकी व्याख्या उस तत्व के रूप में की जाती | प्रत्येक प्रथम-क्रम संरचना <math>\mathcal{M} = (M, \sigma, I)</math> संतोष सम्बन्ध है <math>\mathcal{M} \vDash \phi</math> सभी सूत्रों के लिए परिभाषित <math>\, \phi</math> की भाषा से मिलकर भाषा में <math>\mathcal{M}</math> के प्रत्येक तत्व के लिए एक स्थिर प्रतीक के साथ <math>M,</math> जिसकी व्याख्या उस तत्व के रूप में की जाती है। इस संबंध को टार्स्की की [[टी-स्कीमा]] का उपयोग करके आगमनात्मक रूप से परिभाषित किया गया है। | ||
संरचना <math>\mathcal{M}</math> एक [[सिद्धांत (गणितीय तर्क)]] का एक प्रतिरूप कहा जाता है <math>T</math> यदि की भाषा <math>\mathcal{M}</math> की भाषा के समान है <math>T</math> और हर वाक्य में <math>T</math> से संतुष्ट है <math>\mathcal{M}.</math> इस प्रकार, उदाहरण के लिए, एक वलय, छल्लों की भाषा के लिए एक संरचना है जो प्रत्येक वलय के स्वयंसिद्धों को संतुष्ट करती है, और ज़र्मेलो-फ्रेंकेल स्वयंसिद्धों का एक प्रतिरूप सेट सिद्धांत की भाषा में एक संरचना है जो प्रत्येक | संरचना <math>\mathcal{M}</math> एक [[सिद्धांत (गणितीय तर्क)]] का एक प्रतिरूप कहा जाता है <math>T</math> यदि की भाषा <math>\mathcal{M}</math> की भाषा के समान है <math>T</math> और हर वाक्य में <math>T</math> से संतुष्ट है <math>\mathcal{M}.</math> इस प्रकार, उदाहरण के लिए, एक वलय, छल्लों की भाषा के लिए एक संरचना है जो प्रत्येक वलय के स्वयंसिद्धों को संतुष्ट करती है, और ज़र्मेलो-फ्रेंकेल स्वयंसिद्धों का एक प्रतिरूप सेट सिद्धांत की भाषा में एक संरचना है जो प्रत्येक जेडएफसी स्वयंसिद्धों को संतुष्ट करती है। | ||
=== निश्चित संबंध === | === निश्चित संबंध === | ||
एक <math>n</math>-आर्य संबंध <math>R</math> ब्रह्मांड पर (अर्थात डोमेन) <math>M</math> संरचना का <math>\mathcal{M}</math> परिभाषित करने योग्य कहा जाता है (या स्पष्ट रूप से परिभाषित करने योग्य | एक <math>n</math>-आर्य संबंध <math>R</math> ब्रह्मांड पर (अर्थात डोमेन) <math>M</math> संरचना का <math>\mathcal{M}</math> परिभाषित करने योग्य कहा जाता है (या स्पष्ट रूप से परिभाषित करने योग्य सीएफ [[बेथ निश्चितता]], या <math>\emptyset</math>-परिभाषित करने योग्य, या मापदंडों के साथ निश्चित <math>\emptyset</math>सी एफ नीचे) यदि कोई सूत्र है <math>\varphi(x_1, \ldots, x_n)</math> ऐसा है कि<math display=block>R = \{ (a_1, \ldots, a_n ) \in M^n : \mathcal{M} \vDash \varphi(a_1,\ldots,a_n)\}.</math>दूसरे शब्दों में, <math>R</math> निश्चित है यदि और केवल यदि कोई सूत्र है <math>\varphi</math> ऐसा है कि<math display="block">(a_1,\ldots,a_n ) \in R \Leftrightarrow \mathcal{M} \vDash \varphi(a_1,\ldots,a_n)</math>सही है। | ||
एक महत्वपूर्ण विशेष | एक महत्वपूर्ण विशेष स्थिति विशिष्ट तत्वों की निश्चितता है। तत्व <math>m</math> का <math>M</math> में निश्चित है <math>\mathcal{M}</math> यदि और केवल यदि कोई सूत्र है <math>\varphi(x)</math> ऐसा है कि<math display="block">\mathcal{M}\vDash \forall x ( x = m \leftrightarrow \varphi(x)).</math> | ||
==== मापदंडों के साथ निश्चितता ==== | ==== मापदंडों के साथ निश्चितता ==== | ||
एक रिश्ता <math>R</math> कहा जाता है | एक रिश्ता <math>R</math> कहा जाता है जिसे मापदंडों के साथ परिभाषित किया जा सकता है (या <math>|\mathcal M|</math>-निश्चित) यदि कोई सूत्र है <math>\varphi</math> मापदंडों के साथ <math>\mathcal{M}</math> ऐसा है कि <math>R</math> का प्रयोग करके निश्चित किया जा सकता है <math>\varphi.</math> एक संरचना के प्रत्येक तत्व को प्राचल के रूप में तत्व का उपयोग करके परिभाषित किया जा सकता है। | ||
कुछ लेखक बिना मापदंडों के निश्चित अर्थ के लिए निश्चित का उपयोग करते है, जबकि अन्य लेखकों का मतलब मापदंडों के साथ निश्चित है। मोटे तौर पर, परिपाटी का अर्थ है कि उसे बिना मापदंडों के परिभाषित किया जा सकता है, सेट सिद्धांतकारों के बीच अधिक सामान्य है, जबकि विपरीत सम्मेलन प्रतिरूप सिद्धांतकारों के बीच अधिक सामान्य है। | कुछ लेखक बिना मापदंडों के निश्चित अर्थ के लिए निश्चित का उपयोग करते है, जबकि अन्य लेखकों का मतलब मापदंडों के साथ निश्चित होता है। मोटे तौर पर, परिपाटी का अर्थ है कि उसे बिना मापदंडों के परिभाषित किया जा सकता है, सेट सिद्धांतकारों के बीच अधिक सामान्य होता है, जबकि विपरीत सम्मेलन प्रतिरूप सिद्धांतकारों के बीच अधिक सामान्य होता है। | ||
==== निहित निश्चितता ==== | ==== निहित निश्चितता ==== | ||
Line 163: | Line 163: | ||
ऊपर से याद करें कि ए <math>n</math>-आर्य संबंध <math>R</math> ब्रह्मांड पर <math>M</math> का <math>\mathcal{M}</math> यदि कोई सूत्र है तो स्पष्ट रूप से परिभाषित किया जा सकता है <math>\varphi(x_1, \ldots, x_n)</math> ऐसा है कि<math display=block>R = \{ (a_1,\ldots,a_n ) \in M^n : \mathcal{M} \vDash \varphi(a_1,\ldots,a_n) \}.</math> | ऊपर से याद करें कि ए <math>n</math>-आर्य संबंध <math>R</math> ब्रह्मांड पर <math>M</math> का <math>\mathcal{M}</math> यदि कोई सूत्र है तो स्पष्ट रूप से परिभाषित किया जा सकता है <math>\varphi(x_1, \ldots, x_n)</math> ऐसा है कि<math display=block>R = \{ (a_1,\ldots,a_n ) \in M^n : \mathcal{M} \vDash \varphi(a_1,\ldots,a_n) \}.</math> | ||
यहाँ सूत्र <math>\varphi</math> संबंध को परिभाषित करने के लिए प्रयोग किया जाता है <math>R</math> के हस्ताक्षर के ऊपर होना चाहिए <math>\mathcal{M}</math> इसलिए <math>\varphi</math> उल्लेख नहीं हो सकता <math>R</math> खुद, के बाद से <math>R</math> के हस्ताक्षर में नहीं है <math>\mathcal{M}.</math> यदि कोई सूत्र है <math>\varphi</math> की भाषा युक्त विस्तारित भाषा में <math>\mathcal{M}</math> और एक नया प्रतीक <math>R,</math> और संबंध <math>R</math> पर ही संबंध है <math>\mathcal{M}</math> ऐसा है कि <math>\mathcal{M} \vDash \varphi,</math> तब <math>R</math> परोक्ष रूप से परिभाषित किया जा सकता है <math>\mathcal{M}.</math> बेथ की प्रमेय, प्रत्येक निहित रूप से परिभाषित संबंध स्पष्ट रूप से निश्चित है। | |||
यहाँ सूत्र <math>\varphi</math> संबंध को परिभाषित करने के लिए प्रयोग किया जाता है <math>R</math> के हस्ताक्षर के ऊपर होना चाहिए <math>\mathcal{M}</math> इसलिए <math>\varphi</math> उल्लेख नहीं हो सकता <math>R</math> खुद, के बाद से <math>R</math> के हस्ताक्षर में नहीं है <math>\mathcal{M}.</math> यदि कोई सूत्र है <math>\varphi</math> की भाषा युक्त विस्तारित भाषा में <math>\mathcal{M}</math> और एक नया प्रतीक <math>R,</math> और संबंध <math>R</math> पर ही संबंध है <math>\mathcal{M}</math> ऐसा है कि <math>\mathcal{M} \vDash \varphi,</math> तब <math>R</math> परोक्ष रूप से परिभाषित किया जा सकता है <math>\mathcal{M}.</math> | |||
== कई प्रकार की संरचनाएं == | == कई प्रकार की संरचनाएं == | ||
ऊपर परिभाषित संरचनाओं को कभी-कभी अधिक सामान्य कई-क्रमबद्ध संरचनाओं से अलग करने के लिए एक-क्रमबद्ध संरचना कहा जाता है। कई-सॉर्ट की गई संरचना में डोमेन की मनमानी संख्या हो सकती है। सॉर्ट हस्ताक्षर का हिस्सा है, और वे विभिन्न डोमेन के लिए नामों की भूमिका निभाते है। कई-सॉर्ट किए गए हस्ताक्षर यह भी निर्धारित करते है कि किस प्रकार के कई प्रकार के ढांचे के कार्यों और संबंधों को परिभाषित किया गया है। इसलिए, | ऊपर परिभाषित संरचनाओं को कभी-कभी अधिक सामान्य कई-क्रमबद्ध संरचनाओं से अलग करने के लिए एक-क्रमबद्ध संरचना कहा जाता है। कई-सॉर्ट की गई संरचना में डोमेन की मनमानी संख्या हो सकती है। सॉर्ट हस्ताक्षर का हिस्सा है, और वे विभिन्न डोमेन के लिए नामों की भूमिका निभाते है। कई-सॉर्ट किए गए हस्ताक्षर यह भी निर्धारित करते है कि किस प्रकार के कई प्रकार के ढांचे के कार्यों और संबंधों को परिभाषित किया गया है। इसलिए, कार्य प्रतीकों या संबंध प्रतीकों की समानताएं अधिक जटिल वस्तुएं होनी चाहिए जैसे कि प्राकृतिक संख्याओं के अतिरिक्त टुपल्स ऑफ सॉर्ट। | ||
संचालन रिक्त स्थान, उदाहरण के लिए, निम्नलिखित तरीके से दो क्रमबद्ध संरचनाओं के रूप में माना जा सकता है। संचालन रिक्त स्थान के क्रमबद्ध हस्ताक्षर में दो प्रकार के वी (वैक्टर के लिए) और एस (स्केलर्स के लिए) और निम्नलिखित कार्य प्रतीक होते है: | |||
{| style="width:95%" | {| style="width:95%" | ||
|- valign="top" | |- valign="top" | ||
| | | | ||
* +<sub>'' | * +<sub>''एस''</sub> और ×<sub>''एस''</sub> ऑफ एरिटी (''एस'', ''एस''; ''एस''). | ||
* −<sub>'' | * −<sub>''एस''</sub> ऑफ एरिटी (''एस''; ''एस''). | ||
* 0<sub>'' | * 0<sub>''एस''</sub> और 1<sub>''एस''</sub> ऑफ एरिटी (''एस''). | ||
| | | | ||
* +<sub>'' | * +<sub>''वी''</sub> ऑफ एरिटी (''वी'', ''वी''; ''वी''). | ||
* −<sub>'' | * −<sub>''वी''</sub> ऑफ एरिटी (''वी''; ''वी''). | ||
* 0<sub>'' | * 0<sub>''वी''</sub> ऑफ एरिटी (''वी''). | ||
| | | | ||
* × ऑफ एरिटी ('' | * × ऑफ एरिटी (''एस'', ''वी''; ''वी''). | ||
|} | |} | ||
यदि | यदि वी क्षेत्र एफ पर सदिश स्थान है, तो संबंधित दो-क्रमबद्ध संरचना <math>\mathcal V</math> संचालन डोमेन के होते है <math>|\mathcal V|_V=V</math>, स्केलर डोमेन <math>|\mathcal V|_S=F</math>, और स्पष्ट कार्य, जैसे सदिश शून्य <math>0_V^{\mathcal V}=0\in|\mathcal V|_V</math>, अदिश शून्य <math>0_S^{\mathcal V}=0\in|\mathcal V|_S</math>, या अदिश गुणन <math>\times^{\mathcal V}:|\mathcal V|_S\times|\mathcal V|_V\rightarrow|\mathcal V|_V</math>. | ||
बहु-वर्गीकृत संरचनाओं को अधिकांशतः एक सुविधाजनक उपकरण के रूप में उपयोग किया जाता | बहु-वर्गीकृत संरचनाओं को अधिकांशतः एक सुविधाजनक उपकरण के रूप में उपयोग किया जाता है। लेकिन उन्हें संभवतः ही कभी एक कठोर तरीके से परिभाषित किया जाता है, क्योंकि यह सामान्यीकरण को स्पष्ट रूप से पूरा करने के लिए सीधा और थकाऊ (इसलिए अप्रतिबंधित) होते है। | ||
अधिकांश गणितीय प्रयासों में, छँटाई पर अधिक ध्यान नहीं दिया जाता है। एक [[कई तरह का तर्क]] चूंकि स्वाभाविक रूप से एक प्रकार के सिद्धांत की ओर जाता है। जैसा कि [[बार्ट जैकब्स]] कहते है: एक तर्क हमेशा एक प्रकार के सिद्धांत पर एक तर्क होता है। बदले में यह जोर [[श्रेणीबद्ध तर्क]] की ओर ले जाता है क्योंकि एक प्रकार के सिद्धांत पर एक तर्क स्पष्ट रूप से एक (कुल) श्रेणी से मेल खाता है, तर्क पर कब्जा करना, दूसरे (आधार) श्रेणी पर [[रेशेदार श्रेणी]] होना, [[प्रकार सिद्धांत]] पर कब्जा | अधिकांश गणितीय प्रयासों में, छँटाई पर अधिक ध्यान नहीं दिया जाता है। एक [[कई तरह का तर्क]] चूंकि स्वाभाविक रूप से एक प्रकार के सिद्धांत की ओर जाता है। जैसा कि [[बार्ट जैकब्स]] कहते है: एक तर्क हमेशा एक प्रकार के सिद्धांत पर एक तर्क होता है। बदले में यह जोर [[श्रेणीबद्ध तर्क]] की ओर ले जाता है क्योंकि एक प्रकार के सिद्धांत पर एक तर्क स्पष्ट रूप से एक (कुल) श्रेणी से मेल खाता है, तर्क पर कब्जा करना, दूसरे (आधार) श्रेणी पर [[रेशेदार श्रेणी]] होना, [[प्रकार सिद्धांत]] पर कब्जा करना होता है।<ref>{{Citation | ||
| first = Bart | | first = Bart | ||
| last = Jacobs | | last = Jacobs | ||
Line 201: | Line 199: | ||
=== आंशिक बीजगणित === | === आंशिक बीजगणित === | ||
सार्वभौमिक बीजगणित और प्रतिरूप सिद्धांत दोनों (संरचनाओं या) बीजगणित की कक्षाओं का अध्ययन करते है जो एक हस्ताक्षर और स्वयंसिद्धों के एक सेट द्वारा परिभाषित होते है। प्रतिरूप सिद्धांत के स्थिति में इन स्वयंसिद्धों में पहले क्रम के वाक्यों का रूप है। सार्वभौमिक बीजगणित की औपचारिकता कहीं अधिक प्रतिबंधात्मक है | सार्वभौमिक बीजगणित और प्रतिरूप सिद्धांत दोनों (संरचनाओं या) बीजगणित की कक्षाओं का अध्ययन करते है जो एक हस्ताक्षर और स्वयंसिद्धों के एक सेट द्वारा परिभाषित होते है। प्रतिरूप सिद्धांत के स्थिति में इन स्वयंसिद्धों में पहले क्रम के वाक्यों का रूप है। सार्वभौमिक बीजगणित की औपचारिकता कहीं अधिक प्रतिबंधात्मक होती है, अनिवार्य रूप से यह केवल प्रथम-क्रम के वाक्यों की अनुमति देता है, जिनमें शब्दों के बीच सार्वभौमिक रूप से मात्रात्मक समीकरणों का रूप होता है, उदाहरण {{all}}एक्स{{all}}y (x + y = y + x)। एक परिणाम यह है कि प्रतिरूप सिद्धांत की तुलना में सार्वभौमिक बीजगणित में एक हस्ताक्षर का चुनाव अधिक महत्वपूर्ण होता है। उदाहरण के लिए, समूहों का वर्ग, जिसमें हस्ताक्षर में बाइनरी कार्य प्रतीक × और निरंतर प्रतीक 1 सम्मलित है, एक प्रारंभिक वर्ग है, लेकिन यह [[विविधता (सार्वभौमिक बीजगणित)|विविधता]] नहीं है। यूनिवर्सल बीजगणित इस समस्या को एक यूनरी कार्य प्रतीक <sup>-1</sup>.जोड़कर हल करता है। | ||
क्षेत्र के स्थिति में यह रणनीति सिर्फ जोड़ने के लिए काम करती है। गुणन के लिए यह विफल रहता है क्योंकि 0 में गुणक व्युत्क्रम नहीं होता है। इससे निपटने का एक तदर्थ प्रयास 0 को परिभाषित करना होगा<sup>−1</sup> = 0. (यह प्रयास विफल हो जाता है, अनिवार्य रूप से क्योंकि इस परिभाषा के साथ 0 × 0<sup>-1</sup> = 1 सत्य नहीं | क्षेत्र के स्थिति में यह रणनीति सिर्फ जोड़ने के लिए काम करती है। गुणन के लिए यह विफल रहता है क्योंकि 0 में गुणक व्युत्क्रम नहीं होता है। इससे निपटने का एक तदर्थ प्रयास 0 को परिभाषित करना होगा<sup>−1</sup> = 0. (यह प्रयास विफल हो जाता है, अनिवार्य रूप से क्योंकि इस परिभाषा के साथ 0 × 0<sup>-1</sup> = 1 सत्य नहीं है)। इसलिए, स्वाभाविक रूप से किसी को आंशिक कार्यों की अनुमति देने के लिए प्रेरित किया जाता है, अर्थात ऐसे कार्य जो केवल उनके डोमेन के सबसेट पर परिभाषित होते है। चूँकि, धारणाओं को सामान्य बनाने के कई स्पष्ट तरीके होते है जैसे कि सबसंरचना, समरूपता और पहचान होते है। | ||
=== टाइप की गई भाषाओं के लिए संरचनाएं === | === टाइप की गई भाषाओं के लिए संरचनाएं === | ||
प्रकार सिद्धांत में, कई प्रकार के चर होते है, जिनमें से प्रत्येक का एक प्रकार होता है। प्रकारों को आगमनात्मक रूप से परिभाषित किया गया है | प्रकार सिद्धांत में, कई प्रकार के चर होते है, जिनमें से प्रत्येक का एक प्रकार होता है। प्रकारों को आगमनात्मक रूप से परिभाषित किया गया है, दिए गए दो प्रकार δ और σ का एक प्रकार σ → δ भी है जो प्रकार σ की वस्तुओं से प्रकार δ की वस्तुओं के कार्यों का प्रतिनिधित्व करता है। टाइप की गई भाषा के लिए एक संरचना (सामान्य प्रथम-क्रम शब्दार्थ में) प्रत्येक प्रकार की वस्तुओं का एक अलग सेट सम्मलित होना चाहिए, और कार्य प्रकार के लिए संरचना में उस प्रकार के प्रत्येक वस्तु द्वारा दर्शाए गए कार्य के बारे में पूरी जानकारी होनी चाहिए। | ||
=== उच्च-क्रम की भाषाएँ === | === उच्च-क्रम की भाषाएँ === | ||
{{Main|दूसरे क्रम का तर्क}} | {{Main|दूसरे क्रम का तर्क}} | ||
उच्च-क्रम तर्क के लिए एक से अधिक संभावित शब्दार्थ है, जैसा कि द्वितीय-क्रम तर्क पर लेख में चर्चा की गई है। पूर्ण उच्च-क्रम शब्दार्थ का उपयोग करते समय, एक संरचना के लिए केवल टाइप 0 की वस्तुओं के लिए एक ब्रह्मांड की आवश्यकता होती है, और टी-स्कीमा को विस्तारित किया जाता है जिससे कि उच्च-क्रम प्रकार पर एक | उच्च-क्रम तर्क के लिए एक से अधिक संभावित शब्दार्थ है, जैसा कि द्वितीय-क्रम तर्क पर लेख में चर्चा की गई है। पूर्ण उच्च-क्रम शब्दार्थ का उपयोग करते समय, एक संरचना के लिए केवल टाइप 0 की वस्तुओं के लिए एक ब्रह्मांड की आवश्यकता होती है, और टी-स्कीमा को विस्तारित किया जाता है जिससे कि उच्च-क्रम प्रकार पर एक परिमाणक प्रतिरूप द्वारा संतुष्ट होता है और केवल यदि यह अलग-अलग सत्य होता है। प्रथम-क्रम शब्दार्थ का उपयोग करते समय, प्रत्येक उच्च-क्रम प्रकार के लिए एक अतिरिक्त क्रम जोड़ा जाता है, जैसा कि कई क्रमबद्ध प्रथम क्रम भाषा के स्थिति में होता है। | ||
=== संरचनाएं जो [[उचित वर्ग]] है === | === संरचनाएं जो [[उचित वर्ग]] है === | ||
समुच्चय सिद्धांत और [[श्रेणी सिद्धांत]] के अध्ययन में, कभी-कभी उन संरचनाओं पर विचार करना उपयोगी होता है जिनमें संवाद का क्षेत्र एक समुच्चय के अतिरिक्त एक उचित वर्ग होता है। ऊपर चर्चा किए गए सेट प्रतिरूप से अलग करने के लिए इन संरचनाओं को कभी-कभी क्लास प्रतिरूप कहा जाता है। जब डोमेन एक उचित वर्ग है, तो प्रत्येक कार्य और संबंध प्रतीक को उचित वर्ग द्वारा भी प्रदर्शित किया | समुच्चय सिद्धांत और [[श्रेणी सिद्धांत]] के अध्ययन में, कभी-कभी उन संरचनाओं पर विचार करना उपयोगी होता है जिनमें संवाद का क्षेत्र एक समुच्चय के अतिरिक्त एक उचित वर्ग होता है। ऊपर चर्चा किए गए सेट प्रतिरूप से अलग करने के लिए इन संरचनाओं को कभी-कभी क्लास प्रतिरूप कहा जाता है। जब डोमेन एक उचित वर्ग होता है, तो प्रत्येक कार्य और संबंध प्रतीक को उचित वर्ग द्वारा भी प्रदर्शित किया जाता है। | ||
[[बर्ट्रेंड रसेल]] के '[[गणितीय सिद्धांत]]' में, संरचनाओं को उनके डोमेन के रूप में उचित वर्ग रखने की भी अनुमति थी। | [[बर्ट्रेंड रसेल]] के '[[गणितीय सिद्धांत]]' में, संरचनाओं को उनके डोमेन के रूप में उचित वर्ग रखने की भी अनुमति थी। |
Revision as of 02:18, 22 February 2023
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (April 2010) (Learn how and when to remove this template message) |
सार्वभौमिक बीजगणित और प्रतिरूप सिद्धांत में, संरचना एक सेट (गणित) के साथ-साथ अंतिम संचालन और संबंधों का एक संग्रह होता है जो उस पर परिभाषित होता है।
सार्वभौम बीजगणित उन संरचनाओं का अध्ययन करता है जो समूह, वलय, क्षेत्र और सदिश स्थान जैसी बीजगणितीय संरचनाओं का सामान्यीकरण करती है। सार्वभौम बीजगणित शब्द का उपयोग प्रथम-क्रम के सिद्धांतों की संरचनाओं के लिए किया जाता है, जिसमें कोई संबंध प्रतीक नहीं होता है।[1] प्रतिरूप सिद्धांत का एक अलग दायरा है जिसमें सेट सिद्धांत के प्रतिरूप जैसे मूलभूत संरचनाओं सहित अधिक मनमाना प्रथम-क्रम सिद्धान्त सम्मलित है।
प्रतिरूप-सैद्धांतिक दृष्टिकोण से, संरचनाएं पहले-क्रम तर्क के शब्दार्थ को परिभाषित करने के लिए उपयोग की जाने वाली वस्तुएं है, सीएफ टार्स्की का सत्य का सिद्धांत या टार्स्कियन सिमेंटिक्स का सिद्धांत।
प्रतिरूप सिद्धांत में दिए गए सिद्धांत के लिए, एक संरचना को एक प्रतिरूप कहा जाता है यदि यह उस सिद्धांत के परिभाषित स्वयंसिद्धों को संतुष्ट करता है, चूंकि कभी-कभी इसे सिमेंटिक प्रतिरूप के रूप में असंबद्ध किया जाता है जब कोई गणितीय प्रतिरूप की अधिक सामान्य सेटिंग में धारणा पर चर्चा करता है। तर्कशास्त्री कभी-कभी संरचनाओं को व्याख्या के रूप में संदर्भित करते है,[2] जबकि व्याख्या शब्द का सामान्यतः प्रतिरूप सिद्धांत में एक अलग (चूंकि संबंधित) अर्थ होता है, व्याख्या (प्रतिरूप सिद्धांत) देखें।
डेटाबेस सिद्धांत में, बिना किसी कार्य वाली संरचनाओं का संबंधपरक डेटाबेस के प्रतिरूप के रूप में अध्ययन किया जाता है।
परिभाषा
औपचारिक रूप से, एक संरचना को ट्रिपल के रूप में परिभाषित किया जा सकता है प्रवचन के एक डोमेन से मिलकर एक हस्ताक्षर (तर्क) और एक व्याख्या समारोह यह इंगित करता है कि डोमेन पर हस्ताक्षर की व्याख्या कैसे की जानी है। यह इंगित करने के लिए कि संरचना में एक विशेष हस्ताक्षर है कोई इसे एक -संरचना के रूप में संदर्भित कर सकता है।
डोमेन
संरचना का डोमेन एक मनमाना सेट है, इसे संरचना का अंतर्निहित सेट, वाहक (विशेष रूप से सार्वभौमिक बीजगणित में), ब्रह्मांड (विशेष रूप से प्रतिरूप सिद्धांत) या प्रवचन का डोमेन भी कहा जाता है। मौलिक प्रथम-क्रम तर्क में, संरचना की परिभाषा खाली डोमेन को प्रतिबंधित करती है।[3]
कभी-कभी अंकन या के डोमेन के लिए प्रयोग किया जाता है लेकिन अधिकांशतः एक संरचना और उसके डोमेन (अर्थात, एक ही प्रतीक) के बीच कोई सांकेतिक भेद नहीं किया जाता है संरचना और उसके डोमेन दोनों को संदर्भित करता है।[4]
हस्ताक्षर
हस्ताक्षर (तर्क) एक संरचना के होते है:
- एक सेट कार्य प्रतीकों और संबंध प्रतीकों के साथ होता है
- एक समारोह जो प्रत्येक प्रतीक को बताता है एक प्राकृतिक संख्या प्राकृतिक संख्या एक प्रतीक का की आरती कहलाती है क्योंकि यह व्याख्या की योग्यता होती है
चूंकि बीजगणित में उत्पन्न होने वाले हस्ताक्षरों में अधिकांशतः केवल कार्य प्रतीक होते है, बिना संबंध प्रतीकों वाले हस्ताक्षर को बीजगणितीय हस्ताक्षर कहा जाता है। ऐसे हस्ताक्षर वाली संरचना को बीजगणित भी कहा जाता है, इसे किसी क्षेत्र पर बीजगणित की धारणा के साथ भ्रमित नहीं होना चाहिए।
व्याख्या समारोह
व्याख्या कार्य का हस्ताक्षर के प्रतीकों को कार्य और संबंध प्रदान करता है। प्रत्येक समारोह प्रतीक दया की सौंपा गया है -एरी समारोह डोमेन पर प्रदान करता है। प्रत्येक संबंध प्रतीक दया की एक सौंपा गया है -आर्य संबंध डोमेन पर प्रदान करता है। एक शून्य (-आरी) कार्य प्रतीक एक स्थिर प्रतीक कहा जाता है, क्योंकि इसकी व्याख्या डोमेन के एक स्थिर तत्व के साथ पहचाना जा सकता है।
जब एक संरचना (और इसलिए एक व्याख्या कार्य) संदर्भ द्वारा दी जाती है, तो प्रतीक और इसकी व्याख्या के बीच कोई सांकेतिक भेद नहीं किया जाता है। उदाहरण के लिए, यदि का एक बाइनरी कार्य प्रतीक है एक बस लिखता है इसके अतिरिक्त
उदाहरण
मानक हस्ताक्षर क्षेत्र (गणित) के लिए दो बाइनरी कार्य प्रतीक होते है और जहां अतिरिक्त प्रतीकों को प्राप्त किया जा सकता है, जैसे कि एकात्मक कार्य प्रतीक (विशिष्ट रूप से निर्धारित ) और दो स्थिर प्रतीक और (विशिष्ट रूप से निर्धारित और क्रमश)। इस प्रकार हस्ताक्षर के लिए एक संरचना (बीजगणित) में तत्वों का एक समूह होता है साथ में दो बाइनरी फ़ंक्शंस, जिन्हें एक यूनरी कार्य और दो विशिष्ट तत्वों के साथ बढ़ाया जा सकता है, लेकिन इस बात की कोई आवश्यकता नहीं है कि यह किसी भी क्षेत्र के स्वयंसिद्धों को संतुष्ट करे। परिमेय संख्याएँ वास्तविक संख्याएँ और जटिल संख्याएँ किसी अन्य क्षेत्र की तरह माना जा सकता है -संरचना एक स्पष्ट तरीके से:
- परिमेय संख्याओं का जोड़ है,
- परिमेय संख्याओं का गुणन है,
- वह कार्य है जो प्रत्येक तर्कसंगत संख्या लेता है को और
- संख्या है और
- संख्या है
और और समान रूप से परिभाषित है।[5] इसलिए, परिमित प्रतिरूप सिद्धांत के तरीकों का उपयोग करके बाधा संतुष्टि और समरूपता समस्या की जटिलता का अध्ययन किया जा सकता है।
एक अन्य अनुप्रयोग डेटाबेस सिद्धांत में है, जहां डेटाबेस का एक संबंध प्रतिरूप अनिवार्य रूप से एक संबंध संरचना के समान होता है। इससे पता चलता है कि डेटाबेस पर एक संयोजन क्वेरी को डेटाबेस प्रतिरूप के समान हस्ताक्षर में किसी अन्य संरचना द्वारा वर्णित किया जा सकता है। संबंधपरक प्रतिरूप से क्वेरी का प्रतिनिधित्व करने वाली संरचना के लिए एक समरूपता क्वेरी के समाधान के समान ही है। इससे पता चलता है कि संयोजक क्वेरी समस्या भी समाकारिता समस्या के समतुल्य है।
संरचनाएं और प्रथम-क्रम तर्क
संरचनाओं को कभी-कभी प्रथम-क्रम संरचना के रूप में संदर्भित किया जाता है। यह भ्रामक है, क्योंकि उनकी परिभाषा में कुछ भी उन्हें किसी विशिष्ट तर्क से बांधता नहीं है, और वास्तव में वे शब्दार्थ वस्तुओं के रूप में उपयुक्त है, दोनों पहले क्रम के तर्क के बहुत सीमित अंशों के लिए जैसे कि सार्वभौमिक बीजगणित में उपयोग किया जाता है, और दूसरे क्रम के तर्क के लिए भी उपयोग किया जाता है। प्रथम-क्रम तर्क और प्रतिरूप सिद्धांत के संबंध में, संरचनाओं को अधिकांशतः प्रतिरूप कहा जाता है, तब भी जब प्रश्न किसका प्रतिरूप? होता है तो कोई स्पष्ट उत्तर नहीं होता है।
संतुष्टि संबंध
प्रत्येक प्रथम-क्रम संरचना संतोष सम्बन्ध है सभी सूत्रों के लिए परिभाषित की भाषा से मिलकर भाषा में के प्रत्येक तत्व के लिए एक स्थिर प्रतीक के साथ जिसकी व्याख्या उस तत्व के रूप में की जाती है। इस संबंध को टार्स्की की टी-स्कीमा का उपयोग करके आगमनात्मक रूप से परिभाषित किया गया है।
संरचना एक सिद्धांत (गणितीय तर्क) का एक प्रतिरूप कहा जाता है यदि की भाषा की भाषा के समान है और हर वाक्य में से संतुष्ट है इस प्रकार, उदाहरण के लिए, एक वलय, छल्लों की भाषा के लिए एक संरचना है जो प्रत्येक वलय के स्वयंसिद्धों को संतुष्ट करती है, और ज़र्मेलो-फ्रेंकेल स्वयंसिद्धों का एक प्रतिरूप सेट सिद्धांत की भाषा में एक संरचना है जो प्रत्येक जेडएफसी स्वयंसिद्धों को संतुष्ट करती है।
निश्चित संबंध
एक -आर्य संबंध ब्रह्मांड पर (अर्थात डोमेन) संरचना का परिभाषित करने योग्य कहा जाता है (या स्पष्ट रूप से परिभाषित करने योग्य सीएफ बेथ निश्चितता, या -परिभाषित करने योग्य, या मापदंडों के साथ निश्चित सी एफ नीचे) यदि कोई सूत्र है ऐसा है कि
एक महत्वपूर्ण विशेष स्थिति विशिष्ट तत्वों की निश्चितता है। तत्व का में निश्चित है यदि और केवल यदि कोई सूत्र है ऐसा है कि
मापदंडों के साथ निश्चितता
एक रिश्ता कहा जाता है जिसे मापदंडों के साथ परिभाषित किया जा सकता है (या -निश्चित) यदि कोई सूत्र है मापदंडों के साथ ऐसा है कि का प्रयोग करके निश्चित किया जा सकता है एक संरचना के प्रत्येक तत्व को प्राचल के रूप में तत्व का उपयोग करके परिभाषित किया जा सकता है।
कुछ लेखक बिना मापदंडों के निश्चित अर्थ के लिए निश्चित का उपयोग करते है, जबकि अन्य लेखकों का मतलब मापदंडों के साथ निश्चित होता है। मोटे तौर पर, परिपाटी का अर्थ है कि उसे बिना मापदंडों के परिभाषित किया जा सकता है, सेट सिद्धांतकारों के बीच अधिक सामान्य होता है, जबकि विपरीत सम्मेलन प्रतिरूप सिद्धांतकारों के बीच अधिक सामान्य होता है।
निहित निश्चितता
ऊपर से याद करें कि ए -आर्य संबंध ब्रह्मांड पर का यदि कोई सूत्र है तो स्पष्ट रूप से परिभाषित किया जा सकता है ऐसा है कि
यहाँ सूत्र संबंध को परिभाषित करने के लिए प्रयोग किया जाता है के हस्ताक्षर के ऊपर होना चाहिए इसलिए उल्लेख नहीं हो सकता खुद, के बाद से के हस्ताक्षर में नहीं है यदि कोई सूत्र है की भाषा युक्त विस्तारित भाषा में और एक नया प्रतीक और संबंध पर ही संबंध है ऐसा है कि तब परोक्ष रूप से परिभाषित किया जा सकता है बेथ की प्रमेय, प्रत्येक निहित रूप से परिभाषित संबंध स्पष्ट रूप से निश्चित है।
कई प्रकार की संरचनाएं
ऊपर परिभाषित संरचनाओं को कभी-कभी अधिक सामान्य कई-क्रमबद्ध संरचनाओं से अलग करने के लिए एक-क्रमबद्ध संरचना कहा जाता है। कई-सॉर्ट की गई संरचना में डोमेन की मनमानी संख्या हो सकती है। सॉर्ट हस्ताक्षर का हिस्सा है, और वे विभिन्न डोमेन के लिए नामों की भूमिका निभाते है। कई-सॉर्ट किए गए हस्ताक्षर यह भी निर्धारित करते है कि किस प्रकार के कई प्रकार के ढांचे के कार्यों और संबंधों को परिभाषित किया गया है। इसलिए, कार्य प्रतीकों या संबंध प्रतीकों की समानताएं अधिक जटिल वस्तुएं होनी चाहिए जैसे कि प्राकृतिक संख्याओं के अतिरिक्त टुपल्स ऑफ सॉर्ट।
संचालन रिक्त स्थान, उदाहरण के लिए, निम्नलिखित तरीके से दो क्रमबद्ध संरचनाओं के रूप में माना जा सकता है। संचालन रिक्त स्थान के क्रमबद्ध हस्ताक्षर में दो प्रकार के वी (वैक्टर के लिए) और एस (स्केलर्स के लिए) और निम्नलिखित कार्य प्रतीक होते है:
|
|
|
यदि वी क्षेत्र एफ पर सदिश स्थान है, तो संबंधित दो-क्रमबद्ध संरचना संचालन डोमेन के होते है , स्केलर डोमेन , और स्पष्ट कार्य, जैसे सदिश शून्य , अदिश शून्य , या अदिश गुणन .
बहु-वर्गीकृत संरचनाओं को अधिकांशतः एक सुविधाजनक उपकरण के रूप में उपयोग किया जाता है। लेकिन उन्हें संभवतः ही कभी एक कठोर तरीके से परिभाषित किया जाता है, क्योंकि यह सामान्यीकरण को स्पष्ट रूप से पूरा करने के लिए सीधा और थकाऊ (इसलिए अप्रतिबंधित) होते है।
अधिकांश गणितीय प्रयासों में, छँटाई पर अधिक ध्यान नहीं दिया जाता है। एक कई तरह का तर्क चूंकि स्वाभाविक रूप से एक प्रकार के सिद्धांत की ओर जाता है। जैसा कि बार्ट जैकब्स कहते है: एक तर्क हमेशा एक प्रकार के सिद्धांत पर एक तर्क होता है। बदले में यह जोर श्रेणीबद्ध तर्क की ओर ले जाता है क्योंकि एक प्रकार के सिद्धांत पर एक तर्क स्पष्ट रूप से एक (कुल) श्रेणी से मेल खाता है, तर्क पर कब्जा करना, दूसरे (आधार) श्रेणी पर रेशेदार श्रेणी होना, प्रकार सिद्धांत पर कब्जा करना होता है।[6]
अन्य सामान्यीकरण
आंशिक बीजगणित
सार्वभौमिक बीजगणित और प्रतिरूप सिद्धांत दोनों (संरचनाओं या) बीजगणित की कक्षाओं का अध्ययन करते है जो एक हस्ताक्षर और स्वयंसिद्धों के एक सेट द्वारा परिभाषित होते है। प्रतिरूप सिद्धांत के स्थिति में इन स्वयंसिद्धों में पहले क्रम के वाक्यों का रूप है। सार्वभौमिक बीजगणित की औपचारिकता कहीं अधिक प्रतिबंधात्मक होती है, अनिवार्य रूप से यह केवल प्रथम-क्रम के वाक्यों की अनुमति देता है, जिनमें शब्दों के बीच सार्वभौमिक रूप से मात्रात्मक समीकरणों का रूप होता है, उदाहरण एक्सy (x + y = y + x)। एक परिणाम यह है कि प्रतिरूप सिद्धांत की तुलना में सार्वभौमिक बीजगणित में एक हस्ताक्षर का चुनाव अधिक महत्वपूर्ण होता है। उदाहरण के लिए, समूहों का वर्ग, जिसमें हस्ताक्षर में बाइनरी कार्य प्रतीक × और निरंतर प्रतीक 1 सम्मलित है, एक प्रारंभिक वर्ग है, लेकिन यह विविधता नहीं है। यूनिवर्सल बीजगणित इस समस्या को एक यूनरी कार्य प्रतीक -1.जोड़कर हल करता है।
क्षेत्र के स्थिति में यह रणनीति सिर्फ जोड़ने के लिए काम करती है। गुणन के लिए यह विफल रहता है क्योंकि 0 में गुणक व्युत्क्रम नहीं होता है। इससे निपटने का एक तदर्थ प्रयास 0 को परिभाषित करना होगा−1 = 0. (यह प्रयास विफल हो जाता है, अनिवार्य रूप से क्योंकि इस परिभाषा के साथ 0 × 0-1 = 1 सत्य नहीं है)। इसलिए, स्वाभाविक रूप से किसी को आंशिक कार्यों की अनुमति देने के लिए प्रेरित किया जाता है, अर्थात ऐसे कार्य जो केवल उनके डोमेन के सबसेट पर परिभाषित होते है। चूँकि, धारणाओं को सामान्य बनाने के कई स्पष्ट तरीके होते है जैसे कि सबसंरचना, समरूपता और पहचान होते है।
टाइप की गई भाषाओं के लिए संरचनाएं
प्रकार सिद्धांत में, कई प्रकार के चर होते है, जिनमें से प्रत्येक का एक प्रकार होता है। प्रकारों को आगमनात्मक रूप से परिभाषित किया गया है, दिए गए दो प्रकार δ और σ का एक प्रकार σ → δ भी है जो प्रकार σ की वस्तुओं से प्रकार δ की वस्तुओं के कार्यों का प्रतिनिधित्व करता है। टाइप की गई भाषा के लिए एक संरचना (सामान्य प्रथम-क्रम शब्दार्थ में) प्रत्येक प्रकार की वस्तुओं का एक अलग सेट सम्मलित होना चाहिए, और कार्य प्रकार के लिए संरचना में उस प्रकार के प्रत्येक वस्तु द्वारा दर्शाए गए कार्य के बारे में पूरी जानकारी होनी चाहिए।
उच्च-क्रम की भाषाएँ
उच्च-क्रम तर्क के लिए एक से अधिक संभावित शब्दार्थ है, जैसा कि द्वितीय-क्रम तर्क पर लेख में चर्चा की गई है। पूर्ण उच्च-क्रम शब्दार्थ का उपयोग करते समय, एक संरचना के लिए केवल टाइप 0 की वस्तुओं के लिए एक ब्रह्मांड की आवश्यकता होती है, और टी-स्कीमा को विस्तारित किया जाता है जिससे कि उच्च-क्रम प्रकार पर एक परिमाणक प्रतिरूप द्वारा संतुष्ट होता है और केवल यदि यह अलग-अलग सत्य होता है। प्रथम-क्रम शब्दार्थ का उपयोग करते समय, प्रत्येक उच्च-क्रम प्रकार के लिए एक अतिरिक्त क्रम जोड़ा जाता है, जैसा कि कई क्रमबद्ध प्रथम क्रम भाषा के स्थिति में होता है।
संरचनाएं जो उचित वर्ग है
समुच्चय सिद्धांत और श्रेणी सिद्धांत के अध्ययन में, कभी-कभी उन संरचनाओं पर विचार करना उपयोगी होता है जिनमें संवाद का क्षेत्र एक समुच्चय के अतिरिक्त एक उचित वर्ग होता है। ऊपर चर्चा किए गए सेट प्रतिरूप से अलग करने के लिए इन संरचनाओं को कभी-कभी क्लास प्रतिरूप कहा जाता है। जब डोमेन एक उचित वर्ग होता है, तो प्रत्येक कार्य और संबंध प्रतीक को उचित वर्ग द्वारा भी प्रदर्शित किया जाता है।
बर्ट्रेंड रसेल के 'गणितीय सिद्धांत' में, संरचनाओं को उनके डोमेन के रूप में उचित वर्ग रखने की भी अनुमति थी।
यह भी देखें
टिप्पणियाँ
- ↑ Some authors refer to structures as "algebras" when generalizing universal algebra to allow relations as well as functions.
- ↑ Hodges, Wilfrid (2009). "Functional Modelling and Mathematical Models". In Meijers, Anthonie (ed.). Philosophy of technology and engineering sciences. Handbook of the Philosophy of Science. Vol. 9. Elsevier. ISBN 978-0-444-51667-1.
- ↑ A logical system that allows the empty domain is known as an inclusive logic.
- ↑ As a consequence of these conventions, the notation may also be used to refer to the cardinality of the domain of In practice this never leads to confusion.
- ↑ 5.0 5.1 टिप्पणी: और बाईं ओर के संकेतों को देखें और दाईं ओर की प्राकृतिक संख्या देखें और यूनरी ऑपरेशन माइनस इन </रेफरी>
लेकिन अंगूठी पूर्णांकों की संख्या, जो एक क्षेत्र नहीं है, भी एक है -संरचना उसी तरह। वास्तव में, इसकी कोई आवश्यकता नहीं है any क्षेत्र के स्वयंसिद्धों में एक है -संरचना।
आदेशित फ़ील्ड के लिए एक हस्ताक्षर के लिए एक अतिरिक्त बाइनरी संबंध की आवश्यकता होती है जैसे या और इसलिए इस तरह के हस्ताक्षर के लिए संरचनाएं बीजगणित नहीं हैं, भले ही वे शब्द के सामान्य, ढीले अर्थों में निश्चित रूप से बीजगणितीय संरचनाएं हों।
समुच्चय सिद्धांत के लिए सामान्य हस्ताक्षर में एक एकल द्विआधारी संबंध शामिल होता है इस हस्ताक्षर के लिए एक संरचना में तत्वों का एक सेट होता है और इसकी व्याख्या होती है इन तत्वों पर एक द्विआधारी संबंध के रूप में संबंध।
प्रेरित अवसंरचनाएं और बंद उपसमुच्चय
की उपसंरचना (गणित)|(प्रेरित) उपसंरचना कहलाती है अगर
- और एक ही हस्ताक्षर हैं
- का डोमेन के क्षेत्र में आता है और
- सभी कार्यों और संबंध प्रतीकों की व्याख्या पर सहमत हैं
इस संबंध के लिए सामान्य संकेतन है उपसमुच्चय एक संरचना के डोमेन के बंद कहा जाता है अगर यह के कार्यों के तहत बंद है अर्थात्, यदि निम्न स्थिति संतुष्ट होती है: प्रत्येक प्राकृतिक संख्या के लिए प्रत्येक -एरी फ़ंक्शन प्रतीक (हस्ताक्षर में ) और सभी तत्व आवेदन करने का परिणाम तक -टुपल पुन: का एक अंग है प्रत्येक उपसमुच्चय के लिए का सबसे छोटा बंद उपसमुच्चय है उसमें सम्मिलित है इसे द्वारा उत्पन्न बंद उपसमुच्चय कहा जाता है या पतवार और द्वारा दर्शाया गया या . परिचालक के सत्ता स्थापित पर एक अंतिम क्लोजर ऑपरेटर है .
अगर और एक बंद उपसमुच्चय है, तो की एक प्रेरित उपसंरचना है कहाँ σ के प्रत्येक प्रतीक को प्रतिबंध निर्दिष्ट करता है इसकी व्याख्या में इसके विपरीत, एक प्रेरित उपसंरचना का डोमेन एक बंद उपसमुच्चय है।
एक संरचना के बंद उपसमुच्चय (या प्रेरित अवसंरचना) एक जाली (क्रम) बनाते हैं। दो उपसमुच्चयों का मिलन (गणित) उनका प्रतिच्छेदन है। दो उपसमुच्चयों का जुड़ाव (गणित) उनके संघ द्वारा उत्पन्न बंद उपसमुच्चय है। सार्वभौम बीजगणित एक संरचना के अवसंरचनाओं की जाली का विस्तार से अध्ययन करता है।
उदाहरण
होने देना फ़ील्ड के लिए फिर से मानक हस्ताक्षर बनें। जब माना जाता है प्राकृतिक तरीके से संरचनाएँ, परिमेय संख्याएँ वास्तविक संख्याओं का एक उपसंरचना बनाती हैं, और वास्तविक संख्याएँ जटिल संख्याओं का एक उपसंरचना बनाती हैं। परिमेय संख्याएँ वास्तविक (या सम्मिश्र) संख्याओं की सबसे छोटी उपसंरचना होती हैं जो क्षेत्र के स्वयंसिद्धों को भी संतुष्ट करती हैं।
पूर्णांकों का समुच्चय वास्तविक संख्याओं का और भी छोटा उपसंरचना देता है जो कि एक क्षेत्र नहीं है। दरअसल, पूर्णांक इस हस्ताक्षर का उपयोग करते हुए खाली सेट द्वारा उत्पन्न वास्तविक संख्याओं का आधार हैं। सार बीजगणित की धारणा जो इस हस्ताक्षर में एक क्षेत्र के उप-संरचना से मेल खाती है, वह एक क्षेत्र विस्तार की बजाय एक सबरिंग है।
ग्राफ़ (असतत गणित) को परिभाषित करने का सबसे स्पष्ट तरीका हस्ताक्षर के साथ एक संरचना है एक एकल बाइनरी संबंध प्रतीक से मिलकर ग्राफ़ के शीर्ष संरचना का डोमेन बनाते हैं, और दो शीर्षों के लिए और मतलब कि और किनारे से जुड़े हुए हैं। इस एन्कोडिंग में, प्रेरित सबस्ट्रक्चर की धारणा ग्राफ थ्योरी#सबग्राफ्स की शब्दावली की धारणा से अधिक प्रतिबंधात्मक है। उदाहरण के लिए, चलो एक ग्राफ बनें जिसमें किनारे से जुड़े दो कोने हों, और दें एक ही कोने से बना ग्राफ हो लेकिन कोई किनार न हो। का उपसमूह है लेकिन एक प्रेरित उपसंरचना नहीं। ग्राफ सिद्धांत में धारणा जो प्रेरित उप-संरचनाओं से मेल खाती है, वह प्रेरित उप-अनुच्छेदों की है।
समरूपता और एम्बेडिंग
समरूपता
दो संरचनाएं दी गई हैं और एक ही हस्ताक्षर σ, a (σ-) समरूपता से को एक नक्शा है (गणित) जो कार्यों और संबंधों को संरक्षित करता है। ज्यादा ठीक:
- σ और किसी भी तत्व के प्रत्येक n-ary फ़ंक्शन प्रतीक f के लिए , निम्नलिखित समीकरण धारण करता है:
- .
- हर एन-आरी संबंध के लिए σ और किसी भी तत्व का प्रतीक आर , निम्नलिखित निहितार्थ धारण करता है:
- कहाँ , संबंध प्रतीक की व्याख्या है संरचना में वस्तु सिद्धांत की , क्रमश।
एक समरूपता एच से को आमतौर पर के रूप में दर्शाया गया है , हालांकि तकनीकी रूप से कार्य h डोमेन के बीच है , दो संरचनाओं में से , .
प्रत्येक हस्ताक्षर σ के लिए एक ठोस श्रेणी श्रेणी (गणित) σ-होम है जिसमें वस्तुओं के रूप में σ-संरचनाएं और आकारिकी (श्रेणी सिद्धांत) के रूप में σ-होमोमोर्फिज्म हैं।
एक समरूपता कभी-कभी मजबूत कहा जाता है अगर:
- प्रत्येक 'एन'-आर्य संबंध प्रतीक 'आर' वस्तु सिद्धांत और किसी भी तत्व के लिए ऐसा है कि , वहाँ हैं ऐसा है कि और [citation needed][dubious ]
मजबूत समाकारिताएँ σ-होम श्रेणी की एक उपश्रेणी को जन्म देती हैं जिसका ऊपर विरोध किया गया था।
एम्बेडिंग
ए (σ-) समरूपता एक (σ-) एम्बेडिंग कहा जाता है अगर यह इंजेक्शन समारोह है | एक-से-एक और
- σ और किसी भी तत्व के प्रत्येक n-आर्य संबंध प्रतीक 'R के लिए , निम्नलिखित समानता रखती है:
(जहां पहले की तरह , संरचना में वस्तु सिद्धांत σ के संबंध प्रतीक R की व्याख्या को संदर्भित करता है , क्रमश)।
इस प्रकार एक एम्बेडिंग एक मजबूत समरूपता के समान है जो एक-से-एक है। σ-संरचनाओं और σ-एम्बेडिंग की श्रेणी σ-Emb σ-होम की एक ठोस उपश्रेणी है।
प्रेरित अवसंरचनाएँ σ-Emb में उप-वस्तुओं के अनुरूप हैं। यदि σ में केवल फ़ंक्शन प्रतीक हैं, तो σ-Emb σ-होम के एकरूपता की उपश्रेणी है। इस मामले में प्रेरित अवसंरचना भी σ-होम में subobject के अनुरूप है।
उदाहरण
जैसा कि ऊपर देखा गया है, संरचनाओं के रूप में रेखांकन के मानक एन्कोडिंग में प्रेरित उप-संरचना ठीक-ठीक प्रेरित उप-अनुच्छेद हैं। हालाँकि, एक ग्राफ समरूपता एक ही चीज़ है जो ग्राफ़ को कोड करने वाली दो संरचनाओं के बीच एक होमोमोर्फिज़्म है। पिछले अनुभाग के उदाहरण में, भले ही G का सबग्राफ H प्रेरित न हो, पहचान मैप आईडी: H → G एक समरूपता है। यह नक्शा वास्तव में σ-'होम' श्रेणी में एक मोनोमोर्फिज्म है, और इसलिए H, G का एक सबऑब्जेक्ट है जो एक प्रेरित सबस्ट्रक्चर नहीं है।
समरूपता समस्या
निम्नलिखित समस्या को समरूपता समस्या के रूप में जाना जाता है:
- दो परिमित संरचनाओं को देखते हुए और एक परिमित संबंधपरक हस्ताक्षर के लिए, एक समरूपता खोजें या दिखाएँ कि ऐसा कोई समरूपता मौजूद नहीं है।
हर बाधा संतुष्टि समस्या (CSP) का समरूपता समस्या में अनुवाद है।<ref>Jeavons, Peter; Cohen, David; Pearson, Justin (1998), "Constraints and universal algebra", Annals of Mathematics and Artificial Intelligence, 24: 51–67, doi:10.1023/A:1018941030227, S2CID 15244028.
- ↑ Jacobs, Bart (1999), Categorical Logic and Type Theory, Elsevier, pp. 1–4, ISBN 9780080528700
संदर्भ
- Burris, Stanley N.; Sankappanavar, H. P. (1981), A Course in Universal Algebra, Berlin, New York: Springer-Verlag
- Chang, Chen Chung; Keisler, H. Jerome (1989) [1973], Model Theory, Elsevier, ISBN 978-0-7204-0692-4
- Diestel, Reinhard (2005) [1997], Graph Theory, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
- Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994), Mathematical Logic (2nd ed.), New York: Springer, ISBN 978-0-387-94258-2
- Hinman, P. (2005), Fundamentals of Mathematical Logic, A K Peters, ISBN 978-1-56881-262-5
- Hodges, Wilfrid (1993), Model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-30442-9
- Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6
- Marker, David (2002), Model Theory: An Introduction, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98760-6
- Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98655-5
- Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6
- Rothmaler, Philipp (2000), Introduction to Model Theory, London: CRC Press, ISBN 978-90-5699-313-9
बाहरी संबंध
- Semantics section in Classical Logic (an entry ऑफ Stanford Encyclopedia ऑफ Philosophy)