Relation (mathematics)

A relation between sets X and Y is a subset of the Cartesian product, $R\subseteq X\times Y$. We write $x~R~y$ to indicate that $(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 composition of a relation R between X and Y and a relation S between Y and Z is

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

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

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

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

Relations on a set

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

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

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

Equivalence relation

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

Order

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 $x\leq y$ or $x\preceq y$ for weak orders and $x<y$ or $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 $x<y$, $x=y$, $x>y$ holds.

Functions

We say that a relation R is functional if it satisfies the condition that every $x\in X$ occurs in exactly one pair $(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.