Euclidean relation: Difference between revisions

# Due to the commutativity of ∧ in the definition's antecedent, ''aRb'' ∧ ''aRc'' even implies ''bRc'' ∧ ''cRb'' when ''R'' is right Euclidean. Similarly, ''bRa'' ∧ ''cRa'' implies ''bRc'' ∧ ''cRb'' when ''R'' is left Euclidean.

# The property of being Euclidean is different from [[transitive relation|transitivity]]. For example, ≤ is transitive, but not right Euclidean,<ref>e.g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1</ref> while ''xRy'' defined by 0 ≤ ''x'' ≤ ''y'' + 1 ≤ 2 is not transitive,<ref>e.g. 2''R''1 and 1''R''0, but not 2''R''0</ref> but right Euclidean on [[natural number]]s.

# A relation that is both right Euclidean and [[Reflexive relation|reflexive]] is also symmetric and therefore an [[equivalence relation]].<ref name="fagin"/><ref>''xRy'' and ''xRx'' implies ''yRx''.</ref> Similarly, each left Euclidean and reflexive relation is an equivalence.

# The [[Image (mathematics)#Generalization to binary relations|range]] of a right Euclidean relation is always a subset<ref>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.</ref> of its [[Image (mathematics)#Generalization to binary relations|domain]]. The [[Binary relation#Restriction|restriction]] of a right Euclidean relation to its range is always reflexive,<ref>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''.</ref> 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 on ''X'' that is also [[right total]] (respectively a left Euclidean relation on ''X'' that is also [[left total]]) is an equivalence, since its range (respectively its domain) is ''X''.<ref name="buck">{{citation|title=An Alternative Definition for Equivalence Relations|first=Charles|last=Buck|journal=The Mathematics Teacher|year=1967|volume=60|page=124-125|url=https://www.jstor.org/stable/27957510}}.</ref>