सकर्मक संबंध: Difference between revisions

| name = सकर्मक संबंध

| type = [[द्विआधारी संबंध]]

| field = [[प्राथमिक बीजगणित]]

| statement = एक सम्बन्ध <math>R</math> on a set <math>X</math> यदि सभी तत्वों के लिए यह सकर्मक है <math>a</math>, <math>b</math>, <math>c</math> in <math>X</math>, जब भी <math>R</math> relates <math>a</math>  to <math>b</math> and <math>b</math> to <math>c</math>, then <math>R</math> भी संबंधित है <math>a</math> to <math>c</math>.

 

गणित में, समुच्चय पर संबंध {{math|''R''}} समुच्चय पर {{math|''X''}} सकर्मक है यदि, सभी तत्वों के लिए {{math|''a''}}, {{math|''b''}}, {{math|''c''}} में {{math|''X''}}, जब भी {{math|''R''}} संबंधित {{math|''a''}} को {{math|''b''}} और {{math|''b''}} को {{math|''c''}}, तब {{math|''R''}} संबंध {{math|''a''}} को {{math|''c''}} भी रखता है प्रत्येक आंशिक क्रम के साथ-साथ प्रत्येक [[ तुल्यता संबंध |तुल्यता संबंध]] को सकर्मक होना चाहिए।

एक [[ सजातीय संबंध |सजातीय संबंध]] {{mvar|R}} मंच पर {{mvar|X}} सकर्मक संबंध है यदि,<ref>{{harvnb|Smith|Eggen|St. Andre|2006|loc=p. 145}}</ref>

जहाँ {{math|''a R b''}} के लिए [[ इंफिक्स नोटेशन |इंफिक्स नोटेशन {{math|(''a'', ''b'') ∈ ''R''}}]] है .

== उदाहरण                                                                                                                                             ==

एक गैर-गणितीय उदाहरण के रूप में, संबंध सकर्मक का उत्पादक है। उदाहरण के लिए, यदि एमी बेकी की उत्पादक है, और बेकी कैरी की उत्पादक है, तो एमी भी कैरी की उत्पादक है।

दूसरी ओर, का जन्म माता-पिता सकर्मक संबंध नहीं है, क्योंकि यदि ऐलिस ब्रेंडा का जन्म माता-पिता है, और ब्रेंडा क्लेयर का जन्म माता-पिता है, तो इसका अर्थ यह नहीं है कि ऐलिस क्लेयर का जन्म माता-पिता है। क्या अधिक है, यह [[ संक्रमणरोधी |संक्रमणरोधी]] है: ऐलिस कभी भी क्लेयर की जन्म माता-पिता नहीं हो सकती है

कम से कम उतना बड़ा है, और सामान्य है [[ समानता (गणित) |समानता (गणित)]] विभिन्न [[ सबसेट |सबसेट]] पर सकर्मक संबंध हैं, उदाहरण के लिए, वास्तविक संख्याओं का समुच्चय या प्राकृतिक संख्याओं का समुच्चय:

* उपसमुच्चय है (समुच्चय समावेशन, समुच्चय पर संबंध)

* भाग ([[ भाजक ]], प्राकृतिक संख्या पर संबंध)

* तात्पर्य (भौतिक सशर्त, ⇒ द्वारा प्रतीक, [[ प्रस्ताव |प्रस्ताव]] पर संबंध)

* उत्तराधिकारी कार्य है (प्राकृतिक संख्याओं पर संबंध)

* समुच्चय का सदस्य है (∈ के रूप में चिन्हित)<ref>However, the class of [[von Neumann ordinal]]s is constructed in a way such that ∈ ''is'' transitive when restricted to that class.</ref>

* लंबवत है ([[ यूक्लिडियन ज्यामिति | यूक्लिडियन ज्यामिति]] में रेखाओं पर संबंध)

किसी भी समुच्चय पर खाली सम्बन्ध <math>X</math> सकर्मक है <ref>{{harvnb|Smith|Eggen|St. Andre|2006|loc=p. 146}}</ref><ref>https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf {{Bare URL PDF|date=March 2022}}</ref> क्योंकि कोई तत्व <math>a,b,c \in X</math> नहीं है ऐसा है कि <math>aRb</math> और <math>bRc</math>, और इसलिए ट्रांज़िटिविटी की स्थिति रिक्त सत्य है। सम्बन्ध {{math|''R''}} केवल एक [[ क्रमित युग्म |क्रमित युग्म]] युक्त होना भी सकर्मक है: यदि क्रमित युग्म रूप <math>(x, x)</math> का है कुछ के लिए <math>x \in X</math> केवल ऐसे तत्व <math>a,b,c \in X</math> हैं <math>a=b=c=x</math>, और वास्तव में इस स्थिति में <math>aRc</math>, जबकि यदि क्रमित युग्म रूप का नहीं है <math>(x, x)</math> तो ऐसे कोई तत्व नहीं हैं <math>a,b,c \in X</math> और इसलिए <math>R</math> निर्वात रूप से सकर्मक है।

=== समापन गुण ===

* दो सकर्मक संबंधों का प्रतिच्छेदन सदैव सकर्मक होता है।<ref>{{Cite journal |last=Bianchi |first=Mariagrazia |last2=Mauri |first2=Anna Gillio Berta |last3=Herzog |first3=Marcel |last4=Verardi |first4=Libero |date=2000-01-12 |title=On finite solvable groups in which normality is a transitive relation |url=https://www.degruyter.com/document/doi/10.1515/jgth.2000.012/html |journal=Journal of Group Theory |volume=3 |issue=2 |doi=10.1515/jgth.2000.012 |issn=1433-5883}}</ref> उदाहरण के लिए, यह जानकर कि पहले उत्पन्न हुआ था और उसका वही पहला नाम है जो सकर्मक है, कोई यह निष्कर्ष निकाल सकता है कि वह पहले उत्पन्न हुआ था और उसका पहला नाम भी वही है जो सकर्मक भी है।

* दो सकर्मक संबंधों का मिलन सकर्मक नहीं होना चाहिए। उदाहरण के लिए, पहले उत्पन्न हुआ था या उसका पहला नाम वही है जो सकर्मक संबंध नहीं है, क्योंकि उदाहरण [[ हर्बर्ट हूवर |हर्बर्ट हूवर]] फ्रैंकलिन डी. रूजवेल्ट से संबंधित है, जो बदले में [[ फ्रैंकलिन पियर्स |फ्रैंकलिन पियर्स]] से संबंधित है, जबकि हूवर फ्रैंकलिन पियर्स से संबंधित नहीं है।

* एक सकर्मक संबंध के पूरक को सकर्मक होने की आवश्यकता नहीं है।<ref name="Derek.1964">{{Cite journal |last=Robinson |first=Derek J. S. |date=January 1964 |title=Groups in which normality is a transitive relation |url=https://www.cambridge.org/core/product/identifier/S0305004100037403/type/journal_article |journal=Mathematical Proceedings of the Cambridge Philosophical Society |language=en |volume=60 |issue=1 |pages=21–38 |doi=10.1017/S0305004100037403 |issn=0305-0041}}</ref> उदाहरण के लिए, जबकि सामान्य सकर्मक है, सामान्य नहीं है केवल तत्व के साथ समुच्चय पर संक्रमणीय है।

एक सकर्मक संबंध [[ असममित संबंध |असममित संबंध]] है यदि और केवल यदि यह अप्रतिवर्ती संबंध है।<ref>{{cite book|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|year=2007|publisher=School of Mathematics - Physics Charles University|location=Prague|page=1|url=http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|url-status=dead|archive-url=https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|archive-date=2013-11-02}} Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".</ref> सकर्मक संबंध को रिफ्लेक्सिव संबंध नहीं होना चाहिए। जब यह होता है, इसे [[ पूर्व आदेश |पूर्व आदेश]] कहा जाता है। उदाहरण के लिए, समुच्चय X = {1,2,3} पर:

* R = {(1,1), (2,2), (3,3), (1,3), (3,2)} रिफ्लेक्सिव है, किन्तु सकर्मक नहीं है, क्योंकि जोड़ी (1,2) अनुपस्थित है,

* R = {(1,1), (2,2), (3,3), (1,3)} सकर्मक होने के साथ-साथ सकर्मक भी है, इसलिए यह पूर्व-आदेश है,

* R = {(1,1), (2,2), (3,3)} रिफ्लेक्सिव होने के साथ-साथ सकर्मक भी है, और प्रीऑर्डर।

== सकर्मक विस्तार और सकर्मक समापन                                                                                                                                                                                ==

{{main|सकर्मक समापन}}

माना {{mvar|R}} समुच्चय पर द्विआधारी संबंध हो {{mvar|X}}. का सकर्मक विस्तार {{mvar|R}}, निरूपित {{math|''R''₁}}, पर सबसे छोटा बाइनरी संबंध है {{mvar|X}} ऐसा है कि {{math|''R''₁}} और {{mvar|R}}, और यदि {{math|(''a'', ''b'') ∈ ''R''}} और {{math|(''b'', ''c'') ∈ ''R''}} तब {{math|(''a'', ''c'') ∈ ''R''₁}}.<ref>{{harvnb|Liu|1985|loc=p. 111}}</ref> उदाहरण के लिए मान लीजिए {{mvar|X}} कस्बों का समूह है, जिनमें से कुछ सड़कों से जुड़े हुए हैं। माना {{mvar|R}} कस्बों पर संबंध हो जहां {{math|(''A'', ''B'') ∈ ''R''}} यदि शहर को सीधे जोड़ने वाली कोई सड़क है {{mvar|A}} और शहर {{mvar|B}}. यह संबंध सकर्मक नहीं होना चाहिए। इस संबंध के सकर्मक विस्तार को इसके {{math|(''A'', ''C'') ∈ ''R''₁}} द्वारा परिभाषित किया जा सकता है यदि आप {{mvar|A}} और {{mvar|C}} अधिकतम दो सड़कों का उपयोग करके कस्बों के बीच यात्रा कर सकते हैं।

यदि कोई संबंध सकर्मक है तो उसका सकर्मक विस्तार स्वयं है, अर्थात यदि {{mvar|R}} तब सकर्मक {{math|1=''R''₁ = ''R''}} संबंध है .

का सकर्मक विस्तार {{math|''R''₁}} द्वारा दर्शाया जाएगा {{math|''R''₂}}, और इस तरह से जारी है, सामान्य तौर पर, सकर्मक विस्तार {{math|''R''_''i''}} होने वाला {{math|''R''_{''i'' + 1}}}. का सकर्मक समापन {{mvar|R}}, द्वारा चिह्नित {{math|''R''*}} या {{math|''R''^∞}} का निर्धारित संघ है {{mvar|R}}, {{math|''R''₁}}, {{math|''R''₂}}, ... .<ref name=Liu112>{{harvnb|Liu|1985|loc=p. 112}}</ref> किसी संबंध का सकर्मक समापन सकर्मक संबंध है।<ref name=Liu112 />

 

उपरोक्त कस्बों और सड़कों के उदाहरण के लिए, {{math|(''A'', ''C'') ∈ ''R''*}} परंतु आप कस्बों के बीच यात्रा कर सकें {{mvar|A}} और {{mvar|C}} कितनी भी सड़कों का उपयोग कर सकता है।

* प्रीऑर्डर - रिफ्लेक्सिव सम्बन्ध और सकर्मक सम्बन्ध

* [[ आंशिक रूप से आदेशित सेट | आंशिक रूप से आदेशित समुच्चय]] - एक [[ विषम संबंध |विषम संबंध]] प्रीऑर्डर

* [[ कुल अग्रिम आदेश | कुल अग्रिम आदेश]] - एक [[ जुड़ा हुआ संबंध |जुड़ा हुआ संबंध]] (जिसे पहले टोटल कहा जाता था) प्रीऑर्डर

* तुल्यता संबंध - एक [[ सममित संबंध |सममित संबंध]] पूर्वक्रम

* सख्त कमजोर क्रम - सख्त आंशिक क्रम जिसमें अतुलनीयता तुल्यता संबंध है

* [[ कुल आदेश | कुल आदेश]] - कनेक्टेड (कुल), एंटीसिमेट्रिक और सकर्मक संबंध

कोई सामान्य सूत्र नहीं है जो परिमित समुच्चय पर सकर्मक संबंधों की संख्या की गणना करता है {{OEIS|id=A006905}} ज्ञात है।<ref>Steven R. Finch, [http://www.people.fas.harvard.edu/~sfinch/csolve/posets.pdf "Transitive relations, topologies and partial orders"], 2003.</ref> चूँकि, साथ रिफ्लेक्सिव, सममित और सकर्मक संबंधों की संख्या ज्ञात करने का सूत्र है - दूसरे शब्दों में, तुल्यता संबंध - {{OEIS|id=A000110}}, वे जो सममित और सकर्मक हैं, वे जो सममित, सकर्मक और विषम हैं, और वे जो कुल, सकर्मक और विषम हैं। फीफर <ref>Götz Pfeiffer, "[http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html Counting Transitive Relations]", ''Journal of Integer Sequences'', Vol. 7 (2004), Article 04.3.2.</ref> इस दिशा में कुछ प्रगति की है, इन गुणों के संयोजन के साथ संबंधों को दूसरे के संदर्भ में व्यक्त किया है, किन्तु फिर भी किसी की गणना करना कठिन है। ब्रिंकमैन और मैके (2005) को भी देखें।<ref>Gunnar Brinkmann and Brendan D. McKay,"[http://cs.anu.edu.au/~bdm/papers/topologies.pdf Counting unlabelled topologies and transitive relations]"</ref> माला ने दिखाया कि पूर्णांक गुणांक वाला कोई भी बहुपद समुच्चय पर सकर्मक संबंधों की संख्या के लिए सूत्र का प्रतिनिधित्व नहीं कर सकता है,<ref>{{Cite journal|last=Mala|first=Firdous Ahmad|date=2021-06-14|title=On the number of transitive relations on a set|url=https://doi.org/10.1007/s13226-021-00100-0|journal=Indian Journal of Pure and Applied Mathematics|language=en|doi=10.1007/s13226-021-00100-0|issn=0975-7465}}</ref> और कुछ पुनरावर्ती संबंध पाए जो उस संख्या के लिए निचली सीमा प्रदान करते हैं। उन्होंने यह भी दिखाया कि वह संख्या डिग्री दो का बहुपद है यदि ठीक दो क्रमित जोड़े सम्मिलित हैं।<ref>{{Cite journal|last=Mala|first=Firdous Ahmad|date=2021-10-13|title=Counting Transitive Relations with Two Ordered Pairs|url=https://doi.org/10.26855/jamc.2021.12.002|journal=Journal of Applied Mathematics and Computation|volume=5|issue=4|pages=247–251|doi=10.26855/jamc.2021.12.002|issn=2576-0645}}</ref>

उपप्रमेय: यदि ''R'' असंबद्ध है, तो R;R^T R के प्रांत पर तुल्यता संबंध है।

: प्रमाण: R; R^T अपने डोमेन पर सममित और स्वतुल्य है। R की एकरूपता के साथ, तुल्यता के लिए सकर्मक आवश्यकता पूरी हो जाती है।

== यह भी देखें                                                                                                                                                                                                                       ==

* [[ सकर्मक कमी | सकर्मक कमी]]

* [[ अकर्मक पासा | अकर्मक पासा]]

* वाजिब पसंद सिद्धांत औपचारिक बयान

* [[ काल्पनिक न्यायवाक्य | काल्पनिक न्यायवाक्य]] - भौतिक नियम की परिवर्तनशीलता

[[Category:All articles with bare URLs for citations]]

[[Category:CS1 English-language sources (en)]]