10  Inverses and Composites

Associated with every function \(f\), from \(X\) to \(Y\), say, there is a function from \(\mathcal{P}(X)\) to \(\mathcal{P}(Y)\), namely the function (frequently called \(f\) also) that assigns to each subset \(A\) of \(X\) the image subset \(f(A)\) of \(Y\). The algebraic behavior of the mapping \(A \rightarrow f(A)\) leaves something to be desired. It is true that if \(\{ A_{i} \}\) is a family of subsets of \(X\), then \(f( \bigcup_{i} A_{i}) = \bigcup_{i} f( A_{i})\) (proof?), but the corresponding equation for intersections is false in general (example?), and the connection between images and complements is equally unsatisfactory.

A correspondence between the elements of \(X\) and the elements of \(Y\) does always induce a well-behaved correspondence between the subsets of \(X\) and the subsets of \(Y\), not forward, by the formation of images, but backward, by the formation of inverse images. Given a function \(f\) from \(X\) to \(Y\), let \(f^{-1}\), the inverse of \(f\), be the function from \(\mathcal{P}(Y)\) to \(\mathcal{P}(X)\) such that if \(B \subset Y\), then

\[ f^{-1}(B) = \{ x \in X : f(x) \in B \}. \]

In words: \(f^{-1}(B)\) consists of exactly those elements of \(X\) that \(f\) maps into \(B\); the set \(f^{-1}(B)\) is called the inverse image of \(B\) under \(f\). A necessary and sufficient condition that \(f\) map \(X\) onto \(Y\) is that the inverse image under \(f\) of each non-empty subset of \(Y\) be a non-empty subset of \(X\). (Proof?) A necessary and sufficient condition that \(f\) be one-to-one is that the inverse image under \(f\) of each singleton in the range of \(f\) be a singleton in \(X\).

If the last condition is satisfied, then the symbol \(f^{-1}\) is frequently assigned a second interpretation, namely as the function whose domain is the range of \(f\), and whose value for each \(y\) in the range of \(f\) is the unique \(x\) in \(X\) for which \(f(x) = y\). In other words, for one-to-one functions \(f\) we may write \(f^{-1}(y) = x\) if and only if \(f(x) = y\). This use of the notation is mildly inconsistent with our first interpretation of \(f^{-1}\), but the double meaning is not likely to lead to any confusion.

The connection between images and inverse images is worth a moment’s consideration.

If \(B \subset Y\), then

\[ f(f^{-1}(B)) \subset B. \]

Proof. If \(y \in f(f^{-1}(B))\), then \(y = f(x)\) for some \(x\) in \(f^{-1}(B)\); this means that \(y = f(x)\) and \(f(x) \in B\), and therefore \(y \in B\).

If \(f\) maps \(X\) onto \(Y\), then

\[ f(f^{-1}(B)) = B. \]

Proof. If \(y \in B\), then \(y = f(x)\) for some \(x\) in \(X\), and therefore for some \(x\) in \(f^{-1}(B)\); this means that \(y \in f(f^{-1}(B))\).

If \(A \subset X\), then

\[ A \subset f^{-1}(f(A)) \]

Proof. If \(x \in A\), then \(f(x) \in f(A)\); this means that \(x \in f^{-1}(f(A))\).

If \(f\) is one-to-one, then

\[ A = f^{-1}(f(A)) \]

Proof. If \(x \in f^{-1}(f(A))\), then \(f(x) \in f(A)\), and therefore \(f(x) = f(u)\) for some \(u\) in \(A\); this implies that \(x = u\) and hence that \(x \in A\).

The algebraic behavior of \(f^{-1}\) is unexceptionable. If \(\{ B_{i} \}\) is a family of subsets of \(Y\), then

\[ f^{-1}\left( \bigcup_{i} B_{i} \right) = \bigcup_{i}f^{-1}(B_{i}) \]

and

\[ f^{-1}\left( \bigcap_{i} B_{i} \right) = \bigcap_{i}f^{-1}(B_{i}) \]

The proofs are straightforward. If, for instance, \(x \in f^{-1}( \bigcap_{i} B_{i})\), then \(f(x) \in B_{i}\) for all \(i\), so that \(x \in f^{-1}(B_{i})\) for all \(i\), and therefore \(x \in \bigcap_{i}f^{-1}(B_{i})\); all the steps in this argument are reversible. The formation of inverse images commutes with complementation also; i.e.,

\[ f^{-1}(Y - B) = X - f^{-1}(B) \]

for each subset \(B\) of \(Y\). Indeed: if \(x \in f^{-1}(Y - B)\), then \(f(x) \in Y - B\), so that \(x \notin f^{-1}(B)\), and therefore \(x \in X - f^{-1}(B)\); the steps are reversible. (Observe that the last equation is indeed a kind of commutative law: it says that complementation followed by inversion is the same as inversion followed by complementation.)

The discussion of inverses shows that what a function does can in a certain sense be undone; the next thing we shall see is that what two functions do can sometimes be done in one step. If, to be explicit, \(f\) is a function from \(X\) to \(Y\) and \(g\) is a function from \(Y\) to \(Z\), then every element in the range of \(f\) belongs to the domain of \(g\), and, consequently, \(g(f(x))\) makes sense for each \(x\) in \(X\). The function \(h\) from \(X\) to \(Z\), defined by \(h(x) = g(f(x))\) is called the composite of the functions \(f\) and \(g\); it is denoted by \(g \circ f\) or, more simply, by \(gf\). (Since we shall not have occasion to consider any other kind of multiplication for functions, in this book we shall use the latter, simpler notation only.)

Observe that the order of events is important in the theory of functional composition. In order that \(gf\) be defined, the range of \(f\) must be included in the domain of \(g\), and this can happen without it necessarily happening in the other direction at the same time. Even if both \(fg\) and \(gf\) are defined, which happens if, for instance, \(f\) maps \(X\) into \(Y\) and \(g\) maps \(Y\) into \(X\), the functions \(fg\) and \(gf\) need not be the same; in other words, functional composition is not necessarily commutative.

Functional composition may not be commutative, but it is always associative. If \(f\) maps \(X\) into \(Y\), if \(g\) maps \(Y\) into \(Z\), and if \(h\) maps \(Z\) into \(U\), then we can form the composite of \(h\) with \(gf\) and the composite of \(hg\) with \(f\); it is a simple exercise to show that the result is the same in either case.

The connection between inversion and composition is important; something like it crops up all over mathematics. If \(f\) maps \(X\) into \(Y\) and \(g\) maps \(Y\) into \(Z\), then \(f^{-1}\) maps \(\mathcal{P}(Y)\) into \(\mathcal{P}(X)\) and \(g^{-1}\) maps \(\mathcal{P}(Z)\) into \(\mathcal{P}(Y)\). In this situation, the composites that are formable are \(gf\) and \(f^{-1}g^{-1}\); the assertion is that the latter is the inverse of the former. Proof: if \(x \in (gf)^{-1}(C)\), where \(x \in X\) and \(C \subset Z\), then \(g(f(x)) \in C\), so that \(f(x) \in g^{-1}(C)\), and therefore \(x \in f^{-1}(g^{-1}(C))\); the steps of the argument are reversible.

Inversion and composition for functions are special cases of similar operations for relations. Thus, in particular, associated with every relation \(R\) from \(X\) to \(Y\) there is the inverse (or converse) relation \(R^{-1}\) from \(Y\) to \(X\); by definition \(y R^{-1} x\) means that \(xRy\). Example: if \(R\) is the relation of belonging, from \(X\) to \(\mathcal{P}(X)\), then \(R^{-1}\) is the relation of containing, from \(\mathcal{P}(X)\) to \(X\). It is an immediate consequence of the definitions involved that \(\text{dom }R^{-1} = \text{ran } R\) and \(\text{ran }R^{-1} = \text{dom } R\). If the relation \(R\) is a function, then the equivalent assertions \(xRy\) and \(yR^{-1}x\) can be written in the equivalent forms \(R(x) = y\) and \(x \in R^{-1}( \{ y \} )\).

Because of difficulties with commutativity, the generalization of functional composition has to be handled with care. The composite of the relations \(R\) and \(S\) is defined in case \(R\) is a relation from \(X\) to \(Y\) and \(S\) is a relation from \(Y\) to \(Z\). The composite relation \(T\), from \(X\) to \(Z\), is denoted by \(S \circ R\), or, simply, by \(SR\); it is defined so that \(xTz\) if and only if there exists an element \(y\) in \(Y\) such that \(xRy\) and \(ySz\). For an instructive example, let \(R\) mean “son” and let \(S\) mean “brother” in the set of human males, say. In other words, \(xRy\) means that \(x\) is son of \(y\), and \(ySz\) means that \(y\) is a brother of \(z\). In this case the composite relation \(SR\) means “nephew.” (Query: what do \(R^{-1}\), \(S^{-1}\), \(RS\), and \(R^{-1}S^{-1}\) mean?) If both \(R\) and \(S\) are functions, then \(xRy\) and \(ySz\) can be rewritten as \(R(x) = y\) and \(S(y) = z\) respectively. It follows that \(S(R(x)) = z\) if and only if \(xTz\), so that functional composition is indeed a special case of what is sometimes called the relative product.

The algebraic properties of inversion and composition are the same for relations as for functions. Thus, in particular, composition is commutative by accident only, but it is always associative, and it is always connected with inversion via the equation \((SR)^{-1} = R^{-1}S^{-1}\). (Proofs?)

The algebra of relations provides some amusing formulas. Suppose that, temporarily, we consider relations in one set \(X\) only, and, in particular, let the relation of equality in \(X\) (which is the same as the identity mapping on \(X\)). The relation \(I\) acts as a multiplicative unit; this means that \(IR = RI = R\) for every relation \(R\) in \(X\). Query: is there a connection among \(I\), \(RR^{-1}\), and \(R^{-1}R\)? The three defining properties of an equivalence relation can be formulated in algebraic terms as follows: reflexivity means \(I \subset R\), symmetry means \(R \subset R^{-1}\), and transitivity means \(RR \subset R\).

Exercise 10.1 (Assume in each case that \(f\) is a function from \(X\) to \(Y\)) \((i)\) If \(g\) is a function from \(Y\) to \(X\) such that \(gf\) is the identity on \(X\), then \(f\) is one-to-one and \(g\) maps \(Y\) onto \(X\). \((ii)\) A necessary and sufficient condition that \(f(A \cap B) = f(A) \cap f(B)\) for all subsets \(A\) and \(B\) of \(X\) is that \(f\) be one-to-one. \((iii)\) A necessary and sufficient condition that \(f(X - A) \subset Y - f(A)\) for all subsets \(A\) of \(X\) is that \(f\) be one-to-one. \((iv)\) A necessary and sufficient condition that \(Y - f(A) \subset f(X - A)\) for all subsets \(A\) of \(X\) is that \(f\) map \(X\) onto \(Y\).