Maps写像しゃぞう, injections単射たんしゃ, and surjections全射ぜんしゃ: basic exercises

1Corresponding lectures講義こうぎ

2Order note

This exercise mainly treats maps写像しゃぞう, injections単射たんしゃ, and surjections全射ぜんしゃ, but it also briefly uses inverse maps逆写像ぎゃくしゃぞう and composite maps合成写像ごうせいしゃぞう. An inverse map is obtained by reading the arrows of a bijection全単射ぜんたんしゃ backward, and a composite map $$g\circ f$$g\circ f applies $$f$$f first and then $$g$$g.

3Exercise strategy

For a map写像しゃぞう, check whether each input入力にゅうりょく has exactly one output出力しゅつりょく. For an injection単射たんしゃ, look for collisions. For a surjection全射ぜんしゃ, check whether every element of the codomain終域しゅういき is reached.

4Problem 1

Let $$f:\{1,2,3\}\to \{a,b,c\}$$f:\{1,2,3\}\to\{a,b,c\} be defined by $$f\left(1\right)=a$$f(1)=a, $$f\left(2\right)=b$$f(2)=b, and $$f\left(3\right)=b$$f(3)=b. Is $$f$$f an injection単射たんしゃ or a surjection全射ぜんしゃ?

4.1Answer

Because $$f\left(2\right)=f\left(3\right)=b$$f(2)=f(3)=b with $$2\ne 3$$2\ne3, the map is not an injection単射たんしゃ. Also, no input入力にゅうりょく reaches $$c$$c, so the map is not a surjection全射ぜんしゃ.

4.2Explanation

An injection単射たんしゃ preserves distinctions between inputs, while a surjection全射ぜんしゃ covers the codomain終域しゅういき.

4.3Common mistake

Do not confuse the range値域ちいき $$\{a,b\}$$\{a,b\} with the codomain終域しゅういき $$\{a,b,c\}$$\{a,b,c\}.

5Problem 2

Let $$g:\{1,2,3\}\to \{a,b,c\}$$g:\{1,2,3\}\to\{a,b,c\} be defined by $$g\left(1\right)=b$$g(1)=b, $$g\left(2\right)=c$$g(2)=c, and $$g\left(3\right)=a$$g(3)=a. Find the inverse map逆写像ぎゃくしゃぞう of $$g$$g.

5.1Answer

The map sends distinct inputs入力にゅうりょく to distinct outputs出力しゅつりょく and reaches every element of the codomain終域しゅういき. Hence $$g$$g is a bijection全単射ぜんたんしゃ. Its inverse map逆写像ぎゃくしゃぞう is

5.2Explanation

An inverse map逆写像ぎゃくしゃぞう exists only for a bijection全単射ぜんたんしゃ. First verify bijectivity, then read each arrow backward.

5.3Common mistake

Checking only injectivity単射性たんしゃせい is not enough to construct an inverse map; surjectivity全射性ぜんしゃせい is also required.

To construct an inverse map, every output must determine a unique input, and every element of the codomain終域しゅういき must actually be used. Thus both injectivity and surjectivity must be checked.

6Problem 3

Let $$f:\mathbb{Z}\to \mathbb{Z}$$f:\mathbb Z\to\mathbb Z be defined by $$f\left(n\right)=n+1$$f(n)=n+1. Is $$f$$f an injection単射たんしゃ or a surjection全射ぜんしゃ?

6.1Answer

If $$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2), then $$n_1+1=n_2+1$$n_1+1=n_2+1, so $$n_1=n_2$$n_1=n_2. Thus $$f$$f is an injection単射たんしゃ.

For arbitrary $$m\in \mathbb{Z}$$m\in\mathbb Z, put $$n=m-1\in \mathbb{Z}$$n=m-1\in\mathbb Z. Then $$f\left(n\right)=m$$f(n)=m. Thus $$f$$f is a surjection全射ぜんしゃ, and therefore a bijection全単射ぜんたんしゃ.

6.2Explanation

To prove surjectivity全射性ぜんしゃせい, start with an arbitrary element元げん of the codomain終域しゅういき and construct a corresponding input入力にゅうりょく.

6.3Common mistake

Do not decide from the expression $$n+1$$n+1 alone that $$0$$0 is not reached. The domain定義域ていぎいき is $$\mathbb{Z}$$\mathbb Z, so $$-1$$-1 is available.

7Problem 4

Let $$f:\mathbb{N}\to \mathbb{N}$$f:\mathbb N\to\mathbb N be defined by $$f\left(n\right)=n+1$$f(n)=n+1, where $$\mathbb{N}=\{0,1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{0,1,2,\dots\}. Is $$f$$f an injection単射たんしゃ or a surjection全射ぜんしゃ?

7.1Answer

If $$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2), then $$n_1+1=n_2+1$$n_1+1=n_2+1, so $$n_1=n_2$$n_1=n_2. Thus $$f$$f is an injection単射たんしゃ.

However, there is no $$n\in \mathbb{N}$$n\in\mathbb N satisfying $$f\left(n\right)=0$$f(n)=0. Therefore $$f$$f is not a surjection全射ぜんしゃ.

7.2Explanation

The same formula can have different properties when the domain定義域ていぎいき and codomain終域しゅういき change.

7.3Common mistake

Do not assume the answer is the same as in Problem 3 just because the formula is the same.

8Problem 5

Define $$f:\{1,2\}\to \{a,b\}$$f:\{1,2\}\to\{a,b\} by $$f\left(1\right)=a$$f(1)=a and $$f\left(2\right)=b$$f(2)=b, and define $$g:\{a,b\}\to \{0,1\}$$g:\{a,b\}\to\{0,1\} by $$g\left(a\right)=1$$g(a)=1 and $$g\left(b\right)=0$$g(b)=0. Compute $$(g\circ f)\left(1\right)$$(g\circ f)(1) and $$(g\circ f)\left(2\right)$$(g\circ f)(2), and explain the order of application in the composition合成ごうせい.

8.1Answer

and

Thus $$f$$f is applied first, and then $$g$$g is applied to its output出力しゅつりょく.

8.2Explanation

For a composite map合成写像ごうせいしゃぞう, the map closest to the input入力にゅうりょく on the right is applied first, not the symbol on the left.

8.3Common mistake

Do not read $$g\circ f$$g\circ f as “apply $$g$$g first and then $$f$$f.”

9Proof exercise: properties that pass from a composite map合成写像ごうせいしゃぞう to its component maps

9.1Problem

Let $$f:X\to Y$$f:X\to Y and $$g:Y\to Z$$g:Y\to Z. Prove the following statements.

1. If $$g\circ f$$g\circ f is an injection単射たんしゃ, then $$f$$f is an injection.
2. If $$g\circ f$$g\circ f is a surjection全射ぜんしゃ, then $$g$$g is a surjection.

Then give finite-set counterexamples showing that the statements “if $$g\circ f$$g\circ f is injective, then $$g$$g is injective” and “if $$g\circ f$$g\circ f is surjective, then $$f$$f is surjective” are false in general.

9.2Answer

1. Suppose $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2). Then

The injectivity単射性たんしゃせい of $$g\circ f$$g\circ f gives $$x_1=x_2$$x_1=x_2, so $$f$$f is injective.

1. Take arbitrary $$z\in Z$$z\in Z. Since $$g\circ f$$g\circ f is surjective, there exists $$x\in X$$x\in X such that $$g\left(f\right(x\left)\right)=z$$g(f(x))=z. Put $$y=f\left(x\right)\in Y$$y=f(x)\in Y. Then $$g\left(y\right)=z$$g(y)=z, so $$g$$g is surjective.

The two remaining claims fail in the same example. Let $$X=\left\{1\right\}$$X=\{1\}, $$Y=\{a,b\}$$Y=\{a,b\}, and $$Z=\left\{0\right\}$$Z=\{0\}, and define

The composite $$g\circ f:X\to Z$$g\circ f:X\to Z is a bijection全単射ぜんたんしゃ between singleton sets, so it is both injective and surjective. However, $$g$$g is not injective because $$g\left(a\right)=g\left(b\right)$$g(a)=g(b), and $$f$$f is not surjective because it does not reach $$b\in Y$$b\in Y.

9.3Explanation

A composite map合成写像ごうせいしゃぞう observes only the restriction of $$g$$g to $$f\left(X\right)$$f(X). Thus a collision under $$g$$g involving at least one point outside $$f\left(X\right)$$f(X) does not affect the injectivity of $$g\circ f$$g\circ f. Likewise, $$f$$f need not reach all of $$Y$$Y if its image $$f\left(X\right)$$f(X) still reaches all of $$Z$$Z through $$g$$g.