- Definition
- Properties
- References
In mathematics, Euclidean relations are a class of binary relations that formalizes "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.[1] 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,&91;2&93; while xRy defined by 0 ≤ x ≤ y + 1 ≤ 2 is not transitive,&91;3&93; but right Euclidean on natural numbers.
- 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.
- A relation which is both right Euclidean and reflexive is also symmetric and therefore an equivalence relation.&91;1&93;&91;4&93; Similarly, each left Euclidean and reflexive relation is an equivalence.
- The range of a right Euclidean relation is always a subset&91;5&93; of its domain. The restriction of a right Euclidean relation to its range is always reflexive,&91;6&93; 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.
- 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.&91;7&93;
- A right Euclidean relation is always quasitransitive,&91;8&93; and so is a left Euclidean relation.&91;9&93;
- A semi-connex right Euclidean relation is always transitive;&91;10&93; and so is a semi-connex left Euclidean relation.&91;11&93;
- If X has at least 3 elements, a semi-connex right Euclidean relation R on X cannot be antisymmetric,&91;12&93; and neither can a semi-connex left Euclidean relation on X.&91;13&93; On the 2-element set X = { 0, 1 }, 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.
- 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’.&91;14&93; 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’.
- 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.&91;15&93;
References
1. ^1 {{citation|title=Reasoning About Knowledge|first=Ronald|last=Fagin|authorlink=Ronald Fagin|publisher=MIT Press|year=2003|isbn=978-0-262-56200-3|page=60|url=https://books.google.com/books?id=xHmlRamoszMC&pg=PA60}}.
2. ^e.g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1
3. ^e.g. 2R1 and 1R0, but not 2R0
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, ℕ.
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. ^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.
8. ^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 definion formula cannot be satisfied.
9. ^A similar argument applies, observing that x,y are in the domain of R.
10. ^If xRy ∧ yRz holds, then y and z are in the range of R. Since R is semi-connex, 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.
11. ^Similar, using that x, y are in the domain of R.
12. ^Since R is semi-connex, 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.
13. ^By a similar argument, using the domain of R.
14. ^Only if: R’ is an equivalence as shown above. If x∈X\\ran(R) and xR’y1 and xR’y2, then y1Ry2 by right Euclideaness, hence y1R’y2. — If: if xRy ∧ xRz holds, then y,z∈ran(R). In case also x∈ran(R), even xR’y ∧ xR’z holds, hence yR’z 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.
15. ^ {{cite report | arxiv=1806.05036v2 | author=Jochen Burghardt | title=Simple Laws about Nonprominent Properties of Binary Relations | type=Technical Report | date=Nov 2018 }} Lemma 44-46.
2. ^e.g. 0 ≤ 2 and 0 ≤ 1, but not 2 ≤ 1
3. ^e.g. 2R1 and 1R0, but not 2R0
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, ℕ.
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. ^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.
8. ^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 definion formula cannot be satisfied.
9. ^A similar argument applies, observing that x,y are in the domain of R.
10. ^If xRy ∧ yRz holds, then y and z are in the range of R. Since R is semi-connex, 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.
11. ^Similar, using that x, y are in the domain of R.
12. ^Since R is semi-connex, 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.
13. ^By a similar argument, using the domain of R.
14. ^Only if: R’ is an equivalence as shown above. If x∈X\\ran(R) and xR’y1 and xR’y2, then y1Ry2 by right Euclideaness, hence y1R’y2. — If: if xRy ∧ xRz holds, then y,z∈ran(R). In case also x∈ran(R), even xR’y ∧ xR’z holds, hence yR’z 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.
15. ^ {{cite report | arxiv=1806.05036v2 | author=Jochen Burghardt | title=Simple Laws about Nonprominent Properties of Binary Relations | type=Technical Report | date=Nov 2018 }} Lemma 44-46.
2 : Binary relations|Euclid
- Focal Parameter
- Focal parameter
- Focal Plane
- Focal plane array
- Focal planes
- Focal plane shutter
- Focal Point
- Focal point (disambiguation)
- Focal Point: Mark of the Leaf
- Focal point (optics)
- Focal points
- Focal Point: The Symbol of the Hidden Leaf
- Focal Press
- FOCAL programming language
- Focal seizure
- Focal surface
- Focalt pendulum
- Focal vocabulary
- Focas (Lunar crater)
- Focault pendulum
- Foccacia
- Focea
- Foch-Gilttoyees Provincial Park
- Foch Line
- Fochlucan lyrist