Euclidean relation

Last updated

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."

Contents

Definition

Right Euclidean property: solid and dashed arrows indicate antecedents and consequents, respectively. Euclidean.PNG
Right Euclidean property: solid and dashed arrows indicate antecedents and consequents, respectively.

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

Schematized right Euclidean relation according to property 10. Deeply-colored squares indicate the equivalence classes of R'. Pale-colored rectangles indicate possible relationships of elements in X\ran(R). In these rectangles, relationships may, or may not, hold. Right Euclidean relation scheme svg.svg
Schematized right Euclidean relation according to property 10. Deeply-colored squares indicate the equivalence classes of R′. Pale-colored rectangles indicate possible relationships of elements in X\ran(R). In these rectangles, relationships may, or may not, hold.
  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, [2] while xRy defined by 0 ≤ x ≤ y + 1 ≤ 2 is not transitive, [3] 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. [1] [4] Similarly, each left Euclidean and reflexive relation is an equivalence.
  5. The range of a right Euclidean relation is always a subset [5] of its domain. The restriction of a right Euclidean relation to its range is always reflexive, [6] 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. [7]
  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. [8]
  7. A right Euclidean relation is always quasitransitive, [9] as is a left Euclidean relation. [10]
  8. A connected right Euclidean relation is always transitive; [11] and so is a connected left Euclidean relation. [12]
  9. If X has at least 3 elements, a connected right Euclidean relation R on X cannot be antisymmetric, [13] and neither can a connected left Euclidean relation on X. [14] 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′. [15] 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. [16]

Related Research Articles

In mathematics, a binary relation associates elements of one set called the domain with elements of another set called the codomain. Precisely, a binary relation over sets and is a set of ordered pairs where is in and is in . It encodes the common concept of relation: an element is related to an element , if and only if the pair belongs to the set of ordered pairs that defines the binary relation.

<span class="mw-page-title-main">Equivalence relation</span> Mathematical concept for comparing objects

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equality. Any number is equal to itself (reflexive). If , then (symmetric). If and , then (transitive).

<span class="mw-page-title-main">Partially ordered set</span> Mathematical set with an ordering

In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.

<span class="mw-page-title-main">Preorder</span> Reflexive and transitive binary relation

In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. The name preorder is meant to suggest that preorders are almost partial orders, but not quite, as they are not necessarily antisymmetric.

<span class="mw-page-title-main">Equality (mathematics)</span> Basic notion of sameness in mathematics

In mathematics, equality is a relationship between two quantities or expressions, stating that they have the same value, or represent the same mathematical object. Equality between A and B is written A = B, and pronounced "A equals B". In this equality, A and B are distinguished by calling them left-hand side (LHS), and right-hand side (RHS). Two objects that are not equal are said to be distinct.

In mathematics, a binary relation on a set is reflexive if it relates every element of to itself.

A symmetric relation is a type of binary relation. Formally, a binary relation R over a set X is symmetric if:

In mathematics, a binary relation R on a set X is transitive if, for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c.

In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but not under subtraction: 1 − 2 is not a natural number, although both 1 and 2 are.

<span class="mw-page-title-main">Weak ordering</span> Mathematical ranking of a set

In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered sets and are in turn generalized by (strictly) partially ordered sets and preorders.

In mathematics, a partial equivalence relation is a homogeneous binary relation that is symmetric and transitive. If the relation is also reflexive, then the relation is an equivalence relation.

This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC and in NFU, the version of Quine's New Foundations shown to be consistent by R. B. Jensen in 1969.

In mathematics, the converse of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if and are sets and is a relation from to then is the relation defined so that if and only if In set-builder notation,

In mathematics, a partial order or total order < on a set is said to be dense if, for all and in for which , there is a in such that . That is, for any two elements, one less than the other, there is another element between them. For total orders this can be simplified to "for any two distinct elements, there is another element between them", since all elements of a total order are comparable.

<span class="mw-page-title-main">Quasitransitive relation</span>

The mathematical notion of quasitransitivity is a weakened version of transitivity that is used in social choice theory and microeconomics. Informally, a relation is quasitransitive if it is symmetric for some values and transitive elsewhere. The concept was introduced by Sen (1969) to study the consequences of Arrow's theorem.

In mathematics, a homogeneous relation on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people.

In mathematical logic, the ancestral relation of a binary relation R is its transitive closure, however defined in a different way, see below.

In constructive mathematics, pseudo-order is a name given to certain binary relations appropriate for modeling continuous orderings.

<span class="mw-page-title-main">Relation (mathematics)</span> Relationship between two sets, defined by a set of ordered pairs

In mathematics, a relation denotes some kind of relationship between two objects in a set, which may or may not hold. As an example, "is less than" is a relation on the set of natural numbers; it holds, for instance, between the values 1 and 3, and likewise between 3 and 4, but not between the values 3 and 1 nor between 4 and 4, that is, 3 < 1 and 4 < 4 both evaluate to false. As another example, "is sister of" is a relation on the set of all people, it holds e.g. between Marie Curie and Bronisława Dłuska, and likewise vice versa. Set members may not be in relation "to a certain degree" – either they are in relation or they are not.

In order theory, the Szpilrajn extension theorem, proved by Edward Szpilrajn in 1930, states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties.

References

  1. 1 2 Fagin, Ronald (2003), Reasoning About Knowledge, MIT Press, p. 60, ISBN   978-0-262-56200-3 .
  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 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, 60 (2): 124–125, doi:10.5951/MT.60.2.0124, JSTOR   27957510 .
  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 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′ 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.
  16. ↑ Jochen Burghardt (Nov 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv: 1806.05036v2 . Lemma 44-46.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.