Editing Binary relation (section)

== Homogeneous relation ==
{{main|Homogeneous relation}}
A '''homogeneous relation'''<!---keep boldface: [[Homogeneous relation]] redirects to here---> over a set <math>X</math> is a binary relation over <math>X</math> and itself, i.e. it is a subset of the Cartesian product <math>X \times X.</math><ref name="Winter2007"/><ref name="Müller2012">{{cite book|author=M. E. Müller|title=Relational Knowledge Discovery|year=2012|publisher=Cambridge University Press|isbn=978-0-521-19021-3|page=22}}</ref><ref name="PahlDamrath2001-p496">{{cite book|author1=Peter J. Pahl|author2=Rudolf Damrath|title=Mathematical Foundations of Computational Engineering: A Handbook|year=2001|publisher=Springer Science & Business Media|isbn=978-3-540-67995-0|page=496}}</ref> It is also simply called a (binary) relation over <math>X</math>.

A homogeneous relation <math>R</math> over a set <math>X</math> may be identified with a [[Graph theory#Directed graph|directed simple graph permitting loops]], where <math>X</math> is the vertex set and <math>R</math> is the edge set (there is an edge from a vertex <math>x</math> to a vertex <math>y</math> if and only if <math>xRy</math>).
The set of all homogeneous relations <math>\mathcal{B}(X)</math> over a set <math>X</math> is the [[power set]] <math>2^{X \times X}</math> which is a [[Boolean algebra (structure)|Boolean algebra]] augmented with the [[Involution (mathematics)|involution]] of mapping of a relation to its [[converse relation]]. Considering [[composition of relations]] as a [[binary operation]] on <math>\mathcal{B}(X)</math>, it forms a [[semigroup with involution]].

Some important properties that a homogeneous relation <math>R</math> over a set <math>X</math> may have are:
* {{em|[[Reflexive relation|Reflexive]]}}: for all <math>x \in X,</math> <math>xRx</math>. For example, <math>\geq</math> is a reflexive relation but > is not.
* {{em|[[Irreflexive relation|Irreflexive]]}}: for all <math>x \in X,</math> not <math>xRx</math>. For example, <math>></math> is an irreflexive relation, but <math>\geq</math> is not.
* {{em|[[Symmetric relation|Symmetric]]}}: for all <math>x, y \in X,</math> if <math>xRy</math> then <math>yRx</math>. For example, "is a blood relative of" is a symmetric relation.
* {{em|[[Antisymmetric relation|Antisymmetric]]}}: for all <math>x, y \in X,</math> if <math>xRy</math> and <math>yRx</math> then <math>x = y.</math> For example, <math>\geq</math> is an antisymmetric relation.<ref>{{citation|first1=Douglas|last1=Smith|first2=Maurice|last2=Eggen|first3=Richard|last3=St. Andre|title=A Transition to Advanced Mathematics|edition=6th|publisher=Brooks/Cole|year=2006|isbn=0-534-39900-2|page=160}}</ref>
* {{em|[[Asymmetric relation|Asymmetric]]}}: for all <math>x, y \in X,</math> if <math>xRy</math> then not <math>yRx</math>. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.<ref>{{citation|first1=Yves|last1=Nievergelt|title=Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography|publisher=Springer-Verlag|year=2002|page=[https://books.google.com/books?id=_H_nJdagqL8C&pg=PA158 158]}}.</ref> For example, > is an asymmetric relation, but <math>\geq</math> is not.
* {{em|[[Transitive relation|Transitive]]}}: for all <math>x, y, z \in X,</math> if <math>xRy</math> and <math>yRz</math> then <math>xRz</math>. A transitive relation is irreflexive if and only if it is asymmetric.<ref>{{cite book|last1=Flaška|first1=V.|last2=Ježek|first2=J.|last3=Kepka|first3=T.|last4=Kortelainen|first4=J.|title=Transitive Closures of Binary Relations I|year=2007|publisher=School of Mathematics&nbsp;– Physics Charles University|location=Prague|page=1|url=http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|url-status=dead|archive-url=https://web.archive.org/web/20131102214049/http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf|archive-date=2013-11-02}} Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".</ref> For example, "is ancestor of" is a transitive relation, while "is parent of" is not.
* {{em|[[Connected relation|Connected]]}}: for all <math>x, y \in X,</math> if <math>x \neq y</math> then <math>xRy</math> or <math>yRx</math>.
* {{em|[[Connected relation|Strongly connected]]}}: for all <math>x, y \in X,</math> <math>xRy</math> or <math>yRx</math>.
* {{em|[[Dense order#Generalizations|Dense]]}}: for all <math>x, y \in X,</math> if <math>xRy ,</math> then some <math>z \in X</math> exists such that <math>xRz</math> and <math>zRy</math>.

A {{em|[[Partially ordered set#Formal definition|partial order]]}} is a relation that is reflexive, antisymmetric, and transitive. A {{em|[[Partially ordered set#Correspondence of strict and non-strict partial order relations|strict partial order]]}} is a relation that is irreflexive, asymmetric, and transitive. A {{em|[[total order]]}} is a relation that is reflexive, antisymmetric, transitive and connected.<ref>Joseph G. Rosenstein, ''Linear orderings'', Academic Press, 1982, {{ISBN|0-12-597680-1}}, p.&nbsp;4</ref> A {{em|[[Total order#Strict total order|strict total order]]}} is a relation that is irreflexive, asymmetric, transitive and connected.
An {{em|[[equivalence relation]]}} is a relation that is reflexive, symmetric, and transitive.
For example, "<math>x</math> divides <math>y</math>" is a partial, but not a total order on [[natural numbers]] <math>\N,</math> "<math>x < y</math>" is a strict total order on <math>\N,</math> and "<math>x</math> is parallel to <math>y</math>" is an equivalence relation on the set of all lines in the [[Euclidean plane]].

All operations defined in section {{slink||Operations}} also apply to homogeneous relations.
Beyond that, a homogeneous relation over a set <math>X</math> may be subjected to closure operations like:
; {{em|[[Reflexive closure]]}}: the smallest reflexive relation over <math>X</math> containing <math>R</math>,
; {{em|[[Transitive closure]]}}: the smallest transitive relation over <math>X</math> containing <math>R</math>,
; {{em|[[Equivalence closure]]}}: the smallest [[equivalence relation]] over <math>X</math> containing <math>R</math>.