Composite maps合成写像ごうせいしゃぞう and inverse maps逆写像ぎゃくしゃぞう

1Introduction

The key to a composite map合成写像ごうせいしゃぞう is to read a map写像しゃぞう as an operation. A map $$f:A\to B$$f:A\to B sends an element元げん of $$A$$A to an element of $$B$$B, and a map $$g:B\to C$$g:B\to C sends that result further into $$C$$C. Performing these two operations in sequence is composition.

An inverse map逆写像ぎゃくしゃぞう is an operation that restores the original input. To restore inputs, no two inputs may have collapsed to the same output, and no element of the output side may be left unused. This condition is exactly bijection全単射ぜんたんしゃ.

Order matters in composition合成ごうせい. The codomain終域しゅういき of the first map must match the domain定義域ていぎいき of the next map. An inverse map exists only when every input-output move can be undone in both directions.

2Terms and definitions

Given maps $$f:A\to B$$f:A\to B and $$g:B\to C$$g:B\to C, define the composite map合成写像ごうせいしゃぞう $$g\circ f:A\to C$$g\circ f:A\to C by

The notation $$g\circ f$$g\circ f means that $$f$$f is applied first and $$g$$g is applied second.

The identity map恒等写像こうとうしゃぞう $${id}_A:A\to A$$\mathrm{id}_A:A\to A on a set $$A$$A is the map defined by

For a map $$f:A\to B$$f:A\to B, if a map $$h:B\to A$$h:B\to A satisfies

then $$h$$h is called the inverse map逆写像ぎゃくしゃぞう of $$f$$f and is written $$f^{-1}$$f^{-1}.

3Basic laws: identity maps恒等写像こうとうしゃぞう and associativity

For a map写像しゃぞう $$f:A\to B$$f:A\to B,

Indeed, for every $$a\in A$$a\in A,

For $$f:A\to B$$f:A\to B, $$g:B\to C$$g:B\to C, and $$h:C\to D$$h:C\to D, composition also satisfies the associative law結合則けつごうそく

because both sides send $$a\in A$$a\in A to $$h\left(g\right(f\left(a\right)\left)\right)$$h(g(f(a))). Thus parentheses do not change the result when three or more maps are composed. This is different from changing the order, as in $$g\circ f$$g\circ f versus $$f\circ g$$f\circ g.

4Method

For a composite map合成写像ごうせいしゃぞう, check the types first. In the standard typed composition型かた付つき合成ごうせい used here, the maps are declared as $$f:A\to B$$f:A\to B and $$g:B\to C$$g:B\to C, so the codomain終域しゅういき of $$f$$f is the same set $$B$$B as the domain定義域ていぎいき of $$g$$g. Then $$f\left(a\right)\in B$$f(a)\in B ensures that $$g\left(f\right(a\left)\right)$$g(f(a)) is defined for every $$a\in A$$a\in A.

For an inverse map逆写像ぎゃくしゃぞう, check that $$f$$f is a bijection全単射ぜんたんしゃ before writing $$f^{-1}$$f^{-1} as a map. A preimage逆像ぎゃくぞう $$f^{-1}\left(T\right)$$f^{-1}(T) is defined for any map, but an inverse map $$f^{-1}:B\to A$$f^{-1}:B\to A exists only when $$f$$f is bijective.

5Intuitive explanation

A composite map合成写像ごうせいしゃぞう is like connecting machines in series. Put an input入力にゅうりょく $$a$$a into the first machine $$f$$f, and the output is $$f\left(a\right)$$f(a). Put that output into the second machine $$g$$g, and the output is $$g\left(f\right(a\left)\right)$$g(f(a)). The whole machine is therefore $$g\circ f$$g\circ f.

An inverse map逆写像ぎゃくしゃぞう is a machine that reconstructs the input from the result. If two inputs collapse to the same output, the output alone cannot tell which input was used. If some element of the codomain終域しゅういき is never reached, there is no input to send back from that element.

Composition connects arrows in sequence. In general, $$g\circ f$$g\circ f and $$f\circ g$$f\circ g are not equal. Sometimes only one of them has compatible types型かた; if the types do not match, that composition is not defined.

6Rigorous explanation: inverse maps and bijections

Suppose $$f:A\to B$$f:A\to B has an inverse map逆写像ぎゃくしゃぞう $$h:B\to A$$h:B\to A. If $$f\left(a_1\right)=f\left(a_2\right)$$f(a_1)=f(a_2), then applying $$h$$h to both sides gives

Since $$h\circ f={id}_A$$h\circ f=\mathrm{id}_A, we get $$a_1=a_2$$a_1=a_2. Hence $$f$$f is an injection単射たんしゃ.

Also, for any $$b\in B$$b\in B, put $$a=h\left(b\right)$$a=h(b). Then $$f\left(a\right)=f\left(h\right(b\left)\right)=b$$f(a)=f(h(b))=b by $$f\circ h={id}_B$$f\circ h=\mathrm{id}_B. Hence $$f$$f is a surjection全射ぜんしゃ.

Conversely, if $$f$$f is a bijection全単射ぜんたんしゃ, then for every $$b\in B$$b\in B there exists $$a\in A$$a\in A with $$f\left(a\right)=b$$f(a)=b, and injectivity単射性たんしゃせい makes this $$a$$a unique. Therefore one can define $$f^{-1}\left(b\right)=a$$f^{-1}(b)=a. Without this uniqueness, the value of the inverse map would not be determined.

By this definition, for every $$a\in A$$a\in A and $$b\in B$$b\in B,

Hence $$f^{-1}\circ f={id}_A$$f^{-1}\circ f=\mathrm{id}_A and $$f\circ f^{-1}={id}_B$$f\circ f^{-1}=\mathrm{id}_B, so the constructed map really is an inverse map.

7Proposition: uniqueness of an inverse map逆写像ぎゃくしゃぞう

If a map写像しゃぞう $$f:A\to B$$f:A\to B has an inverse map逆写像ぎゃくしゃぞう, that inverse is unique. Indeed, if $$h,k:B\to A$$h,k:B\to A are both inverse maps of $$f$$f, the associative law結合則けつごうそく and identity laws恒等則こうとうそく give

This uniqueness justifies the unambiguous notation $$f^{-1}$$f^{-1}.

8Worked example: an inverse map逆写像ぎゃくしゃぞう and two-sided verification

8.1Problem

Let $$A=\{1,2,3\}$$A=\{1,2,3\} and $$B=\{a,b,c\}$$B=\{a,b,c\}. Define $$f:A\to B$$f:A\to B by

Check that $$f$$f is a bijection全単射ぜんたんしゃ, find its inverse map逆写像ぎゃくしゃぞう, and verify that both composites are identity maps恒等写像こうとうしゃぞう.

8.2Explanation

The values $$f\left(1\right),f\left(2\right),f\left(3\right)$$f(1),f(2),f(3) are $$b,c,a$$b,c,a, and they are distinct. Thus distinct inputs入力にゅうりょく are sent to distinct outputs出力しゅつりょく, so $$f$$f is an injection単射たんしゃ.

Every element元げん of the codomain終域しゅういき $$B=\{a,b,c\}$$B=\{a,b,c\} appears as a value of $$f$$f. Therefore $$f$$f is a surjection全射ぜんしゃ. Hence $$f$$f is a bijection全単射ぜんたんしゃ.

The inverse map逆写像ぎゃくしゃぞう is obtained by reading the arrows backward:

For each $$x=1,2,3$$x=1,2,3, one has $$f^{-1}\left(f\right(x\left)\right)=x$$f^{-1}(f(x))=x, and for each $$y=a,b,c$$y=a,b,c, one has $$f\left(f^{-1}\right(y\left)\right)=y$$f(f^{-1}(y))=y. Therefore

9How to distinguish the ideas

• In $$g\circ f$$g\circ f, $$f$$f is applied first and $$g$$g is applied second.
• Before forming a composite map合成写像ごうせいしゃぞう, check that the output type and the next input type match.
• An inverse map逆写像ぎゃくしゃぞう exists only for a bijection全単射ぜんたんしゃ.
• Do not confuse a preimage逆像ぎゃくぞう with an inverse map逆写像ぎゃくしゃぞう.

First check the domain定義域ていぎいき and codomain終域しゅういき. For a candidate inverse $$g:B\to A$$g:B\to A of $$f:A\to B$$f:A\to B, verify both $$g\circ f={id}_A$$g\circ f=\mathrm{id}_A and $$f\circ g={id}_B$$f\circ g=\mathrm{id}_B, not just one side.

10Proof supplement: why composition preserves injectivity and surjectivity

Let $$f:X\to Y$$f:X\to Y and $$g:Y\to Z$$g:Y\to Z. If both $$f$$f and $$g$$g are injective単射たんしゃ, then $$g\circ f$$g\circ f is injective.

To prove this, assume $$(g\circ f)\left(x_1\right)=(g\circ f)\left(x_2\right)$$(g\circ f)(x_1)=(g\circ f)(x_2). This means $$g\left(f\right(x_1\left)\right)=g\left(f\right(x_2\left)\right)$$g(f(x_1))=g(f(x_2)). Since $$g$$g is injective, $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2). Since $$f$$f is injective, $$x_1=x_2$$x_1=x_2. Therefore $$g\circ f$$g\circ f is injective.

If both $$f$$f and $$g$$g are surjective全射ぜんしゃ, then $$g\circ f$$g\circ f is surjective. Take arbitrary $$z\in Z$$z\in Z. Since $$g$$g is surjective, there exists $$y\in Y$$y\in Y with $$g\left(y\right)=z$$g(y)=z. Since $$f$$f is surjective, there exists $$x\in X$$x\in X with $$f\left(x\right)=y$$f(x)=y. Hence $$(g\circ f)\left(x\right)=z$$(g\circ f)(x)=z.

Combining these two statements, the composite of bijections全単射ぜんたんしゃ is again a bijection. The existence of an inverse map is another way to say that injectivity and surjectivity hold at the same time.

11Exercise link

12Related links