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.
Graph of Relation
Let $\RR$ be a relation on $S \times T$.
The graph 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 particular instance of a 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 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
Equality
Let $S$ and $T$ be sets.
The concept of equality:
- $x = y$
where:
- $x \in S$ and $y \in T$
is an example of a relation on $S \times T$.
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}$
Between
Let $A$, $B$ and $C$ be sets of points on a plane.
Let $\RR \subseteq A \times B \times C$ denote the subset of $A \times B \times C$ defined as:
- $\forall a \in A, b \in B, c \in C: \tuple {a, b, c \in \R}$ if and only if $a$ lies between $b$ and $c$
Then $\RR$ is an example of a ternary relation on $A \times B \times C$.
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.
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): relation: 1.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): relation: 1.
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): relation
- 2021: Richard Earl and James Nicholson: The Concise Oxford Dictionary of Mathematics (6th ed.) ... (previous) ... (next): relation