Binary relation
Binary Relations
equivalence relation: symmetric, transitive, reflexive
partial equivalence: symmetric, transitive
List of properties
Important properties that a binary relation may have include:
reflexivity, irreflexivity, coreflexivity
symmetry, antisymmetry, asymmetry
transitivity
totality
right Euclidean, left Euclidean, Euclidean
trichotomy, serial properties, set-like properties
List of relations
List of some relations by properties
equivalence: reflexive, symmetric, transitive.
partial equivalence: symmetric, transitive.
reflexive: symmetric, transitive, serial.
partial order: reflexive, antisymmetric, transitive.
total order (linear order, or chain): partial order that is total.
well-order: linear order where every nonempty subset has a least element.
Total
This definition for total is different from left total. For example, >= is a total relation.
Trichotomous
For example, > is a trichotomous relation, while the relation "divides" on natural numbers is not.
Euclidean
A Euclidean relation is both left and right Euclidean. Equality is a Euclidean relation because if x=y and x=z, then y=z.
Serial
"Is greater than" is a serial relation on the integers. But it is not a serial relation on the positive integers, because there is no y in the positive integers such that 1 > y. However, "is less than" is a serial relation on the positive integers, the rational numbers and the real numbers.
Every reflexive relation is serial: for a given x, choose y = x. A serial relation can be equivalently characterized as every element having a non-empty successor neighborhood. Similarly an inverse serial relation is a relation in which every element has non-empty predecessor neighborhood.
Set-like or Local
The usual ordering < on the class of ordinal numbers is set-like, while its inverse > is not.
Partial equivalence relation
A partial equivalence relation (PER) R on a set X is a relation that is symmetric and transitive.
It holds for all a, b, c ∈ X that: 1. if aRb, then bRa (symmetry) 2. if aRb and bRc, then aRc (transitivity)
If R is also reflexive, then R is an equivalence relation.
Reference
Last updated