सकर्मक संबंध

Transitive relation

Type	Binary relation
Field	Elementary algebra
Statement	A relation $R$ on a set $X$ is transitive if, for all elements $a$, $b$, $c$ in $X$, whenever $R$ relates $a$ to $b$ and $b$ to $c$, then $R$ also relates $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} पर:

• आर = {(1,1), (2,2), (3,3), (1,3), (3,2)} रिफ्लेक्सिव है, लेकिन सकर्मक नहीं है, क्योंकि जोड़ी (1,2) अनुपस्थित है,
• आर = {(1,1), (2,2), (3,3), (1,3)} सकर्मक होने के साथ-साथ सकर्मक भी है, इसलिए यह पूर्व-आदेश है,
• आर = {(1,1), (2,2), (3,3)} रिफ्लेक्सिव होने के साथ-साथ सकर्मक भी है, और प्रीऑर्डर।

सकर्मक विस्तार और सकर्मक बंद

Main article: Transitive closure

होने देना 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) को भी देखें। माला ने दिखाया कि पूर्णांक गुणांक वाला कोई भी बहुपद सेट पर सकर्मक संबंधों की संख्या के लिए सूत्र का प्रतिनिधित्व नहीं कर सकता है, और कुछ पुनरावर्ती संबंध पाए जो उस संख्या के लिए निचली सीमा प्रदान करते हैं। उन्होंने यह भी दिखाया कि वह संख्या डिग्री दो का बहुपद है यदि the set ठीक दो क्रमित जोड़े शामिल हैं।

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 हमेशा यह दर्शाता है कि xRz धारण नहीं करता है। उदाहरण के लिए, यदि xy एक सम संख्या है तो xRy द्वारा परिभाषित संबंध अकर्मक है, लेकिन प्रतिसंक्रमणीय नहीं। xRy द्वारा परिभाषित संबंध यदि x सम है और y विषम संख्या है तो सकर्मक और प्रतिसंक्रमणीय दोनों है। xRy द्वारा परिभाषित संबंध यदि x, y की उत्तराधिकारी फलन संख्या है, दोनों अकर्मक है और संक्रमणरोधी। राजनीतिक प्रश्नों या समूह प्राथमिकताओं जैसी स्थितियों में अकर्मण्यता के अप्रत्याशित उदाहरण उत्पन्न होते हैं। स्टोचैस्टिक संस्करणों (स्टोकेस्टिक ट्रांज़िटिविटी ) के लिए सामान्यीकृत, ट्रांज़िटिविटी के अध्ययन में निर्णय सिद्धांत , साइकोमेट्रिक्स और उपयोगीता के अनुप्रयोग मिलते हैं। एक सकर्मक संबंध और सामान्यीकरण है;इसके गैर-सममित भाग पर ही सकर्मक होना आवश्यक है। ऐसे संबंधों का उपयोग सामाजिक पसंद सिद्धांत या सूक्ष्मअर्थशास्त्र में किया जाता है। प्रस्ताव: यदि आर एक असमान संबंध है, तो आर;आर^T सकर्मक है।

प्रमाण: मान लीजिए $xR;R^{T}yR;R^{T}z.$ फिर ए और बी ऐसे हैं $xRaR^{T}yRbR^{T}z.$ चूँकि R एकसंयोजक है, yRb और aR^Ty का अर्थ a=b है। इसलिए एक्सआरएआर^Tz, इसलिए xR;R^टीजेड और आर; आर^T सकर्मक है।

उपप्रमेय: यदि आर असंबद्ध है, तो आर;आर^T 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श्रेणी: प्रारंभिक बीजगणितसकर्मक संबंध