A relation from a set $A$ to a set $B$ specifies which ordered pairs $(a,b)$ are related. Formally, a relation is a subset

$$R\subseteq A\times B.$$

If $(a,b)\in R$, we can write

$$aRb.$$

Examples

On the integers, the relation “is less than” contains pairs $(a,b)$ for which $a<b$.

A relation does not have to associate each input with exactly one output. One element can be related to many elements, to none, or several elements can be related to the same element.

Relations on one set

When

$$R\subseteq A\times A,$$

we call $R$ a relation on $A$.

Important properties include:

• reflexive: $aRa$ for every $a$;
• symmetric: $aRb$ implies $bRa$;
• antisymmetric: $aRb$ and $bRa$ imply $a=b$;
• transitive: $aRb$ and $bRc$ imply $aRc$.

Different combinations of these properties define structures such as equivalence relations and partial orders.