In mathematics, a homogeneous relation (also called endorelation) 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. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations. Terminology particular for graph theory is used for description, with an ordinary (undirected) graph presumed to correspond to a symmetric relation, and a general endorelation corresponding to a directed graph. An endorelation R corresponds to a logical matrix of 0s and 1s, where the expression xRy corresponds to an edge between x and y in the graph, and to a 1 in the square matrix of R. It is called an adjacency matrix in graph terminology.

Particular homogeneous relations

Some particular homogeneous relations over a set X (with arbitrary elements x1 , x2 ) are: E = ∅ x1Ex2 holds never; U = X × X x1Ux2 holds always; x ∈ X} x1Ix2 holds if and only if x1 = x2 .

Example

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.

Properties

Some important properties that a homogeneous relation R over a set X may have are: x ∈ X , xRx . For example, ≥ is a reflexive relation but > is not. x ∈ X , not xRx . For example, > is an irreflexive relation, but ≥ is not. x, y ∈ X , if xRy then x = y . For example, the relation over the integers in which each odd number is related to itself is a coreflexive relation. The equality relation is the only example of a both reflexive and coreflexive relation, and any coreflexive relation is a subset of the identity relation. x, y ∈ X , if xRy then xRx . x, y ∈ X , if xRy then yRy . x, y ∈ X , if xRy then xRx and yRy . A relation is quasi-reflexive if, and only if, it is both left and right quasi-reflexive. The previous 6 alternatives are far from being exhaustive; e.g., the binary relation xRy defined by 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. x, y ∈ X , if xRy then yRx . For example, "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. x, y ∈ X , if xRy and yRx then x = y . For example, ≥ is an antisymmetric relation; so is >, but vacuously (the condition in the definition is always false). x, y ∈ X , if xRy then not yRx . A relation is asymmetric if and only if it is both antisymmetric and irreflexive. For example, > is an asymmetric relation, but ≥ is not. 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. x, y, z ∈ X , if xRy and yRz then xRz . A transitive relation is irreflexive if and only if it is asymmetric. For example, "is ancestor of" is a transitive relation, while "is parent of" is not. x, y, z ∈ X , if xRy and yRz then never xRz . x, y, z ∈ X , if xRz , then xRy or yRz . This is used in pseudo-orders in constructive mathematics. x, y, z ∈ X , if xRy and yRz but neither yRx nor zRy , then xRz but not zRx . x, y, z ∈ X , if x and y are incomparable with respect to R and if the same is true of y and z, then x and z are also incomparable with respect to R. This is used in weak orderings. 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. x, y ∈ X such that xRy , there exists some z ∈ X such that xRz and zRy . This is used in dense orders. x, y ∈ X , if x ≠ y then xRy or yRx . This property is sometimes called "total", which is distinct from the definitions of "left/right-total" given below. x, y ∈ X , xRy or yRx . This property, too, is sometimes called "total", which is distinct from the definitions of "left/right-total" given below. x, y ∈ X , exactly one of xRy , yRx or x = y holds. For example, > is a trichotomous relation on the real numbers, while the relation "divides" over the natural numbers is not. x, y, z ∈ X , if xRy and xRz then yRz . For example, = is a Euclidean relation because if x = y and x = z then y = z . x, y, z ∈ X , if yRx and zRx then yRz . xnR...Rx3Rx2Rx1 can exist). If the axiom of dependent choice is assumed, both conditions are equivalent. Moreover, all properties of binary relations in general also may apply to homogeneous relations: x ∈ X , the class of all y such that yRx is a set. (This makes sense only if relations over proper classes are allowed.) x, z ∈ X and all y ∈ Y , if xRy and zRy then x = z . x ∈ X and all y, z ∈ Y , if xRy and xRz then y = z . x ∈ X there exists a y ∈ Y such that xRy . This property is different from the definition of connected (also called total by some authors). y ∈ Y , there exists an x ∈ X such that xRy. A is a relation that is reflexive and transitive. A, also called or , is a relation that is reflexive, transitive, and connected. A, also called , is a relation that is reflexive, antisymmetric, and transitive. A, also called , is a relation that is irreflexive, antisymmetric, and transitive. A, also called , , or , is a relation that is reflexive, antisymmetric, transitive and connected. A, also called , , or , is a relation that is irreflexive, antisymmetric, transitive and connected. A is a relation that is symmetric and transitive. An 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.

Operations

If R is a homogeneous relation over a set X then each of the following is a homogeneous relation over X: x ∈ X} ∪ R or the smallest reflexive relation over X containing R. This can be proven to be equal to the intersection of all reflexive relations containing R. x ∈ X} or the largest irreflexive relation over X contained in R. R* = (R+)= , the smallest preorder containing R. All operations defined in also apply to homogeneous relations. ! ! Reflexivity ! Symmetry ! Transitivity ! Connectedness ! Symbol ! Example ! Directed graph ! Undirected graph ! Dependency ! Tournament ! Preorder ! Total preorder ! Partial order ! Strict partial order ! Total order ! Strict total order ! Partial equivalence relation ! Equivalence relation

Enumeration

The set of all homogeneous relations over a set X is the set 2X×X , which is a Boolean algebra augmented with the involution of mapping of a relation to its converse relation. Considering composition of relations as a binary operation on, it forms a monoid with involution where the identity element is the identity relation. The number of distinct homogeneous relations over an n-element set is 2n 2 Notes: 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).

Examples

Generalizations