# Definition:Relation

(Redirected from Definition:Binary Relation)

## Definition

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

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

$\RR = \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).

### Notation

If $\tuple {x, y}$ is an ordered pair such that $\tuple {x, y} \in \RR$, we use the notation:

$s \mathrel \RR t$

or:

$\map \RR {s, t}$

and can say:

$s$ bears $\RR$ to $t$
$s$ stands in the relation $\RR$ to $t$

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

### Truth Set

Let $\RR$ be a relation on $S \times T$.

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

$\map \TT \RR = \set {\tuple {s, t}: s \mathrel \RR t}$

### General Definition

Let $\ds \Bbb 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 $\RR$ defined as:

$\RR := \struct {S_1, S_2, \ldots, S_n, R}$

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

To indicate that $\tuple {s_1, s_2, \ldots, s_n} \in R$, we write:

$\map \RR {s_1, s_2, \ldots, s_n}$

### 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:

$\RR \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.

### 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 $\set {\text {true}, \text {false} }$:

$\RR: S \times T \to \set {\text {true}, \text {false} }: \forall \tuple {s, t} \in S \times T: \map \RR {s, t} = \begin{cases} \text {true} & : \tuple {s, t} \in \RR \\ \text {false} & : \tuple {s, t} \notin \RR \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.

### Class Theoretical Definition

Let $V$ be a basic universe.

In the context of class theory, a relation $\RR$ is a subclass of the Cartesian product $V \times V$.

## Abuse of Notation

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

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

$\tuple {s, t} \in \RR$

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 \RR t$

is produced by the following $\LaTeX$ code:

s \mathrel \RR t