Inmathematics, ahomogeneous relation (also calledendorelation) on a setX is abinary relation betweenX and itself, i.e. it is a subset of theCartesian productX ×X.^[1][2][3] This is commonly phrased as "a relation onX"^[4] or "a (binary) relation overX".^[5][6] An example of a homogeneous relation is the relation ofkinship, where the relation is between people.

Common types of endorelations includeorders,graphs, andequivalences. Specialized studies oforder theory andgraph theory have developed understanding of endorelations. Terminology particular for graph theory is used for description, with an ordinary (undirected) graph presumed to correspond to asymmetric relation, and a general endorelation corresponding to adirected graph. An endorelationR corresponds to alogical matrix of 0s and 1s, where the expressionxRy (x isR-related toy) corresponds to an edge betweenx andy in the graph, and to a 1 in thesquare matrix ofR. It is called anadjacency matrix in graph terminology.

Some particular homogeneous relations over a setX (with arbitrary elementsx₁,x₂) are:

Empty relation

E =∅;
that is,x₁Ex₂ holds never;

Universal relation

U =X ×X;
that is,x₁Ux₂ holds always;

Identity relation (see alsoIdentity function)

I = {(x,x) |x ∈X};
that is,x₁Ix₂ holds if and only ifx₁ =x₂.

Matrix representation of the relation "is adjacent to" on the set of tectonic plates

		Af	An	Ar	Au	Ca	Co	Eu	In	Ju	NA	Na	Pa	Ph	SA	Sc	So
African	Af
Antarctic	An
Arabian	Ar
Australian	Au
Caribbean	Ca
Cocos	Co
Eurasian	Eu
Indian	In
Juan de Fuca	Ju
North american	NA
Nazca	Na
Pacific	Pa
Philippine	Ph
South american	SA
Scotia	Sc
Somali	So

Sixteen largetectonic plates of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as alogical matrix with 1 (depicted "") indicating contact and 0 ("") no contact. This example expresses a symmetric relation.

Some important properties that a homogeneous relationR over a setX may have are:

Reflexive

for allx ∈X,xRx. For example, ≥ is a reflexive relation but > is not.

Irreflexive (orstrict)

for allx ∈X, notxRx. For example, > is an irreflexive relation, but ≥ is not.

Coreflexive

for allx,y ∈X, ifxRy thenx =y.^[7] 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.

Left quasi-reflexive

for allx,y ∈X, ifxRy thenxRx.

Right quasi-reflexive

for allx,y ∈X, ifxRy thenyRy.

Quasi-reflexive

for allx,y ∈X, ifxRy thenxRx andyRy. 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 relationxRy defined byy =x² 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.

Symmetric

for allx,y ∈X, ifxRy thenyRx. For example, "is a blood relative of" is a symmetric relation, becausex is a blood relative ofy if and only ify is a blood relative ofx.

Antisymmetric

for allx,y ∈X, ifxRy andyRx thenx =y. For example, ≥ is an antisymmetric relation; so is >, butvacuously (the condition in the definition is always false).^[8]

Asymmetric

for allx,y ∈X, ifxRy then notyRx. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.^[9] 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 relationxRy defined byx > 2 is neither symmetric nor antisymmetric, let alone asymmetric.

Transitive

for allx,y,z ∈X, ifxRy andyRz thenxRz. A transitive relation is irreflexive if and only if it is asymmetric.^[10] For example, "is ancestor of" is a transitive relation, while "is parent of" is not.

Antitransitive

for allx,y,z ∈X, ifxRy andyRz then neverxRz.

Co-transitive

if the complement ofR is transitive. That is, for allx,y,z ∈X, ifxRz, thenxRy oryRz. This is used inpseudo-orders in constructive mathematics.

Quasitransitive

for allx,y,z ∈X, ifxRy andyRz but neitheryRx norzRy, thenxRz but notzRx.

Transitivity of incomparability

for allx,y,z ∈X, ifx andy are incomparable with respect toR and if the same is true ofy andz, thenx andz are also incomparable with respect toR. This is used inweak orderings.

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

Dense

for allx,y ∈X such thatxRy, there exists somez ∈X such thatxRz andzRy. This is used indense orders.

Connected

for allx,y ∈X, ifx ≠y thenxRy oryRx. This property is sometimes^{[citation needed]} called "total", which is distinct from the definitions of "left/right-total" given below.

Strongly connected

for allx,y ∈X,xRy oryRx. This property, too, is sometimes^{[citation needed]} called "total", which is distinct from the definitions of "left/right-total" given below.

Trichotomous

for allx,y ∈X, exactly one ofxRy,yRx orx =y holds. For example, > is a trichotomous relation on the real numbers, while the relation "divides" over the natural numbers is not.^[11]

Right Euclidean (or justEuclidean)

for allx,y,z ∈X, ifxRy andxRz thenyRz. For example, = is a Euclidean relation because ifx =y andx =z theny =z.

Left Euclidean

for allx,y,z ∈X, ifyRx andzRx thenyRz.

Well-founded

every nonempty subsetS ofX contains aminimal element with respect toR. Well-foundedness implies thedescending chain condition (that is, no infinite chain... x_nR...Rx₃Rx₂Rx₁ can exist). If theaxiom of dependent choice is assumed, both conditions are equivalent.^[12][13]

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

Set-like

for allx ∈X, theclass of ally such thatyRx is a set. (This makes sense only if relations over proper classes are allowed.)

Left-unique

for allx,z ∈X and ally ∈Y, ifxRy andzRy thenx =z.

Univalent

for allx ∈X and ally,z ∈Y, ifxRy andxRz theny =z.^[14]

Total (also called left-total)

for allx ∈X there exists ay ∈Y such thatxRy. This property is different from the definition ofconnected (also calledtotal by some authors).^{[citation needed]}

Surjective (also called right-total)

for ally ∈Y, there exists anx ∈X such thatxRy.

Apreorder is a relation that is reflexive and transitive. Atotal preorder, also calledlinear preorder orweak order, is a relation that is reflexive, transitive, and connected.

Apartial order, also calledorder,^{[citation needed]} is a relation that is reflexive, antisymmetric, and transitive. Astrict partial order, also calledstrict order,^{[citation needed]} is a relation that is irreflexive, antisymmetric, and transitive. Atotal order, also calledlinear order,simple order, orchain, is a relation that is reflexive, antisymmetric, transitive and connected.^[15] Astrict total order, also calledstrict linear order,strict simple order, orstrict chain, is a relation that is irreflexive, antisymmetric, transitive and connected.

Apartial equivalence relation is a relation that is symmetric and transitive. Anequivalence 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.

A univalent relation may also be called apartial function. A(total)function is a partial function that is left-total. Aninjective function (or partial function) is one whose inverse is univalent. Asurjective function is one that is right-total.

Implications and conflicts between properties of homogeneous binary relations

IfR is a homogeneous relation over a setX then each of the following is a homogeneous relation overX:

Reflexive closure,R⁼

Defined asR⁼ = {(x,x) |x ∈X} ∪R or the smallest reflexive relation overX containingR. This can be proven to be equal to theintersection of all reflexive relations containingR.

Reflexive reduction,R^≠

Defined asR^≠ =R \ {(x,x) |x ∈X} or the largestirreflexive relation overX contained inR.

Transitive closure,R⁺

Defined as the smallest transitive relation overX containingR. This can be seen to be equal to the intersection of all transitive relations containingR.

Reflexive transitive closure,R*

Defined asR* = (R⁺)⁼, the smallestpreorder containingR.

Reflexive transitive symmetric closure,R^≡

Defined as the smallestequivalence relation overX containingR.

All operations defined inBinary relation § Operations also apply to homogeneous relations.

Homogeneous relations by property

	Reflexivity	Symmetry	Transitivity	Connectedness	Symbol	Example
Directed graph					→
Undirected graph		Symmetric
Dependency	Reflexive	Symmetric
Tournament	Irreflexive	Asymmetric				Pecking order
Preorder	Reflexive		Transitive		≤	Preference
Total preorder	Reflexive		Transitive	Connected	≤
Partial order	Reflexive	Antisymmetric	Transitive		≤	Subset
Strict partial order	Irreflexive	Asymmetric	Transitive		<	Strict subset
Total order	Reflexive	Antisymmetric	Transitive	Connected	≤	Alphabetical order
Strict total order	Irreflexive	Asymmetric	Transitive	Connected	<	Strict alphabetical order
Partial equivalence relation		Symmetric	Transitive
Equivalence relation	Reflexive	Symmetric	Transitive		~, ≡	Equality

The set of all homogeneous relations${\displaystyle \mathcal{B}(X)}$ over a setX is the set2^X×X, which is aBoolean algebra augmented with theinvolution of mapping of a relation to itsconverse relation. Consideringcomposition of relations as abinary operation on${\displaystyle \mathcal{B}(X)}$, it forms amonoid with involution where the identity element is the identity relation.^[16]

The number of distinct homogeneous relations over ann-element set is2ⁿ² (sequenceA002416 in theOEIS):

Note thatS(n,k) refers toStirling numbers of the second kind.

Notes:

• The number of irreflexive relations is the same as that of reflexive relations.
• The number ofstrict partial orders (irreflexive transitive relations) is the same as that of partial orders.
• The number of strict weak orders is the same as that of total preorders.
• The total orders are the partial orders that are also total preorders. The number of preorders that are neither a partial order nor a total preorder is, therefore, the number of preorders, minus the number of partial orders, minus the number of total preorders, plus the number of total orders: 0, 0, 0, 3, and 85, respectively.
• The number of equivalence relations is the number ofpartitions, which is theBell number.

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

• Order relations, includingstrict orders:
  • Greater than
  • Greater than or equal to
  • Less than
  • Less than or equal to
  • Divides (evenly)
  • Subset of
• Equivalence relations:
  • Equality
  • Parallel with (foraffine spaces)
  • Equinumerosity or "is inbijection with"
  • Isomorphic
  • Equipollent line segments
• Tolerance relation, a reflexive and symmetric relation:
  • Dependency relation, a finite tolerance relation
  • Independency relation, the complement of some dependency relation
• Kinship relations

• Abinary relation in general need not be homogeneous, it is defined to be a subsetR ⊆X ×Y for arbitrary setsX andY.
• Afinitary relation is a subsetR ⊆X₁ × ... ×X_n for somenatural numbern and arbitrary setsX₁, ...,X_n, it is also called ann-ary relation.

• Properties of binary relations

• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from June 2021
• Articles with unsourced statements from June 2020
• Articles with unsourced statements from March 2020