समुच्चय, संबंध, फलन, आंशिक क्रम व जालक

यह खंड का गिनती-अध्याय है, और गिनतियाँ याद रखने योग्य हैं क्योंकि घड़ी के नीचे उन्हें व्युत्पन्न करने में ही समय जाता है। n-अवयवी समुच्चय पर संबंध केवल n² क्रमित युग्मों का उपसमुच्चय है, अतः कुल 2(n²) संबंध हैं — और प्रत्येक गुण उनमें कुछ युग्म नियत कर देता है व शेष मुक्त छोड़ता है, और यहीं से हर दूसरा सूत्र आता है। स्वतुल्यता n विकर्ण युग्मों को 1 पर नियत करती है, n² − n मुक्त छोड़कर: 2(n² − n) स्वतुल्य संबंध। सममिति प्रत्येक विकर्णेतर युग्म को उसके प्रतिबिंब से बाँध देती है, n विकर्ण प्रविष्टियाँ व उसके ऊपर के n(n − 1)/2 युग्म मुक्त छोड़कर: 2(n(n+1)/2) सममित संबंध। दोनों सूत्र एक ही विचार हैं — मुक्त चुनाव गिनें — और जो अभ्यर्थी उन्हें इस रीति से पुनर्रचित करता है उसे कभी याद नहीं रखना पड़ता कि कौन घातांक किसके साथ जाता है। जो एक गिनती दो की घात नहीं है वह तुल्यता-संबंधों की संख्या है, क्योंकि समुच्चय पर तुल्यता-संबंध उसके विभाजन के समान ही वस्तु है: वे बेल संख्याएँ हैं, और तीन अवयवों पर 5 हैं, 8 नहीं। वह तादात्म्य अध्याय का सर्वाधिक उपयोगी एकल तथ्य है, और इसीलिए "कितने तुल्यता-संबंध" व "कितने प्रकार से विभाजन" भिन्न वस्त्रों में एक ही प्रश्न हैं। क्रम की ओर, आंशिक क्रम स्वतुल्य, प्रतिसममित व संक्रामक होता है, और जालक वह आंशिक क्रम जिसमें प्रत्येक अवयव-युग्म का लघुतम ऊर्ध्व परिबंध व महत्तम अधो परिबंध दोनों हों। भाज्यता के अंतर्गत किसी संख्या के भाजक मानक उदाहरण हैं और वही जो GATE बारंबार देता है: 12 हेतु lub, ल.स. है और glb, म.स., और दोनों समुच्चय के भीतर रहते हैं, अतः वह जालक है। प्रतिसममिति वह शर्त है जिसे अभ्यर्थी सर्वाधिक गलत पढ़ते हैं: वह a ≤ b तथा b ≤ a को वर्जित नहीं करती, वह कहती है कि जब दोनों सत्य हों, तो a व b एक ही अवयव हैं।

मुक्त चुनाव गिनकर संबंध गिनना

n अवयवों के समुच्चय पर, तथा n = 3 पर हल किया
प्रकारगिनती, व वह कहाँ से आती हैn = 3 पर
सभी संबंध2(n²) — n² क्रमित युग्मों में प्रत्येक भीतर या बाहर2⁹ = 512
स्वतुल्य2(n² − n) — n विकर्ण युग्म अनिवार्यतः भीतर, शेष मुक्त2⁶ = 64
सममित2(n(n+1)/2) — विकर्ण तथा प्रत्येक प्रतिबिंब-युग्म में एक मुक्त2⁶ = 64 (n = 3 पर संयोग; अन्यत्र दोनों सूत्र भिन्न हैं)
स्वतुल्य व सममित2(n(n−1)/2) — केवल विकर्ण के ऊपर के युग्म मुक्त2³ = 8
तुल्यताबेल संख्या Bₙ — दो की घात नहीं, क्योंकि संक्रामकता प्रति-युग्म शर्त नहीं हैB₃ = 5 (तथा B₄ = 15)
🎯 तुल्यता-संबंध विभाजन क्यों है
स्वतुल्यता प्रत्येक अवयव को उसके अपने वर्ग में रखती है, सममिति वर्गों को पारस्परिक बनाती है, और संक्रामकता अतिव्यापी वर्गों को एक में जोड़ देती है। जो बचता है वह समुच्चय को ढकने वाले अरिक्त, असंयुक्त खंडों का परिवार है — विभाजन। यह तादात्म्य दोनों दिशाओं में चलता है और कुछ नहीं खोता, अतः तुल्यता-संबंध गिनना विभाजन गिनना ही है, और इसीलिए उत्तर दो की घात के बजाय बेल संख्या है। तीन-अवयवी समुच्चय हेतु पाँच विभाजन ये हैं: तीनों साथ; प्रत्येक अवयव अकेला; तथा दो अवयवों को युग्मित करने व एक को बाहर छोड़ने के तीन प्रकार। इन पाँचों को हाथ से गिनना किसी सूत्र से तेज़ है, और छोटा समुच्चय देने वाले प्रश्न में चलाने योग्य जाँच यही है।

फलन — तीन गिनतियाँ

  • m-समुच्चय से n-समुच्चय तक सभी फलन: nᵐ। m निवेशों में प्रत्येक स्वतंत्र रूप से n निर्गमों में एक चुनता है। 3-समुच्चय से 2-समुच्चय तक वह 2³ = 8 है। ध्यान दें कौन अक्षर घातांक है — प्रांत का आकार ऊपर है, और उसे उलटना मानक भूल है।
  • एकैकी फलन: n·(n − 1)···(n − m + 1)। प्रत्येक निवेश नया निर्गम लेता है, अतः चुनाव घटते जाते हैं। 2-समुच्चय से 4-समुच्चय तक: 4 × 3 = 12। m > n होने पर एक भी नहीं, और यही कोष्ठिका-सिद्धांत को गिनती के रूप में कहना है।
  • आच्छादक फलनों हेतु समावेशन–अपवर्जन चाहिए। m-समुच्चय से 2-समुच्चय पर आच्छादक 2ᵐ − 2 हैं, क्योंकि दो अचर फलन ही ऐसे हैं जो कोई मान छोड़ते हैं: 3-समुच्चय से वह 8 − 2 = 6, और 4-समुच्चय से 16 − 2 = 14। बड़े सहप्रांत हेतु सामान्य रूप एकांतर चिह्नों वाला योग है, और GATE सहप्रांत छोटा रखता ही इसलिए है कि घटाव दिखता रहे।
  • एकैकी-आच्छादक हेतु m = n चाहिए, और तब उनकी संख्या n! है। समान आकार के परिमित समुच्चयों पर एकैकी, आच्छादक व एकैकी-आच्छादक संपाती हो जाते हैं — यह तथ्य अनंत समुच्चयों हेतु असत्य है और ठीक इसीलिए पूछा जाता है।

आंशिक क्रम व जालक

आंशिक क्रम स्वतुल्य, प्रतिसममित व संक्रामक होता है। प्रतिसममिति वह शर्त है जिसे सावधानी से पढ़ना चाहिए: वह कहती है कि यदि a ≤ b तथा b ≤ a हो तो a = b, जो दोनों-ओर की स्थिति वर्जित नहीं करती बल्कि उसे अवयव व स्वयं तक सीमित कर देती है। आंशिक क्रम जालक बनता है जब प्रत्येक युग्म का लघुतम ऊर्ध्व परिबंध (योग) व महत्तम अधो परिबंध (मिलन) हो; वह पूर्ण क्रम होता है जब कोई भी दो अवयव तुलनीय हों, जो बहुत प्रबल शर्त है और GATE के उदाहरणों में विरल।

🧠 भाज्यता के अंतर्गत n के भाजक जानने योग्य उदाहरण हैं
12 के भाजक लें — {1, 2, 3, 4, 6, 12} — "भाग देता है" से क्रमित। स्वतुल्य (प्रत्येक संख्या स्वयं को भाग देती है), प्रतिसममित (यदि a, b को व b, a को भाग दे तो धन पूर्णांकों हेतु a = b), संक्रामक। दो भाजकों का योग उनका ल.स. व मिलन उनका म.स. है, और नियत n के भाजकों हेतु दोनों n के भाजकों में ही रहते हैं — अतः वह जालक है, नीचे 1 व ऊपर n सहित। 30 का भाजक-जालक 8 अवयवों का है और तीन अभाज्य 2, 3 व 5 पर बूलीय जालक है, इसीलिए D₃₀ के प्रश्नों व 3-समुच्चय के घात-समुच्चय के प्रश्नों के उत्तर समान होते हैं।

मुख्य बिंदु

  • मुक्त युग्म गिनकर संबंध गिनें: कुल 2(n²), स्वतुल्य 2(n² − n), सममित 2(n(n+1)/2)। उन्हें पुनर्रचित करना याद रखने से बेहतर है।
  • तुल्यता-संबंध विभाजन हैं, अतः उनकी गिनती बेल संख्या है, दो की घात नहीं: 3-समुच्चय पर 5, 4-समुच्चय पर 15।
  • m-समुच्चय से n-समुच्चय तक फलनों की संख्या nᵐ है — प्रांत का आकार घातांक है, और उसे उलटना मानक भूल है।
  • एकैकी फलन n(n−1)···(n−m+1) चलते हैं और m > n पर लुप्त हो जाते हैं, और यही कोष्ठिका-सिद्धांत गिनती के रूप में। 2-समुच्चय पर आच्छादक 2ᵐ − 2 हैं।
  • आंशिक क्रम स्वतुल्य, प्रतिसममित व संक्रामक है। प्रतिसममिति दोनों-ओर की स्थिति को अवयव व स्वयं तक सीमित करती है; वह उसे वर्जित नहीं करती।
  • जालक हेतु प्रत्येक युग्म का योग व मिलन चाहिए। n के भाजकों हेतु ये ल.स. व म.स. हैं, और दोनों समुच्चय के भीतर रहते हैं।
  • k भिन्न अभाज्यों के गुणनफल का भाजक-जालक k अवयवों पर बूलीय जालक है — D₃₀ व 3-समुच्चय का घात-समुच्चय समान उत्तर देते हैं।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. 3 अवयवों के समुच्चय पर स्वतुल्य संबंधों की संख्या है:

    1. 8
    2. 64
    3. 512
    4. 5
    उत्तर देखें

    उत्तर: B — 64

    3² = 9 क्रमित युग्म हैं। स्वतुल्यता 3 विकर्ण युग्मों को उपस्थित होने पर विवश करती है, जिससे 9 − 3 = 6 युग्म बचते हैं, प्रत्येक भीतर या बाहर होने हेतु मुक्त: 2⁶ = 64। सभी 512 संबंधों की परिगणना कर छानने पर भी 64 मिलता है, और इस अध्याय का आँकड़ा इसी रीति से जाँचा गया। विकल्प C संबंधों की कुल संख्या 2⁹ है, और विकल्प D तीन अवयवों पर तुल्यता-संबंधों की संख्या — दोनों इस परिवार में भ्रामक विकल्प के रूप में आते हैं, अतः पढ़ें कि कौन गुण पूछा गया। सामान्य सूत्र 2(n² − n) याद करने के बजाय पुनर्रचित करने योग्य है: जो गुण विवश करता है उसे नियत करें, जो मुक्त बचे उसे गिनें।

  2. समुच्चय {a, b, c} पर तुल्यता-संबंधों की संख्या है:

    1. 5
    2. 8
    3. 64
    4. 512
    उत्तर देखें

    उत्तर: A — 5

    समुच्चय पर तुल्यता-संबंध ठीक उसका विभाजन है, अतः तीन अवयवों के विभाजन गिनें: तीनों एक खंड में; प्रत्येक अवयव अकेला; तथा दो को साथ रखकर एक को बाहर छोड़ने के तीन प्रकार। वह 1 + 1 + 3 = 5 है, बेल संख्या B₃, और सभी 512 संबंधों की परिगणना कर तीनों गुणों से छानने पर 5 मिलता है। विकल्प B, C व D दो की घातें हैं, और प्रश्न का मुद्दा यही है कि यह गिनती वैसी नहीं: स्वतुल्यता व सममिति प्रति-युग्म शर्तें हैं और दो की घात में गुणित होती हैं, परंतु संक्रामकता नहीं — वह त्रिकों को बाँधती है, अतः उसे मुक्त चुनावों से नहीं गिना जा सकता। चार अवयवों हेतु उत्तर 15 है, 16 नहीं।

  3. 4 अवयवों के समुच्चय से 2 अवयवों के समुच्चय पर आच्छादक फलनों की संख्या है:

    1. 16
    2. 14
    3. 8
    4. 12
    उत्तर देखें

    उत्तर: B — 14

    कुल 2⁴ = 16 फलन हैं। फलन आच्छादक होने में केवल तब विफल होता है जब वह दो निर्गमों में एक छोड़ दे, और ऐसा करने के केवल दो प्रकार हैं — दो अचर फलन। अतः 16 − 2 = 14। विकल्प A कुल है, और वह इसलिए दिया गया कि आच्छादकता की शर्त भूलना ही यहाँ उपलब्ध पूरी त्रुटि है। विकल्प D, 2-समुच्चय से 4-समुच्चय तक एकैकी फलनों की संख्या है, जो प्रतिबिंब-प्रश्न है — 4-समुच्चय से 2-समुच्चय तक एक भी एकैकी फलन नहीं, क्योंकि 4 > 2 और कोष्ठिका-सिद्धांत उन्हें वर्जित करता है। सूत्र चुनने से पहले तीर की दिशा देखें: आच्छादक व एकैकी विपरीत दिशाओं में संकेत करते हैं, और विकल्प-सूची में प्रायः दोनों उत्तर होंगे।

  4. "भाग देता है" संबंध के अंतर्गत 12 के भाजकों का समुच्चय है:

    1. आंशिक क्रम पर जालक नहीं
    2. जालक, जिसमें योग = ल.स. व मिलन = म.स.
    3. पूर्ण क्रम
    4. आंशिक क्रम नहीं, क्योंकि भाज्यता प्रतिसममित नहीं है
    उत्तर देखें

    उत्तर: B — जालक, जिसमें योग = ल.स. व मिलन = म.स.

    धन पूर्णांकों पर भाज्यता स्वतुल्य, प्रतिसममित व संक्रामक है, अतः यह आंशिक क्रम है — और भाजकों {1, 2, 3, 4, 6, 12} हेतु किन्हीं दो सदस्यों के ल.स. व म.स. स्वयं 12 के भाजक हैं, अतः प्रत्येक युग्म का योग व मिलन है: वह जालक है। विकल्प C विफल है क्योंकि 2 व 3 अतुलनीय हैं — कोई दूसरे को भाग नहीं देता — और पूर्ण क्रम हेतु प्रत्येक युग्म का तुलनीय होना आवश्यक है। विकल्प D रुककर सोचने योग्य वास्तविक जाल है: धन पूर्णांकों पर भाज्यता प्रतिसममित है, क्योंकि a | b तथा b | a से a = b होना ही पड़ता है; वह प्रतिसममित होना तब छोड़ती है जब ऋणात्मक अनुमत हों, जहाँ 2 व −2 बराबर न होते हुए भी परस्पर भाग देते हैं। प्रांत दावे का भाग है।

  5. समुच्चय A पर संबंध R प्रतिसममित है यदि:

    1. किसी भी a, b हेतु (a, b) व (b, a) दोनों R में न हों
    2. जब भी (a, b) व (b, a) दोनों R में हों, तो a = b
    3. जब भी (a, b) R में हो, (b, a) न हो
    4. R में कोई युग्म (a, a) न हो
    उत्तर देखें

    उत्तर: B — जब भी (a, b) व (b, a) दोनों R में हों, तो a = b

    प्रतिसममिति दोनों-ओर की स्थिति की अनुमति देती है और उसे सीमित करती है: यदि दोनों दिशाएँ सत्य हों, तो दोनों अवयव एक ही हैं। यही आंशिक क्रम को साथ ही स्वतुल्य होने देता है, क्योंकि (a, a) का दोनों ओर जाना कोई विरोध नहीं। विकल्प A व C असममिति का वर्णन करते हैं, जो कड़ाई से प्रबल शर्त है, (a, a) को पूर्णतः वर्जित करती है और इसीलिए स्वतुल्यता से असंगत है — और एक को दूसरा समझ लेना ही वह कारण है जिससे अभ्यर्थी निष्कर्ष निकालते हैं कि पूर्णांकों पर ≤ प्रतिसममित नहीं। विकल्प D अस्वतुल्य संबंध की परिभाषा है, फिर भिन्न गुण। भाज्यता, ≤ तथा समुच्चय-अंतर्वेशन सभी प्रतिसममित हैं और सभी स्वतुल्य, और तीनों इस प्रकरण के मानक उदाहरण हैं।

  6. मान लें A में 4 अवयव हैं। निम्नलिखित में कौन सही हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. A के घात-समुच्चय में 16 अवयव हैं
    2. A पर 2¹⁶ संबंध हैं
    3. A पर 16 तुल्यता-संबंध हैं
    4. A से A पर 4! एकैकी-आच्छादक फलन हैं
    उत्तर देखें

    उत्तर: A — A के घात-समुच्चय में 16 अवयव हैं; B — A पर 2¹⁶ संबंध हैं; D — A से A पर 4! एकैकी-आच्छादक फलन हैं

    चार में तीन सत्य हैं। n-समुच्चय के घात-समुच्चय में 2ⁿ सदस्य होते हैं, अतः 2⁴ = 16 — विकल्प A। संबंध 4² = 16 क्रमित युग्मों का उपसमुच्चय है, अतः उनकी संख्या 2¹⁶ है — विकल्प B। और परिमित समुच्चय से स्वयं पर एकैकी-आच्छादक फलन क्रमचय है, अतः 4! = 24 हैं — विकल्प D। विकल्प C जाल है और यही कारण है कि यह MSQ है: तुल्यता-संबंधों की संख्या बेल संख्या B₄ = 15 है, 16 नहीं। पंद्रह व सोलह में एक का अंतर है, आसपास के सभी विकल्प दो की घातें हैं, और तेज़ी से बढ़ता अभ्यर्थी मान लेगा कि यह गिनती भी उसी प्रतिरूप का अनुसरण करती है। वह नहीं करती, क्योंकि संक्रामकता युग्मों के बजाय त्रिकों को बाँधती है — वही एक संरचनात्मक तथ्य जिस पर यह अध्याय बारंबार लौटता है।

  7. 3 अवयवों के समुच्चय पर सममित संबंधों की संख्या _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 64

    सममिति (a, b) को (b, a) से बाँध देती है, अतः मुक्त चुनाव 3 विकर्ण प्रविष्टियाँ तथा विकर्ण के ऊपर के 3 प्रतिबिंब-युग्मों में से एक-एक हैं: 3 + 3 = 6 मुक्त चुनाव, जिससे 2⁶ = 64। सामान्य सूत्र 2(n(n+1)/2) है, और n(n + 1)/2 ठीक विकर्ण पर व उसके ऊपर की कोष्ठिकाओं की गिनती है। सभी 512 संबंधों की परिगणना कर सममिति से छानने पर 64 मिलता है, और यह इसी रीति से जाँचा गया। ध्यान दें 64 तीन अवयवों पर स्वतुल्य संबंधों की संख्या भी है — n = 3 पर संयोग, जहाँ n² − n व n(n + 1)/2 दोनों 6 हैं, और वह n = 4 पर समाप्त हो जाता है, जहाँ वे 12 व 10 हैं। n = 4 पर रखा प्रश्न प्रायः ठीक इसी कारण वहाँ रखा जाता है।

  8. 30 के भाजक-जालक (भाज्यता से क्रमित 30 के भाजक) में अवयवों की संख्या _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 8

    30 = 2 × 3 × 5, तीन भिन्न अभाज्य प्रत्येक पहली घात पर, अतः भाजक उन अभाज्यों का कोई भी उपसमुच्चय है: उनमें 2³ = 8 — 1, 2, 3, 5, 6, 10, 15, 30। वह तादात्म्य ही उपयोगी भाग है: k भिन्न अभाज्यों के गुणनफल का भाजक-जालक k अवयवों पर बूलीय जालक है, अतः D₃₀ के प्रश्न व 3-समुच्चय के घात-समुच्चय के प्रश्न का उत्तर, हास आरेख व ऊँचाई समान होती है। सामान्यतः n = p₁a₁···p_ka_k के भाजकों की संख्या (a₁ + 1)···(a_k + 1) है, जो यहाँ 8 और 12 = 2² × 3 हेतु 6 देती है। संख्यात्मक-उत्तर प्रश्न होने से इस पर ऋणात्मक अंकन नहीं, अतः इसे कभी रिक्त न छोड़ें।