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\]