असंयुक्त सेट

दो असंयुक्त सेट

गणित में, दो सेट (गणित) को असंयुक्त सेट कहा जाता है यदि उनमें कोई तत्व (गणित) समान नहीं है। समान रूप से, दो असंयुक्त सेट ऐसे सेट होते हैं जिनका प्रतिच्छेदन (सेट सिद्धांत) खाली सेट होता है।^[1] उदाहरण के लिए, {1, 2, 3} और {4, 5, 6} असंयुक्त समुच्चय हैं, जबकि {1, 2, 3} और {3, 4, 5} असंयुक्त नहीं हैं। दो या दो से अधिक समुच्चयों के संग्रह को असंयुक्त कहा जाता है यदि संग्रह के कोई भी दो अलग-अलग समुच्चय असंयुक्त हों।

सामान्यीकरण

सेटों का एक असंयुक्त संग्रह

असंयुक्त समुच्चयों की इस परिभाषा को समुच्चयों के परिवार और समुच्चयों के अनुक्रमित परिवार तक बढ़ाया जा सकता है।

परिभाषा के अनुसार, सेटों के संग्रह को सेटों का परिवार कहा जाता है (जैसे कि सत्ता स्थापित , उदाहरण के लिए)। कुछ स्रोतों में यह सेटों का एक सेट है, जबकि अन्य स्रोत इसे सेटों का एक मल्टीसेट होने की अनुमति देते हैं, जिसमें कुछ सेट दोहराए जाते हैं। एक indexed family of sets $\left(A_{i}\right)_{i\in I},$ परिभाषा के अनुसार यह एक सेट-वैल्यू फ़ंक्शन (गणित) है (अर्थात्, यह एक फ़ंक्शन है जो एक सेट निर्दिष्ट करता है $A_{i}$ प्रत्येक तत्व को $i\in I$ इसके डोमेन में) जिसका डोमेन $I$ इसका कहा जाता है index set (और इसके डोमेन के तत्वों को कहा जाता है indices).

समुच्चय के एक परिवार के लिए दो सूक्ष्म रूप से भिन्न परिभाषाएँ हैं ${\mathcal {F}}$ जोड़ीवार विसंयोजन कहलाता है। ऐसी ही एक परिभाषा के अनुसार, यदि परिवार में प्रत्येक दो समूह या तो समान हैं या असंयुक्त हैं तो परिवार असंयुक्त होता है। यह परिभाषा सेट के जोड़ीवार असंयुक्त परिवारों को एक ही सेट की बार-बार प्रतियां रखने की अनुमति देगी। एक वैकल्पिक परिभाषा के अनुसार, परिवार में प्रत्येक दो समूह असंयुक्त होने चाहिए; बार-बार प्रतिलिपियों की अनुमति नहीं है. वही दो परिभाषाएँ सेटों के अनुक्रमित परिवार पर लागू की जा सकती हैं: पहली परिभाषा के अनुसार, परिवार में प्रत्येक दो अलग-अलग सूचकांकों को ऐसे सेटों का नाम देना चाहिए जो असंयुक्त या समान हों, जबकि दूसरे के अनुसार, प्रत्येक दो अलग-अलग सूचकांकों को असंयुक्त सेटों का नाम देना चाहिए .^[2] उदाहरण के लिए, सेट का परिवार { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, ... } दोनों परिभाषाओं के अनुसार असंयुक्त है, जैसा कि परिवार है { {..., −2, 0, 2, 4, ...}, {..., −3, −1, 1, 3, 5} }पूर्णांकों के दो समता वर्गों में से। हालाँकि, परिवार $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ 10 सदस्यों के साथ दो असंयुक्त सेटों में से प्रत्येक में पांच पुनरावृत्तियां होती हैं, इसलिए यह पहली परिभाषा के तहत जोड़ीदार असंयुक्त है, लेकिन दूसरे के तहत नहीं।

दो समुच्चयों को लगभग असंयुक्त समुच्चय कहा जाता है यदि उनका प्रतिच्छेदन किसी अर्थ में छोटा हो। उदाहरण के लिए, दो अनंत समुच्चय जिनका प्रतिच्छेदन एक परिमित समुच्चय है, उन्हें लगभग असंयुक्त कहा जा सकता है।^[3] टोपोलॉजी में, पृथक्करण की तुलना में अधिक सख्त शर्तों के साथ अलग-अलग सेटों की विभिन्न धारणाएँ हैं। उदाहरण के लिए, दो सेटों को तब अलग माना जा सकता है जब उनमें असंयुक्त समापन (टोपोलॉजी) या असंयुक्त पड़ोस (गणित) हो। इसी प्रकार, एक मीट्रिक स्थान में, सकारात्मक रूप से अलग किए गए सेट एक गैर-शून्य मीट्रिक स्थान से अलग किए गए सेट होते हैं।^[4]

अंतर्विभाजन

दो समुच्चयों, या समुच्चयों के एक परिवार की असम्बद्धता, उनके युग्मों के प्रतिच्छेदन (समुच्चय सिद्धांत) के रूप में व्यक्त की जा सकती है।

दो समुच्चय A और B असंयुक्त हैं यदि और केवल यदि उनका प्रतिच्छेदन हो $A\cap B$ खाली सेट है.^[1]इस परिभाषा से यह निष्कर्ष निकलता है कि प्रत्येक समुच्चय रिक्त समुच्चय से असंयुक्त होता है, और यह कि रिक्त समुच्चय ही एकमात्र ऐसा समुच्चय है जो स्वयं से असंयुक्त है।^[5] यदि किसी संग्रह में कम से कम दो सेट हैं, तो शर्त यह है कि संग्रह असंयुक्त है, इसका मतलब है कि पूरे संग्रह का प्रतिच्छेदन खाली है। हालाँकि, सेटों के संग्रह में असंबद्ध हुए बिना एक खाली चौराहा हो सकता है। इसके अतिरिक्त, जबकि दो से कम सेटों का संग्रह तुच्छ रूप से असंयुक्त होता है, क्योंकि तुलना करने के लिए कोई जोड़े नहीं होते हैं, एक सेट के संग्रह का प्रतिच्छेदन उस सेट के बराबर होता है, जो गैर-रिक्त हो सकता है।^[2]उदाहरण के लिए, तीन सेट { {1, 2}, {2, 3}, {1, 3} } एक खाली चौराहा है लेकिन असंयुक्त नहीं है। वास्तव में, इस संग्रह में कोई भी दो असंयुक्त सेट नहीं हैं। साथ ही समुच्चयों का खाली परिवार जोड़ीवार असंयुक्त है।^[6] हेली परिवार सेटों की एक प्रणाली है जिसके भीतर खाली चौराहों वाले एकमात्र उपपरिवार वे हैं जो जोड़ीदार रूप से असंयुक्त हैं। उदाहरण के लिए, वास्तविक संख्याओं के बंद अंतराल एक हेली परिवार बनाते हैं: यदि बंद अंतरालों के एक परिवार में एक खाली चौराहा है और न्यूनतम है (यानी परिवार के किसी भी उपपरिवार में एक खाली चौराहा नहीं है), तो इसे जोड़ीदार रूप से असंयुक्त होना चाहिए।^[7]

विच्छेद संघ और विभाजन

किसी समुच्चय^[8] प्रत्येक विभाजन को समतुल्य संबंध द्वारा वर्णित किया जा सकता है, एक द्विआधारी संबंध जो बताता है कि विभाजन में दो तत्व एक ही सेट से संबंधित हैं या नहीं।^[8]असंयुक्त-सेट डेटा संरचनाएँ^[9] और विभाजन परिशोधन^[10] एक सेट के विभाजन को कुशलतापूर्वक बनाए रखने के लिए कंप्यूटर विज्ञान में दो तकनीकें हैं, क्रमशः, यूनियन संचालन जो दो सेटों को विलय करते हैं या शोधन संचालन जो एक सेट को दो में विभाजित करते हैं।

एक असंयुक्त मिलन का मतलब दो चीजों में से एक हो सकता है। सबसे सरल रूप से, इसका अर्थ उन समुच्चयों का मिलन हो सकता है जो असंयुक्त हैं।^[11] लेकिन यदि दो या दो से अधिक समुच्चय पहले से ही असंयुक्त नहीं हैं, तो संशोधित समुच्चयों का मिलन करने से पहले उन्हें असंयुक्त बनाने के लिए समुच्चयों को संशोधित करके उनका असंयुक्त संघ बनाया जा सकता है।^[12] उदाहरण के लिए, दो सेटों को प्रत्येक तत्व को तत्व की एक क्रमबद्ध जोड़ी और एक बाइनरी मान से प्रतिस्थापित करके असंयुक्त बनाया जा सकता है जो यह दर्शाता है कि यह पहले या दूसरे सेट से संबंधित है या नहीं।^[13] दो से अधिक सेटों के परिवारों के लिए, प्रत्येक तत्व को तत्व की एक क्रमबद्ध जोड़ी और उस सेट के सूचकांक द्वारा प्रतिस्थापित किया जा सकता है जिसमें यह शामिल है।^[14]

यह भी देखें

असंयुक्त उत्तल सेटों के लिए हाइपरप्लेन पृथक्करण प्रमेय
परस्पर अनन्य कार्यक्रम
अपेक्षाकृत अभाज्य, अभाज्य भाजक के असंयुक्त सेट वाली संख्याएँ
सेपरॉयड
पैकिंग सेट करें , सेट के एक परिवार के सबसे बड़े असंयुक्त उपपरिवार को खोजने की समस्या

संदर्भ

↑ ^1.0 ^1.1 Halmos, P. R. (1960), Naive Set Theory, Undergraduate Texts in Mathematics, Springer, p. 15, ISBN 9780387900926.
↑ ^2.0 ^2.1 Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), A Transition to Advanced Mathematics, Cengage Learning, p. 95, ISBN 978-0-495-56202-3.
↑ Halbeisen, Lorenz J. (2011), Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer monographs in mathematics, Springer, p. 184, ISBN 9781447121732.
↑ Copson, Edward Thomas (1988), Metric Spaces, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, p. 62, ISBN 9780521357326.
↑ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA textbooks, Mathematical Association of America, p. 59, ISBN 9780883857793.
↑ See answers to the question ″Is the empty family of sets pairwise disjoint?″
↑ Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038.
↑ ^8.0 ^8.1 Halmos (1960), p. 28.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Chapter 21: Data structures for Disjoint Sets", Introduction to Algorithms (Second ed.), MIT Press, pp. 498–524, ISBN 0-262-03293-7.
↑ Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035, S2CID 33265037.
↑ Ferland, Kevin (2008), Discrete Mathematics: An Introduction to Proofs and Combinatorics, Cengage Learning, p. 45, ISBN 9780618415380.
↑ Arbib, Michael A.; Kfoury, A. J.; Moll, Robert N. (1981), A Basis for Theoretical Computer Science, The AKM series in Theoretical Computer Science: Texts and monographs in computer science, Springer-Verlag, p. 9, ISBN 9783540905738.
↑ Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21, ISBN 9781852332471.
↑ Lee, John M. (2010), Introduction to Topological Manifolds, Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64, ISBN 9781441979407.

बाहरी संबंध

Weisstein, Eric W. "Disjoint Sets". MathWorld.

[halmos-1] 1.0 ^1.1 Halmos, P. R. (1960), Naive Set Theory, Undergraduate Texts in Mathematics, Springer, p. 15, ISBN 9780387900926.

[douglas-2] 2.0 ^2.1 Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), A Transition to Advanced Mathematics, Cengage Learning, p. 95, ISBN 978-0-495-56202-3.

[3] Halbeisen, Lorenz J. (2011), Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer monographs in mathematics, Springer, p. 184, ISBN 9781447121732.

[4] Copson, Edward Thomas (1988), Metric Spaces, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, p. 62, ISBN 9780521357326.

[5] Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA textbooks, Mathematical Association of America, p. 59, ISBN 9780883857793.

[6] See answers to the question ″Is the empty family of sets pairwise disjoint?″

[7] Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038.

[h60-28-8] 8.0 ^8.1 Halmos (1960), p. 28.

[9] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Chapter 21: Data structures for Disjoint Sets", Introduction to Algorithms (Second ed.), MIT Press, pp. 498–524, ISBN 0-262-03293-7.

[10] Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035, S2CID 33265037.

[11] Ferland, Kevin (2008), Discrete Mathematics: An Introduction to Proofs and Combinatorics, Cengage Learning, p. 45, ISBN 9780618415380.

[12] Arbib, Michael A.; Kfoury, A. J.; Moll, Robert N. (1981), A Basis for Theoretical Computer Science, The AKM series in Theoretical Computer Science: Texts and monographs in computer science, Springer-Verlag, p. 9, ISBN 9783540905738.

[13] Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21, ISBN 9781852332471.

[14] Lee, John M. (2010), Introduction to Topological Manifolds, Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64, ISBN 9781441979407.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]