1

Let $S$ and $T$ be sets or classes.

Let $S×T$ be their Cartesian product, ${\{(s,t):s{\in}S {\land}t{\in}T}\}$

Many sources will then define relation on $S×T$ to be any set $R$ such that $R{\subseteq}S×T$.

However, according to this website, that definition is incomplete: relation is an ordered triple $(S,T,R)$. The definition is incomplete, because "this approach leaves the precise nature of $S$ and $T$ undefined." What does this mean?

asdasdf
  • 769

3 Answers3

2

This is really just a minor linguistic issue. The important point is that one often wants to talk about the domain and range of a relation. So the definition of a relation should be stated so that the domain and range are clear. One way to do this is the formalistic "ordered tuple" method such as you found on that web site: a relation is an ordered triple $(S,T,R)$ such that $R \subset S \times T$.

If I were writing a textbook, I would take a different approach altogether in defining a relation, something like this:

  • Given sets $S,T$, a relation between $S$ and $T$ is a subset of their Cartesian product $S \times T$.

Notice what I did there: Instead of building $S$ and $T$ into the notation of the relation, I built them into the terminology of the relation.

By the way, the formalistic "ordered tuple" notation is somewhat common, for example a group is often defined as an ordered triple $(G,\ast,e)$ where $G$ is a set, $\ast$ is a binary operation on $G$, $e \in G$, and a bunch of properties hold.

Lee Mosher
  • 120,280
  • 3
    Although if $R \subseteq S \times T \subseteq U \times V$, you have to take some extra care to ensure the reader can distinguish between "The relation between $S$ and $T$ given by $R$" and "The relation between $U$ and $V$ given by $R$", so the dependent type of relations between $S$ and $T$ isn't a strictly superior notion to the sum type of all relations. –  Nov 28 '16 at 17:05
1

For some formal stuff, this is necessary - or even to properly define peroperties of relations. For example a relation $R\subseteq S\times T$ is called left-total if $\forall s\in S\exists t\in T\colon (s,t)\in R$. But suppose I only give you the relation only as set of pairs $R=\{(1,3),(2,5),(3,1)\}$ without telling you what $S$ and $T$ I have in mind- can you tell me whether this relation is left-total?

Hagen von Eitzen
  • 374,180
1

An important part of the 'identity' of a relation is that it has a 'signature': the order relation $\leq$ on the real numbers is specifically a "Binary relation on $\mathbb{R}$ and $\mathbb{R}$".

We could define two other relations:

  • The binary relation $\star$ on $\mathbb{C}$ and $\mathbb{C}$ given by "$r \star s$ if and only if $r$ and $s$ are both real and $r \leq s$".
  • The unary predicate $P$ on $\mathbb{R} \times \mathbb{R}$ given by "$(r,s)$ has property $P$ if and only if $r \leq s$"

But all of these relations have the same graph! That is, all three of the following sets are equal:

$$ \{ (r,s) \in \mathbb{R} \times \mathbb{R} \mid r \leq s \} $$ $$ \{ (r,s) \in \mathbb{C} \times \mathbb{C} \mid r \star s \} $$ $$ \{ x \in \mathbb{R} \times \mathbb{R} \mid P(x) \} $$

Thus, in isolation, the graph of a relation is insufficient to completely specify what relation is under consideration. That is the point being made.

One method to completely specify the relation is as an object that contains both its signature and its graph; e.g. if I name the set defined above as $R$, then the triple $(\mathbb{R}, \mathbb{R}, R)$ specifies that we are talking about $\leq$. Similarly, $(\mathbb{C}, \mathbb{C}, R)$ indicates $\star$ and $(\mathbb{R} \times \mathbb{R}, R)$ indicates $P$.

Now, in some situations, we might have context that tells us what the signature is, so the graph is enough to specify the relation. Similarly in a situation where we don't care to distinguish between $\leq$, $\star$, and $P$, we again might just use the graph if we feel the need to represent the relation in terms of sets.