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

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

$$(\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 फ़ंक्शन जो किसी ऑब्जेक्ट को असाइन करता है F(x, g) किसी तत्व के प्रत्येक जोड़े के लिए x ∈ X और समारोह g प्रारंभिक खंड पर {y: y R x} का X. फिर अनूठा कार्य है G ऐसा है कि हर के लिए x ∈ X,

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

अर्थात यदि हम फंक्शन बनाना चाहते हैं G पर X, हम परिभाषित कर सकते हैं G(x) के मूल्यों का उपयोग करना G(y) के लिए y R 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.
• समुच्चय {{math|N × N}प्राकृतिक संख्याओं के कार्टेशियन उत्पाद का }, द्वारा आदेश दिया गया (n₁, n₂) < (m₁, m₂) यदि और केवल यदि 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 ≥ .... इन तुच्छ अवरोही अनुक्रमों से बचने के लिए, आंशिक क्रम ≤ के साथ काम करते समय, अच्छी तरह से नींव की परिभाषा (शायद निहित रूप से) को वैकल्पिक संबंध < परिभाषित करने के लिए लागू करना आम है 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