यूक्लिडियन संबंध

गणित में यूक्लिडियन संबंध, बाइनरी संबंधों का एक वर्ग है जो यूक्लिड के संख्याओ में "स्वत: सिद्ध 1" को निष्चित रूप देता है, कि वे परिमाण में समान और एक दूसरे के बराबर हैं।"

परिभाषा

राईट यूक्लिडियन गुण: ठोस और असतत रेखा क्रमशः पूर्ववर्ती और परिणाम दर्शाते हैं।

एक समुच्चय X पर एक बाइनरी संबंध R यूक्लिडियन है (कभी-कभी राईट यूक्लिडियन भी कहा जाता है) यदि यह निम्नलिखित को संतुष्ट करता है की X में प्रत्येक a, b, c के लिए, यदि a, b और c से संबंधित है और b, c से संबंधित है।^[1] तो इसे संकेत तर्क के रूप में लिखने पर:

\forall a,b,c\in X\,(a\,R\,b\land a\,R\,c\to b\,R\,c).

दुसरे तरह यदि X पर एक संबंध R, लेफ्ट यूक्लिडियन है, और X में प्रत्येक a, b, c के लिए, यदि b, a से संबंधित है और c, a से संबंधित है, तो b, c से संबंधित होगा :

\forall a,b,c\in X\,(b\,R\,a\land c\,R\,a\to b\,R\,c).

गुण

संपत्ति 10 के अनुसार योजनाबद्ध सही यूक्लिडियन संबंध। गहरे रंग के वर्ग आर के समतुल्य वर्गों का संकेत देते हैं′. हल्के रंग के आयत X\ran(R) में तत्वों के संभावित संबंधों का संकेत देते हैं। इन आयतों में संबंध हो भी सकते हैं और नहीं भी।

परिभाषा के पूर्व पद में ∧ क्रमविनिमेयता के कारण aRb ∧ aRc का तात्पर्य bRc ∧ cRb से भी है, जब R राइट यूक्लिडियन है, इसी प्रकार bRa ∧ cRa का तात्पर्य bRc ∧ cRb से है, जब R एक लेफ्ट यूक्लिडियन है।

यूक्लिडियन होने का गुण धनात्मक संबंध से भिन्न होता है। उदाहरण के लिए '≤' धनात्मक है, लेकिन राइट यूक्लिडियन नहीं है,^[2] जबकि xRy 0 ≤ x ≤ y + 1 ≤ 2 द्वारा परिभाषित संक्रामक नहीं है,^[3] लेकिन प्राकृतिक संख्याओ पर राइट यूक्लिडियन है।
सममित संबंधों के लिए धनात्मकता, राइट यूक्लिडियन और लेफ्ट यूक्लिडियन सभी के सामान होता हैं। जबकि एक असममित संबंध भी धनात्मक और राइट यूक्लिडियन दोनों हो सकता है, उदाहरण के लिए, xRy को y=0 द्वारा परिभाषित किया गया है।
एक संबंध जो राइट यूक्लिडियन, स्वतुल्य संबंध और सममित तीनो है, तो वह तुल्य संबंध भी होगा।^[1]^[4] इसी प्रकार से प्रत्येक लेफ्ट यूक्लिडियन और स्वतुल्य संबंध के बीच एक समानता होती है।
एक राइट यूक्लिडियन संबंध का परिसर इसके डोमेन के उपसमुच्चय होता है।^[5] अपनी परिसर के संबंध में राईट यूक्लिडियन का प्रतिबंध, स्वतुल्य संबंध होता है, और इसलिए इनमे एक समानता भी होता है।^[6] इसी तरह एक लेफ्ट यूक्लिडियन संबंध का डोमेन इसकी परिसर के उपसमुच्चय होता है, और एक लेफ्ट यूक्लिडियन संबंध का इसके डोमेन के लिए प्रतिबंध के बीच एक समानता होती है।
एक संबंध R लेफ्ट और राईट दोनों यूक्लिडियन है, यदि R का डोमेन और श्रेणी आपस में बराबर हैं तो R के उस समुच्चय के बीच तुल्यता संबंध होगा |^[7]
एक राईट यूक्लिडियन संबंध हमेशा लेफ्ट यूक्लिडियन संबंध की तरह अकर्मक होता है |^[8] ^[9]
एक संबंधित राईट यूक्लिडियन संबंध हमेशा धनात्मक होता है;^[10] और ऐसा ही एक संबंधित लेफ्ट यूक्लिडियन संबंध भी धनात्मक होता है|^[11]
यदि X में कम से कम 3 संख्याये है, तो X से सम्बंधित राईट यूक्लिडियन संबंध R, प्रतिसममित संबंध नहीं हो सकता है,^[12] और न ही X पर लेफ्ट यूक्लिडियन संबंध को जोड़ा जा सकता है।^[13] दो संख्याये समुच्चय X = {0, 1} में हैं, यदि उदा. संबंध xRy, y=1 द्वारा परिभाषित है, तो यह राईट यूक्लिडियन और असममित होगा | और यदि x=1 द्वारा परिभाषित xRy है, तो यह लेफ्ट यूक्लिडियन और असममित होगा ।
एक समुच्चय X पर एक संबंध R राईट यूक्लिडियन है, यदि प्रतिबंध R′ := R|_ran(R) के बीच एक समानता है, और X\ran(R) में प्रत्येक x के लिए वे सभी संख्या जिनसे x, R के साथ संबंधित है,वे सभी R के अंतर्गत समतुल्य होंगे′.^[14] इसी प्रकार X पर R लेफ्ट यूक्लिडियन है,तो R′ := R|dom(R) के बीच एक तुल्यता है और X\dom(R) में प्रत्येक x के लिए, R के अंतर्गत x से संबंधित सभी संख्या R′ के तुल्य हैं।
एक लेफ्ट यूक्लिडियन संबंध, लेफ्ट -अद्वितीय संबंध और साथ ही प्रतिसममित संबंध भी होते है। इसी तरह एक राईट यूक्लिडियन संबंध, राईट अद्वितीय और यह असममित सम्बन्ध भी होते है।
लेफ्ट यूक्लिडियन और लेफ्ट अद्वितीय संबंध रिक्त रूप से धनात्मक होते है, और ऐसा ही एक राईट यूक्लिडियन और राईट अद्वितीय संबंध भी रिक्त रूप से धनात्मक होते हैं |
एक लेफ्ट यूक्लिडियन संबंध लगभग प्रतिवर्ती होता है। लेफ्ट-अद्वितीय संबंधों के लिय यह बिपरीत होता है,और प्रत्येक राईट यूक्लिडियन संबंध राईट और लगभग स्वतुल्य है, और प्रत्येक राईट अद्वितीय और राईट अर्ध-स्वतुल्य संबंध राईट यूक्लिडियन है।^[15]

संदर्भ

↑ ^1.0 ^1.1 Fagin, Ronald (2003), Reasoning About Knowledge, MIT Press, p. 60, ISBN 978-0-262-56200-3.
↑ e.g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1
↑ e.g. 2R1 and 1R0, but not 2R0
↑ xRy and xRx implies yRx.
↑ Equality of domain and range isn't necessary: the relation xRy defined by y=min{x,2} is right Euclidean on the natural numbers, and its range, {0,1,2}, is a proper subset of its domain of the natural numbers.
↑ If y is in the range of R, then xRy ∧ xRy implies yRy, for some suitable x. This also proves that y is in the domain of R.
↑ The only if direction follows from the previous paragraph. — For the if direction, assume aRb and aRc, then a,b,c are members of the domain and range of R, hence bRc by symmetry and transitivity; left Euclideanness of R follows similarly.
↑ If xRy ∧ ¬yRx ∧ yRz ∧ ¬zRy holds, then both y and z are in the range of R. Since R is an equivalence on that set, yRz implies zRy. Hence the antecedent of the quasi-transitivity definition formula cannot be satisfied.
↑ A similar argument applies, observing that x,y are in the domain of R.
↑ If xRy ∧ yRz holds, then y and z are in the range of R. Since R is connected, xRz or zRx or x=z holds. In case 1, nothing remains to be shown. In cases 2 and 3, also x is in the range. Hence, xRz follows from the symmetry and reflexivity of R on its range, respectively.
↑ Similar, using that x, y are in the domain of R.
↑ Since R is connected, at least two distinct elements x,y are in its range, and xRy ∨ yRx holds. Since R is symmetric on its range, even xRy ∧ yRx holds. This contradicts the antisymmetry property.
↑ By a similar argument, using the domain of R.
↑ Only if: R′ is an equivalence as shown above. If x∈X\ran(R) and xR′y₁ and xR′y₂, then y₁Ry₂ by right Euclideaness, hence y₁R′y₂. — If: if xRy ∧ xRz holds, then y,z∈ran(R). In case also x∈ran(R), even xR′y ∧ xR′z holds, hence yR′z by symmetry and transitivity of R′, hence yRz. In case x∈X\ran(R), the elements y and z must be equivalent under R′ by assumption, hence also yRz.
↑ Jochen Burghardt (Nov 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036v2. Lemma 44-46.

[fagin-1] 1.0 ^1.1 Fagin, Ronald (2003), Reasoning About Knowledge, MIT Press, p. 60, ISBN 978-0-262-56200-3.

[2] .g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1

[3] .g. 2R1 and 1R0, but not 2R0

[4] xRy and xRx implies yRx.

[5] Equality of domain and range isn't necessary: the relation xRy defined by y=min{x,2} is right Euclidean on the natural numbers, and its range, {0,1,2}, is a proper subset of its domain of the natural numbers.

[6] If y is in the range of R, then xRy ∧ xRy implies yRy, for some suitable x. This also proves that y is in the domain of R.

[7] The only if direction follows from the previous paragraph. — For the if direction, assume aRb and aRc, then a,b,c are members of the domain and range of R, hence bRc by symmetry and transitivity; left Euclideanness of R follows similarly.

[8] If xRy ∧ ¬yRx ∧ yRz ∧ ¬zRy holds, then both y and z are in the range of R. Since R is an equivalence on that set, yRz implies zRy. Hence the antecedent of the quasi-transitivity definition formula cannot be satisfied.

[9] A similar argument applies, observing that x,y are in the domain of R.

[10] If xRy ∧ yRz holds, then y and z are in the range of R. Since R is connected, xRz or zRx or x=z holds. In case 1, nothing remains to be shown. In cases 2 and 3, also x is in the range. Hence, xRz follows from the symmetry and reflexivity of R on its range, respectively.

[11] Similar, using that x, y are in the domain of R.

[12] Since R is connected, at least two distinct elements x,y are in its range, and xRy ∨ yRx holds. Since R is symmetric on its range, even xRy ∧ yRx holds. This contradicts the antisymmetry property.

[13] By a similar argument, using the domain of R.

[14] Only if: R′ is an equivalence as shown above. If x∈X\ran(R) and xR′y₁ and xR′y₂, then y₁Ry₂ by right Euclideaness, hence y₁R′y₂. — If: if xRy ∧ xRz holds, then y,z∈ran(R). In case also x∈ran(R), even xR′y ∧ xR′z holds, hence yR′z by symmetry and transitivity of R′, hence yRz. In case x∈X\ran(R), the elements y and z must be equivalent under R′ by assumption, hence also yRz.

[15] Jochen Burghardt (Nov 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036v2. Lemma 44-46.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

यूक्लिडियन संबंध

परिभाषा

गुण

संदर्भ

Navigation menu

Search