Euclidean relation


In mathematics, Euclidean relations are a class of binary relations that formalizes ":wikisource:Page:First_six_books_of_the_elements_of_Euclid_1847_Byrne.djvu/26|Axiom 1" in Euclid's Elements: "Magnitudes which are equal to the same are equal to each other."

Definition

A binary relation R on a set X is Euclidean if it satisfies the following: for every a, b, c in X, if a is related to b and c, then b is related to c. To write this in predicate logic:
Dually, a relation R on X is left Euclidean if for every a, b, c in X, if b is related to a and c is related to a, then b is related to c:

Properties

  1. 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.
  2. The property of being Euclidean is different from transitivity. For example, ≤ is transitive, but not right Euclidean, while xRy defined by 0 ≤ x ≤ y + 1 ≤ 2 is not transitive, but right Euclidean on natural numbers.
  3. For symmetric relations, transitivity, right Euclideanness, and left Euclideanness all coincide. However, also a non-symmetric relation can be both transitive and right Euclidean, for example, xRy defined by y=0.
  4. A relation which is both right Euclidean and reflexive is also symmetric and therefore an equivalence relation. Similarly, each left Euclidean and reflexive relation is an equivalence.
  5. The range of a right Euclidean relation is always a subset of its domain. The restriction of a right Euclidean relation to its range is always reflexive, 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.
  6. A relation R is both left and right Euclidean, if, and only if, the domain and the range set of R agree, and R is an equivalence relation on that set.
  7. A right Euclidean relation is always quasitransitive, and so is a left Euclidean relation.
  8. A semi-connex right Euclidean relation is always transitive; and so is a semi-connex left Euclidean relation.
  9. If X has at least 3 elements, a semi-connex right Euclidean relation R on X cannot be antisymmetric, and neither can a semi-connex left Euclidean relation on X. On the 2-element set X =, e.g. the relation xRy defined by y=1 is semi-connex, right Euclidean, and antisymmetric, and xRy defined by x=1 is semi-connex, left Euclidean, and antisymmetric.
  10. A relation R on a set X is right Euclidean if, and only if, the restriction R’ := Rran is an equivalence and for each x in X\ran, all elements to which x is related under R are equivalent under R’. Similarly, R on X is left Euclidean if, and only if, R’ := Rdom is an equivalence and for each x in X\dom, all elements that are related to x under R are equivalent under R’.
  11. A left Euclidean relation is left-unique if, and only if, it is antisymmetric. Similarly, a right Euclidean relation is right unique if, and only if, it is anti-symmetric.
  12. A left Euclidean and left unique relation is vacuously transitive, and so is a right Euclidean and right unique relation.
  13. A left Euclidean relation is left quasi-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.