# Homogeneous relation > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Homogeneous_relation > Markdown URL: https://mediated.wiki/source/Homogeneous_relation.md > Source: https://en.wikipedia.org/wiki/Homogeneous_relation > Source revision: 1318819548 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Binary relation over a set and itself}} In [mathematics](/source/mathematics), a '''homogeneous relation''' (also called '''endorelation''') on a set ''X'' is a [binary relation](/source/binary_relation) between ''X'' and itself, i.e. it is a subset of the [Cartesian product](/source/Cartesian_product) {{math|''X'' × ''X''}}.{{cite book|author=Michael Winter|title=Goguen Categories: A Categorical Approach to L-fuzzy Relations|year=2007|publisher=Springer|isbn=978-1-4020-6164-6|pages=x-xi}}{{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}}{{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}} This is commonly phrased as "a relation on ''X''"{{cite book |last1=Mordeson |first1=John N. |last2=Nair |first2=Premchand S. |title=Fuzzy Mathematics: An Introduction for Engineers and Scientists |date=8 November 2012 |publisher=Physica |isbn=978-3-7908-1808-6 |page=2 |url=https://books.google.com/books?id=KfLwCAAAQBAJ&pg=PA2 |language=en}} or "a (binary) relation over ''X''".{{cite book |last1=Tanaev |first1=V. |last2=Gordon |first2=W. |last3=Shafransky |first3=Yakov M. |title=Scheduling Theory. Single-Stage Systems |date=6 December 2012 |publisher=Springer Science & Business Media |isbn=978-94-011-1190-4 |page=41 |url=https://books.google.com/books?id=ITDyCAAAQBAJ&pg=PA41 |language=en}}{{cite book |last1=Meyer |first1=Bertrand |title=Touch of Class: Learning to Program Well with Objects and Contracts |date=29 June 2009 |publisher=Springer Science & Business Media |isbn=978-3-540-92145-5 |page=509 |url=https://books.google.com/books?id=AYNKAAAAQBAJ&pg=PA509 |language=en}} An example of a homogeneous relation is the relation of [kinship](/source/kinship), where the relation is between people. Common types of endorelations include [order](/source/order_(mathematics))s, [graph](/source/graph_(discrete_mathematics))s, and [equivalences](/source/equivalence_relation). Specialized studies of [order theory](/source/order_theory) and [graph theory](/source/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](/source/symmetric_relation), and a general endorelation corresponding to a [directed graph](/source/directed_graph). An endorelation ''R'' corresponds to a [logical matrix](/source/logical_matrix) of 0s and 1s, where the expression ''xRy'' (''x'' is ''R''-related to ''y'') corresponds to an edge between ''x'' and ''y'' in the graph, and to a 1 in the [square matrix](/source/square_matrix) of ''R''. It is called an [adjacency matrix](/source/adjacency_matrix) in graph terminology. == Particular homogeneous relations == Some particular homogeneous relations over a set ''X'' (with arbitrary elements {{math|''x''{{sub|1}}}}, {{math|''x''{{sub|2}}}}) are: ;Empty relation : {{math|1=''E'' = [∅](/source/empty_set)}};
that is, {{math|''x''{{sub|1}}''Ex''{{sub|2}}}} holds never; ;Universal relation : {{math|1=''U'' = ''X'' × ''X''}};
that is, {{math|''x''{{sub|1}}''Ux''{{sub|2}}}} holds always; ;Identity relation (see also ''[Identity function](/source/Identity_function)'') : {{math|1=''I'' = {(''x'', ''x'') {{!}} ''x'' ∈ ''X''}}};
that is, {{math|''x''{{sub|1}}''Ix''{{sub|2}}}} holds if and only if {{math|1=''x''{{sub|1}} = ''x''{{sub|2}}}}. === Example === {|class=wikitable style="float:right" |+ 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''' || {{ya}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{ya}} |- | Antarctic ||'''An''' || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{ya}} || {{ya}} |- | Arabian ||'''Ar''' || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} |- | Australian ||'''Au ''' || {{na}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} |- | Caribbean ||'''Ca''' || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} |- | Cocos ||'''Co''' || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} |- | Eurasian ||'''Eu''' || {{ya}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} |- | Indian ||'''In''' || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} |- | Juan de Fuca ||'''Ju''' || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} |- | North american ||'''NA''' || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{ya}} || {{ya}} || {{na}} || {{na}} |- | Nazca ||'''Na''' || {{na}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} |- | Pacific ||'''Pa''' || {{na}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} |- | Philippine ||'''Ph''' || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} |- | South american ||'''SA''' || {{ya}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} |- | Scotia ||'''Sc''' || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} || {{na}} |- | Somali ||'''So''' || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} |} [[File:Tectonic plates (2022).svg|thumb|right|The binary relation that describes whether two [tectonic plates](/source/Plate_tectonics) are in contact is a homogenous relation, because both the first and second argument are from the same set, that is the set of tectonic plates on [Earth](/source/Earth).]] Sixteen large [tectonic plate](/source/tectonic_plate)s of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as a [logical matrix](/source/logical_matrix) with 1 (depicted "13px") indicating contact and 0 ("13px") no contact. This example expresses a symmetric relation. == Properties == {{See also|:Category:Binary relations}} Some important properties that a homogeneous relation {{mvar|R}} over a set {{mvar|X}} may have are: ; {{em|[Reflexive](/source/Reflexive_relation)}} : for all {{math|''x'' ∈ ''X''}}, {{math|''xRx''}}. For example, ≥ is a reflexive relation but > is not. ; {{em|[Irreflexive](/source/Irreflexive_relation)}} (or {{em|strict}}) : for all {{math|''x'' ∈ ''X''}}, not {{math|''xRx''}}. For example, > is an irreflexive relation, but ≥ is not. ; {{em|[Coreflexive](/source/Coreflexive_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} then {{math|1=''x'' = ''y''}}.{{cite conference |last1=Fonseca de Oliveira |first1=J. N. |last2=Pereira Cunha Rodrigues |first2=C. D. J. |name-list-style=amp |year=2004 |url=https://www.researchgate.net/publication/221440123 |title=Transposing Relations: From Maybe Functions to Hash Tables |location=Stirling, Scotland |conference=Mathematics of Program Construction, 7th International Conference |page=337}} 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. ; {{em|[Left quasi-reflexive](/source/Left_quasi-reflexive)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} then {{math|''xRx''}}. ; {{em|[Right quasi-reflexive](/source/Right_quasi-reflexive)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} then {{math|''yRy''}}. ; {{em|[Quasi-reflexive](/source/Quasi-reflexive_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} then {{math|''xRx''}} and {{math|''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 {{math|''xRy''}} defined by {{math|1=''y'' = ''x''2}} is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair {{math|(0, 0)}}, and {{math|(2, 4)}}, but not {{math|(2, 2)}}, respectively. The latter two facts also rule out (any kind of) quasi-reflexivity. ; {{em|[Symmetric](/source/Symmetric_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} then {{math|''yRx''}}. For example, "is a blood relative of" is a symmetric relation, because {{mvar|x}} is a blood relative of {{mvar|y}} if and only if {{mvar|y}} is a blood relative of {{mvar|x}}. ; {{em|[Antisymmetric](/source/Antisymmetric_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''yRx''}} then {{math|1=''x'' = ''y''}}. For example, ≥ is an antisymmetric relation; so is >, but [vacuously](/source/Vacuous_truth) (the condition in the definition is always false).{{cite book|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}} ; {{em|[Asymmetric](/source/Asymmetric_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} then not {{math|''yRx''}}. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.{{cite book|first1=Yves|last1=Nievergelt|title=Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography|publisher=Springer|year=2002|page=[https://books.google.com/books?id=_H_nJdagqL8C&pg=PA158 158]}}. 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 {{math|''xRy''}} defined by {{math|''x'' > 2}} is neither symmetric nor antisymmetric, let alone asymmetric. ; {{em|[Transitive](/source/Transitive_relation)}} : for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''yRz''}} then {{math|''xRz''}}. A transitive relation is irreflexive if and only if it is asymmetric.{{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 – 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". For example, "is ancestor of" is a transitive relation, while "is parent of" is not. ; {{em|[Antitransitive](/source/Antitransitive)}} : for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''yRz''}} then never {{math|''xRz''}}. ; {{em|[Co-transitive](/source/Co-transitivity)}} : if the complement of ''R'' is transitive. That is, for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRz''}}, then {{math|''xRy''}} or {{math|''yRz''}}. This is used in [pseudo-order](/source/pseudo-order)s in constructive mathematics. ; {{em|[Quasitransitive](/source/Quasitransitive_relation)}} : for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''yRz''}} but neither {{math|''yRx''}} nor {{math|''zRy''}}, then {{math|''xRz''}} but not {{math|''zRx''}}. ; {{em|[Transitivity of incomparability](/source/Transitivity_of_incomparability)}} : for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{mvar|x}} and {{mvar|y}} are incomparable with respect to {{mvar|R}} and if the same is true of {{mvar|y}} and {{mvar|z}}, then {{mvar|x}} and {{mvar|z}} are also incomparable with respect to {{mvar|R}}. This is used in [weak ordering](/source/weak_ordering)s. Again, the previous 5 alternatives are not exhaustive. For example, the relation {{math|''xRy''}} if ({{math|1=''y'' = 0}} or {{math|1=''y'' = ''x''+1}}) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them. ; {{em|[Dense](/source/Dense_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}} such that {{math|''xRy''}}, there exists some {{math|''z'' ∈ ''X''}} such that {{math|''xRz''}} and {{math|''zRy''}}. This is used in [dense order](/source/dense_order)s. ; {{em|[Connected](/source/Connected_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|1=''x'' ≠ ''y''}} then {{math|''xRy''}} or {{math|''yRx''}}. This property is sometimes{{citation needed|reason=By whom?|date=June 2021}} called "total", which is distinct from the definitions of "left/right-total" given below. ; {{em|[Strongly connected](/source/Connected_relation)}} : for all {{math|''x'', ''y'' ∈ ''X''}}, {{math|''xRy''}} or {{math|''yRx''}}. This property, too, is sometimes{{citation needed|reason=By whom?|date=June 2021}} called "total", which is distinct from the definitions of "left/right-total" given below. ; {{em|[Trichotomous](/source/Trichotomy_(mathematics))}} : for all {{math|''x'', ''y'' ∈ ''X''}}, exactly one of {{math|''xRy''}}, {{math|''yRx''}} or {{math|1=''x'' = ''y''}} holds. For example, > is a trichotomous relation on the real numbers, while the relation "divides" over the natural numbers is not.Since neither 5 divides 3, nor 3 divides 5, nor 3=5. ; {{em|[Right Euclidean](/source/Euclidean_relation)}} (or just {{em|Euclidean}}) : for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''xRz''}} then {{math|''yRz''}}. For example, = is a Euclidean relation because if {{math|1=''x'' = ''y''}} and {{math|1=''x'' = ''z''}} then {{math|1=''y'' = ''z''}}. ; {{em|Left Euclidean}} : for all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''yRx''}} and {{math|''zRx''}} then {{math|''yRz''}}. ; {{em|[Well-founded](/source/Well-founded_relation)}} : every nonempty subset {{mvar|S}} of {{mvar|X}} contains a [minimal element](/source/Maximal_and_minimal_elements) with respect to {{mvar|R}}. Well-foundedness implies the [descending chain condition](/source/descending_chain_condition) (that is, no infinite chain {{math|... ''x''''n''''R''...''Rx''3''Rx''2''Rx''1}} can exist). If the [axiom of dependent choice](/source/axiom_of_dependent_choice) is assumed, both conditions are equivalent.{{cite web |title=Condition for Well-Foundedness |url=https://proofwiki.org/wiki/Condition_for_Well-Foundedness |website=ProofWiki |access-date=20 February 2019 |archive-date=20 February 2019 |archive-url=https://web.archive.org/web/20190220181521/https://proofwiki.org/wiki/Condition_for_Well-Foundedness |url-status=dead }}{{cite book |last1=Fraisse |first1=R. |title=Theory of Relations |volume=145 |date=15 December 2000 |publisher=Elsevier |isbn=9780444505422 |page=46 |edition=1st |url=https://www.elsevier.com/books/theory-of-relations/fraisse/978-0-444-50542-2 |access-date=20 February 2019}} Moreover, all properties of binary relations in general also may apply to homogeneous relations: ; {{em|Set-like}} : for all {{math|''x'' ∈ ''X''}}, the [class](/source/Class_(set_theory)) of all {{mvar|y}} such that {{math|''yRx''}} is a set. (This makes sense only if relations over proper classes are allowed.) ; {{em|Left-unique}} : for all {{math|''x'', ''z'' ∈ ''X''}} and all {{math|''y'' ∈ ''Y''}}, if {{math|''xRy''}} and {{math|''zRy''}} then {{math|1=''x'' = ''z''}}. ; {{em|Univalent}} : for all {{math|''x'' ∈ ''X''}} and all {{math|''y'', ''z'' ∈ ''Y''}}, if {{math|''xRy''}} and {{math|''xRz''}} then {{math|1=''y'' = ''z''}}.{{cite book |first1=Gunther |last1=Schmidt |first2=Thomas |last2=Strohlein |year=2012 |orig-year=1st pub. 1993 |url={{Google books|ZgarCAAAQBAJ|plainurl=yes}}|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|page=54|location=Berlin, Heidelberg|publisher=Springer}} ; {{em|[Total](/source/total_relation)}} (also called left-total) : for all {{math|''x'' ∈ ''X''}} there exists a {{math|''y'' ∈ ''Y''}} such that {{math|''xRy''}}. This property is different from the definition of ''connected'' (also called ''total'' by some authors).{{citation needed|date=June 2020}} ; {{em|Surjective}} (also called right-total) : for all {{math|''y'' ∈ ''Y''}}, there exists an {{math|''x'' ∈ ''X''}} such that ''xRy''. A {{em|[preorder](/source/preorder)}} is a relation that is reflexive and transitive. A {{em|[total preorder](/source/Weak_ordering)}}, also called {{em|linear preorder}} or {{em|weak order}}, is a relation that is reflexive, transitive, and connected. A {{em|[partial order](/source/Partially_ordered_set)}}, also called {{em|order}},{{citation needed|date=March 2020}} is a relation that is reflexive, antisymmetric, and transitive. A {{em|[strict partial order](/source/Partially_ordered_set)}}, also called {{em|strict order}},{{citation needed|date=March 2020}} is a relation that is irreflexive, antisymmetric, and transitive. A {{em|[total order](/source/total_order)}}, also called {{em|linear order}}, {{em|simple order}}, or {{em|chain}}, is a relation that is reflexive, antisymmetric, transitive and connected.{{cite book |first=Joseph G. |last=Rosenstein |title=Linear orderings |publisher=Academic Press |year=1982 |isbn=0-12-597680-1 |page=4}} A {{em|[strict total order](/source/Total_order)}}, also called {{em|strict linear order}}, {{em|strict simple order}}, or {{em|strict chain}}, is a relation that is irreflexive, antisymmetric, transitive and connected. A {{em|[partial equivalence relation](/source/partial_equivalence_relation)}} is a relation that is symmetric and transitive. An {{em|[equivalence relation](/source/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. A univalent relation may also be called a {{em|[partial function](/source/partial_function)}}. A {{em|(total) [function](/source/function_(mathematics))}} is a partial function that is left-total. An {{em|[injective function](/source/injective_function)}} (or partial function) is one whose inverse is univalent. A {{em|[surjective function](/source/surjective_function)}} is one that is right-total. {| class="wikitable mw-collapsible mw-collapsed" style="float;" |- ! Implications and conflicts between properties of homogeneous binary relations |- | [[File:BinRelProp Impl Confl.gif|thumb|750px|Implications (blue) and conflicts (red) between properties (yellow) of homogeneous binary relations. For example, every asymmetric relation is irreflexive (''"{{color|#808000|ASym}} {{color|#000080|⇒}} {{color|#808000|Irrefl}}"''), and no relation on a non-empty set can be both irreflexive and reflexive (''"{{color|#808000|Irrefl}} {{color|#800000|#}} {{color|#808000|Refl}}"''). Omitting the red edges results in a [Hasse diagram](/source/Hasse_diagram).]] |} == Operations == If ''R'' is a homogeneous relation over a set ''X'' then each of the following is a homogeneous relation over ''X'': ; {{em|[Reflexive closure](/source/Reflexive_closure)}}, ''R''= : Defined as {{math|1 = ''R''= = {(''x'', ''x'') {{!}} ''x'' ∈ ''X''} ∪ ''R''}} or the smallest reflexive relation over ''X'' containing ''R''. This can be proven to be equal to the [intersection](/source/Intersection_(set_theory)) of all reflexive relations containing ''R''. ; {{em|Reflexive reduction}}, ''R''≠ : Defined as {{math|1 = ''R''≠ = ''R'' \ {(''x'', ''x'') {{!}} ''x'' ∈ ''X''}}} or the largest [irreflexive](/source/irreflexive) relation over ''X'' contained in ''R''. ; {{em|[Transitive closure](/source/Transitive_closure)}}, ''R''+ : Defined as the smallest transitive relation over ''X'' containing ''R''. This can be seen to be equal to the intersection of all transitive relations containing ''R''. ; {{em|Reflexive transitive closure}}, ''R''* : Defined as {{math|1=''R''* = (''R''+)=}}, the smallest [preorder](/source/preorder) containing ''R''. ; {{em|[Reflexive transitive symmetric closure](/source/Reflexive_transitive_symmetric_closure)}}, ''R''≡ : Defined as the smallest [equivalence relation](/source/equivalence_relation) over ''X'' containing ''R''. All operations defined in ''{{section link|Binary relation|Operations}}'' also apply to homogeneous relations. : {| class="wikitable sortable" style="text-align:center;" |+ Homogeneous relations by property |- ! ! [Reflexivity](/source/Reflexive_relation) ! [Symmetry](/source/Symmetric_relation) ! [Transitivity](/source/Transitive_relation) ! [Connectedness](/source/Connected_relation) ! Symbol ! Example |- ! [Directed graph](/source/Directed_graph) | | | | | → | |- ! [Undirected graph](/source/Undirected_graph) | | {{yes|Symmetric}} | | | | |- ! [Dependency](/source/Dependency_relation) | {{yes|Reflexive}} | {{yes|Symmetric}} | | | | |- ! [Tournament](/source/Tournament_(graph_theory)) | {{no|Irreflexive}} | {{no|Asymmetric}} | | | | [Pecking order](/source/Pecking_order) |- ! [Preorder](/source/Preorder) | {{yes|Reflexive}} | | {{yes|Transitive}} | | ≤ | [Preference](/source/Preference) |- ! [Total preorder](/source/Weak_ordering) | {{yes|Reflexive}} | | {{yes|Transitive}} | {{yes|Connected}} | ≤ | |- ! [Partial order](/source/Partially_ordered_set) | {{yes|Reflexive}} | {{no|Antisymmetric}} | {{yes|Transitive}} | | ≤ | [Subset](/source/Subset) |- ! [Strict partial order](/source/Partially_ordered_set) | {{no|Irreflexive}} | {{no|Asymmetric}} | {{yes|Transitive}} | | < | Strict subset |- ! [Total order](/source/Total_order) | {{yes|Reflexive}} | {{no|Antisymmetric}} | {{yes|Transitive}} | {{yes|Connected}} | ≤ | [Alphabetical order](/source/Alphabetical_order) |- ! [Strict total order](/source/Total_order) | {{no|Irreflexive}} | {{no|Asymmetric}} | {{yes|Transitive}} | {{yes|Connected}} | < | Strict alphabetical order |- ! [Partial equivalence relation](/source/Partial_equivalence_relation) | | {{yes|Symmetric}} | {{yes|Transitive}} | | | |- ! [Equivalence relation](/source/Equivalence_relation) | {{yes|Reflexive}} | {{yes|Symmetric}} | {{yes|Transitive}} | | ~, ≡ | [Equality](/source/Equality_(mathematics)) |} == Enumeration == The set of all homogeneous relations \mathcal{B}(X) over a set ''X'' is the set {{math|[2''X''×''X''](/source/Power_set)}}, which is a [Boolean algebra](/source/Boolean_algebra_(structure)) augmented with the [involution](/source/Involution_(mathematics)) of mapping of a relation to its [converse relation](/source/converse_relation). Considering [composition of relations](/source/composition_of_relations) as a [binary operation](/source/binary_operation) on \mathcal{B}(X), it forms a [monoid with involution](/source/monoid_with_involution) where the identity element is the identity relation.{{cite book |last1=Schmidt |first1=Gunther |last2=Ströhlein |first2=Thomas |title=Relations and Graphs: Discrete Mathematics for Computer Scientists |date=1993 |publisher=Springer |location=Berlin, Heidelberg |isbn=978-3-642-77968-8 |page=14 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-77968-8_2|chapter-url-access=subscription |language=en |chapter=Homogeneous Relations|doi=10.1007/978-3-642-77968-8_2 }} The number of distinct homogeneous relations over an ''n''-element set is {{math|2''n''2}} {{OEIS|id=A002416}}: {{number of relations}} Notes: * The number of irreflexive relations is the same as that of reflexive relations. * The number of [strict partial orders](/source/Partially_ordered_set) (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 of [partition](/source/Partition_of_a_set)s, which is the [Bell number](/source/Bell_number). The homogeneous relations can be grouped into pairs (relation, [complement](/source/Binary_relation)), except that for {{math|1=''n'' = 0}} the relation is its own complement. The non-symmetric ones can be grouped into [quadruple](/source/4-tuple)s (relation, complement, inverse, inverse complement). == Examples == * [Order relation](/source/Order_relation)s, including [strict order](/source/strict_order)s: ** [Greater than](/source/Greater_than) ** Greater than or equal to ** [Less than](/source/Less_than) ** Less than or equal to ** [Divides](/source/Divides) (evenly) ** [Subset](/source/Subset) of * [Equivalence relation](/source/Equivalence_relation)s: ** [Equality](/source/Equality_(mathematics)) ** [Parallel](/source/Parallel_(geometry)) with (for [affine space](/source/affine_space)s) ** [Equinumerosity](/source/Equinumerosity) or "is in [bijection](/source/bijection) with" ** [Isomorphic](/source/Isomorphism) ** [Equipollent line segments](/source/Equipollence_(geometry)) * [Tolerance relation](/source/Tolerance_relation), a reflexive and symmetric relation: ** [Dependency relation](/source/Dependency_relation), a finite tolerance relation ** [Independency relation](/source/Independency_relation), the complement of some dependency relation * [Kinship relations](/source/Kinship) == Generalizations == * A [binary relation](/source/binary_relation) in general need not be homogeneous, it is defined to be a subset {{nowrap|''R'' ⊆ ''X'' × ''Y''}} for arbitrary sets ''X'' and ''Y''. * A [finitary relation](/source/finitary_relation) is a subset {{nowrap|''R'' ⊆ ''X''1 × ... × ''X''''n''}} for some [natural number](/source/natural_number) ''n'' and arbitrary sets ''X''1, ..., ''X''''n'', it is also called an ''n''-ary relation. == References == {{reflist}} Category:Properties of binary relations --- Adapted from the Wikipedia article [Homogeneous relation](https://en.wikipedia.org/wiki/Homogeneous_relation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Homogeneous_relation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.