$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 1.2: Relations. Mappings

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

## 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 , 3 , 4\}; & R = \{3, 5\}; & R = \{1, 3, 4, 5\}; \\ R = \emptyset; & R^{-1} = \{1, 3, 7\}; & R^{-1} = \emptyset; \\ R^{-1} = \{1, 2, 3\}; & R^{-1} = \{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$