सकर्मक संबंध

सकर्मक संबंध

Type	द्विआधारी संबंध
Field	प्राथमिक बीजगणित
Statement	एक सम्बन्ध $R$ on a set $X$ यदि सभी तत्वों के लिए यह सकर्मक है $a$, $b$, $c$ in $X$, जब भी $R$ relates $a$ to $b$ and $b$ to $c$, then $R$ भी संबंधित है $a$ to $c$.
Symbolic statement	$\forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc$

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

परिभाषा

Transitive binary relations
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ ✗ ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ ✗ Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is required by the definition of the row's term (at the very left). For example, the definition of an equivalence relation requires it to be symmetric. ✗ indicates that the property may, or may not hold. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc,$ and there are additional properties that a homogeneous relation may satisfy.

एक सजातीय संबंध R मंच पर X सकर्मक संबंध है यदि,

सबके लिए a, b, c ∈ X, यदि a R b और b R c, तब a R c.

या पहले क्रम के तर्क के संदर्भ में:

$\forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc$,

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

उदाहरण

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

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

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

जब भी x > y और y > z, तब भी x > z

जब भी x ≥ y और y ≥ z, तब भी x ≥ z

जब भी x = y और y = z, तब भी x = z।

सकर्मक संबंधों के अधिक उदाहरण:

• उपसमुच्चय है (समुच्चय समावेशन, समुच्चय पर संबंध)
• भाग (भाजक , प्राकृतिक संख्या पर संबंध)
• तात्पर्य (भौतिक सशर्त, ⇒ द्वारा प्रतीक, प्रस्ताव पर संबंध)

गैर-सकर्मक संबंधों के उदाहरण:

• उत्तराधिकारी कार्य है (प्राकृतिक संख्याओं पर संबंध)
• समुच्चय का सदस्य है (∈ के रूप में चिन्हित)
• लंबवत है ( यूक्लिडियन ज्यामिति में रेखाओं पर संबंध)

किसी भी समुच्चय पर खाली सम्बन्ध $X$ सकर्मक है क्योंकि कोई तत्व $a,b,c\in X$ नहीं है ऐसा है कि $aRb$ और $bRc$, और इसलिए ट्रांज़िटिविटी की स्थिति रिक्त सत्य है। सम्बन्ध R केवल एक क्रमित युग्म युक्त होना भी सकर्मक है: यदि क्रमित युग्म रूप $(x,x)$ का है कुछ के लिए $x\in X$ केवल ऐसे तत्व $a,b,c\in X$ हैं $a=b=c=x$, और वास्तव में इस स्थिति में $aRc$, जबकि यदि क्रमित युग्म रूप का नहीं है $(x,x)$ तो ऐसे कोई तत्व नहीं हैं $a,b,c\in X$ और इसलिए $R$ निर्वात रूप से सकर्मक है।

गुण

समापन गुण

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

अन्य गुण

एक सकर्मक संबंध असममित संबंध है यदि और केवल यदि यह अप्रतिवर्ती संबंध है। सकर्मक संबंध को रिफ्लेक्सिव संबंध नहीं होना चाहिए। जब यह होता है, इसे पूर्व आदेश कहा जाता है। उदाहरण के लिए, समुच्चय 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 article: सकर्मक समापन

माना R समुच्चय पर द्विआधारी संबंध हो X. का सकर्मक विस्तार R, निरूपित R₁, पर सबसे छोटा बाइनरी संबंध है X ऐसा है कि R₁ और R, और यदि (a, b) ∈ R और (b, c) ∈ R तब (a, c) ∈ R₁. उदाहरण के लिए मान लीजिए X कस्बों का समूह है, जिनमें से कुछ सड़कों से जुड़े हुए हैं। माना R कस्बों पर संबंध हो जहां (A, B) ∈ R यदि शहर को सीधे जोड़ने वाली कोई सड़क है A और शहर B. यह संबंध सकर्मक नहीं होना चाहिए। इस संबंध के सकर्मक विस्तार को इसके (A, C) ∈ R₁ द्वारा परिभाषित किया जा सकता है यदि आप A और C अधिकतम दो सड़कों का उपयोग करके कस्बों के बीच यात्रा कर सकते हैं।

यदि कोई संबंध सकर्मक है तो उसका सकर्मक विस्तार स्वयं है, अर्थात यदि R तब सकर्मक R₁ = R संबंध है .

का सकर्मक विस्तार R₁ द्वारा दर्शाया जाएगा R₂, और इस तरह से जारी है, सामान्य तौर पर, सकर्मक विस्तार R_i होने वाला R_{i + 1}. का सकर्मक समापन R, द्वारा चिह्नित R* या R^∞ का निर्धारित संघ है R, R₁, R₂, ... . किसी संबंध का सकर्मक समापन सकर्मक संबंध है।

संबंध लोगों के समूह का जन्म माता-पिता है, यह सकर्मक संबंध नहीं है। चूँकि, जीव विज्ञान में अक्सर पीढ़ियों की मनमानी संख्या पर जन्म के पितृत्व पर विचार करने की आवश्यकता उत्पन्न होती है: संबंध सकर्मक संबंध का जन्म उत्पादक है और यह संबंध का सकर्मक समापन है जो जन्म का माता-पिता है।

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

संबंध प्रकार जिनमें ट्रांज़िटिविटी की आवश्यकता होती है

• प्रीऑर्डर - रिफ्लेक्सिव सम्बन्ध और सकर्मक सम्बन्ध
• आंशिक रूप से आदेशित समुच्चय - एक विषम संबंध प्रीऑर्डर
• कुल अग्रिम आदेश - एक जुड़ा हुआ संबंध (जिसे पहले टोटल कहा जाता था) प्रीऑर्डर
• तुल्यता संबंध - एक सममित संबंध पूर्वक्रम
• सख्त कमजोर क्रम - सख्त आंशिक क्रम जिसमें अतुलनीयता तुल्यता संबंध है
• कुल आदेश - कनेक्टेड (कुल), एंटीसिमेट्रिक और सकर्मक संबंध

सकर्मक संबंधों की गिनती

कोई सामान्य सूत्र नहीं है जो परिमित समुच्चय पर सकर्मक संबंधों की संख्या की गणना करता है (sequence A006905 in the OEIS) ज्ञात है। चूँकि, साथ रिफ्लेक्सिव, सममित और सकर्मक संबंधों की संख्या ज्ञात करने का सूत्र है - दूसरे शब्दों में, तुल्यता संबंध - (sequence A000110 in the OEIS), वे जो सममित और सकर्मक हैं, वे जो सममित, सकर्मक और विषम हैं, और वे जो कुल, सकर्मक और विषम हैं। फीफर इस दिशा में कुछ प्रगति की है, इन गुणों के संयोजन के साथ संबंधों को दूसरे के संदर्भ में व्यक्त किया है, किन्तु फिर भी किसी की गणना करना कठिन है। ब्रिंकमैन और मैके (2005) को भी देखें। माला ने दिखाया कि पूर्णांक गुणांक वाला कोई भी बहुपद समुच्चय पर सकर्मक संबंधों की संख्या के लिए सूत्र का प्रतिनिधित्व नहीं कर सकता है, और कुछ पुनरावर्ती संबंध पाए जो उस संख्या के लिए निचली सीमा प्रदान करते हैं। उन्होंने यह भी दिखाया कि वह संख्या डिग्री दो का बहुपद है यदि ठीक दो क्रमित जोड़े सम्मिलित हैं।

Number of n-element binary relations of different types

Elem­ents	Any	Transitive	Reflexive	Symmetric	Preorder	Partial order	Total preorder	Total order	Equivalence relation
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
n	2n2		2n2−n	2n(n+1)/2			${\textstyle \sum _{k=0}^{n}k!S(n,k)}$	n!	${\textstyle \sum _{k=0}^{n}S(n,k)}$
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

Note that S(n, k) refers to Stirling numbers of the second kind.

संबंधित गुण

रॉक-पेपर-कैंची खेल अकर्मक और प्रतिसंक्रमणीय संबंध x बीट्स y पर आधारित है।

एक संबंध R को अकर्मण्यता कहा जाता है यदि यह सकर्मक नहीं है, अर्थात, यदि xRy और yRz है, किन्तु xRz नहीं है, कुछ x, y, z के लिए।

एक संबंध R को अकर्मक कहा जाता है यदि यह सकर्मक नहीं है, अर्थात, यदि xRy और yRz है, किन्तु कुछ x, y, z के लिए xRz नहीं है। इसके विपरीत, एक संबंध R को एंटीट्रांसिटिव कहा जाता है यदि xRy और yRz हमेशा यह दर्शाते हैं कि xRz पकड़ में नहीं आता है। उदाहरण के लिए, यदि xy एक सम संख्या है तो xRy द्वारा परिभाषित संबंध अकर्मक है, किन्तु प्रतिसंक्रमणीय नहीं है। यदि x सम है और y विषम संख्या है तो xRy द्वारा परिभाषित संबंध सकर्मक और प्रतिसंक्रमणीय दोनों है। यदि x, y की उत्तराधिकारी संख्या है तो xRy द्वारा परिभाषित संबंध अकर्मक और प्रतिसंक्रमणीय दोनों है। राजनीतिक प्रश्नों या समूह प्राथमिकताओं जैसी स्थितियों में अकर्मण्यता के अप्रत्याशित उदाहरण सामने आते हैं।

स्टोचैस्टिक संस्करणों ( स्टोकेस्टिक ट्रांज़िटिविटी ) के लिए सामान्यीकृत, ट्रांज़िटिविटी के अध्ययन में निर्णय सिद्धांत , साइकोमेट्रिक्स और उपयोगीता के अनुप्रयोग मिलते हैं।

एक सकर्मक संबंध और सामान्यीकरण है; इसके गैर-सममित भाग पर ही सकर्मक होना आवश्यक है। ऐसे संबंधों का उपयोग सामाजिक पसंद सिद्धांत या सूक्ष्मअर्थशास्त्र में किया जाता है।

प्रस्ताव: यदि R एक असमान संबंध है, तो R^T R सकर्मक है।

प्रमाण: मान लीजिए कि a और b ऐसे हैं कि एकसमान, yRb और arty का अर्थ a=b है। इसलिए $xR;R^{T}yR;R^{T}z.$, इसलिए $xRaR^{T}yRbR^{T}z.$ और aR^Ty सकर्मक है।

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

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

यह भी देखें

• सकर्मक कमी
• अकर्मक पासा
• वाजिब पसंद सिद्धांत औपचारिक बयान
• काल्पनिक न्यायवाक्य - भौतिक नियम की परिवर्तनशीलता

संदर्भ

• Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics (3rd ed.), Addison-Wesley, ISBN 0-201-19912-2
• Liu, C.L. (1985), Elements of Discrete Mathematics, McGraw-Hill, ISBN 0-07-038133-X
• Gunther Schmidt, 2010. Relational Mathematics. Cambridge University Press, ISBN 978-0-521-76268-7.
• Smith, Douglas; Eggen, Maurice; St.Andre, Richard (2006), A Transition to Advanced Mathematics (6th ed.), Brooks/Cole, ISBN 978-0-534-39900-9
• Pfeiffer, G. (2004). Counting transitive relations. Journal of Integer Sequences, 7(2), 3.

बाहरी कड़ियाँ

• "Transitivity", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Transitivity in Action at cut-the-knot