# Definition:Relation

## Contents

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

- $\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 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 $\mathcal R$ be the set defined as:

- $\mathcal R = \set {\paren {S_1, S_2}: S_1 \subseteq S_2, S_1 \in S, S_2 \in S}$

Then $\mathcal R$ 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 $\mathcal R$ 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 $\mathcal R$

- $\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 $\mathcal R$ can be described as:

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

## Also see

- Definition:Trivial Relation, the
**relation**on $S \times T$ in which every element of $S$ is related to every element of $T$.

- 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