# 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 of the Cartesian product of $S$ and $T$.

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:

$\map {\mathcal R} {s, t}$

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 $\RR$ be a relation on $S \times S$.

Then $\RR$ 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:

$\RR \subseteq S \times T$

where:

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

Thus under this treatment, $\RR$ 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:

$\struct {S \times T, \map P {s, t} }$

where:

$S \times T$ is the Cartesian product of $S$ and $T$
$\map P {s, t}$ is a propositional function on ordered pairs $\tuple {s, t}$ 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 as a relation 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 $\text { 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$.

## Examples

### Subsets of Initial Segment of Natural Numbers

Let $S$ be the set of all the subsets of the initial segment of the natural numbers $\set {1, 2, 3, \ldots, n}$.

Let $\RR$ be the set defined as:

$\RR = \set {\tuple {S_1, S_2}: S_1 \subseteq S_2, S_1 \in S, S_2 \in S}$

Then $\RR$ is a relation on $S$.

### Ordering on Arbitrary Sets of Integers

Let $A = \set {1, 2, 3, 4}$ and $B = \set {1, 2, 3}$ be sets of integers.

Consider the following diagram, where:

$A$ runs along the top
$B$ runs down the left hand side
a relation $\RR$ between $A$ and $B$ is indicated by marking with $\bullet$ every ordered pair $\tuple {a, b} \in A \times B$ which is in the truth set of $\RR$
$\begin {array} {r|rrrr} A \times B & 1 & 2 & 3 & 4 \\ \hline 1 & \bullet & \bullet & \bullet & \circ \\ 2 & \bullet & \bullet & \circ & \circ \\ 3 & \bullet & \circ & \circ & \circ \\ \end {array}$

This relation $\RR$ can be described as:

$\RR = \set {\tuple {x, y} \in A \times B: x + y \le 4}$

## Also see

• Results about relations can be found here.

## Linguistic Note

That which is defined in the mathematical context as a relation is usually referred to in natural language, as a relationship.

## Technical Note

The expression:

$s \mathrel {\mathcal R} t$

is produced by the following $\LaTeX$ code:

s \mathrel {\mathcal R} t