View source for Relation (mathematics)

{{Short description|Relationship between two sets, defined by a set of ordered pairs}}
{{about|basic notions of (homogeneous binary) relations in mathematics|a more in-depth treatment|Binary relation|relations on any number of elements|Finitary relation}}

<!---TODO: find a picture that exemplifies a real-world situation--->
[[File:Relación binaria 01.svg|thumb|300px|Illustration of an example relation on a set {{math|1=''A'' = {{mset| a, b, c, d }}}}. An arrow from {{mvar|x}} to {{mvar|y}} indicates that the relation holds between {{mvar|x}} and {{mvar|y}}. The relation is represented by the set 
<!---need to split set manually, since page rendering doesn't insert line breaks--->
{{math|{ (a,a),}} {{math|(a,b),}} {{math|(a,d),}} {{math|(b,a),}} {{math|(b,d),}} {{math|(c,b),}} {{math|(d,c),}} {{math|(d,d) } }} of ordered pairs.]]
In [[mathematics]], a '''relation''' denotes some kind of ''relationship'' between two [[mathematical object|objects]] in a [[Set (mathematics)|set]]<!---is some property that--->, which may or may not hold.<ref>{{cite book|first=Robert R.|last=Stoll|year=1963|title=Set Theory and Logic|publisher=Dover Publications|location=San Francisco, CA|isbn=978-0-486-63829-4}}</ref> As an example, "''is less than''" is a relation on the set of [[natural number]]s; it holds, for instance, between the values {{math|1}} and {{math|3}} (denoted as {{math|1 < 3}}), and likewise between {{math|3}} and {{math|4}} (denoted as {{math|3 < 4}}), but not between the values {{math|3}} and {{math|1}} nor between {{math|4}} and {{math|4}}, that is, {{math|3 < 1}} and {{math|4 < 4}} both evaluate to false.
As another example, "''is sister of''{{-"}} is a relation on the set of all people, it holds e.g. between [[Marie Curie]] and [[Bronisława Dłuska]], and likewise vice versa.
Set members may not be in relation "to a certain degree" – either they are in relation or they are not.

Formally, a relation {{mvar|R}} over a set {{mvar|X}} can be seen as a set of [[ordered pair]]s {{math|(''x'',''y'')}} of members of {{mvar|X}}.{{sfn|Codd|1970|ps=}}
The relation {{mvar|R}} holds between {{mvar|x}} and {{mvar|y}} if {{math|(''x'',''y'')}} is a member of {{mvar|R}}.
For example, the relation "''is less than''" on the natural numbers is an [[infinite set]] {{math|1=''R''<sub>less</sub>}} of pairs of natural numbers that contains both {{math|(1,3)}} and {{math|(3,4)}}, but neither {{math|(3,1)}} nor {{math|(4,4)}}.
The relation "''is a [[nontrivial divisor]] of''{{-"}} on the set of one-digit natural numbers is <!---finite and---> sufficiently small to be shown here:
{{math|1=''R''<sub>dv</sub> = {{mset| (2,4), (2,6), (2,8), (3,6), (3,9), (4,8) }}}}; for example {{math|2}} is a nontrivial divisor of {{math|8}}, but not vice versa, hence {{math|1=(2,8) ∈ ''R''<sub>dv</sub>}}, but {{math|1=(8,2) ∉ ''R''<sub>dv</sub>}}.

If {{mvar|R}} is a relation that holds for {{mvar|x}} and {{mvar|y}} one often writes {{math|''xRy''}}. For most common relations in mathematics, special symbols are introduced, like "{{math|<}}" for ''"is less than"'', and "{{math|{{!}}}}" for ''"is a nontrivial divisor of"'', and, most popular "{{math|1==}}" for ''"is equal to"''. For example, "{{math|1 < 3}}", "{{math|1}} is less than {{math|3}}", and "{{math|1=(1,3) ∈ ''R''<sub>less</sub>}}" mean all the same; some authors also write "{{math|1=(1,3) ∈ (<)}}".

Various properties of relations are investigated.
A relation {{mvar|R}} is reflexive if {{math|''xRx''}} holds for all {{mvar|x}}, and irreflexive if {{math|''xRx''}} holds for no {{mvar|x}}.
It is symmetric if {{math|''xRy''}} always implies {{math|''yRx''}}, and asymmetric if {{math|''xRy''}} implies that {{math|''yRx''}} is impossible.
It is transitive if {{math|''xRy''}} and {{math|''yRz''}} always implies {{math|''xRz''}}.
For example, "''is less than''" is irreflexive, asymmetric, and transitive, but neither reflexive nor symmetric.
"''is sister of''{{-"}} is transitive, but neither reflexive (e.g. [[Pierre Curie]] is not a sister of himself), nor symmetric, nor asymmetric; while being irreflexive or not may be a matter of definition (is every woman a sister of herself?),
"''is ancestor of''{{-"}} is transitive, while "''is parent of''{{-"}} is not.
Mathematical theorems are known about combinations of relation properties, such as "a transitive relation is irreflexive if, and only if, it is asymmetric".

Of particular importance are relations that satisfy certain combinations of properties.
A [[partial order]] is a relation that is reflexive, antisymmetric, and transitive,{{sfn|Halmos|1968|loc=Ch 14|ps=}}
an [[equivalence relation]] is a relation that is reflexive, symmetric, and transitive,{{sfn|Halmos|1968|loc=Ch 7|ps=}}
a [[Function (mathematics)|function]] is a relation that is right-unique and left-total (see [[Relation (mathematics)#Properties of relations|below]]).<ref>{{Cite web|url=https://mathinsight.org/definition/relation|title=Relation definition – Math Insight|website=mathinsight.org|access-date=2019-12-11}}</ref>{{sfn|Halmos|1968|loc=Ch 8|ps=}}

Since relations are sets, they can be manipulated using set operations, including [[union (set theory)|union]], [[intersection (set theory)|intersection]], and [[complement (set theory)|complementation]], leading to the [[algebra of sets]]. Furthermore, the [[calculus of relations]] includes the operations of taking the [[converse relation|converse]] and [[composition of relations|composing relations]].<ref name="Schroder.1895">[[Ernst Schröder (mathematician)|Ernst Schröder]] (1895) [https://archive.org/details/vorlesungenberd03mlgoog Algebra und Logic der Relative], via [[Internet Archive]]</ref><ref name="Lewis.1918">[[C. I. Lewis]] (1918) [https://archive.org/details/asurveyofsymboli00lewiuoft A Survey of Symbolic Logic], pp. 269–279, via internet Archive</ref>{{sfn|Schmidt|2010|loc=Chapt. 5|ps=}}

The above concept of relation{{efn|called "homogeneous binary relation (on sets)" when delineation from its generalizations is important}} has been generalized to admit relations between members of two different sets (''[[heterogeneous relation]]'', like "''lies on''" between the set of all [[point (geometry)|points]] and that of all [[line (geometry)|lines]] in geometry), relations between three or more sets (''[[finitary relation]]'', like ''"person {{math|x}} lives in town {{math|y}} at time {{math|z}}"''), and relations between [[class (mathematics)|classes]]{{efn|a generalization of sets}} (like "''is an element of''{{-"}} on the class of all sets, see ''{{section link|Binary_relation#Sets_versus_classes}}'').

== Definition ==

Given a set {{math|''X''}}, a relation {{math|''R''}} over {{math|''X''}} is a set of [[ordered pair]]s of elements from {{math|''X''}}, formally: {{math|1=''R'' ⊆ {{mset| (''x'',''y'') {{!}} ''x'', ''y'' ∈ ''X'' }}}}.{{sfn|Codd|1970|ps=}}{{sfn|Enderton|1977|loc=Ch 3. p. 40|ps=}}

The statement {{math|(''x'',''y'') ∈ ''R''}} reads "{{math|''x''}} is {{math|''R''}}-related to {{math|''y''}}" and is written in  [[infix notation]] as {{math|''xRy''}}.<ref name="Schroder.1895"/><ref name="Lewis.1918"/> The order of the elements is important; if {{math|''x'' ≠ ''y''}} then {{math|''yRx''}} can be true or false independently of {{math|''xRy''}}. For example, {{math|3}} divides {{math|9}}, but {{math|9}} does not divide {{math|3}}.

== Representation of relations ==

{| style="float: right"
| [[File:Rotated ellipse bg red.svg|thumb|The representation of the relation {{math|1=''R''<sub>el</sub> =}} {{math|{{(}} (''x'',''y'') ∈ '''R''' × '''R''' {{pipe}}}} {{math|''x''<sup>2</sup> + ''xy'' + ''y''<sup>2</sup> {{=}} 1 {{)}}}} as a 2D-plot yields an [[ellipse]].]]
|}
{| class="wikitable" style="float: right"
! {{diagonal split header|''x''|''y''}}
! 1 !! 2 !! 3 !! 4 !! 6 !! 12
|-
! 1
| {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} 
|-
! 2
| {{na}} || {{ya}} || {{na}} || {{ya}} || {{ya}} || {{ya}} 
|-
! 3
| {{na}} || {{na}} || {{ya}} || {{na}} || {{ya}} || {{ya}} 
|-
! 4
| {{na}} || {{na}} || {{na}} || {{ya}} || {{na}} || {{ya}} 
|-
! 6
| {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} || {{ya}} 
|-
! 12
| {{na}} || {{na}} || {{na}} || {{na}} || {{na}} || {{ya}} 
|- 
|COLSPAN=7 | Representation of {{math|''R''<sub>div</sub>}}<br>as a Boolean matrix
|}
{| style="float: right"
| [[File:Relation repr 12div svg.svg|thumb|Representation ''R''<sub>div</sub> as [[Hasse diagram]] (black lines) and [[directed graph]] (all lines)]]
|}

A relation {{math|''R''}} on a finite set {{math|''X''}} may be represented as:
* [[Directed graph]]: Each member of {{math|''X''}} corresponds to a vertex; a directed edge from {{math|''x''}} to {{math|''y''}} exists if and only if {{math|(''x'',''y'') ∈ ''R''}}.
* [[Boolean matrix]]: The members of {{math|''X''}} are arranged in some fixed sequence {{math|''x''<sub>1</sub>}}, ..., {{math|''x''<sub>''n''</sub>}}; the matrix has dimensions {{math|''n'' × ''n''}}, with the element in line {{math|''i''}}, column {{math|''j''}}, being {{text|[[File:Yes check.svg|13px]]}},<!---taken from source code of [[Template:ya]]---> if {{math|(''x''<sub>''i''</sub>,''x''<sub>''j''</sub>) ∈ ''R''}}, and {{text|[[File:Dark Red x.svg|13px]]}},<!---taken from source code of [[Template:na]]---> otherwise.
* [[plot (graphics)|2D-plot]]: As a generalization of a Boolean matrix, a relation on the –infinite– set {{math|'''R'''}} of [[real number]]s can be represented as a two-dimensional geometric figure: using [[Cartesian coordinates]], draw a [[point (geometry)|point]] at {{math|(''x'',''y'')}} whenever {{math|(''x'',''y'') ∈ ''R''}}.
A transitive{{efn|see [[#Properties of relations|below]]}} relation {{math|''R''}} on a finite set {{math|''X''}} may be also represented as
* [[Hasse diagram]]: Each member of {{math|''X''}} corresponds to a vertex; directed edges are drawn such that a [[directed path]] from {{math|''x''}} to {{math|''y''}} exists if and only if {{math|(''x'',''y'') ∈ ''R''}}. Compared to a directed-graph representation, a Hasse diagram needs fewer edges, leading to a less tangled image. Since the relation "''a directed path exists from {{math|x}} to {{math|y}}''" is transitive, only transitive relations can be represented in Hasse diagrams. Usually the diagram is laid out such that all edges point in an upward direction, and the arrows are omitted. 

For example, on the set of all divisors of {{math|12}}, define the relation {{math|''R''<sub>div</sub>}} by 
: {{math|''x'' ''R''<sub>div</sub> ''y''}} if {{math|''x''}} is a divisor of {{math|''y''}} and {{math|''x'' ≠ ''y''}}.
Formally, {{math|1=''X'' = {{mset| 1, 2, 3, 4, 6, 12 }}}} and {{math|1=''R''<sub>div</sub> = {{mset| (1,2), (1,3), (1,4), (1,6), (1,12), (2,4), (2,6), (2,12), (3,6), (3,12), (4,12), (6,12) }}}}.
The representation of {{math|''R''<sub>div</sub>}} as a Boolean matrix is shown in the middle table; the representation both as a Hasse diagram and as a directed graph is shown in the left picture.

The following are equivalent:
* {{math|''x'' ''R''<sub>div</sub> ''y''}} is true.
* {{math|(''x'',''y'') ∈  ''R''<sub>div</sub>}}.
* A path from {{math|''x''}} to {{math|''y''}} exists in the Hasse diagram representing {{math|''R''<sub>div</sub>}}.
* An edge from {{math|''x''}} to {{math|''y''}} exists in the directed graph representing {{math|''R''<sub>div</sub>}}.
* In the Boolean matrix representing {{math|''R''<sub>div</sub>}}, the element in line {{math|''x''}}, column {{math|''y''}} is "{{text|[[File:Yes check.svg|13px]]}}".

As another example, define the relation {{math|''R''<sub>el</sub>}} on {{math|'''R'''}} by
: {{math|''x'' ''R''<sub>el</sub> ''y''}} if {{math|1=''x''<sup>2</sup> + ''xy'' + ''y''<sup>2</sup> = 1}}.
The representation of {{math|''R''<sub>el</sub>}} as a 2D-plot obtains an ellipse, see right picture. Since {{math|'''R'''}} is not finite, neither a directed graph, nor a finite Boolean matrix, nor a Hasse diagram can be used to depict {{math|''R''<sub>el</sub>}}.

== Properties of relations ==
Some important properties that a relation {{mvar|R}} over a set {{mvar|X}} may have are:

; {{em|[[Reflexive relation|Reflexive]]}}: for all {{math|''x'' ∈ ''X''}}, {{math|''xRx''}}. For example, {{math|≥}} is a reflexive relation but {{math|>}} is not.

; {{em|[[Irreflexive relation|Irreflexive]]}} (or {{em|strict}}): for all {{math|''x'' ∈ ''X''}}, not {{math|''xRx''}}. For example, {{math|>}} is an irreflexive relation, but {{math|≥}} is not.

The previous 2 alternatives are not exhaustive; e.g., the red relation {{math|1=''y'' = ''x''<sup>2</sup>}} given in the diagram below is neither irreflexive, nor reflexive, since it contains the pair {{math|(0,0)}}, but not {{math|(2,2)}}, respectively.

; {{em|[[Symmetric relation|Symmetric]]}}: 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 relation|Antisymmetric]]}}: for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''yRx''}} then {{math|1=''x'' = ''y''}}. For example, {{math|≥}} is an antisymmetric relation; so is {{math|>}}, but [[Vacuous truth|vacuously]] (the condition in the definition is always false).{{sfn|Smith|Eggen|St. Andre|2006|p=160|ps=}}

; {{em|[[Asymmetric relation|Asymmetric]]}}: 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.{{sfn|Nievergelt|2002|p=[https://books.google.com/books?id=_H_nJdagqL8C&pg=PA158 158]|ps=}} For example, {{math|>}} is an asymmetric relation, but {{math|≥}} 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 (e.g. {{math|5''R''1}}, but not {{math|1''R''5}}) nor antisymmetric (e.g. {{math|6''R''4}}, but also {{math|4''R''6}}), let alone asymmetric.

; {{em|[[Transitive relation|Transitive]]}}: 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.{{sfn|Flaška|Ježek|Kepka|Kortelainen|2007|loc=p.1 Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".|ps=}} For example, "is ancestor of" is a transitive relation, while "is parent of" is not.

; {{em|[[Connected relation|Connected]]}}: for all {{math|''x'', ''y'' ∈ ''X''}}, if {{math|1=''x'' ≠ ''y''}} then {{math|''xRy''}} or {{math|''yRx''}}. For example, on the natural numbers, {{math|<}} is connected, while "''is a divisor of''{{-"}} is not (e.g. neither {{math|5''R''7}} nor {{math|7''R''5}}).

; {{em|[[Connected relation|Strongly connected]]}}: for all {{math|''x'', ''y'' ∈ ''X''}}, {{math|''xRy''}} or {{math|''yRx''}}. For example, on the natural numbers, {{math|≤}} is strongly connected, but {{math|<}} is not. A relation is strongly connected if, and only if, it is connected and reflexive.

[[File:The four types of binary relations.png|thumb|Examples of four types of relations over the [[real number]]s: one-to-one (in green), one-to-many (in blue), many-to-one (in red), many-to-many (in black). 2D-plot representation is used.]]

Uniqueness properties:
; ''Injective''{{efn|name="heterogeneous"|These properties also generalize to heterogeneous relations.}} (also called ''left-unique''<ref name=kkm/>) : For all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''zRy''}} then {{math|1=''x'' = ''z''}}. For example, the green and blue relations in the diagram are injective, but the red one is not (as it relates both {{math|−1}} and {{math|1}} to {{math|1}}), nor is the black one (as it relates both {{math|−1}} and {{math|1}} to {{math|0}}).
; ''Functional''<ref>Van Gasteren 1990, p. 45.</ref><ref>{{Cite web|title=Functional relation - Encyclopedia of Mathematics|url=https://encyclopediaofmath.org/wiki/Functional_relation|access-date=2024-06-13|website=encyclopediaofmath.org}}</ref><ref>{{Cite web|title=functional relation in nLab|url=https://ncatlab.org/nlab/show/functional+relation|access-date=2024-06-13|website=ncatlab.org}}</ref>{{efn|name="heterogeneous"}} (also called ''right-unique'',<ref name=kkm>{{harvnb|Kilp|Knauer|Mikhalev|2000|p=3}}. The same four definitions appear in the following: {{harvnb|Pahl|Damrath|2001|p=506}}, {{harvnb|Best|1996|pp=19–21}}, {{harvnb|Riemann|1999|pp=21–22}}</ref> ''right-definite''{{sfn|Mäs|2007|ps=}} or ''univalent''{{sfn|Schmidt|2010|loc=Chapt. 5|ps=}}) : For all {{math|''x'', ''y'', ''z'' ∈ ''X''}}, if {{math|''xRy''}} and {{math|''xRz''}} then {{math|1=''y'' = ''z''}}. Such a relation is called a {{em|[[partial function]]}}. For example, the red and green relations in the diagram are functional, but the blue one is not (as it relates {{math|1}} to both {{math|−1}} and {{math|1}}), nor is the black one (as it relates 0 to both −1 and 1).

Totality properties:

; {{em|[[Serial relation|Serial]]}}{{efn|name="heterogeneous"}} (also called {{em|total}} or {{em|left-total}}): For all {{math|''x'' ∈ ''X''}}, there exists some {{math|''y'' ∈ ''X''}} such that {{math|''xRy''}}. Such a relation is called a ''[[multivalued function]]''. For example, the red and green relations in the diagram are total, but the blue one is not (as it does not relate {{math|−1}} to any real number), nor is the black one (as it does not relate {{math|2}} to any real number). As another example, {{math|>}} is a serial relation over the integers. But it is not a serial relation over the positive integers, because there is no {{mvar|y}} in the positive integers such that {{math|1 > ''y''}}.{{sfn|Yao|Wong|1995|ps=}} However, {{math|<}} is a serial relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is serial: for a given {{mvar|x}}, choose {{math|1=''y'' = ''x''}}.

; ''Surjective''{{efn|name="heterogeneous"}} (also called ''right-total''<ref name=kkm/> or ''onto''): For all {{math|''y'' ∈ ''Y''}}, there exists an {{math|''x'' ∈ ''X''}} such that {{math|''xRy''}}. For example, the green and blue relations in the diagram are surjective, but the red one is not (as it does not relate any real number to {{math|−1}}), nor is the black one (as it does not relate any real number to {{math|2}}).

=== Combinations of properties ===

: {| class="wikitable mw-collapsible" style="text-align:center;float:right;"
|+ align="top" | Relations by property
|-
!
! {{vertical header|[[Reflexive relation|Reflexivity]]}}
! {{vertical header|[[Symmetric relation|Symmetry]]}}
! {{vertical header|[[Transitive relation|Transitivity]]}}
! {{vertical header|[[Connected relation|Connectedness]]}}
! {{vertical header|Example}}
|-
! [[Partially ordered set#Formal definition|Partial order]]
| {{yes|Refl}}
| {{no|Antisym}}
| {{yes}}
|
| [[Subset]]
|-
! [[Partially ordered set#Correspondence of strict and non-strict partial order relations|Strict partial order]]
| {{no|Irrefl}}
| {{no|Asym}}
| {{yes}}
|
| Strict subset
|-
! [[Total order]]
| {{yes|Refl}}
| {{no|Antisym}}
| {{yes}}
| {{yes}}
| [[Alphabetical order]]
|-
! [[Total order#Strict total order|Strict total order]]
| {{no|Irrefl}}
| {{no|Asym}}
| {{yes}}
| {{yes}}
| Strict alphabetical order
|-
! [[Equivalence relation]]
| {{yes|Refl}}
| {{yes|Sym}}
| {{yes}}
|
| [[Equality (mathematics)|Equality]]
|}

Relations that satisfy certain combinations of the above properties are particularly useful, and thus have received names by their own.

; {{em|[[Equivalence relation]]}}: A relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and serial, since these properties imply reflexivity.

Orderings:

<!---
; {{em|[[Preorder]]}}: A relation that is reflexive and transitive.
; {{em|[[Weak ordering#Total preorders|Total preorder]]}} (also, {{em|linear preorder}} or {{em|weak order}}): A relation that is reflexive, transitive, and connected.
--->
; {{em|[[Partially ordered set#Formal definition|Partial order]]}}: A relation that is reflexive, antisymmetric, and transitive.

; {{em|[[Partially ordered set#Correspondence of strict and non-strict partial order relations|Strict partial order]]}}: A relation that is irreflexive, asymmetric, and transitive.

; {{em|[[Total order]]}}: A relation that is reflexive, antisymmetric, transitive and connected.{{sfn|Rosenstein|1982|p=4|ps=}}

; {{em|[[Total order#Strict total order|Strict total order]]}}: A relation that is irreflexive, asymmetric, transitive and connected.

<!---
; {{em|[[Partial equivalence relation]]}}: A relation that is symmetric and transitive.
--->
Uniqueness properties:

; ''One-to-one''{{efn|name="heterogeneous"}}: Injective and functional. For example, the green relation in the diagram is one-to-one, but the red, blue and black ones are not.
; ''One-to-many''{{efn|name="heterogeneous"}}: Injective and not functional. For example, the blue relation in the diagram is one-to-many, but the red, green and black ones are not.
; ''Many-to-one''{{efn|name="heterogeneous"}}: Functional and not injective. For example, the red relation in the diagram is many-to-one, but the green, blue and black ones are not.
; ''Many-to-many''{{efn|name="heterogeneous"}}: Not injective nor functional. For example, the black relation in the diagram is many-to-many, but the red, green and blue ones are not.

Uniqueness and totality properties:
; A {{em|[[Function (mathematics)|function]]}}{{efn|name="heterogeneous"}}: A relation that is functional and total. For example, the red and green relations in the diagram are functions, but the blue and black ones are not.
; An {{em|[[Injective function|injection]]}}{{efn|name="heterogeneous"}}: A function that is injective. For example, the green relation in the diagram is an injection, but the red, blue and black ones are not.
; A {{em|[[Surjective function|surjection]]}}{{efn|name="heterogeneous"}}: A function that is surjective. For example, the green relation in the diagram is a surjection, but the red, blue and black ones are not.
; A {{em|[[bijection]]}}{{efn|name="heterogeneous"}}: A function that is injective and surjective. For example, the green relation in the diagram is a bijection, but the red, blue and black ones are not.

== Operations on relations ==

; {{em|Union}}{{efn|name="heterogeneous operation"|This operation also generalizes to heterogeneous relations.}}: If {{math|''R''}} and {{math|''S''}} are relations over {{math|''X''}} then {{math|1 = ''R'' ∪ ''S'' = {{mset| (''x'', ''y'') {{!}} ''xRy'' or ''xSy'' }}}} is the {{em|union relation}} of {{math|''R''}} and {{math|''S''}}. The identity element of this operation is the empty relation. For example, {{math|≤}} is the union of {{math|<}} and {{math|1==}}, and {{math|≥}} is the union of {{math|>}} and {{math|1==}}.

; {{em| Intersection}}{{efn|name="heterogeneous operation"}}: If {{math|''R''}} and {{math|''S''}} are relations over {{math|''X''}} then {{math|1 = ''R'' ∩ ''S'' = {{mset| (''x'', ''y'') {{!}} ''xRy'' and ''xSy'' }}}} is the {{em|intersection relation}} of {{math|''R''}} and {{math|''S''}}. The identity element of this operation is the universal relation. For example, "is a lower card of the same suit as" is the intersection of "is a lower card than" and "belongs to the same suit as".

; {{em| Composition}}{{efn|name="heterogeneous operation"}}: If {{math|''R''}} and {{math|''S''}} are relations over {{math|''X''}} then {{math|1 = ''S'' ∘ ''R'' = {{mset| (''x'', ''z'') {{!}} there exists ''y'' ∈ ''X'' such that ''xRy'' and ''ySz'' }}}} (also denoted by {{math|''R''; ''S''}}) is the [[relative product]] of {{math|''R''}} and {{math|''S''}}. The identity element is the identity relation. The order of {{math|''R''}} and {{math|''S''}} in the notation {{math|''S'' ∘ ''R''}}, used here agrees with the standard notational order for [[composition of functions]]. For example, the composition "is mother of" {{math|∘}} "is parent of" yields "is maternal grandparent of", while the composition "is parent of" {{math|∘}} "is mother of" yields "is grandmother of". For the former case, if {{math|''x''}} is the parent of {{math|''y''}} and {{math|''y''}} is the mother of {{math|''z''}}, then {{math|''x''}} is the maternal grandparent of {{math|''z''}}.

; {{em| Converse}}{{efn|name="heterogeneous operation"}}: If {{math|''R''}} is a relation over sets {{math|''X''}} and {{math|''Y''}} then {{math|1=''R''<sup>T</sup> = {{mset| (''y'', ''x'') {{!}} ''xRy'' }}}} is the ''converse relation'' of {{math|''R''}} over {{math|''Y''}} and {{math|''X''}}. For example, {{math|1==}} is the converse of itself, as is {{math|≠}}, and {{math|<}} and {{math|>}} are each other's converse, as are {{math|≤}} and {{math|≥}}.

; {{em| Complement}}{{efn|name="heterogeneous operation"}}: If {{math|''R''}} is a relation over {{math|''X''}} then {{math|1 = {{overline|''R''}} = {{mset| (''x'', ''y'') {{!}} ''x'', ''y'' ∈ ''X'' and not ''xRy'' }}}} (also denoted by {{math|{{strikethrough|''R''}}}} or {{math|&not;''R''}}) is the ''complementary relation'' of {{math|''R''}}. For example, {{math|1==}} and {{math|≠}} are each other's complement, as are {{math|⊆}} and {{math|⊈}}, {{math|⊇}} and {{math|⊉}}, and {{math|∈}} and {{math|∉}}, and, for [[total order]]s, also {{math|<}} and {{math|≥}}, and {{math|>}} and {{math|≤}}. The complement of the [[converse relation]] {{math|''R''<sup>T</sup>}} is the converse of the complement: <math>\overline{R^\mathsf{T}} = \bar{R}^\mathsf{T}.</math>

; {{em| Restriction}}{{efn|name="heterogeneous operation"}}: If {{math|''R''}} is a relation over {{math|''X''}} and {{math|''S''}} is a subset of {{math|''X''}} then {{math|1=''R''<sub>{{!}}''S''</sub> = {{mset| (''x'', ''y'') {{!}} ''xRy'' and ''x'', ''y'' ∈ ''S'' }}}} is the {{em|{{visible anchor|restriction relation|Restriction relation|Restriction of a homogeneous relation}}}} of {{math|''R''}} to {{math|''S''}}. The expression {{math|1=''R''<sub>{{!}}''S''</sub> = {{mset| (''x'', ''y'') {{!}} ''xRy'' and ''x'' ∈ ''S'' }}}} is the {{em|{{visible anchor|left-restriction relation|Left-restriction relation}}}} of {{math|''R''}} to {{math|''S''}}; the expression {{math|1=''R''<sup>{{!}}''S''</sup> = {{mset| (''x'', ''y'') {{!}} ''xRy'' and ''y'' ∈ ''S'' }}}} is called the {{em|{{visible anchor|right-restriction relation|Right-restriction relation}}}} of {{math|''R''}} to {{math|''S''}}. If a relation is [[Reflexive relation|reflexive]], irreflexive, [[Symmetric relation|symmetric]], [[Antisymmetric relation|antisymmetric]], [[Asymmetric relation|asymmetric]], [[Transitive relation|transitive]], [[Serial relation|total]], [[Trichotomy (mathematics)|trichotomous]], a [[partial order]], [[total order]], [[strict weak order]], [[Strict weak order#Total preorders|total preorder]] (weak order), or an [[equivalence relation]], then so too are its restrictions. However, the transitive closure of a restriction is a subset of the restriction of the transitive closure, i.e., in general not equal. For example, restricting the relation "{{math|''x''}} is parent of {{math|''y''}}" to females yields the relation "{{math|''x''}} is mother of the woman {{math|''y''}}"; its transitive closure does not relate a woman with her paternal grandmother. On the other hand, the transitive closure of "is parent of" is "is ancestor of"; its restriction to females does relate a woman with her paternal grandmother.

A relation {{math|''R''}} over sets {{math|''X''}} and {{math|''Y''}} is said to be {{em|{{visible anchor|contained in|Containment of relations}}}} a relation {{math|''S''}} over {{math|''X''}} and {{math|''Y''}}, written {{math|''R'' ⊆ ''S''}}, if {{math|''R''}} is a subset of {{math|''S''}}, that is, for all {{math|''x'' ∈ ''X''}} and {{math|''y'' ∈ ''Y''}}, if {{math|''xRy''}}, then {{math|''xSy''}}. If {{math|''R''}} is contained in {{math|''S''}} and {{math|''S''}} is contained in {{math|''R''}}, then {{math|''R''}} and {{math|''S''}} are called ''equal'' written {{math|1=''R'' = ''S''}}. If {{math|''R''}} is contained in {{math|''S''}} but {{math|''S''}} is not contained in {{math|''R''}}, then {{math|''R''}} is said to be {{em|{{visible anchor|smaller|Smaller relation}}}} than {{math|''S''}}, written {{math|''R'' ⊊ ''S''}}. For example, on the [[rational number]]s, the relation {{math|>}} is smaller than {{math|≥}}, and equal to the composition {{math|> ∘ >}}.

== Theorems about relations ==
* A relation is asymmetric if, and only if, it is antisymmetric and irreflexive.
* A transitive relation is irreflexive if, and only if, it is asymmetric.
* A relation is reflexive if, and only if, its complement is irreflexive.
* A relation is strongly connected if, and only if, it is connected and reflexive.
* A relation is equal to its converse if, and only if, it is symmetric.
* A relation is connected if, and only if, its complement is anti-symmetric.
* A relation is strongly connected if, and only if, its complement is asymmetric.{{sfn|Schmidt|Ströhlein|1993|ps=}}
* If {{math|''R''}} and {{math|''S''}} are relations over a set {{math|''X''}}, and {{math|''R''}} is contained in {{math|''S''}}, then
** If {{math|''R''}} is reflexive, connected, strongly connected, left-total, or right-total, then so is {{math|''S''}}.
** If {{math|''S''}} is irreflexive, asymmetric, anti-symmetric, left-unique, or right-unique, then so is {{math|''R''}}.
* A relation is reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, connected, strongly connected, and transitive if its converse is, respectively.

== Examples ==
* [[Order relation]]s, including [[strict order]]s:
** [[Greater than]]
** Greater than or equal to
** [[Less than]]
** Less than or equal to
** [[Divides]] (evenly)
** [[Subset]] of
* [[Equivalence relation]]s:
** [[Equality (mathematics)|Equality]]
** [[Parallel (geometry)|Parallel]] with (for [[affine space]]s)
** Is in [[bijection]] with
** [[Isomorphism|Isomorphic]]
* [[Tolerance relation]], a reflexive and symmetric relation:
** [[Dependency relation]], a finite tolerance relation
** [[Independency relation]], the complement of some dependency relation
* [[Kinship#Composition of relations|Kinship relations]]

== Generalizations ==
The above concept of relation has been generalized to admit relations between members of two different sets.
Given sets {{math|''X''}} and {{math|''Y''}}, a ''[[heterogeneous relation]]'' {{math|''R''}} over {{math|''X''}} and {{math|''Y''}} is a subset of {{math|1= {{mset| (''x'',''y'') {{!}} ''x''∈''X'', ''y''∈''Y'' }}}}.{{sfn|Codd|1970|ps=}}<ref>{{harvnb|Enderton|1977|loc=Ch 3. p. 40}}</ref> 
When {{math|1=''X'' = ''Y''}}, the relation concept described above is obtained; it is often called ''homogeneous relation'' (or ''endorelation''){{sfn|Müller|2012|p=22|ps=}}{{sfn|Pahl|Damrath|2001|p=496|ps=}} to distinguish it from its generalization.
The above properties and operations that are marked "{{efn|name="heterogeneous"}}" and "{{efn|name="heterogeneous operation"}}", respectively, generalize to heterogeneous relations.
An example of a heterogeneous relation is "ocean {{math|''x''}} borders continent {{math|''y''}}".
The best-known examples are [[function (mathematics)|functions]]{{efn|that is, right-unique and left-total heterogeneous relations}} with distinct domains and ranges, such as {{math|sqrt : '''N''' → '''R'''{{sub|+}}}}.

== See also ==
* [[Incidence structure]], a heterogeneous relation between set of points and lines
* [[Order theory]], investigates properties of order relations
* [[Relation algebra]]

== Notes ==
{{notelist}} 	

== References ==
{{reflist}}

== Bibliography ==
{{refbegin}}
* {{cite book
 | last1=Best |first1=Eike | author-link=Eike Best
 | year=1996
 | title=Semantics of Sequential and Parallel Programs
 | publisher=Prentice Hall
 | isbn=978-0-13-460643-9
}}
* {{cite journal |last1=Codd |first1=Edgar Frank |date=June 1970 |title=A Relational Model of Data for Large Shared Data Banks |url=https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf |journal=Communications of the ACM |volume=13 |issue=6 |pages=377–387 |doi=10.1145/362384.362685 |s2cid=207549016 |access-date=2020-04-29}}
* {{cite book |last=Codd |first=Edgar Frank |author-link=Edgar F. Codd |year=1990 |title=The Relational Model for Database Management: Version 2 |url=https://dl.acm.org/doi/pdf/10.5555/77708 |location=Boston |publisher=[[Addison-Wesley]] |isbn=978-0201141924 }}
* {{cite book |last=Enderton |first=Herbert |author-link=Herbert Enderton |year=1977 |title=Elements of Set Theory |location=Boston |publisher=[[Academic Press]] |isbn=978-0-12-238440-0}}
* {{cite book
 |last1=Flaška |first1=V.
 |last2=Ježek |first2=J.
 |last3=Kepka |first3=T.
 |last4=Kortelainen |first4=J.
 |year=2007
 |title=Transitive Closures of Binary Relations I
 |publisher=School of Mathematics&nbsp;– Physics Charles University |location=Prague
 |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
}}
* {{cite book |last=Halmos |first=Paul R. |year=1968 |title=[[Naive Set Theory (book)|Naive Set Theory]] |location=Princeton |publisher=Nostrand }}
* {{cite book |last1=Kilp |first1=Mati |last2=Knauer |first2=Ulrich |last3=Mikhalev |first3=Alexander |year=2000 |title=Monoids, Acts and Categories: with Applications to Wreath Products and Graphs |location=Berlin |publisher=[[Walter de Gruyter|De Gruyter]] |isbn=978-3-11-015248-7 }}
* {{citation |last=Mäs |first=Stephan |year=2007 |title=Spatial Information Theory: 8th International Conference, COSIT 2007, Melbourne, Australia, September 19–23, Proceedings |series=Lecture Notes in Computer Science |publisher=Springer |volume=4736 |pages=285–302 |contribution=Reasoning on Spatial Semantic Integrity Constraints |doi=10.1007/978-3-540-74788-8_18 |isbn=978-3-540-74786-4 }}
* {{cite book |last1=Müller |first1=M. E. |year=2012 |title=Relational Knowledge Discovery |publisher=Cambridge University Press |isbn=978-0-521-19021-3 }}
* {{citation |first1=Yves |last1=Nievergelt |year=2002 |title=Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography |publisher=Springer-Verlag }}
* {{cite book
 | first1=Peter J. |last1=Pahl
 | first2=Rudolf |last2=Damrath
 | year=2001
 | title=Mathematical Foundations of Computational Engineering: A Handbook
 | publisher=Springer Science & Business Media
 | isbn=978-3-540-67995-0
}}
* {{cite journal |last=Peirce |first=Charles Sanders |author-link=Charles Sanders Peirce |year=1873 |title=Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic |url= https://archive.org/details/descriptionanot00peirgoog/mode/2up |journal=Memoirs of the American Academy of Arts and Sciences |volume=9 |issue=2 |pages=317–178 |doi= 10.2307/25058006|jstor=25058006 |bibcode=1873MAAAS...9..317P |hdl=2027/hvd.32044019561034 |access-date=2020-05-05 |hdl-access=free }}
* {{cite book
 | last1=Riemann | first1=Robert-Christoph
 | year=1999
 | title=Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus
 | publisher=Herbert Utz Verlag
 | isbn=978-3-89675-629-9
}}
* {{citation |last1=Rosenstein |first1=Joseph G. |year=1982 |title=Linear orderings |publisher=Academic Press |isbn=0-12-597680-1}}
* {{cite book |last=Schmidt |first=Gunther |author-link=Gunther Schmidt |year=2010 |title=Relational Mathematics |url=https://books.google.com/books?id=E4dREBTs5WsC |location=Cambridge |publisher=[[Cambridge University Press]] |isbn=978-0-521-76268-7 }}
* {{cite book
 | last1=Schmidt | first1=Gunther | author1-link=Gunther Schmidt
 | last2=Ströhlein | first2=Thomas
 | year=1993
 | title=Relations and Graphs: Discrete Mathematics for Computer Scientists
 | url=https://books.google.com/books?id=ZgarCAAAQBAJ
 | location=Berlin | publisher=Springer
 | isbn=978-3-642-77970-1
 }}
* {{citation |last1=Smith |first1=Douglas |last2=Eggen |first2=Maurice |last3=St. Andre |first3=Richard |year=2006 |title=A Transition to Advanced Mathematics |edition=6th |publisher=Brooks/Cole |isbn=0-534-39900-2 }}
* {{cite book |last=Van Gasteren |first=Antonetta |author-link= |date=1990 |title=On the Shape of Mathematical Arguments |url= |location=Berlin |publisher=Springer |page= |isbn=9783540528494}}
* {{cite journal |last1=Yao |first1=Y.Y. |last2=Wong |first2=S.K.M. |year=1995 |title = Generalization of rough sets using relationships between attribute values |journal = Proceedings of the 2nd Annual Joint Conference on Information Sciences |pages=30–33 |url=http://www2.cs.uregina.ca/~yyao/PAPERS/relation.pdf }}
{{refend}}

{{Functions navbox}}
{{DEFAULTSORT:Relation}}
[[Category:Mathematical relations| ]]