A function induces a map on subsets, , : just as each element of is sent to an element of , each subset of is sent to its image. On its own this map is mostly a bookkeeping device, but it sets up its counterpart in the opposite direction, which we use constantly.
Definition 1.5.1 (Inverse images). Let . For , the inverse image of under is This defines a map . For , the set , also written , is the fiber of over .
Surjectivity and injectivity can be read off from inverse images: is surjective if and only if the inverse image of every nonempty subset of is nonempty (equivalently, every fiber is nonempty), and is injective if and only if the inverse image of each singleton in the range of is a singleton in (equivalently, every fiber has at most one element).
There are some connections between images and inverse images which we collect here.
Proposition 1.5.2 (Images and inverse images). Let .
- If , then .
- If is surjective and , then .
- If , then .
- If is injective and , then .
- If is a family of subsets of , then and, for , .
- for each .
Proof. (a) An element of has the form with .
(b) If , choose with ; then , so . Together with (a), this gives equality.
(c) If , then , so .
(d) If , then for some , so . Together with (c), this gives equality.
(e) lies in some if and only if lies in some , and lies in every if and only if lies in every .
(f) if and only if . ∎
We now move on to composites.
Definition 1.5.3 (Composition). Let and . Since the codomain of is the domain of , we can apply to the values of . The composite of and is the function often written simply . We read it right to left: applies first, then .
Proposition 1.5.4 (Associativity of composition). Let , , and . Then . Moreover, .
Proof. Both and are functions from to that send each to , so they are the same set of pairs. Similarly, and both send to . ∎
Composition need not be commutative, even when both composites are defined and have the same domain and codomain: for with and , we have but .
Proposition 1.5.5 (Inverse functions). Let .
- If is bijective, then for each there is exactly one with . Setting defines a function , the inverse of , which satisfies and .
- Conversely, if there is a function with and , then is bijective and .
In particular, the inverse of a bijection is a bijection, with .
Proof. (a) Such an exists because is surjective, and it is unique because is injective; so is a function. By construction , and is the unique element sent to , namely .
(b) If , then , so is injective; and every equals , so is surjective. Finally, is an element that sends to , so .
The last statement follows by applying (b) to , with . ∎
Note. The notation now has two meanings: the inverse image map , defined for every , and the inverse function , defined only when is bijective. For bijective the two agree in the sense that . If is only injective, the construction in (a) still gives an inverse function , defined on the range of .
Proposition 1.5.6 (Composites of injections, surjections, and bijections). Let and .
- If and are injective, so is ; if they are surjective, so is . If they are bijective, so is , and .
- For inverse images, for every , for arbitrary and .
Proof. (a) If , injectivity of and then of gives . If , choose with and with ; then . If both maps are bijective, associativity gives and similarly ; now apply Proposition 1.5.5(b).
(b) An element lies in either side exactly when . ∎
In both statements the order reverses: to undo “first , then ” we must undo first, and the composite is in general not even defined. We will meet the same reversal for inverses in a group (Proposition 2.1.5).
1.5.1 Converse and Composite Relations
Functions are relations, after all, and both constructions of this section make sense for relations in general. The converse (or inverse) of a relation is the relation A function is bijective exactly when its converse is a function from to : the domain of the converse is , which is exactly when is surjective, and the uniqueness condition for the converse is injectivity of . In that case the converse is the inverse function of Proposition 1.5.5.
Composition generalizes in the same way. If and are relations, their composite, also called their relative product, is the relation When and are functions, holds exactly when ; so composition of functions is a special case of the relative product.