Definition:Relation

From ProofWiki
Jump to navigation Jump to search

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

  • 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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Relation&oldid=715885"