सुस्थापित संबंध

"नोथेरियन प्रेरण" redirects here. For सांस्थिति में उपयोग, see नोथेरियन संस्थानिक स्थान.

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 पर सुस्थापित संबंध (या उचित प्रकार से स्थापित या मूलभूत) कहा जाता है यदि प्रत्येक अरिक्त उपसमुच्चय S ⊆ X में R के संबंध में न्यूनतम अवयव है, अर्थात अवयव m ∈ S किसी भी s ∈ S के लिए s R m से संबंधित नहीं है (उदाहरण के लिए, s, m से छोटा नहीं है)। किसी दूसरे शब्दों में, संबंध उचित प्रकार से स्थापित होता है यदि,

$$(\forall S\subseteq X)\;[S\neq \varnothing \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)]$$

कुछ लेखकों ने अतिरिक्त नियम सम्मिलित किया है कि R समुच्चय के जैसा है। अर्थात किसी दिए गए अवयव से अल्प अवयव समुच्चय बनाते हैं।

समतुल्य रूप से, निर्भर रूचि के स्वयंसिद्ध को मानते हुए, संबंध उचित प्रकार से स्थापित होता है, जब इसमें कोई अनंत अवरोही श्रृंखला नहीं होती है, जिसे सिद्ध किया जा सकता है जब X के अवयवों में कोई अनंत अनुक्रम x₀, x₁, x₂, ... नहीं होता है जैसे कि x_n+1 R x_n प्रत्येक प्राकृतिक संख्या n के लिए है।

आदेश सिद्धांत में, आंशिक आदेश को उचित प्रकार से स्थापित कहा जाता है, यदि संबंधित स्ट्रीक्ट आदेश उचित प्रकार से स्थापित संबंध है। यदि आदेश कुल आदेश है तो इसे उत्तम-व्यवस्था कहा जाता है।

समुच्चय सिद्धांत में, समुच्चय x को उचित प्रकार से स्थापित समुच्चय कहा जाता है, यदि समुच्चय संबंध x के सकर्मक संवृत होने पर उचित प्रकार से स्थापित होता है। नियमितता का स्वयंसिद्ध, जो ज़र्मेलो-फ्रेंकेल समुच्चय सिद्धांत के स्वयंसिद्धों में से है, यह प्रमाणित करता है कि सभी समुच्चय उचित प्रकार से स्थापित हैं।

संबंध R, X पर विपरीत उचित प्रकार से स्थापित, ऊपर की ओर उचित प्रकार से स्थापित या नोथेरियन है, यदि विपरीत संबंध R⁻¹X पर उचित प्रकार से स्थापित है। इस स्थिति में R को आरोही श्रृंखला की स्थिति को पूर्ण करने के लिए भी कहा जाता है। पुनर्लेखन प्रणालियों के संदर्भ में, नोथेरियन संबंध को समापन भी कहा जाता है।

प्रेरण और प्रत्यावर्तन

महत्वपूर्ण कारण है कि उचित प्रकार से स्थापित संबंध रोचक हैं क्योंकि उन पर ट्रांसफिनिट प्रेरण का संस्करण उपयोग किया जा सकता है: यदि (X, R) सुस्थापित संबंध है, P(x) X के अवयवों की कुछ संपत्ति है, और हम उसे दिखाना चाहते हैं,

P(x) X के सभी अवयवों x के लिए है,

यह दर्शाने के लिए पर्याप्त है कि:

यदि x, X का अवयव है और P(y) सभी y के लिए सत्य है, जैसे कि y R x, तब P(x) भी सत्य होना चाहिए।

वह है,

$$(\forall x\in X)\;[(\forall y\in X)\;[y\mathrel {R} x\implies P(y)]\implies P(x)]\quad {\text{implies}}\quad (\forall x\in X)\,P(x).$$

उचित प्रकार से स्थापित प्रेरण को एमी नोथेर के पश्चात कभी-कभी नोथेरियन प्रेरण कहा जाता है।

प्रेरण के साथ-साथ, उचित प्रकार से स्थापित संबंध भी ट्रांसफिनिट प्रत्यावर्तन द्वारा वस्तुओं के निर्माण का समर्थन करते हैं। मान लीजिये (X, R) समुच्चय-जैसे उचित प्रकार से स्थापित संबंध और F फलन है जो प्रारंभिक खंड {y: y R x} पर अवयव x ∈ X और फलन g के प्रत्येक जोड़े के लिए ऑब्जेक्ट F(x, g) असाइन करता है। तब अद्वितीय फलन G ऐसा होता है कि प्रत्येक x ∈ X के लिए होता है।

$$G(x)=F\left(x,G\vert _{\left\{y:\,y\mathrel {R} x\right\}}\right)$$

अर्थात यदि हम X पर फलन G बनाना चाहते हैं, तो हम y R x के लिए G(y) के मानों का उपयोग करके G(x) को परिभाषित कर सकते हैं।

उदाहरण के रूप में, सुस्थापित संबंध (N, S) पर विचार करें, जहां N सभी प्राकृतिक संख्याओं का समुच्चय है, और S उत्तराधिकारी फलन x ↦ x+1 का आरेख है, तब S पर प्रेरण सामान्य गणितीय प्रेरण है, और S पर पुनरावर्तन प्रिमिटिव पुनरावर्ती देता है। यदि हम क्रम संबंध (N, <) पर विचार करते हैं, तो हम पूर्ण प्रेरण और पाठ्यक्रम-की-मूल्य पुनरावर्तन प्राप्त करते हैं। यह कथन कि (N, <) उचित प्रकार से स्थापित है को सुव्यवस्थित सिद्धांत के रूप में भी जाना जाता है।

उचित प्रकार से स्थापित प्रेरण के अन्य रोचक विशेष स्थिति हैं। जब उचित प्रकार से स्थापित संबंध सभी क्रमिक संख्याओं के वर्ग पर सामान्य क्रम होता है, तो प्रौद्योगिकी को ट्रांसफ़ाइन प्रेरण कहा जाता है। जब उचित प्रकार से स्थापित समुच्चय पुनरावर्ती-परिभाषित डेटा संरचनाओं का समुच्चय होता है, तो प्रौद्योगिकी को संरचनात्मक प्रेरण कहा जाता है। जब उचित प्रकार से स्थापित संबंध सार्वभौमिक वर्ग पर सदस्यता स्थापित करता है, तो प्रौद्योगिकी को ∈-प्रेरण के रूप में जाना जाता है। अधिक विवरण के लिए उन लेखों को देखें।

उदाहरण

उचित प्रकार से स्थापित संबंध जो पूर्ण प्रकार से आदेशित नहीं हैं उनमें सम्मिलित हैं:

• सकारात्मक पूर्णांक {1, 2, 3, ...}, a < b द्वारा परिभाषित क्रम के साथ यदि और केवल a b और a ≠ b को विभाजित करता है।
• निश्चित वर्णमाला पर सभी परिमित स्ट्रिंग का समुच्चय s < t द्वारा परिभाषित क्रम के साथ यदि और केवल s, t का उचित सबस्ट्रिंग है।
• (n₁, n₂) < (m₁, m₂) द्वारा क्रमित प्राकृतिक संख्याओं के जोड़े का समुच्चय N × N यदि और केवल n₁ < m₁ और n₂ < m₂ है।
• प्रत्येक वर्ग जिसके अवयव समुच्चय हैं, संबंध ∈ (का अवयव है) के साथ है। यह नियमितता का स्वयंसिद्ध है।
• संबंध R के साथ किसी भी परिमित निर्देशित एसाइक्लिक आरेख के नोड्स को इस प्रकार परिभाषित किया गया है कि a R b यदि और केवल a से b तक कोई किनारा है।

संबंधों के उदाहरण जो उचित प्रकार से स्थापित नहीं हैं उनमें सम्मिलित हैं:

• ऋणात्मक पूर्णांक {−1, −2, −3, ...}, सामान्य क्रम के साथ, चूंकि किसी भी असीमित उपसमुच्चय में अल्प से अल्प अवयव नहीं होता है।
• अनुक्रम "B" > "AB" > "AAB" > "AAAB" > ... के पश्चात से सामान्य (लेक्सिकोग्राफिक) क्रम के अनुसार एक से अधिक अवयवों के साथ परिमित वर्णमाला पर स्ट्रिंग्स का समुच्चय अनंत अवरोही श्रृंखला है। यह संबंध उचित प्रकार से स्थापित होने में विफल रहता है, पूर्ण समुच्चय में न्यूनतम अवयव होता है, अर्थात् रिक्त स्ट्रिंग होता है।
• मानक क्रम के अनुसार गैर-नकारात्मक परिमेय संख्याओं (या वास्तविक संख्याओं) का समुच्चय, उदाहरण के लिए, सकारात्मक परिमेय (या वास्तविक) के उपसमुच्चय में न्यूनतम की अल्पता होती है।

अन्य गुण

यदि (X, <) उचित प्रकार से स्थापित संबंध है और x का अवयव X है, तो x से प्रारंभ होने वाली अवरोही श्रृंखला सभी परिमित हैं, किन्तु इसका तात्पर्य यह नहीं है कि उनकी लंबाई आवश्यक रूप से परिमित है। निम्नलिखित उदाहरण पर विचार करें: मान लीजिए कि X नए अवयव ω के साथ धनात्मक पूर्णांकों का समूह है जो किसी भी पूर्णांक से बड़ा है। तब X उचित प्रकार से स्थापित समुच्चय है, किन्तु इच्छानुसार रूप से महान (परिमित) लंबाई के ω से प्रारंभ होने वाली अवरोही श्रृंखलाएं हैं; शृंखला ω, n − 1, n − 2, ..., 2, 1 की लंबाई n किसी भी n के लिए है।

मोस्टोव्स्की पतन लेम्मा का अर्थ है कि समुच्चय सदस्यता विस्तारित सुस्थापित संबंधों के मध्य सार्वभौमिक है: किसी भी समुच्चय-जैसे उचित प्रकार से स्थापित संबंध R के लिए वर्ग X पर जो कि विस्तारित है, वहां वर्ग C उपस्थित है जैसे कि (X, R) के लिए आइसोमोर्फिक (C, ∈) है।

प्रतिवर्तनीयता

संबंध R को प्रतिवर्त संबंध कहा जाता है, यदि a R a संबंध के क्षेत्र में प्रत्येक a के लिए धारण करता है। अरिक्त डोमेन पर प्रत्येक प्रतिवर्त संबंध में अनंत अवरोही श्रृंखलाएं होती हैं, क्योंकि कोई निरंतर अनुक्रम अवरोही श्रृंखला है। उदाहरण के लिए, उनके सामान्य क्रम ≤ के साथ प्राकृतिक संख्याओं में, हमारे निकट 1 ≥ 1 ≥ 1 ≥ .... है I इन अल्प अवरोही अनुक्रमों से सुरक्षित होने के लिए, आंशिक क्रम ≤ के साथ कार्य करते समय, उचित प्रकार से आधार की परिभाषा को प्रस्तावित करना सामान्य है (संभवतः निहित रूप से) वैकल्पिक संबंध < के लिए इस प्रकार परिभाषित किया गया है कि a < b यदि और केवल a ≤ b और a ≠ b होते है। सामान्यतः, जब पूर्व आदेश ≤ के साथ कार्य करते हैं, तो संबंध < परिभाषित का उपयोग करना सामान्य है, a < b यदि और केवल a ≤ b और b ≰ a होते है। प्राकृतिक संख्याओं के संदर्भ में, इसका अर्थ है कि संबंध <, जो उचित प्रकार से स्थापित है, संबंध ≤ के अतिरिक्त प्रयोग किया जाता है, जो नहीं है। कुछ लेखों में, इन फलन को सम्मिलित करने के लिए उपरोक्त परिभाषा उचित प्रकार से स्थापित संबंध की परिभाषा में परिवर्तित कर दी गई है।

संदर्भ

• Just, Winfried and Weese, Martin (1998) Discovering Modern Set Theory. I, American Mathematical Society ISBN 0-8218-0266-6.
• Karel Hrbáček & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, "Well-founded relations", pages 251–5, Marcel Dekker ISBN 0-8247-7915-0