Definition:Relation

From ProofWiki
Jump to: navigation, search

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 = \left({S, T, R}\right)$

where $R \subseteq S \times T$ is a subset.


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 $\left({s, t}\right) \in R$, we can write:

$s \mathrel {\mathcal R} t$

or:

$\mathcal R \left({s, t}\right)$

and can say $s$ bears $\mathcal R$ to $t$.


If $\left({s, t}\right) \notin R$, we can write: $s \not \mathrel{\mathcal R} t$, that is, by drawing a line through the relation symbol.

See Complement of Relation.


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 $\left({s, t}\right)$ of $S \times T$ such that $s \mathrel{\mathcal R} t$:

$\mathcal T \left({\mathcal R}\right) = \left\{ {\left({s, t}\right): s \mathrel {\mathcal R} t}\right\}$


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:

$\left({S \times T, P \left({s, t}\right)}\right)$

where:

$S \times T$ is the Cartesian product of $S$ and $T$
$P \left({s, t}\right)$ is a propositional function on ordered pairs $\left({s, t}\right)$ 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:

$\left({s, t}\right) \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 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$.


Also see

  • Results about relations can be found here.


Linguistic Note

In natural language what we have defined as a relation is usually understood as a relationship.


Technical Note

The expression:

$s \mathrel {\mathcal R} t$

is produced by the following $\LaTeX$ code:

s \mathrel {\mathcal R} t