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

In the context of class theory, the definition follows the same lines:

Let $V$ be a basic universe.

Let $A$ and $B$ be subclasses of $V$.

A **relation** $\RR$ is a subclass of the Cartesian product $A \times B$.

Note that in this context either or both of $A$ and $B$ can be $V$ itself.

## 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$**.

The word **relationship** is often seen, particularly in the mundane (non-mathematical) context.

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

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

is produced by the following $\LaTeX$ code:

s \mathrel \RR t

## Sources

- 1939: E.G. Phillips:
*A Course of Analysis*(2nd ed.) ... (previous) ... (next): Chapter $\text {I}$: Number: $1.2$ Fundamental notions - 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: $1.5$ Relations - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next):**relation**:**1.** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**relation**