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."
Definition
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:
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
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 transitivity. For example, ≤ is transitive, but not right Euclidean,e.g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1 while xRy defined by 0 ≤ x ≤ y + 1 ≤ 2 is not transitive,e.g. 2R1 and 1R0, but not 2R0 but right Euclidean on natural numbers. 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. A relation that is both right Euclidean and reflexive is also symmetric and therefore an equivalence relation.xRy and xRx implies yRx. Similarly, each left Euclidean and reflexive relation is an equivalence. The range of a right Euclidean relation is always a subsetEquality 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. of its domain. The restriction of a right Euclidean relation to its range is always reflexive,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. 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.. 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.The only if direction follows from the previous paragraph. — For the if direction, assume aRb and aRc, then a,b,c are members of the domain and range of R, hence bRc by symmetry and transitivity; left Euclideanness of R follows similarly. A right Euclidean relation is always quasitransitive,If xRy ∧ ¬yRx ∧ yRz ∧ ¬zRy holds, then both y and z are in the range of R. Since R is an equivalence on that set, yRz implies zRy. Hence the antecedent of the quasi-transitivity definition formula cannot be satisfied. as is a left Euclidean relation.A similar argument applies, observing that x,y are in the domain of R. A connected right Euclidean relation is always transitive;If xRy ∧ yRz holds, then y and z are in the range of R. Since R is connected, xRz or zRx or x=z holds. In case 1, nothing remains to be shown. In cases 2 and 3, also x is in the range. Hence, xRz follows from the symmetry and reflexivity of R on its range, respectively. and so is a connected left Euclidean relation.Similar, using that x, y are in the domain of R. If X has at least 3 elements, a connected right Euclidean relation R on X cannot be antisymmetric,Since R is connected, at least two distinct elements x,y are in its range, and xRy ∨ yRx holds. Since R is symmetric on its range, even xRy ∧ yRx holds. This contradicts the antisymmetry property. and neither can a connected left Euclidean relation on X.By a similar argument, using the domain of R. 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. A relation R on a set X is right Euclidean if, and only if, the restriction R := Rran(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.Only if: R is an equivalence as shown above. If x∈X\ran(R) and xRy1 and xRy2, then y1Ry2 by right Euclideaness, hence y1Ry2. — If: if xRy ∧ xRz holds, then y,z∈ran(R). In case also x∈ran(R), even xRy ∧ xRz holds, hence yRz by symmetry and transitivity of R, hence yRz. In case x∈X\ran(R), the elements y and z must be equivalent under R by assumption, hence also yRz. Similarly, R on X is left Euclidean if, and only if, R := Rdom(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. 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. 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 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. Lemma 44-46. A binary relation is left Euclidean if and only if its converse is right Euclidean.
References