Definition:Relation/Relation as Subset of Cartesian Product

From ProofWiki
Jump to navigation Jump to search


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$


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

Also defined as

As a sideline, it is noted that some sources define a relation $\mathcal R$ as a set of ordered pairs, with no initial reference to the domain or image of $\mathcal R$.

The domain and image of $\mathcal R$ are then defined as the sets:

\(\displaystyle \Dom {\mathcal R}\) \(=\) \(\displaystyle \set {x: \exists y: \tuple {x, y} \in \mathcal R}\)
\(\displaystyle \Img {\mathcal R}\) \(=\) \(\displaystyle \set {y: \exists x: \tuple {x, y} \in \mathcal R}\)

Using this approach, the cartesian product $S \times T$ of two sets $S$ and $T$ is defined as the relation consisting of all the ordered pairs $\tuple {x, y}$ where $x \in S$ and $y \in T$, rather than defining the cartesian product first and the relation as being a subset of it.

Also see


where the remark is made with reference to the definition of a mapping