संबंधों की संरचना

द्विआधारी संबंधों के गणित में, संबंधों की संरचना एक नए द्विआधारी संबंध का निर्माण है R; S दो दिए गए द्विआधारी संबंधों से R और S. संबंधों की गणना में संबंधों के संयोजन को 'सापेक्ष गुणन' कहा जाता है, और इसके परिणाम को एक सापेक्ष उत्पाद कहा जाता है। फलन रचना संबंधों की रचना का विशेष मामला है जहां शामिल सभी संबंध फलन (गणित) हैं।

चाचा शब्द एक मिश्रित संबंध को इंगित करता है: एक व्यक्ति को चाचा होने के लिए, उसे माता-पिता का भाई होना चाहिए। बीजगणितीय तर्क में कहा जाता है कि चाचा ($xUz$) संबंधों की संरचना है ( का एक भाई है$xBy$) और के माता पिता है ($yPz$).

$$U=BP\quad {\text{ is equivalent to: }}\quad xByPz{\text{ if and only if }}xUz.$$

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

परिभाषा

अगर $R\subseteq X\times Y$ और $S\subseteq Y\times Z$ दो द्विआधारी संबंध हैं, तो उनकी रचना $R;S$ संबंध है

$$R;S=\{(x,z)\in X\times Z:{\text{ there exists }}y\in Y{\text{ such that }}(x,y)\in R{\text{ and }}(y,z)\in S\}.$$

दूसरे शब्दों में, $R;S\subseteq X\times Z$ नियम द्वारा परिभाषित किया गया है जो कहता है $(x,z)\in R;S$ अगर और केवल अगर कोई तत्व है $y\in Y$ ऐसा है कि $x\,R\,y\,S\,z$ (वह है, $(x,y)\in R$ और $(y,z)\in S$).

सांकेतिक रूपांतर

संबंधों की संरचना के लिए एक इन्फिक्स संकेतन के रूप में अर्धविराम 1895 की अर्नेस्ट श्रोडर की पाठ्यपुस्तक से मिलता है। गुंथर श्मिट ने विशेष रूप से संबंधपरक गणित (2011) में अर्धविराम के उपयोग को नवीनीकृत किया है। अर्धविराम का उपयोग फ़ंक्शन संरचना # श्रेणी सिद्धांत में प्रयुक्त फ़ंक्शन संरचना के लिए नोटेशन के साथ वैकल्पिक नोटेशन (ज्यादातर कंप्यूटर वैज्ञानिकों द्वारा) साथ ही भाषाई गतिशील शब्दार्थ के भीतर गतिशील संयोजन के लिए संकेतन। एक छोटा घेरा $(R\circ S)$ जॉन एम. होवी द्वारा अपनी पुस्तकों में संबंधों के अर्धसमूहों पर विचार करते हुए संबंधों की संरचना के इन्फिक्स नोटेशन के लिए उपयोग किया गया है। हालांकि, कार्यों की संरचना का प्रतिनिधित्व करने के लिए छोटे वृत्त का व्यापक रूप से उपयोग किया जाता है $g(f(x))=(g\circ f)(x)$ जो ऑपरेशन अनुक्रम से पाठ अनुक्रम को उलट देता है। रेखांकन और संबंध के परिचयात्मक पृष्ठों में छोटे वृत्त का उपयोग किया गया था जब तक इसे तुलना के पक्ष में छोड़ दिया गया (कोई इंफिक्स नोटेशन नहीं)। संयोग#गणित $(RS)$ आमतौर पर बीजगणित में गुणन को दर्शाने के लिए उपयोग किया जाता है, इसलिए यह सापेक्ष गुणन को भी दर्शा सकता है।

आगे वृत्त संकेतन के साथ, सबस्क्रिप्ट का उपयोग किया जा सकता है। कुछ लेखक लिखना पसंद करते हैं $\circ _{l}$ और $\circ _{r}$ स्पष्ट रूप से जब आवश्यक हो, इस पर निर्भर करता है कि क्या बाएँ या दाएँ संबंध पहले लागू होता है। कंप्यूटर विज्ञान में एक और भिन्नता सामने आई है Z संकेतन: $\circ$ पारंपरिक (दाएं) रचना को निरूपित करने के लिए प्रयोग किया जाता है, लेकिन ⨾ (U+2A3E ⨾ Z NOTATION RELATIONAL COMPOSITION) बाईं रचना को दर्शाता है। द्विआधारी संबंध $R\subseteq X\times Y$ कभी-कभी morphisms के रूप में माना जाता है $R:X\to Y$ एक श्रेणी (गणित) में संबंधों की श्रेणी जिसमें वस्तुओं के रूप में सेट होते हैं। Rel में, morphisms की संरचना उपरोक्त परिभाषित संबंधों की बिल्कुल संरचना है। सेट के सेट की श्रेणी श्रेणी Rel की एक उपश्रेणी है जिसमें समान वस्तुएँ हैं लेकिन कम रूप हैं।

गुण

• संबंधों की संरचना साहचर्य संपत्ति है: $R;(S;T)=(R;S);T.$
• का विलोम संबंध $R\,;S$ है $(R\,;S)^{\textsf {T}}=S^{\textsf {T}}\,;R^{\textsf {T}}.$ यह संपत्ति एक सेट पर सभी द्विआधारी संबंधों के सेट को शामिल करने के साथ एक अर्धसमूह बनाती है।
• आंशिक कार्य की संरचना | (आंशिक) कार्य (यानी, कार्यात्मक संबंध) फिर से एक (आंशिक) कार्य है।
• अगर $R$ और $S$ इंजेक्शन हैं, तो $R\,;S$ इंजेक्शन है, जो इसके विपरीत केवल इंजेक्शन का तात्पर्य है $R.$
• अगर $R$ और $S$ फिर विशेषण हैं $R\,;S$ आक्षेपात्मक है, जिसका विपरीत अर्थ केवल की आक्षेपकता है $S.$
• एक सेट पर द्विआधारी संबंधों का सेट $X$ (यानी, से संबंध $X$ को $X$) साथ में (बाएं या दाएं) संबंध रचना शून्य के साथ एक मोनोइड बनाती है, जहां पहचान मानचित्र पर $X$ तटस्थ तत्व है, और खाली सेट अवशोषक तत्व है।

मैट्रिसेस के संदर्भ में रचना

परिमित द्विआधारी संबंध तार्किक मैट्रिक्स द्वारा दर्शाए जाते हैं। इन आव्यूहों की प्रविष्टियाँ या तो शून्य या एक हैं, यह इस बात पर निर्भर करता है कि तुलना की गई वस्तुओं के अनुरूप पंक्ति और स्तंभ के लिए प्रतिनिधित्व किया गया संबंध गलत है या सही है। ऐसे मैट्रिसेस के साथ काम करने में बूलियन अंकगणित शामिल है $1+1=1$ और $1\times 1=1.$ दो तार्किक आव्यूहों के आव्यूह गुणनफल में एक प्रविष्टि 1 होगी, तभी, यदि पंक्ति और स्तंभ के गुणन में संगत 1 हो। रचना के कारक। मैट्रिसेस काल्पनिक न्यायवाक्य और सॉराइट्स के माध्यम से पारंपरिक रूप से निकाले गए निष्कर्षों की गणना करने के लिए एक विधि का गठन करते हैं।

विषम संबंध

एक विषम संबंध पर विचार करें $R\subseteq A\times B;$ यही है जहां $A$ और $B$ विशिष्ट समुच्चय हैं। फिर संबंध की रचना का उपयोग करना $R$ इसके विपरीत संबंध के साथ $R^{\textsf {T}},$ सजातीय संबंध हैं $RR^{\textsf {T}}$ (पर $A$) और $R^{\textsf {T}}R$ (पर $B$).

अगर सभी के लिए $x\in A$ कुछ मौजूद है $y\in B,$ ऐसा है कि $xRy$ (वह है, $R$ बायाँ-कुल संबंध है|(बाएँ-)कुल संबंध), तो सभी के लिए $x,xRR^{\textsf {T}}x$ ताकि $RR^{\textsf {T}}$ एक प्रतिवर्त संबंध है या $I\subseteq RR^{\textsf {T}}$ जहां मैं पहचान संबंध है $\{xIx:x\in A\}.$ इसी प्रकार यदि $R$ तब एक विशेषण संबंध है

$$R^{\textsf {T}}R\supseteq I=\{xIx:x\in B\}.$$
 इस मामले में $R\subseteq RR^{\textsf {T}}R.$ एक द्विक्रियात्मक संबंध के लिए विपरीत समावेशन होता है।

रचना ${\bar {R}}^{\textsf {T}}R$ फेरर के प्रकार के संबंधों को अलग करने के लिए प्रयोग किया जाता है, जो संतुष्ट करता है $R{\bar {R}}^{\textsf {T}}R=R.$

उदाहरण

होने देना $A=$ {फ्रांस, जर्मनी, इटली, स्विट्जरलैंड} और $B=$ {फ्रेंच, जर्मन, इटालियन} संबंध के साथ $R$ द्वारा दिए गए $aRb$ कब $b$ की राष्ट्रभाषा है $a.$ चूंकि दोनों $A$ और $B$ परिमित है, $R$ एक तार्किक मैट्रिक्स द्वारा प्रतिनिधित्व किया जा सकता है, यह मानते हुए कि पंक्तियाँ (ऊपर से नीचे) और स्तंभ (बाएँ से दाएँ) वर्णानुक्रम में क्रमबद्ध हैं:

$${\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\\1&1&1\end{pmatrix}}.$$

विलोम संबंध $R^{\textsf {T}}$ ट्रांसपोज़्ड मैट्रिक्स और रिलेशन कंपोज़िशन से मेल खाता है $R^{\textsf {T}};R$ मैट्रिक्स उत्पाद के अनुरूप है $R^{\textsf {T}}R$ जब योग तार्किक संयोजन द्वारा कार्यान्वित किया जाता है। यह पता चला है कि $3\times 3$ आव्यूह $R^{\textsf {T}}R$ प्रत्येक स्थिति में 1 होता है, जबकि उलटा मैट्रिक्स उत्पाद इस प्रकार गणना करता है:

$$RR^{\textsf {T}}={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\\1&1&1&1\end{pmatrix}}.$$

यह मैट्रिक्स सममित है, और एक सजातीय संबंध का प्रतिनिधित्व करता है $A.$ तदनुसार, $R^{\textsf {T}}\,;R$ पर सार्वभौमिक संबंध है $B,$ इसलिए कोई भी दो भाषाएँ एक राष्ट्र को साझा करती हैं जहाँ वे दोनों बोली जाती हैं (वास्तव में: स्विट्जरलैंड)। इसके विपरीत, यह प्रश्न कि क्या दो दिए गए राष्ट्र एक भाषा साझा करते हैं, का उपयोग करके उत्तर दिया जा सकता है $R\,;R^{\textsf {T}}.$

श्रोडर नियम

दिए गए सेट के लिए $V,$ सभी बाइनरी संबंधों का संग्रह $V$ समावेशन (सेट सिद्धांत) द्वारा आदेशित एक बूलियन जाली बनाता है $(\subseteq ).$ याद रखें कि पूरक (सेट सिद्धांत) समावेशन को उलट देता है: $A\subseteq B{\text{ implies }}B^{\complement }\subseteq A^{\complement }.$ संबंधों के गणित में एक ओवरबार द्वारा सेट के पूरक का प्रतिनिधित्व करना आम है: ${\bar {A}}=A^{\complement }.$ अगर $S$ एक द्विआधारी संबंध है, चलो $S^{\textsf {T}}$ विलोम संबंध का प्रतिनिधित्व करते हैं, जिसे ट्रांज़ोज़ भी कहा जाता है। फिर श्रोडर नियम हैं

$$QR\subseteq S\quad {\text{ is equivalent to }}\quad Q^{\textsf {T}}{\bar {S}}\subseteq {\bar {R}}\quad {\text{ is equivalent to }}\quad {\bar {S}}R^{\textsf {T}}\subseteq {\bar {Q}}.$$

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

$$LM\subseteq N{\text{ implies }}{\bar {N}}M^{\textsf {T}}\subseteq {\bar {L}}.$$

श्रोडर नियमों और पूरकता के साथ एक अज्ञात संबंध के लिए हल किया जा सकता है $X$ समावेशन के संबंध में जैसे

$$RX\subseteq S\quad {\text{and}}\quad XR\subseteq S.$$

उदाहरण के लिए, श्रोडर नियम द्वारा $RX\subseteq S{\text{ implies }}R^{\textsf {T}}{\bar {S}}\subseteq {\bar {X}},$ और पूरकता देता है $X\subseteq {\overline {R^{\textsf {T}}{\bar {S}}}},$ जिसे वाम अवशेष कहा जाता है $S$ द्वारा $R$.

भागफल

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

परिभाषाएँ:

• वाम अवशिष्ट: $A\backslash B\mathrel {:=} {\overline {A^{\textsf {T}}{\bar {B}}}}$
• सही अवशिष्ट: $D/C\mathrel {:=} {\overline {{\bar {D}}C^{\textsf {T}}}}$
• सममित भागफल: $\operatorname {syq} (E,F)\mathrel {:=} {\overline {E^{\textsf {T}}{\bar {F}}}}\cap {\overline {{\bar {E}}^{\textsf {T}}F}}$

श्रोडर के नियमों का उपयोग करना, $AX\subseteq B$ के बराबर है $X\subseteq A\setminus B.$ इस प्रकार बायां अवशेष सबसे बड़ा संबंध संतोषजनक है $AX\subseteq B.$ इसी तरह समावेशन $YC\subseteq D$ के बराबर है $Y\subseteq D\setminus C,$ और सही अवशिष्ट सबसे बड़ा संबंध संतोषजनक है $YC\subseteq D.$ कोई भी सुडोकू सॉल्विंग एल्गोरिदम#रिलेशन्स एंड रेजिडुअल्स के साथ अवशिष्टों के तर्क का अभ्यास कर सकता है।

शामिल हों: रचना का दूसरा रूप

एक कांटा ऑपरेटर $(<)$ दो संबंधों को जोड़ने के लिए पेश किया गया है $c:H\to A$ और $d:H\to B$ में $c\,(<)\,d:H\to A\times B.$ निर्माण अनुमानों पर निर्भर करता है $a:A\times B\to A$ और $b:A\times B\to B,$ संबंधों के रूप में समझा जाता है, जिसका अर्थ है कि विपरीत संबंध हैं $a^{\textsf {T}}$ और $b^{\textsf {T}}.$ फिरforkका $c$ और $d$ द्वारा दिया गया है

$$c\,(<)\,d~\mathrel {:=} ~c;a^{\textsf {T}}\cap \ d;b^{\textsf {T}}.$$

संबंधों की रचना का दूसरा रूप, जो सामान्य पर लागू होता है $n$-स्थान के लिए संबंध $n\geq 2,$ संबंधपरक बीजगणित की ज्वाइन (संबंधपरक बीजगणित) संक्रिया है। यहां परिभाषित दो द्विआधारी संबंधों की सामान्य संरचना उनके शामिल होने से प्राप्त की जा सकती है, जिससे एक टर्नरी संबंध हो जाता है, जिसके बाद एक प्रक्षेपण होता है जो मध्य घटक को हटा देता है। उदाहरण के लिए, क्वेरी लैंग्वेज SQL में ऑपरेशन जॉइन (SQL) है।

यह भी देखें

• Demonic composition
• Friend of a friend

संदर्भ

• M. Kilp, U. Knauer, A.V. Mikhalev (2000) Monoids, Acts and Categories with Applications to Wreath Products and Graphs, De Gruyter Expositions in Mathematics vol. 29, Walter de Gruyter,ISBN 3-11-015248-7.