Relation (Mathematics)

In mathematics a relation is a property which holds between certain elements of some set or sets. Examples include equality between numbers or other quantities; comparison or order relations such as "greater than" or "less than" between magnitudes; geometrical relations such as parallel, congruence, similarity or between-ness; abstract concepts such as isomorphism or homeomorphism. A relation may involve one term (unary) in which case we may identify it with a property or predicate; the commonest examples involve two terms (binary); three terms (ternary) and in general we write an n-ary relation.

Relations may be expressed by formulae, geometric concepts or algorithms, but in keeping with the modern definition of mathematics, it is most convenient to identify a relation with the set of values for which it holds true.

Formally, then, we define a binary relation between sets X and Y as a subset of the Cartesian product, ${\displaystyle R\subseteq X\times Y}$. We write ${\displaystyle x~R~y}$ to indicate that ${\displaystyle (x,y)\in R}$, and say that x "stands in the relation R to" y, or that x "is related by R to" y.

The transpose of a relation R between X and Y is the relation ${\displaystyle R^{\top }}$ between Y and X defined by

${\displaystyle R^{\top }=\{(y,x)\in Y\times X:(x,y)\in R\}.\,}$

The composition of a relation R between X and Y and a relation S between Y and Z is

${\displaystyle R\circ S=\{(x,z)\in X\times Z:\exists y\in Y,~(x,y)\in R{\hbox{ and }}(y,z)\in S\}.\,}$

More generally, we define an n-ary relation to be a subset of the product of n sets ${\displaystyle R\subseteq X_{1}\times \cdots \times X_{n}}$.

Relations on a set[edit]

A relation R on a set X is a relation between X and itself, that is, a subset of ${\displaystyle X\times X}$.

• R is reflexive if ${\displaystyle (x,x)\in R}$ for all ${\displaystyle x\in X}$.
• R is irrreflexive if ${\displaystyle (x,x)\not \in R}$ for all ${\displaystyle x\in X}$.
• R is symmetric if ${\displaystyle (x,y)\in R\Leftrightarrow (y,x)\in R}$; that is, ${\displaystyle R=R^{\top }}$.
• R is antisymmetric if ${\displaystyle (x,y)\in R\Rightarrow (y,x)\not \in R}$; that is, R and its transpose are disjoint.
• R is transitive if ${\displaystyle (x,y),(y,z)\in R\Rightarrow (x,z)}$; that is, ${\displaystyle R\circ R\subseteq R}$.

A relation on a set X is equivalent to a directed graph with vertex set X.

Equivalence relation[edit]

For more information, see: Equivalence relation.

An equivalence relation on a set X is one which is reflexive, symmetric and transitive. The identity relation X is the diagonal ${\displaystyle \{(x,x):x\in X\}}$.

Order[edit]

For more information, see: Order (relation).

A (strict) partial order is which is irreflexive, antisymmetric and transitive. A weak partial order is the union of a strict partial order and the identity. The usual notations for a partial order are ${\displaystyle x\leq y}$ or ${\displaystyle x\preceq y}$ for weak orders and ${\displaystyle x<y}$ or ${\displaystyle x\prec y}$ for strict orders.

A total or linear order is one which has the trichotomy property: for any x, y exactly one of the three statements ${\displaystyle x<y}$, ${\displaystyle x=y}$, ${\displaystyle x>y}$ holds.

Functions[edit]

For more information, see: Function (mathematics).

We say that a relation R is functional if it satisfies the condition that every ${\displaystyle x\in X}$ occurs in exactly one pair ${\displaystyle (x,y)\in R}$. We then define the value of the function at x to be that unique y. We thus identify a function with its graph. Composition of relations corresponds to function composition in this definition. The identity relation is functional, and defines the identity function on X.