# Binary relation

## Relationship between elements of two sets / From Wikipedia, the free encyclopedia

#### Dear Wikiwand AI, let's keep it short by simply answering these key questions:

Can you list the top facts and stats about Binary relation?

Summarize this article for a 10 year old

In mathematics, a **binary relation** associates elements of one set, called the *domain*, with elements of another set, called the *codomain*.^{[1]} A binary relation over sets $X$ and $Y$ is a set of ordered pairs $(x,y)$ consisting of elements $x$ from $X$ and $y$ from $Y$.^{[2]} It encodes the common concept of relation: an element $x$ is *related* to an element $y$, if and only if the pair $(x,y)$ belongs to the set of ordered pairs that defines the binary relation.

Transitive binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ |

An example of a binary relation is the "divides" relation over the set of prime numbers $\mathbb {P}$ and the set of integers $\mathbb {Z}$, in which each prime $p$ is related to each integer $z$ that is a multiple of $p$, but not to an integer that is not a multiple of $p$. In this relation, for instance, the prime number $2$ is related to numbers such as $-4$, $0$, $6$, $10$, but not to $1$ or $9$, just as the prime number $3$ is related to $0$, $6$, and $9$, but not to $4$ or $13$.

Binary relations are used in many branches of mathematics to model a wide variety of concepts. These include, among others:

- the "is greater than", "is equal to", and "divides" relations in arithmetic;
- the "is congruent to" relation in geometry;
- the "is adjacent to" relation in graph theory;
- the "is orthogonal to" relation in linear algebra.

A function may be defined as a binary relation that meets additional constraints.^{[3]} Binary relations are also heavily used in computer science.

A binary relation over sets $X$ and $Y$ is an element of the power set of $X\times Y.$ Since the latter set is ordered by inclusion ($\subseteq$), each relation has a place in the lattice of subsets of $X\times Y.$ A binary relation is called a homogeneous relation when $X=Y$. A binary relation is also called a heterogeneous relation when it is not necessary that $X=Y$.

Since relations are sets, they can be manipulated using set operations, including union, intersection, and complementation, and satisfying the laws of an algebra of sets. Beyond that, operations like the 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,^{[4]} Clarence Lewis,^{[5]} and Gunther Schmidt.^{[6]} 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 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 $n=2$ of an $n$-ary relation over sets $X_{1},\dots ,X_{n}$, which is a subset of the Cartesian product $X_{1}\times \cdots \times X_{n}.$^{[2]}