Right Euclidean property: solid and dashed arrows indicate antecedents and consequents, respectively.
Abinary relationR on asetX isEuclidean (sometimes calledright Euclidean) if it satisfies the following: for everya,b,c inX, ifa is related tob andc, thenb is related toc.[1] To write this inpredicate logic:
Dually, a relationR onX isleft Euclidean if for everya,b,c inX, ifb is related toa andc is related toa, thenb is related toc:
Schematized right Euclidean relation according to property 10. Deeply-colored squares indicate the equivalence classes ofR′. Pale-colored rectangles indicate possible relationships of elements inX\ran(R). In these rectangles, relationships may, or may not, hold.
Due to the commutativity of ∧ in the definition's antecedent,aRb ∧aRc even impliesbRc ∧cRb whenR is right Euclidean. Similarly,bRa ∧cRa impliesbRc ∧cRb whenR is left Euclidean.
The property of being Euclidean is different fromtransitivity. For example, ≤ is transitive, but not right Euclidean,[2] whilexRy defined by 0 ≤x ≤y + 1 ≤ 2 is not transitive,[3] but right Euclidean onnatural numbers.
Forsymmetric relations, transitivity, right Euclideanness, and left Euclideanness all coincide. However, a non-symmetric relation can also be both transitive and right Euclidean, for example,xRy defined byy=0.
A relation that is both right Euclidean andreflexive is also symmetric and therefore anequivalence relation.[1][4] Similarly, each left Euclidean and reflexive relation is an equivalence.
Therange of a right Euclidean relation is always a subset[5] of itsdomain. Therestriction of a right Euclidean relation to its range is always reflexive,[6] and therefore an equivalence. Similarly, the domain of a left Euclidean relation is a subset of its range, and the restriction of a left Euclidean relation to its domain is an equivalence. Therefore, a right Euclidean relation onX that is alsoright total (respectively a left Euclidean relation onX that is alsoleft total) is an equivalence, since its range (respectively its domain) isX.[7]
A relationR is both left and right Euclidean, if, and only if, the domain and the range set ofR agree, andR is an equivalence relation on that set.[8]
A right Euclidean relation is alwaysquasitransitive,[9] as is a left Euclidean relation.[10]
Aconnected right Euclidean relation is always transitive;[11] and so is a connected left Euclidean relation.[12]
IfX has at least 3 elements, a connected right Euclidean relationR onX cannot beantisymmetric,[13] and neither can a connected left Euclidean relation onX.[14] On the 2-element setX = { 0, 1 }, e.g. the relationxRy defined byy=1 is connected, right Euclidean, and antisymmetric, andxRy defined byx=1 is connected, left Euclidean, and antisymmetric.
A relationR on a setX is right Euclidean if, and only if, the restrictionR′ :=R|ran(R) is an equivalence and for eachx inX\ran(R), all elements to whichx is related underR are equivalent underR′.[15] Similarly,R onX is left Euclidean if, and only if,R′ :=R|dom(R) is an equivalence and for eachx inX\dom(R), all elements that are related tox underR are equivalent underR′.
A left Euclidean relation isleft-unique if, and only if, it isantisymmetric. Similarly, a right Euclidean relation is right unique if, and only if, it is anti-symmetric.
A left Euclidean and left unique relation is vacuously transitive, and so is a right Euclidean and right unique relation.
A left Euclidean relation is leftquasi-reflexive. For left-unique relations, the converse also holds. Dually, each right Euclidean relation is right quasi-reflexive, and each right unique and right quasi-reflexive relation is right Euclidean.[16]
^Equality of domain and range isn't necessary: the relationxRy defined byy=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.
^Ify is in the range ofR, thenxRy ∧xRy impliesyRy, for some suitablex. This also proves thaty is in the domain ofR.
^Theonly if direction follows from the previous paragraph. — For theif direction, assumeaRb andaRc, thena,b,c are members of the domain and range ofR, hencebRc by symmetry and transitivity; left Euclideanness ofR follows similarly.
^IfxRy ∧ ¬yRx ∧yRz ∧ ¬zRy holds, then bothy andz are in the range ofR. SinceR is an equivalence on that set,yRz implieszRy. Hence the antecedent of the quasi-transitivity definition formula cannot be satisfied.
^A similar argument applies, observing thatx,y are in the domain ofR.
^IfxRy ∧yRz holds, theny andz are in the range ofR. SinceR is connected,xRz orzRx orx=z holds. In case 1, nothing remains to be shown. In cases 2 and 3, alsox is in the range. Hence,xRz follows from the symmetry and reflexivity ofR on its range, respectively.
^SinceR is connected, at least two distinct elementsx,y are in itsrange, andxRy ∨yRx holds. SinceR is symmetric on its range, evenxRy ∧yRx holds. This contradicts the antisymmetry property.
^Only if:R′ is an equivalence as shown above. Ifx∈X\ran(R) andxR′y1 andxR′y2, theny1Ry2 by right Euclideaness, hencey1R′y2. —If: ifxRy ∧xRz holds, theny,z∈ran(R). In case alsox∈ran(R), evenxR′y ∧xR′z holds, henceyR′z by symmetry and transitivity ofR′, henceyRz. In casex∈X\ran(R), the elementsy andz must be equivalent underR′ by assumption, hence alsoyRz.
^Jochen Burghardt (Nov 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report).arXiv:1806.05036v2. Lemma 44-46.
