Editing Binary relation (section)

{{Short description|Relationship between elements of two sets}}
{{hatnote|This article covers advanced notions. For basic topics, see [[Relation (mathematics)]].}}
{{Binary relations}}
[[File:Illustration of a binary relationship R.svg|thumb|An example of a binary relation R between two finite sets of [[natural numbers]], A and B. Note that R is a subset of the [[Cartesian product]], A ''×'' B. In this example, R = {(a, b) ∈ A ''×'' B: a < b}]]
In [[mathematics]], a '''binary relation''' associates some elements of one [[Set (mathematics)|set]] called the ''domain'' with some  elements of another set called the ''codomain''.<ref>{{Cite web|last=Meyer|first=Albert|date=17 November 2021|title=MIT 6.042J Math for Computer Science, Lecture 3T, Slide 2|url=https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/lecture-slides/MIT6_042JS16_Relations.pdf|url-status=live|archive-url=https://web.archive.org/web/20211117161447/https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/lecture-slides/MIT6_042JS16_Relations.pdf |archive-date=2021-11-17 }}</ref> Precisely, a binary relation over sets <math>X</math> and <math>Y</math> is a set of  [[ordered pair]]s <math>(x, y)</math>, where <math>x</math> is an element of <math>X</math> and <math>y</math> is an element of <math>Y</math>.<ref name="Codd1970">{{cite journal |last1=Codd |first1=Edgar Frank 
|authorlink=Edgar F. Codd|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 |archive-url=https://web.archive.org/web/20040908011134/http://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf |archive-date=2004-09-08 |url-status=live |journal=Communications of the ACM |volume=13 |issue=6 |pages=377–387 |doi=10.1145/362384.362685 |s2cid=207549016 |access-date=2020-04-29}}</ref> It encodes the common concept of relation: an element <math>x</math> is ''related'' to an element <math>y</math>, [[if and only if]] the pair <math>(x, y)</math> belongs to the set of ordered pairs that defines the binary relation.

An example of a binary relation is the "[[divides]]" relation over the set of [[prime number]]s <math>\mathbb{P}</math> and the set of [[integer]]s <math>\mathbb{Z}</math>, in which each prime <math>p</math> is related to each integer <math>z</math> that is a [[Divisibility|multiple]] of <math>p</math>, but not to an integer that is not a [[Multiple (mathematics)|multiple]] of <math>p</math>. In this relation, for instance, the prime number <math>2</math> is related to numbers such as <math>-4</math>, <math>0</math>, <math>6</math>, <math>10</math>, but not to <math>1</math> or <math>9</math>, just as the prime number <math>3</math> is related to <math>0</math>, <math>6</math>, and <math>9</math>, but not to <math>4</math> or <math>13</math>.

Binary relations, and especially [[homogeneous relation]]s, are used in many branches of mathematics to model a wide variety of concepts. These include, among others:
* the "[[Inequality (mathematics)|is greater than]]", "[[Equality (mathematics)|is equal to]]", and "divides" relations in [[arithmetic]];
* the "[[Congruence (geometry)|is congruent to]]" relation in [[geometry]];
* the "is adjacent to" relation in [[graph theory]];
* the "is [[orthogonal]] to" relation in [[linear algebra]].

A [[Function (mathematics)|function]] may be defined as a binary relation that meets additional constraints.<ref>{{Cite web|url=https://mathinsight.org/definition/relation|title=Relation definition – Math Insight|website=mathinsight.org|access-date=2019-12-11}}</ref> Binary relations are also heavily used in [[computer science]].

A binary relation over sets <math>X</math> and <math>Y</math> is an element of the [[power set]] of <math>X \times Y.</math> Since the latter set is ordered by [[Inclusion (set theory)|inclusion]] (<math>\subseteq</math>), each relation has a place in the [[Lattice (order)|lattice]] of subsets of <math>X \times Y.</math> A binary relation is called a [[#Homogeneous relation|''homogeneous relation'']] when <math>X = Y</math>. A binary relation is also called a ''heterogeneous relation'' when it is not necessary that <math>X = Y</math>.

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]], and satisfying the laws of an [[algebra of sets]]. Beyond that, operations like the [[converse relation|converse]] of a relation and the [[composition of relations]] are available, satisfying the laws of a [[calculus of relations]], for which there are textbooks by [[Ernst Schröder (mathematician)|Ernst Schröder]],<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> [[Clarence Lewis]],<ref name="Lewis.1918">[[C. I. Lewis]] (1918) [https://archive.org/details/asurveyofsymboli00lewiuoft A Survey of Symbolic Logic], pages 269–279, via internet Archive</ref> and [[Gunther Schmidt]].<ref name=gs>[[Gunther Schmidt]], 2010. ''Relational Mathematics''. Cambridge University Press, {{ISBN|978-0-521-76268-7}}, Chapt. 5</ref> A deeper analysis of relations involves decomposing them into subsets called ''concepts'', and placing them in a [[complete lattice]].

In some systems of [[axiomatic set theory]], relations are extended to [[Class (mathematics)|classes]], which are generalizations of sets. This extension is needed for, among other things, modeling the concepts of "is an element of" or "is a subset of" in set theory, without running into logical inconsistencies such as [[Russell's paradox]].

A binary relation is the most studied special case <math>n = 2</math> of an [[Finitary relation|<math>n</math>-ary relation]] over sets <math>X_1, \dots, X_n</math>, which is a subset of the [[Cartesian product]] <math>X_1 \times \cdots \times X_n.</math><ref name="Codd1970"/>