Euclidean relation

The following applies to a right Euclidean relation : provided that a has the same relationship to b and a to c (solid arrows), then also b to c (dashed arrow)

A Euclidean relation is a binary relation in mathematics , for which Euclid's axiom "What is the same is also the same" applies.

definition

A binary relation R on an amount X is called Euclidean (or right-Euclidean ) when for any items a , b , c in X , the following condition is satisfied: is a to b , and a to c , as it is in the same relationship also b to c in this regard. This can also be expressed in terms of predicate logic with . ${\ displaystyle \ forall a, b, c \ in X (aRb \ land aRc \ implies bRc)}$

A relation R on X is called left-Euclidean if for any a , b , c in X : if both b and c are related to a , then b is also related to c , formally . ${\ displaystyle \ forall a, b, c \ in X (bRa \ land cRa \ implies bRc)}$

properties

The following applies to transitivity : provided that a is related to b and b to c , then also a to c

The property of being Euclidean is different from transitivity . For example, the relation ≤ on the natural numbers is transitive, but not right-Euclidean, while the relation defined by on the natural numbers is not transitive, but right-Euclidean. ${\ displaystyle xRy: \ Leftrightarrow 0 \ leq x \ leq y + 1 \ leq 2}$ ${\ displaystyle R}$

For a symmetrical relation the properties transitivity, right and left Euclidean coincide. But a non-symmetric relation can also be transitive as well as right-Euclidean, e.g. B. xRy defined by y = 0.

A relation that is both right-Euclidean and reflexive is necessarily also symmetrical and therefore an equivalence relation . Likewise, every left-Euclidean and reflexive relation is necessarily an equivalence.

The image area of a right Euclidean relation is always a subset of its original image area . The restriction of a right-Euclidean relation to its image area is always reflexive and therefore an equivalence relation. Likewise, the archetype of a left-Euclidean relation is always a subset of its image domain, and the restriction of a left-Euclidean relation to its archetype is an equivalence.

A relation R is left and right Euclidean if and only if its archetype and its image area coincide and R is an equivalence relation on this set.

A right-Euclidean relation is always quasitransitive , as is a left-Euclidean relation.

A connex right Euclidean relation is always also transitive, as is a connex left Euclidean relation.

When X has at least 3 elements connected forms a right-Euclidean relation can R on X is not antisymmetric be, the same applies to a left-connected forms Euclidean relation on X . On the two-element set X = {0, 1} z. B. the relation defined by connex, right-Euclidean and antisymmetric; is connected, left-Euclidean and antisymmetric on this set. ${\ displaystyle xRy: \ Leftrightarrow y = 1}$ ${\ displaystyle xRy: \ Leftrightarrow x = 1}$

References and comments

↑ The book I of the elements of Euclid contains an axiomatic foundation in which this principle is listed as the 1st axiom of general rules of equality ( "Τὰ τῷ αὐτῷ ἴσα καὶ ἀλλήλοις ἐστὶν ἴσα" ); see W.-D. Geyer: Euclid: The elements - an overview. Lecture on ancient mathematics, SS 2001, p. 3 (PDF; 275 kB).

^ ^A ^b Ronald Fagin: Reasoning About Knowledge . MIT Press, 2003, ISBN 978-0-262-56200-3 , pp. 60 (English, limited preview in Google Book Search).

↑ Since z. B. 0 2 and 0 gilt 1, but not 2 1.

↑ Since z. B. 2 R 1 and 1 R 0 applies, but not 2 R 0.

↑ Because from xRy and xRx follows yRx .

↑ Equality of archetype and image area is not necessary: the relation xRy defined by y = min { x , 2} is right-Euclidean on the natural numbers and its image area {0,1,2} is a real subset of its archetype area ℕ .

↑ If y lies in the image area of R , then xRy ∧ xRy for a suitable x implies that yRy . This also shows that y lies in the archetype of R.

↑ The " " direction follows from the previous paragraph. - For the " " direction, assume that aRb and aRc hold, then a , b , c lie in the archetype and in the image area of R ; thus bRc follows because of symmetry and transitivity. The left Euclidean property of R follows analogously. ${\ displaystyle \ Rightarrow}$ ${\ displaystyle \ Leftarrow}$

↑ If xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy holds, are both y and z in the image region of R . Since R is an equivalence on this set, it follows from yRz already the contradiction zRy .

↑ ^a ^b ^c with an analogous argument, the location of x and y in the range of archetype R used.

↑ If xRy ∧ yRz holds, then are y and z in the image region of R . Since R is connected, xRz or zRx or x = z applies .

↑ Since R is connected, there are at least two different elements x and y in its image area , for which xRy ∨ yRx applies . It even holds that xRy ∧ yRx . This contradicts the antisymmetry.

[1] The book I of the elements of Euclid contains an axiomatic foundation in which this principle is listed as the 1st axiom of general rules of equality ( "Τὰ τῷ αὐτῷ ἴσα καὶ ἀλλήλοις ἐστὶν ἴσα" ); see W.-D. Geyer: Euclid: The elements - an overview. Lecture on ancient mathematics, SS 2001, p. 3 (PDF; 275 kB).

[fagin-2] A ^b Ronald Fagin: Reasoning About Knowledge . MIT Press, 2003, ISBN 978-0-262-56200-3 , pp. 60 (English, limited preview in Google Book Search).

[3] Since z. B. 0 2 and 0 gilt 1, but not 2 1.

[4] Since z. B. 2 R 1 and 1 R 0 applies, but not 2 R 0.

[5] Because from xRy and xRx follows yRx .

[6] Equality of archetype and image area is not necessary: the relation xRy defined by y = min { x , 2} is right-Euclidean on the natural numbers and its image area {0,1,2} is a real subset of its archetype area ℕ .