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

"Noetherian induction" redirects here. For the use in topology, see Noetherian topological space.

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