1.2: Relations. Mappings

Relations

In §1, we have already considered sets of ordered pairs, such as Cartesian products $A \times B$ or sets of the form $\{(x, y) | P (x, y)\}$ (cf. §§1–3, Problem 7). If the pair $(x, y)$ is an element of such a set $R$, we write

$$(x, y) \in R \label{eq1}$$

treating $(x, y)$ as one thing. Note that this does not imply that $x$ and $y$ taken separately are members of $R$ (in which case we would write $x, y \in R$). We call $x$, $y$ the terms of $(x, y)$.

In mathematics, it is customary to call any set of ordered pairs a relation. For example, all sets listed in Problem 7 of §§1–3 are relations. Since relations are sets, equality $R = S$ for relations means that they consist of the same elements (ordered pairs), i.e., that

$$(x, y) \in R \iff (x, y) \in S$$

If $(x, y) \in R$, we call $y$ an $R$-relative of $x$; we also say that $y$ is $R$-related to $x$ or that the relation $R$ holds between $x$ and $y$ (in this order). Instead of $(x, y) ∈ R$, we also write $xRy$, and often replace “$R$” by special symbols like $<$, $∼$, etc. Thus, in case (i) of Problem 7 above, “$xRy$” means that $x < y$.

Replacing all pairs $(x, y) \in R$ by the inverse pairs $(y, x)$, we obtain a new relation, called the inverse of $R$ and denoted $R^{-1}$. Clearly, $xR^{−1}y$ iff $yRx$; thus

$$R^{-1} = \{(x, y) | yRx\} = \{(y, x) | xRy\}.$$

Hence $R$, in turn, is the inverse of $R^{−1}$; i.e.,

$$(R^{-1})^{-1} = R.$$

For example, the relations $<$ and $>$ between numbers are inverse to each other; so also are the relations $\subseteq$ and $\supseteq$ between sets. (We may treat “$\subseteq$” as the name of the set of all pairs $(X,Y)$ such that $X \subseteq Y$ in a given space.)

If $R$ contains the pairs $(x, x′), (y, y′), (z, z′), . . .$, we shall write

$$R = \begin{pmatrix} x & y & z & \ldots \\ x' & y' & z' & \text{ } \end{pmatrix}; \hskip 5pt e.g., \hskip 5pt R = \begin{pmatrix} 1 & 4 & 1 & 3 \\ 2 & 2 & 1 & 1 \end{pmatrix}.$$

To obtain $R^{−1}$, we simply interchange the upper and lower rows in Equation $\ref{eq1}$.

Definition 1

The set of all left terms $x$ of pairs $(x, y) \in R$ is called the domain of $R$, denoted $D_{R}$. The set of all right terms of these pairs is called the range of $R$, denoted $D_{R}^{′}$. Clearly, $x \in D_{R}$ iff $xRy$ for some $y$. In symbols,

$$x \in D_{R} \iff (\exists y) \hskip 5pt xRy; \hskip 5pt \text{similarly,} \hskip 5pt y \in D_{R}^{'} \iff (\exists x) \hskip 5pt xRy.$$

In Equation $\ref{eq1}$, $D_{R}$ is the upper row, and $D_{R}^{′}$ is the lower row. Clearly,

$$D_{R^{-1}} = D_{R}^{'} \hskip 5pt \text{and} \hskip 5pt D_{R^{-1}}^{'} = D_{R}.$$

For example, if

$$R = \begin{pmatrix} 1 & 4 & 1 \\ 2 & 2 & 1 \end{pmatrix},$$

then

$$D_{R} = D_{R^{-1}}^{'} = \{1, 4\} \hskip 5pt \text{and} \hskip 5pt D_{R}^{'} = D_{R^{-1}} = \{1, 2\}.$$

Definition 2

The image of a set $A$ under a relation $R$ (briefly, the $R-image$ of $A$) is the set of all $R$-relatives of elements of $A$, denoted $R[A]$. The inverse image of $A$ under $R$ is the image of $A$ under the inverse relation, i.e., $R^{−1}[A]$. If A consists of a single element, $A = {x}$, then $R[A]$ and $R^{−1}[A]$ are also written $R[x]$ and $R^{−1}[x]$, respectively, instead of $R[{x}]$ and $R^{−1}[{x}]$.

Example $\PageIndex{1}$

Let

$$R = \begin{pmatrix} 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 7 \\ 1 & 3 & 4 & 5 & 3 & 4 & 1 & 3 & 5 & 1 \end{pmatrix}, \hskip 5pt A = \{1, 2\}, \hskip 5pt B = \{2 , 4\}.$$

Then

$$\begin{array}{lll} R[1] = \{1 , 3 , 4\}; & R[2] = \{3, 5\}; & R[3] = \{1, 3, 4, 5\}; \\ R[5] = \emptyset; & R^{-1}[1] = \{1, 3, 7\}; & R^{-1}[2] = \emptyset; \\ R^{-1}[3] = \{1, 2, 3\}; & R^{-1}[4] = \{1, 3\}; & R[A] = \{1, 3, 4, 5\}; \\ R^{-1}[A] = \{1, 3, 7\}; & R[B] = \{3, 5\}. \end{array}$$

By definition, $R[x]$ is the set of all $R$-relatives of $x$. Thus

$$y \in R[x] \hskip 5pt \text{iff} \hskip 5pt(x, y) \in R; \hskip 5pt \text{i.e.,} \hskip 5pt xRy.$$

More generally, $y \in R[A]$ means that $(x, y) \in R$ for some $x \in A$. In symbols,

$$y \in R[A] \iff (\exists x \in A) (x, y) \in R.$$

Note that $R[A]$ is always defined.

Mappings

We shall now consider an especially important kind of relation.

Definition 3

A relation $R$ is called a mapping (map), or a function, or a transformation, iff every element $x \in D_{R}$ has a unique $R$-relative, so that $R[x]$ consists of a single element. This unique element is denoted by $R(x)$ and is called the function value at $x$ (under $R$). Thus $R(x)$ is the only member of $R[x]$.

If, in addition, different elements of $D_{R}$ have different images, $R$ is called a one-to-one (or one-one) map. In this case,

$$x \neq y\left(x, y \in D_{R}\right) \text{ implies } R(x) \neq R(y);$$

equivalently,

$$R(x)=R(y) \text{ implies } x=y.$$

In other words, no two pairs belonging to $R$ have the same left, or the same right, terms. This shows that $R$ is one to one iff $R^{−1}$, too, is a map. Mappings are often denoted by the letters $f, g, h, F, \psi$, etc.

A mapping $f$ is said to be “from $A$ to $B$” iff $D_{f} = A$ and $D_{f}^{′} \subseteq B$; we then write

$$f : A \rightarrow B \quad\left("f \text{ maps } A \text{ into } B"\right)$$

If, in particular, $D_{f} = A$ and $D_{f}^{′} = B$, we call $f$ a map of $A$ onto $B$, and we write

$$f : A \underset{\mathrm{onto}}{\longrightarrow} B \quad\left("f \text{ maps } A \text{ onto } B"\right)$$

If $f$ is both onto and one to one, we write

$$f : A \longleftrightarrow B$$

($f: A \longleftrightarrow B$ means that $f$ is one to one).

All pairs belonging to a mapping $f$ have the form $(x, f(x))$ where $f(x)$ is the function value at $x$, i.e., the unique $f$-relative of $x, x \in D_{f}$. Therefore, in order to define some function $f$, it suffices to specify its domain $D_{f}$ and the function value $f(x)$ for each $x \in D_{f}$ . We shall often use such definitions. It is customary to say that $f$ is defined on $A$ (or “$f$ is a function on $A$”) iff $A = D_{f}$.

Example $\PageIndex{2}$

(a) The relation
$$R=\{(x, y) | x \text{ is the wife of } y\}$$
is a one-to-one map of the set of all wives onto the set of all husbands. $R^{-1}$ is here a one-to-one map of the set of all husbands $\left(=D_{R}^{\prime}\right)$ onto
the set of all wives $\left(=D_{R}\right)$.

(b) The relation
$$f=\{(x, y) | y \text{ is the father of } x\}$$

is a map of the set of all people onto the set of their fathers. It is not one to one since several persons may have the same father ($f$-relative), and so $x \neq x^{\prime}$ does not imply $f(x) \neq f\left(x^{\prime}\right) .$

(c) Let

$$g=\left( \begin{array}{cccc}{1} & {2} & {3} & {4} \\ {2} & {2} & {3} & {8}\end{array}\right)$$

Then $g$ is a map of $D_{g}=\{1,2,3,4\}$ onto $D_{g}^{\prime}=\{2,3,8\},$ with

$$g(1)=2, g(2)=2, g(3)=3, g(4)=8$$

(As noted above, these formulas may serve to define $g .)$ It is not one to one since $g(1)=g(2),$ so $g^{-1}$ is not a map.

(d) Consider

$$f : N \rightarrow N, \text{ with } f(x)=2x \text{ for each } x \in N$$

By what was said above, $f$ is well defined. It is one to one since $x \neq y$ implies $2 x \neq 2 y .$ Here $D_{f}=N($ the naturals $),$ but $D_{f}^{\prime}$ consists of even naturals only. Thus $f$ is not onto $N$ (it is onto a smaller set, the even naturals); $f^{-1}$ maps the even naturals onto all of $N .$

The domain and range of a relation may be quite arbitrary sets. In particular, we can consider functions $f$ in which each element of the domain $D_{f}$ is itself an ordered pair $(x, y)$ or $n$-tuple $\left(x_{1}, x_{2}, \ldots, x_{n}\right) .$ Such mappings are called functions of two (respectively, $n )$ variables. To any $n$ -tuple $\left(x_{1}, \ldots, x_{n}\right)$ that belongs to $D_{f},$ the function $f$ assigns a unique function value, denoted by $f\left(x_{1}, \ldots, x_{n}\right) .$ It is convenient to regard $x_{1}, x_{2}, \ldots, x_{n}$ as certain variables; then the function value, too, becomes a variable depending on the $x_{1}, \ldots, x_{n}$. Often $D_{f}$ consists of all ordered $n$-tuples of elements taken from a set $A$, i.e., $D_{f}=A^{n}$ (cross-product of $n$ sets, each equal to $A ) .$ The range may be an arbitrary set $B ;$ so $f : A^{n} \rightarrow B$. Similarly, $f : A \times B \rightarrow C$ is a function of two variables, with $D_{f}=A \times B, D_{f}^{\prime} \subseteq C$.

Functions of two variables are also called (binary) operations. For example, addition of natural numbers may be treated as a map $f : N \times N \rightarrow N,$ with $f(x, y)=x+y .$

Definition 4

A relation $R$ is said to be
(i) reflexive iff we have $x R x$ for each $x \in D_{R}$;
(ii) symmetric iff $x R y$ always implies $y R x$;
(iii) transitive iff $x R y$ combined with $y R z$ always implies $x R z$.

$R$ is called an equivalence relation on a set $A$ iff $A=D_{R}$ and $R$ has all the three properties (i), (ii), and (iii). For example, such is the equality relation on $A$ (also called the identity map on $A )$ denoted

$$I_{A}=\{(x, y) | x \in A, x=y\}$$

Equivalence relations are often denoted by special symbols resembling equality, such as $\equiv, \approx, \sim,$ etc. The formula $x R y,$ where $R$ is such a symbol, is read

$$"x \text{ is equivalent (or} R \text{-equivalent) to } y,"$$

and $R[x]=\{y | x R y\}$ (i.e., the $R$-image of $x )$ is called the $R$-equivalence class (briefly $R$-class) of $x$ in $A ;$ it consists of all elements that are $R$-equivalent to $x$ and hence to each other (for $x R y$ and $x R z$ imply first $y R x,$ by symmetry, and hence $y R z,$ by transitivity). Each such element is called a representative of the given $R$-class, or its generator. We often write $[x]$ for $R[x]$.

Example $\PageIndex{3}$

(a') The inequality relation $<$ between real numbers is transitive since

$$x<y \text{ and } y<z \text{ implies } x<z$$

it is neither reflexive nor symmetric. (Why?)

(b') The inclusion relation $\subseteq$ between sets is reflexive (for $A \subseteq A$) and transitive $($ for $A \subseteq B$ and $B \subseteq C$ implies $A \subseteq C),$ but it is not symmetric.

(c') The membership relation $\in$ between an element and a set is neither reflexive nor symmetric nor transitive $(x \in A$ and $A \in \mathcal{M}$ does not imply $x \in \mathcal{M} )$.

(d') Let $R$ be the parallelism relation between lines in a plane, i.e., the set of all pairs $(X, Y),$ where $X$ and $Y$ are parallel lines. Writing $\|$ for $R,$ we have $X\|X, X\| Y$ implies $Y \| X,$ and $(X \| Y$ and $Y$ \| $Z)$ implies $X \| Z,$ so $R$ is an equivalence relation. An $R$ -class here consists of all lines parallel to a given line in the plane.

(e') Congruence of triangles is an equivalence relation. (Why?)

Theorem $\PageIndex{1}$

If $R$ (also written $\equiv$) is an equivalence relation on $A,$ then all R-classes are disjoint from each other, and $A$ is their union.

Proof

Take two $R$-classes, $[p] \neq[q]$. Seeking a contradiction, suppose they are not disjoint, so

$$(\exists x) \quad x \in[p] \text{ and } x \in[q];$$

i.e., $p \equiv x \equiv q$ and hence $p \equiv q .$ But then, by symmetry and transitivity,

$$y \in[p] \Leftrightarrow y \equiv p \Leftrightarrow y \equiv q \Leftrightarrow y \in[q];$$

i.e., $[p]$ and $[q]$ consist of the same elements $y,$ contrary to assumption $[q] \neq[q]$. Thus, indeed, any two (distinct) $R$-classes are disjoint.

Also, by reflexivity,

$$(\forall x \in A) \quad x \equiv x$$

i.e., $x \in[x] .$ Thus each $x \in A$ is in some $R$-class (namely, in $[x] ) ;$ of $A$ is in the union of such classes,

$$A \subseteq \bigcup_{x} R[x]$$

Conversely,

$$(\forall x) \quad R[x] \subseteq A$$

since

$$y \in R[x] \Rightarrow x R y \Rightarrow y R x \Rightarrow(y, x) \in R \Rightarrow y \in D_{R}=A$$

by definition. Thus $A$ contains all $R[x],$ hence their union, and so

$$A=\bigcup_{x} R[x] . \square$$