Euclidean relation

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:

:\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:

:\forall a, b, c\in X,(b,R, a \land c ,R, a \to b ,R, 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, 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 := 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. 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.
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.

References

References

1. Fagin, Ronald. (2003). "Reasoning About Knowledge". MIT Press.
2. e.g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1
3. e.g. 2''R''1 and 1''R''0, but not 2''R''0
4. ''xRy'' and ''xRx'' implies ''yRx''.
5. 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.
6. 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''.
7. Buck, Charles. (1967). "An Alternative Definition for Equivalence Relations". The Mathematics Teacher.
8. 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.
9. 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.
10. A similar argument applies, observing that ''x'',''y'' are in the domain of ''R''.
11. 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.
12. Similar, using that ''x'', ''y'' are in the domain of ''R''.
13. Since ''R'' is connected, at least two distinct elements ''x'',''y'' are in its [[Image (mathematics)#Generalization to binary relations. range]], and ''xRy'' ∨ ''yRx'' holds. Since ''R'' is symmetric on its range, even ''xRy'' ∧ ''yRx'' holds. This contradicts the antisymmetry property.
14. By a similar argument, using the domain of ''R''.
15. ''Only if:'' ''R{{prime'' is an equivalence as shown above. If ''x''∈''X''\ran(''R'') and ''xR{{primey''₁ and ''xR{{primey''₂, then ''y''₁''Ry''₂ by right Euclideaness, hence ''y''₁''R{{primey''₂. — ''If'': if ''xRy'' ∧ ''xRz'' holds, then ''y'',''z''∈ran(''R''). In case also ''x''∈ran(''R''), even ''xR{{primey'' ∧ ''xR{{primez'' holds, hence ''yR{{primez'' by symmetry and transitivity of ''R{{prime'', hence ''yRz''. In case ''x''∈''X''\ran(''R''), the elements ''y'' and ''z'' must be equivalent under ''R{{prime'' by assumption, hence also ''yRz''.
16. Jochen Burghardt. (Nov 2018). "Simple Laws about Nonprominent Properties of Binary Relations".