Editing Binary relation (section)

== Types of binary relations ==
<!-- [[functional relation]] redirects to this section -->
[[File:The four types of binary relations.png|thumb|Examples of four types of binary 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).]]

Some important types of binary relations <math>R</math> over sets <math>X</math> and <math>Y</math> are listed below.

Uniqueness properties:
* '''Injective'''<!---[[Injective relation]]---><ref name="vangasteren1990">Van Gasteren 1990, p. 45.</ref> (also called '''left-unique'''<!---[[Left-unique relation]]---><ref name="kilp2000">Kilp, Knauer, Mikhalev 2000, p. 3.</ref>): for all <math>x, y \in X</math> and all <math>z \in Y,</math> if <math>xRz</math> and <math>yRz</math> then <math>x = y</math>. In other words, every element of the codomain has ''at most'' one [[Image (mathematics)|preimage]] element. For such a relation, <math>Y</math> is called ''a [[primary key]]'' of <math>R</math>.<ref name="Codd1970" /> For example, the green and blue binary relations in the diagram are injective, but the red one is not (as it relates both <math>-1</math> and <math>1</math> to <math>1</math>), nor the black one (as it relates both <math>-1</math> and <math>1</math> to <math>0</math>).
* '''[[Functional relationship|Functional]]'''<!---[[Functional relation]]---><ref name="vangasteren1990" /><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> (also called '''right-unique'''<!---[[Right-unique relation]]---><ref name="kilp2000" /> or '''univalent'''<ref>Schmidt 2010, p. 49.</ref>): for all <math>x \in X</math> and all <math>y, z \in Y,</math> if <math>xRy</math> and <math>xRz</math> then <math>y = z</math>. In other words, every element of the domain has ''at most'' one [[Image (mathematics)|image]] element. Such a binary relation is called a {{em|[[partial function]]}} or {{em|partial mapping}}.<ref>Kilp, Knauer, Mikhalev 2000, p. 4.</ref> For such a relation, <math>\{ X \}</math> is called {{em|a primary key}} of <math>R</math>.<ref name="Codd1970" /> For example, the red and green binary relations in the diagram are functional, but the blue one is not (as it relates <math>1</math> to both <math>1</math> and <math>-1</math>), nor the black one (as it relates <math>0</math> to both <math>-1</math> and <math>1</math>).
* '''One-to-one'''<!---[[One-to-one relation]]--->: injective and functional. For example, the green binary relation in the diagram is one-to-one, but the red, blue and black ones are not.
* '''One-to-many'''<!---[[One-to-many relation]]--->: injective and not functional. For example, the blue binary relation in the diagram is one-to-many, but the red, green and black ones are not.
* '''Many-to-one'''<!---[[Many-to-one relation]]--->: functional and not injective. For example, the red binary relation in the diagram is many-to-one, but the green, blue and black ones are not.
* '''Many-to-many'''<!---[[Many-to-many relation]]--->: not injective nor functional. For example, the black binary relation in the diagram is many-to-many, but the red, green and blue ones are not.

Totality properties (only definable if the domain <math>X</math> and codomain <math>Y</math> are specified):
* '''[[Total relation|Total]]'''<!---[[Total relation]]---><ref name="vangasteren1990" /> (also called '''left-total'''<!---[[Left-total relation]]---><ref name="kilp2000" />): for all <math>x \in X</math> there exists a <math>y \in Y</math> such that <math>xRy</math>. In other words, every element of the domain has ''at least'' one image element. In other words, the domain of definition of <math>R</math> is equal to <math>X</math>. This property, is different from the definition of {{em|[[Connected relation|connected]]}} (also called {{em|total}} by some authors){{citation needed|date=June 2020}} in [[Homogeneous relation#Properties|Properties]]. Such a binary relation is called a {{em|[[multivalued function]]}}. For example, the red and green binary relations in the diagram are total, but the blue one is not (as it does not relate <math>-1</math> to any real number), nor the black one (as it does not relate <math>2</math> to any real number). As another example, <math>></math> is a total relation over the [[Integer|integers]]. But it is not a total relation over the positive integers, because there is no <math>y</math> in the positive integers such that <math>1 > y</math>.<ref>{{cite journal|last = Yao|first = Y.Y.|author2=Wong, S.K.M.|title = Generalization of rough sets using relationships between attribute values|journal = Proceedings of the 2nd Annual Joint Conference on Information Sciences|year = 1995|pages = 30–33|url = http://www2.cs.uregina.ca/~yyao/PAPERS/relation.pdf}}.</ref> However, <math><</math> is a total relation over the positive integers, the rational numbers and the real numbers. Every reflexive relation is total: for a given <math>x</math>, choose <math>y = x</math>.
* '''Surjective'''<!---[[Surjective relation]]---><ref name="vangasteren1990" /> (also called '''right-total'''<!---[[Right-total relation]]---><ref name="kilp2000" />): for all <math>y \in Y</math>, there exists an <math>x \in X</math> such that <math>xRy</math>. In other words, every element of the codomain has ''at least'' one preimage element. In other words, the codomain of definition of <math>R</math> is equal to <math>Y</math>. For example, the green and blue binary relations in the diagram are surjective, but the red one is not (as it does not relate any real number to <math>-1</math>), nor the black one (as it does not relate any real number to <math>2</math>).

Uniqueness and totality properties (only definable if the domain <math>X</math> and codomain <math>Y</math> are specified):
* A '''[[Function (mathematics)|function]]''' (also called '''mapping'''<ref name="kilp2000" />): a binary relation that is functional and total. In other words, every element of the domain has ''exactly'' one image element. For example, the red and green binary relations in the diagram are functions, but the blue and black ones are not.
* An '''[[Injective function|injection]]''': a function that is injective. For example, the green relation in the diagram is an injection, but the red one is not; the black and the blue relation is not even a function.
* A '''[[Surjective function|surjection]]''': a function that is surjective. For example, the green relation in the diagram is a surjection, but the red one is not.
* A '''[[Bijection, injection and surjection|bijection]]''': a function that is injective and surjective. In other words, every element of the domain has ''exactly'' one image element and every element of the codomain has ''exactly'' one preimage element. For example, the green binary relation in the diagram is a bijection, but the red one is not.

{{Anchor|set-like-relation}}If relations over proper classes are allowed:
* '''Set-like''' (also called '''local'''): for all <math>x \in X</math>, the [[Class (set theory)|class]] of all <math>y \in Y</math> such that <math>yRx</math>, i.e. <math>\{y \in Y, yRx\}</math>, is a set. For example, the relation <math>\in</math> is set-like, and every relation on two sets is set-like.<ref>{{cite book|title=Set theory: an introduction to independence proofs|page=102 |url=https://archive.org/details/settheoryintrodu0000kune/page/102/mode/2up|url-access=registration|last1=Kunen |first1=Kenneth|publisher=North-Holland|year=1980|isbn=0-444-85401-0|zbl=0443.03021}}</ref> The usual ordering < over the class of [[ordinal number]]s is a set-like relation, while its inverse > is not.{{citation needed|date=February 2022}}