Skip to main content
\(\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

1.2: Relations. Mappings

  • Page ID
    19022
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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