Binary Relation - Relations Over A Set

Relations Over A Set

If X = Y then we simply say that the binary relation is over X, or that it is an endorelation over X. Some types of endorelations are widely studied in graph theory, where they're known as directed graphs.

The set of all binary relations Rel(X) on a set X is the set 2X × X which is a Boolean algebra augmented with the involution of mapping of a relation to its inverse relation. For the theoretical explanation see Relation algebra.

Some important types of binary relations over a set X are:

• reflexive: for all x in X it holds that xRx. For example, "greater than or equal to" is a reflexive relation but "greater than" is not.
• irreflexive (or strict): for all x in X it holds that not xRx. "Greater than" is an example of an irreflexive relation.
• coreflexive: for all x and y in X it holds that if xRy then x = y. "Equal to and odd" is an example of a coreflexive relation.
• symmetric: for all x and y in X it holds that if xRy then yRx. "Is a blood relative of" is a symmetric relation, because x is a blood relative of y if and only if y is a blood relative of x.
• antisymmetric: for all distinct x and y in X, if xRy then not yRx.
• asymmetric: for all x and y in X, if xRy then not yRx. (So asymmetricity is stronger than anti-symmetry. In fact, asymmetry is equivalent to anti-symmetry plus irreflexivity.)
• transitive: for all x, y and z in X it holds that if xRy and yRz then xRz. (Note that, under the assumption of transitivity, irreflexivity and asymmetry are equivalent.)
• total: for all x and y in X it holds that xRy or yRx (or both). "Is greater than or equal to" is an example of a total relation (this definition for total is different from left total in the previous section).
• trichotomous: for all x and y in X exactly one of xRy, yRx or x = y holds. "Is greater than" is an example of a trichotomous relation.
• Euclidean: for all x, y and z in X it holds that if xRy and xRz, then yRz (and zRy). Equality is a Euclidean relation because if x=y and x=z, then y=z.
• serial: for all x in X, there exists y in X such that xRy. "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, the "Is less than" is a serial relation on the positive integers (the natural numbers), the rational numbers and the real numbers. Every reflexive relation is serial.
• set-like: for every x in X, the class of all y such that yRx is a set. (This makes sense only if we allow relations on proper classes.) The usual ordering < on the class of ordinal numbers is set-like, while its inverse > is not.

A relation that is reflexive, symmetric, and transitive is called an equivalence relation. A relation that is reflexive, antisymmetric, and transitive is called a partial order. A partial order that is total is called a total order, simple order, linear order, or a chain. A linear order where every nonempty set has a least element is called a well-order. A relation that is symmetric, transitive, and serial is also reflexive.