Before describing what a relation is generally, let us define a more specific kind of a relation: a binary relation. Basically, a binary relation $R$ involves objects coming from two collections $A,B$, where the objects are paired up so that each pair consists of an object from $A$, and an object from $B$.

More formally, a binary relation is a subset $R$ of the Cartesian product of two sets $A$ and $B$. One may write

to indicate that the ordered pair $(a,b)$ is an element of $R$. A subset of $A\times A$ is simply called a binary relation on $A$. If $R$ is a binary relation on $A$, then we write

to mean $a_{1}\>R\>a_{2},a_{2}\>R\>a_{3},\ldots,$ and $a_{{n-1}}\>R\>a_{n}$.

Given a binary relation $R\subseteq A\times B$, the domain $\operatorname{dom}(R)$ of $R$ is the set of elements in $A$ forming parts of the pairs in $R$. In other words,

and the range $\operatorname{ran}(R)$ of $R$ is the set of parts of pairs of $R$ coming from $B$:

An example of a binary relation is the less-than relation on the integers, i.e., $<$ $\subseteq\mathbb{Z}\times\mathbb{Z}$. $(1,2)\in$ $<$, but $(2,1)\notin$ $<$.

Remarks.

1. 1.

   In set theory, a binary relation is simply a set of ordered pairs (of sets or classes, depending on the axiom system used). Notice that, unlike the previous definition, sets (or classes) $A$ and $B$ are not specified in advance. Given a (binary) relation $R$, the domain of $R$ is the set (or class) of elements $a$ such that $aRb$ for some $b$, and the range of $R$ is the set (or class) or elements $b$ such that $aRb$ for some $a$. The union and the domain and the range of $R$ is called the field of $R$.

2. 2.

   It may be possible to define a relation over a class. For example, if $\mathcal{C}$ is the class of all sets, then $\in$ can be thought of as a binary relation on $\mathcal{C}$.

3. 3.

   In term rewriting theory, a binary relation on a set is sometimes called a reduction, and is written $\to$. This is to signify that $a\to b$ means that the element $a$ is being “reduced” to $b$ via $\to$.

From the definition of a binary relation, we can easily generalize it to that of an arbitrary relation. Since a binary relation involves two sets, an arbitrary relation involves an arbitrary collection of sets. More specifically, a relation $R$ is a subset of some Cartesian product of a collection of sets. In symbol, this is

where each $A_{i}$ is a set, indexed by some set $I$.

From this more general definition, we see that a binary relation is just a relation where $I$ has two elements. In addition, an $n$-ary relation is a relation where the cardinality of $I$ is $n$ ($n$ finite). In symbol, we have

It is not hard to see that any $n$-ary relation where $n>1$ can be viewed as a binary relation in $n-1$ different ways, for

where $j$ ranges from $1$ through $n-1$.

A common name for a $3$-ary relation is a ternary relation. It is also possible to have a $1$-ary relation, or commonly known as a unary relation, which is nothing but a subset of some set.

Remarks.

1. 1.

   Following from the first remark from the previous section, relations of higher arity can be inductively defined: for $n>1$, an $(n+1)$-ary relation is a binary relation whose domain is an $n$-ary relation. In this setting, a “unary relation” and relations whose arity is of “arbitrary” cardinality are not defined.

2. 2.

   A relation can also be viewed as a function (which itself is a relation). Let $R\subseteq A:=\prod_{{i\in I}}A_{i}$. As a subset of $A$, $R$ can be identified with the characteristic function

   $$\chi_{R}:A\to\{0,1\},$$

   where $\chi_{R}(x)=1$ iff $x\in R$ and $\chi_{R}(x)=0$ otherwise. Therefore, an $n$-ary relation is equivalent to an $(n+1)$-ary characteristic function. From this, one may say that a $0$-ary, or a nullary relation is a unary characteristic function. In other words, a nullary relation is just a an element in $\{0,1\}$ (or truth/falsity).