Euclidean relation

In mathematics, Euclidean relations are a class of binary relations that formalize "Axiom 1" in Euclid's Elements: "Magnitudes which are equal to the same are equal to each other."

A binary relation R on a set X is Euclidean (sometimes called right 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:

${\displaystyle \forall a,b,c\in X\,(a\,R\,b\land a\,R\,c\to b\,R\,c).}$

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:

${\displaystyle \forall a,b,c\in X\,(b\,R\,a\land c\,R\,a\to b\,R\,c).}$

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, a non-symmetric relation can also be both transitive and right Euclidean, for example, xRy defined by y=0.
4. A relation that 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. 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.
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, as is a left Euclidean relation.
8. A connected right Euclidean relation is always transitive; and so is a connected left Euclidean relation.
9. If X has at least 3 elements, a connected right Euclidean relation R on X cannot be antisymmetric, and neither can a connected left Euclidean relation on X. On the 2-element set X = { 0, 1 }, e.g. the relation xRy defined by y=1 is connected, right Euclidean, and antisymmetric, and xRy defined by x=1 is connected, left Euclidean, and antisymmetric.
10. A relation R on a set X is right Euclidean if, and only if, the restriction R′ := R|_ran(R) is an equivalence and for each x in X\ran(R), 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′ := R|_dom(R) is an equivalence and for each x in X\dom(R), 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.