Homogeneous relation

In mathematics, a homogeneous relation (also called endorelation) over a set X is a binary relation over X and itself, i.e. it is a subset of the Cartesian product X × X.[2][3] This is commonly phrased as "a relation on X"[4] or "a (binary) relation over X".[5][6] An example of a homogeneous relation is the relation of kinship, where the relation is over people.

A homogeneous relation R over a set X may be identified with a directed simple graph permitting loops, or if it is symmetric, with an undirected simple graph permitting loops, where X is the vertex set and R is the edge set (there is an edge from a vertex x to a vertex y if and only if xRy). It is called the adjacency relation of the graph.

Some important particular homogeneous relations over a set X (with arbitrary elements x1, x2) are:

Fifteen large tectonic plates of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as a logical matrix with 1 indicating contact and 0 no contact. This example expresses a symmetric relation.

Some important properties that a homogeneous relation R over a set X may have are:

The previous 6 alternatives are far from being exhaustive; e.g., the red binary relation y = x2 is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair (0, 0), and (2, 4), but not (2, 2), respectively. The latter two facts also rule out (any kind of) quasi-reflexivity.

Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation xRy defined by x > 2 is neither symmetric nor antisymmetric, let alone asymmetric.

Again, the previous 5 alternatives are not exhaustive. For example, the relation xRy if (y = 0 or y = x+1) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.

Moreover, all properties of binary relations in general also may apply to homogeneous relations:

A preorder is a relation that is reflexive and transitive. A total preorder, also called linear preorder or weak order, is a relation that is reflexive, transitive, and connected.

A partial order, also called order,[citation needed] is a relation that is reflexive, antisymmetric, and transitive. A strict partial order, also called strict order,[citation needed] is a relation that is irreflexive, antisymmetric, and transitive. A total order, also called linear order, simple order, or chain, is a relation that is reflexive, antisymmetric, transitive and connected.[14] A strict total order, also called strict linear order, strict simple order, or strict chain, is a relation that is irreflexive, antisymmetric, transitive and connected.

A partial equivalence relation is a relation that is symmetric and transitive. An equivalence relation is a relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and total, since these properties imply reflexivity.

If R is a homogeneous relation over a set X then each of the following is a homogeneous relation over X:

All operations defined in Binary relation § Operations on binary relations also apply to homogeneous relations.

The number of distinct homogeneous relations over an n-element set is 2n2 (sequence in the OEIS):

The homogeneous relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).