Euclidean relation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, Euclidean relations are a class of binary relations that satisfy a weakened form of transitivity that formalizes Euclid's "Common Notion 1" in The Elements: things which equal the same thing also equal one another.

Definition[edit]

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:

\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).

Relation to transitivity[edit]

The property of being Euclidean is different from transitivity: both the Euclidean property and transitivity infer a relation between b and c from relations between a and b and between a and c, but with different argument orderings in the relations. However, if a relation is symmetric, then the argument orders do not matter; thus a symmetric relation with any one of these three properties (transitive, right Euclidean, left Euclidean) must have all three.[1]

If a relation is Euclidean and reflexive, then it must also be symmetric and hence transitive (following the previous paragraph), and so it must be an equivalence relation. Consequently, equivalence relations are exactly the reflexive Euclidean relations.[1]

References[edit]

  1. ^ a b c Fagin, Ronald (2003), Reasoning About Knowledge, MIT Press, p. 60, ISBN 978-0-262-56200-3 .