# Definition:Relation

(Redirected from Definition:Binary Relation)

## Definition

Let $S \times T$ be the cartesian product of two sets or classes $S$ and $T$.

A relation on $S \times T$ is an ordered triple:

$\mathcal R = \tuple {S, T, R}$

where $R \subseteq S \times T$ is a subset.

What this means is that a relation relates (certain) elements of one set or class $S$ with (certain) elements of another, $T$.

Not all elements of $S$ need to be related to every (or even any) element of $T$ (but see Trivial Relation).

When $\tuple {s, t} \in R$, we can write:

$s \mathrel {\mathcal R} t$

or:

$\mathcal R \left({s, t}\right)$

and can say $s$ bears $\mathcal R$ to $t$.

If $\\tuple {s, t}) \notin R$, we can write: $s \not \mathrel {\mathcal R} t$, that is, by drawing a line through the relation symbol.

### Truth Set

Let $\mathcal R$ be a relation on $S \times T$.

The truth set of $\mathcal R$ is the set of all ordered pairs $\tuple {s, t}$ of $S \times T$ such that $s \mathrel {\mathcal R} t$:

$\map {\mathcal T} {\mathcal R} = \set {\tuple {s, t}: s \mathrel {\mathcal R} t}$

### General Definition

Let $\displaystyle \mathbb S = \prod_{i \mathop = 1}^n S_i = S_1 \times S_2 \times \ldots \times S_n$ be the cartesian product of $n$ sets $S_1, S_2, \ldots, S_n$.

An $n$-ary relation on $\Bbb S$ is an ordered $n + 1$-tuple $\mathcal R$ defined as:

$\mathcal R = \left({S_1, S_2, \ldots, S_n, R}\right)$

where $R$ is an arbitrary subset $R \subseteq \Bbb S$.

To indicate that $\left({s_1, s_2, \ldots, s_n}\right) \in R$, we write:

$\mathcal R \left({s_1, s_2, \ldots, s_n}\right)$

### Unary Relation

As a special case of an $n$-ary relation on $S$, note that when $n = 1$ we define a unary relation on $S$ as:

$\mathcal R \subseteq S$

That is, a unary relation is a subset of $S$.

### Endorelation

Let $S \times S$ be the cartesian product of a set or class $S$ with itself.

Let $\mathcal R$ be a relation on $S \times S$.

Then $\mathcal R$ is referred to as an endorelation on $S$.

## Also defined as

### Relation as a Subset of a Cartesian Product

Most treatments of set theory and relation theory define a relation on $S \times T$ to refer to just the truth set itself:

$\mathcal R \subseteq S \times T$

where:

$S \times T$ is the Cartesian product of $S$ and $T$.

Thus under this treatment, $\mathcal R$ is a set of ordered pairs, the first coordinate from $S$ and the second coordinate from $T$.

This approach leaves the precise nature of $S$ and $T$ undefined.

While this definition is usually perfectly adequate, on $\mathsf{Pr} \infty \mathsf{fWiki}$ the full formal definition is preferred.

There may be many places on $\mathsf{Pr} \infty \mathsf{fWiki}$ where this simplified approach is taken. However, there exists an ongoing maintenance task to address this.

### Relation as an Ordered Pair

Some sources define a relation between $S$ and $T$ as an ordered pair:

$\left({S \times T, P \left({s, t}\right)}\right)$

where:

$S \times T$ is the Cartesian product of $S$ and $T$
$P \left({s, t}\right)$ is a propositional function on ordered pairs $\left({s, t}\right)$ of $S \times T$.

Note that this approach leaves the domain and codomain inadequately defined.

This situation arises in the case that $S$ or $T$ are empty, whence it follows that $S \times T$ is empty, but $T$ or $S$ are not themselves uniquely determined.

### Relation as a Mapping

It is possible to define a relation as a mapping from the cartesian product $S \times T$ to the set of truth values $\left\{{\text{true}, \text{false}}\right\}$:

$\mathcal R: S \times T \to \left\{{\text{true}, \text{false}}\right\}: \forall \left({s, t}\right) \in S \times T: \mathcal R \left({s, t}\right) = \begin{cases} \text{true} & : \left({s, t}\right) \in \mathcal R \\ \text{false} & : \left({s, t}\right) \notin \mathcal R \end{cases}$

This is called the characteristic function of the relation.

However, care needs to be taken that a mapping then cannot be defined as a special relation, as this would be circular.

## Notation

By abuse of notation, the usual technique for denoting a relation $\mathcal R$ on $S \times T$ is:

$\mathcal R \subseteq S \times T$

thereby endorsing the approach of defining a relation as a subset of a Cartesian product.

Similarly, it is equally common to denote the expression $s \mathrel {\mathcal R} t$ as:

$\tuple {s, t} \in \mathcal R$

While this approach conflates the relation with its truth set, it is sufficiently convenient and widespread as to be endorsed by $\mathsf{Pr} \infty \mathsf{fWiki}$.

We have not been able to find more mathematically rigorous notations for this that are at the same time not overly unwieldy.

## Also known as

In this context, technically speaking, what has been defined can actually be referred to as a binary relation.

In the field of predicate logic, a relation can be seen referred to as a relational property.

Some sources, for example 1974: P.M. Cohn: Algebra: Volume 1, use the term correspondence for what is defined here as relation, reserving the term relation for what on $\mathsf{Pr} \infty \mathsf{fWiki}$ is defined as endorelation, that is, a relation on $S \times S$ for some set $S$.

As this can cause confusion with the usage of correspondence to mean a relation which is both left-total and right-total, it is recommended that this is not used.

Some sources prefer the term relation between $S$ and $T$ as it can be argued that this provides better emphasis on the existence of the domain and codomain.

1968: Nicolas Bourbaki: Theory of Sets refers to a correspondence between $S$ and $T$.

## Also see

• Results about relations can be found here.

## Linguistic Note

In natural language what we have defined as a relation is usually understood as a relationship.

## Technical Note

The expression:

$s \mathrel {\mathcal R} t$

is produced by the following $\LaTeX$ code:

s \mathrel {\mathcal R} t