✖

क्रम संबंध

क्रम संबंध, समुच्चय पर ऐसा द्विआधारी संबंध है, जो स्वतुल्य, प्रतिसममित और संक्रामक हो।

प्रेरणा

क्रम एक सामान्य अवधारणा है, जिससे हम रोज़मर्रा के जीवन में भी काम लेते हैं। बहुत-सी चीज़ों को किसी न किसी तरह क्रम में रखा जा सकता है — शब्दों को वर्णमाला के अनुसार, विद्यालय में विद्यार्थियों को लंबाई के अनुसार, सामान को कीमत के अनुसार। इन सबका वर्णन क्रम संबंध करता है, जिसे सामान्यतः चिह्न ≤ से दर्शाते हैं। संबंधित चिह्न हैं: <, >, ≥। इनका अर्थ स्पष्ट है।

ऐसे संबंध से हम क्या अपेक्षा रखेंगे? चिह्न से ही स्पष्ट है कि क्रम संबंध में समान अवयव भी होंगे — अर्थात् हमें संबंध “से कम या बराबर है” के गुण परिभाषित करने हैं। इसलिए ऐसा संबंध स्वतुल्य होना चाहिए। a ≤ a सत्य होना चाहिए।

आगे क्या? सममिति निश्चित रूप से सत्य नहीं होगी — यदि कीमत के अनुसार क्रम हो और कार रोटी से सस्ती हो, तो निश्चित रूप से रोटी साथ ही कार से सस्ती नहीं होगी। व्यापक रूप से हम क्या अपेक्षा करेंगे, यदि ऐसा हो कि a ≤ b और साथ ही b ≤ a? क्या इसका कभी कोई अर्थ होगा? हाँ, यदि a = b हो। संबंध में रखे गए अवयवों का क्रम केवल तब महत्वहीन है, जब वे अवयव समान हों — अतः क्रम संबंध प्रतिसममित है।

अंत में, यदि हम जानते हैं कि कार रोटी से महँगी है और हवाई जहाज़ कार से भी महँगा है, तो हम अपेक्षा करते हैं कि हवाई जहाज़ निश्चित रूप से रोटी से महँगा होगा। इसका वर्णन संक्रामकता करती है।

आंशिक क्रम

अभी हमने जो परिभाषित किया, वह वास्तव में केवल आंशिक क्रम है, पूर्ण क्रम नहीं। पूर्ण क्यों नहीं? आइए, समुच्चयों पर क्रम परिभाषित करें। दो समुच्चयों की तुलना हम किस तरह कर सकते हैं?

हम कहेंगे कि समुच्चय A, समुच्चय B से कम या बराबर है, यदि A ⊆ B, अर्थात् यदि A, B का उपसमुच्चय है। इसका अर्थ बनता है, क्योंकि यदि A = {1, 2} और B = {1, 2, 3} हों, तो A के बारे में हम कह सकते हैं कि वह छोटा है — B में वही अवयव हैं, जो A में, और इसके अलावा संख्या तीन भी है। अतः, उदाहरण के लिए, ये सत्य होंगे:

  • {a, c} ≤ {a, b, c, d}
  • ∅ ≤ {5, n, x}
  • {x, e, s} ≤ {x, e, s}

कठिनाई तब होती है, जब हम इन समुच्चयों की तुलना करना चाहें: A = {a, b} और B = {a, c}। इनमें से कौन छोटा है या बड़ा? कठिनाई यह है कि दोनों समुच्चयों में अवयव a तो है, पर दूसरा अवयव अलग-अलग है। कोई भी समुच्चय दूसरे का उपसमुच्चय नहीं है, इसलिए न A ≤ B सत्य है, न B ≤ A। हमारे क्रम के अनुसार ऐसे समुच्चय अतुलनीय हैं।

इसलिए हम पूर्णतः क्रमित समुच्चय, जिसे शृंखला (chain) भी कहते हैं, उस समुच्चय को कहते हैं, जिसके कोई भी दो अवयव तुलनीय हों। ऐसे समुच्चय हैं, उदाहरण के लिए, सामान्य क्रम वाले संख्या समुच्चय। किन्हीं भी दो वास्तविक संख्याओं a, b के लिए आप तय कर सकते हैं कि a ≤ b है या b ≤ a।

जीवन से उदाहरण

तुलना न करना जहाँ बेहतर हो, उसका एक उदाहरण सुंदरता के अनुसार क्रम हो सकता है। तब संबंध < का अर्थ होगा “कम सुंदर होना”। शायद हमें इसे उलटे ढंग से परिभाषित करना चाहिए, > को “अधिक सुंदर होना” मानकर, ताकि हम अधिक शिष्ट रहें :-)। दो महिलाओं की आपस में तुलना करने का शायद अर्थ है, जैसे “नेहा” < “प्रिया”, इस अर्थ में कि प्रिया, नेहा से अधिक सुंदर है। या दो पुरुषों की: “रोहन” < “अमित”, इस अर्थ में कि अमित, रोहन से अधिक सुंदर है।

समस्या यह है कि किसी पुरुष और किसी महिला की सुंदरता की तुलना शायद ही की जा सकती है। प्रिया अधिक सुंदर है या अमित? नेहा कम सुंदर है या रोहन? इसकी जाँच न करना ही बेहतर है…

यदि अंतिम उदाहरण में हम स्वयं को, उदाहरण के लिए, केवल महिलाओं तक सीमित रखें, तो कह सकते हैं कि हमारे पास पूर्णतः क्रमित समुच्चय है, क्योंकि हम सभी महिलाओं की सुंदरता की तुलना कर सकते हैं।

न्यूनतमी और अधिकतमी अवयव, न्यूनतम और अधिकतम अवयव

यदि क्रमित समुच्चय M दिया हो, तो अवयव min ∈ M को न्यूनतमी (minimal) कहते हैं, यदि ऐसा कोई x ∈ M न हो कि x < min। अर्थात् हम ऐसा कोई अवयव नहीं ढूँढ सकते, जो अवयव min से कम हो।

अवयव max ∈ M को अधिकतमी (maximal) कहते हैं, यदि ऐसा कोई x ∈ M न हो कि x > max। अर्थात् हम ऐसा कोई अवयव नहीं ढूँढ सकते, जो इससे बड़ा हो।

ये दोनों अवधारणाएँ न्यूनतम और अधिकतम अवयव की अवधारणाओं से भिन्न हैं।

अवयव a ∈ M को न्यूनतम (least) कहते हैं, यदि सभी x ∈ M के लिए a ≤ x हो। अर्थात् न्यूनतम अवयव a, समुच्चय M के अन्य सभी अवयवों से कम या बराबर है।

अवयव b ∈ M को अधिकतम (greatest) कहते हैं, यदि सभी x ∈ M के लिए b ≥ x हो। अधिकतम अवयव b, समुच्चय M के अन्य सभी अवयवों से बड़ा या बराबर है।

अधिकतम अवयव और अधिकतमी अवयव में क्या अंतर है? अधिकतमी अवयव एक से अधिक हो सकते हैं, क्योंकि समुच्चय का पूर्णतः क्रमित होना आवश्यक नहीं है। यदि हम रूप के आधार पर लोगों की तुलना वाले उदाहरण पर लौटें, तो कह सकते हैं कि काव्या सबसे सुंदर महिला है और अर्जुन सबसे सुंदर पुरुष है। पर इन दोनों व्यक्तियों की आपस में तुलना हम नहीं कर सकते, हम नहीं जानते कि काव्या अधिक सुंदर है या अर्जुन।

अतः दोनों अवयव अधिकतमी हैं। हम ऐसा कोई व्यक्ति नहीं ढूँढ सकते, जो अर्जुन से अधिक सुंदर हो — अर्जुन अन्य सभी पुरुषों से अधिक सुंदर है और महिलाओं से उसकी तुलना हम नहीं कर सकते। काव्या के साथ भी ऐसा ही है — वह सभी महिलाओं से अधिक सुंदर है और पुरुषों से उसकी तुलना हम नहीं कर सकते।

पर इनमें से कोई भी अधिकतम, इस अर्थ में सबसे सुंदर, नहीं है। क्योंकि अर्जुन को सबसे सुंदर/अधिकतम होने के लिए सभी व्यक्तियों से अधिक सुंदर होना पड़ता, सभी महिलाओं सहित। पर हम कह चुके हैं कि महिलाओं से उसकी तुलना हम नहीं कर सकते, इसलिए वह सबसे सुंदर व्यक्ति नहीं हो सकता। क्रम सिद्धांत की शब्दावली में वह केवल अधिकतमी है।

शायद आसानी से दिखता है कि यदि समुच्चय में अधिकतम अवयव है, तो वह अवयव साथ ही अधिकतमी भी है। यदि अवयव a समुच्चय के अन्य सभी अवयवों से बड़ा है (अधिकतम अवयव की परिभाषा), तो निश्चित रूप से हमें इससे भी बड़ा कोई अवयव नहीं मिलेगा (अधिकतमी अवयव की परिभाषा)।

अधिकतम और न्यूनतम अवयव वाले समुच्चय का एक उदाहरण संवृत अंतराल [0, 1] है। यदि हम वही अंतराल विवृत लें, तो उसमें न अधिकतम अवयव होगा, न न्यूनतम: (0, 1)।

यदि हमें अपरिमित रूप से अनेक न्यूनतमी अवयव चाहिए हों, तो हम क्रम R इस प्रकार परिभाषित कर सकते हैं। पहले सहायक समुच्चय Mx परिभाषित करते हैं। इन समुच्चयों का रूप यह होगा: अंतराल (0, 1) के सभी x के लिए समुच्चय Mx = {y | y = x + n} परिभाषित करते हैं, जहाँ n कोई ऋणेतर पूर्णांक है। इससे हमें, उदाहरण के लिए, ऐसे समुच्चय मिलते हैं:

M0,5={0.5;1.5;2.5;3.5;…}M0,7={0.7;1.7;2.7;3.7;…}M0,8={0.8;1.8;2.8;3.8;…}

प्रत्येक समुच्चय Mx पर हम सामान्य क्रम परिभाषित करते हैं, जिसे Rx से दर्शाते हैं। अंत में हम बस इन क्रमों का सम्मिलन लेते हैं: R = ∪ Rx। इस क्रम में हम हमेशा केवल पहले बनाई गई शृंखलाओं के भीतर ही तुलना कर सकते हैं। अतः हम पता कर सकते हैं कि 0.5 ≤ 2.5 है या नहीं, पर यह पता नहीं कर सकते कि 0.5 ≤ 2.7 है या नहीं, क्योंकि ये संख्याएँ एक ही समुच्चय Mx में नहीं थीं और इसलिए उनका संबंध परिभाषित नहीं है।

इस क्रम संबंध में अंतराल (0, 1) का प्रत्येक अवयव न्यूनतमी अवयव है।

हासे आरेख

क्रमित समुच्चयों को हासे आरेख से चित्रित किया जा सकता है। यह एक ग्राफ़ है, जिसमें शीर्ष समुच्चय के अवयवों को दर्शाते हैं और शीर्षों (a, b) के बीच किनारा बताता है कि a < b और साथ ही ऐसा कोई c नहीं है कि a < c < b। अर्थात् अवयवों a और b के बीच कोई और अवयव नहीं है। साथ ही ग्राफ़ में शीर्ष a, शीर्ष b से नीचे होना चाहिए। हासे आरेख का उदाहरण:

हासे आरेख

यह हासे आरेख क्रमित समुच्चय {A, B, C, D, E, F} को दर्शाता है। इसमें: A < B, B < E, और निश्चित रूप से A < E भी, पर इन शीर्षों के बीच कोई किनारा नहीं है, क्योंकि शीर्ष B ऐसा है कि A < B < E। अवयव E और D अतुलनीय हैं, क्योंकि कोई भी दूसरे के ऊपर या नीचे नहीं है।

यद्यपि हासे आरेख सामान्यतः इसी तरह सुंदर ढंग से संरेखित बनाए जाते हैं, यह बिलकुल आवश्यक नहीं है। पिछला हासे आरेख ऐसा भी दिख सकता है:

असुंदर हासे आरेख

एक और उदाहरण यह समुच्चय है: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}। ये संख्या 60 के प्राकृत भाजक हैं। विभाज्यता के अनुसार क्रम इस प्रकार दिखाया जा सकता है:

विभाज्यता के अनुसार क्रमित समुच्चय

विभाज्यता के अनुसार क्रम का अर्थ है कि (a, b) ∈ R यदि और केवल यदि a, b को विभाजित करता है। आरेख में देखा जा सकता है कि प्रत्येक संख्या के ऊपर वे संख्याएँ हैं, जिन्हें वह विभाजित करती है। उदाहरण के लिए, संख्या 6 के ऊपर संख्याएँ 12, 30 और 60 हैं। संख्या 4 के ऊपर संख्याएँ 12, 20 और 60 हैं। आदि। इसके विपरीत, संख्या 3 के ऊपर संख्या 10 नहीं है, क्योंकि तीन उसे विभाजित नहीं करती — ध्यान दीजिए, चित्र में संख्या 10 संख्या 3 से ऊपर है, पर उस तक “नीचे से ऊपर” कोई रेखा नहीं जाती। यदि हम संख्या 3 से केवल ऊपर की ओर चलें, तो संख्याओं 15 और 6 तक जा सकते हैं और उनसे संख्या 30 तक। संख्या 10 तक हम केवल नीचे उतरकर पहुँच सकते, जो वर्जित है।

विषय-सूची: संबंध, संबंधों पर संक्रियाएँ, द्विआधारी संबंध, समुच्चय पर द्विआधारी संबंध, तुल्यता संबंध, क्रम संबंध, जालक