Map composition

We can define a new map by composing two or more maps. Map composition can be regarded as an operation between maps. As such, we can make an algebra of maps.

Definition (map composition)

Let $f:A\to B$ and $g:B\to C$ be maps. In particular, note that $\text{cod}f=\text{dom}g$. Then, we define a new map, denoted $g\circ f:A\to C$, by

$$(g\circ f)(x)=g(f(x))$$

for each $x\in A$. This new map $g\circ f$ is called the composition of $f$ with $g$. It is convenient to read $g\circ f$ as "$g$ after $f$."

The composition can be graphically represented as in the following commutative diagram:

Remark. As noted in the definition, we can compose $g\circ f$ if and only if $\text{cod}f=\text{dom}g$.

Remark. Some authors (e.g., in computer science) prefer to write $f;g$ ("$f$, then $g$") rather than $g\circ f$.

Example. Suppose that

$$f:\mathbb{Z}\to \mathbb{Z};f(x)=x-1,$$

and

$$g:\mathbb{Z}\to {\mathbb{N}}_0;g(x)=x^2.$$

Then, $$g\circ f:\mathbb{Z}\to {\mathbb{N}}_0;(g\circ f)(x)=x^2-2x+1.$$

(Recall that ${\mathbb{N}}_0=\mathbb{N}\cup \{0\}$.)

Theorem

Let $f:A\to B$ and $g:B\to C$ be maps. 

1. If $f$ and $g$ are injective, then $g\circ f$ is injective.
2. If $f$ and $g$ are surjective, then $g\circ f$ is surjective.

Proof.

1. We assume that $f$ and $g$ are injective. Suppose $a,a^{\prime }\in A$ and $a\ne a^{\prime }$. Since $f$ is injective, we have $f(a)\ne f(a^{\prime })$. Since $g$ is injective, $g(f(a))\ne g(f(a^{\prime }))$. That is, $(g\circ f)(a)\ne (g\circ f)(a^{\prime })$. Thus, $g\circ f$ is injective.
2. We assume that $f$ and $g$ are surjective. Since $g$ is surjective, for any $c\in C$, there exists some $b\in B$ such that $c=g(b)$. For this $b$, since $f$ is surjective, there exists some $a\in A$ such that $b=f(a)$. In summary, for any $c\in C$, there exists some $a\in A$ such that $c=g(f(a))$, that is, $(g\circ f)(a)=c$. Hence, $g\circ f$ is surjective.

■

Corollary

The composition of two bijections is a bijection.

Theorem

Let $f:A\to B$, $g:B\to C$, and $h:C\to D$ be maps. Then, we have

$$(h\circ g)\circ f=h\circ (g\circ f).$$

In other words, map composition is associative. This can be graphically represented in the following diagram:

Proof. For any $x\in A$, we have

$$\begin{array}{rcl}((h\circ g)\circ f)(x)& =& (h\circ g)(f(x))\\ & =& h(g(f(x))\\ & =& h((g\circ f)(x))\\ & =& (h\circ (g\circ f))(x).\end{array}$$ 

■

Because of this associativity, we can denote both $(h\circ g)\circ f$ and $h\circ (g\circ f)$ as $h\circ g\circ h$ without parentheses.

Theorem

Let $\alpha :X\to Y$ be a map. The following are equivalent

1. The map $\alpha$ is a bijection.
2. There exists a map $\beta :Y\to X$ such that $\beta \circ \alpha ={\text{Id}}_X$ and $\alpha \circ \beta ={\text{Id}}_Y$.

Proof. ($1⟹2$) Suppose $\alpha$ is a bijection. This means that for each $y\in Y$, there exists a unique $x\in X$ such that $y=\alpha (x)$. Using this unique $x$, let us define $\beta (y)=x$. Thus, for each $y\in Y$, $\beta (y)\in X$ is uniquely determined, and hence $\beta :Y\to X$ is a well-defined map. By this definition, for each $x\in X$, we have $\beta (\alpha (x))=x$. Thus, $\beta \circ \alpha ={\text{Id}}_X.$ Similarly, for each $y\in Y$, we have $\alpha (\beta (y))=y$, and hence $\alpha \circ \beta ={\text{Id}}_Y.$

($2⟹1$) Suppose that such $\beta$ as given above exists. Then, for each $y\in Y$, $(\alpha \circ \beta )(y)=\alpha (\beta (y))={\text{Id}}_Y(y)=y$ so that $y\in \text{im}\alpha$. This means that $Y\subset \text{im}\alpha$. $\text{im}\alpha \subset Y$ is trivial. Hence, $Y=\text{im}\alpha$, and $\alpha$ is surjective. Next, suppose that $x,x^{\prime }\in X$ and $\alpha (x)=\alpha (x^{\prime })$. Apply $\beta$ on both sides, and we have $\beta (\alpha (x))=\beta (\alpha (x^{\prime }))$. But, $\beta \circ \alpha ={\text{Id}}_X$ so we have ${\text{Id}}_X(x)={\text{Id}}_X(x^{\prime })$, and hence $x=x^{\prime }$. Thus, $\alpha$ is injective. In summary, $\alpha$ is both surjective and injective, so it is bijective.

■

Remark. The map $\beta$ in the above theorem is called the inverse map of $\alpha$ and is denoted as ${\alpha }^{-1}$. It should be obvious that the inverse map of $\beta ={\alpha }^{-1}$ is $\alpha$. □