写像しゃぞうmapと単射たんしゃinjection・全射ぜんしゃsurjection - 基本演習きほんえんしゅう

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

1対応たいおうする講義こうぎlecture

1Corresponding lectures講義こうぎ

2順序上じゅんじょじょうの注意ちゅうい

この演習えんしゅうでは、写像しゃぞうmap、単射たんしゃinjection、全射ぜんしゃsurjectionに加くわえて、逆写像ぎゃくしゃぞうinverse mapと合成写像ごうせいしゃぞうcomposite mapも短みじかく扱あつかう。逆写像ぎゃくしゃぞうinverse mapは全単射ぜんたんしゃbijectionの矢印やじるしを逆向ぎゃくむきに読よむ写像しゃぞうであり、合成写像ごうせいしゃぞうcomposite map $$g\circ f$$g\circ f は先さきに $$f$$f、次つぎに $$g$$g を適用てきようする写像しゃぞうである。

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.

3演習えんしゅう方針ほうしん

写像しゃぞうmapでは、各かく入力にゅうりょくinputに[ちょうど 1 つ]の出力しゅつりょくoutputがあるかを確認かくにんする。単射たんしゃinjectionは衝突しょうとつの有無うむ、全射ぜんしゃsurjectionは終域しゅういきcodomainへの到達とうたつで判定はんていする。

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.

4問題もんだい 1

$$f:\{1,2,3\}\to \{a,b,c\}$$f:\{1,2,3\}\to\{a,b,c\} を $$f\left(1\right)=a$$f(1)=a、$$f\left(2\right)=b$$f(2)=b、$$f\left(3\right)=b$$f(3)=b で定義ていぎする。$$f$$f は単射たんしゃinjectionか、全射ぜんしゃsurjectionか。

4.1解答かいとう

$$f\left(2\right)=f\left(3\right)=b$$f(2)=f(3)=b で $$2\ne 3$$2\ne3 なので、$$f$$f は単射たんしゃinjectionではない。また $$c$$c に到達とうたつする入力にゅうりょくinputが存在そんざいしないので、$$f$$f は全射ぜんしゃsurjectionでもない。

4.2解説かいせつ

単射たんしゃinjectionは入力にゅうりょくの区別くべつを保存ほぞんする性質せいしつであり、全射ぜんしゃsurjectionは終域しゅういきcodomainを覆おおう性質せいしつである。

4.3よくある誤あやまり

値域ちいきrange $$\{a,b\}$$\{a,b\} と終域しゅういきcodomain $$\{a,b,c\}$$\{a,b,c\} を混同こんどうする誤あやまりである。

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\}.

5問題もんだい 2

$$g:\{1,2,3\}\to \{a,b,c\}$$g:\{1,2,3\}\to\{a,b,c\} を $$g\left(1\right)=b$$g(1)=b、$$g\left(2\right)=c$$g(2)=c、$$g\left(3\right)=a$$g(3)=a で定義ていぎする。$$g$$g の逆写像ぎゃくしゃぞうinverse mapを求もとめよ。

5.1解答かいとう

$$g$$g は各かく入力にゅうりょくinputを異ことなる出力しゅつりょくoutputへ送おくり、終域しゅういきcodomainの全すべてに到達とうたつしている。したがって全単射ぜんたんしゃbijectionである。逆写像ぎゃくしゃぞうinverse mapは $$g^{-1}\left(a\right)=3$$g^{-1}(a)=3、$$g^{-1}\left(b\right)=1$$g^{-1}(b)=1、$$g^{-1}\left(c\right)=2$$g^{-1}(c)=2 である。

5.2解説かいせつ

逆写像ぎゃくしゃぞうinverse mapは全単射ぜんたんしゃbijectionのときにだけ存在そんざいする。まず全単射ぜんたんしゃbijectionを確認かくにんしてから矢印やじるしを逆向ぎゃくむきに読よむ。

5.3よくある誤あやまり

単射たんしゃinjectionだけを確認かくにんして逆写像ぎゃくしゃぞうinverse mapを作つくる誤あやまりである。

逆写像ぎゃくしゃぞうinverse mapを作つくるには、出力しゅつりょくから入力にゅうりょくへ一意いちいに戻もどれることに加くわえて、終域しゅういきcodomainのすべての元げんelementが使つかわれていることも必要ひつようである。したがって単射性たんしゃせいinjectivityだけでなく全射性ぜんしゃせいsurjectivityも確認かくにんする。

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.

6問題もんだい 3

$$f:\mathbb{Z}\to \mathbb{Z}$$f:\mathbb Z\to\mathbb Z を $$f\left(n\right)=n+1$$f(n)=n+1 とする。$$f$$f は単射たんしゃinjectionか、全射ぜんしゃsurjectionか。

6.1解答かいとう

$$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2) とすると $$n_1+1=n_2+1$$n_1+1=n_2+1 なので $$n_1=n_2$$n_1=n_2 である。したがって単射たんしゃinjectionである。

任意にんいの $$m\in \mathbb{Z}$$m\in\mathbb Z に対たいして $$n=m-1\in \mathbb{Z}$$n=m-1\in\mathbb Z と置おくと $$f\left(n\right)=m$$f(n)=m である。したがって全射ぜんしゃsurjectionである。よって全単射ぜんたんしゃbijectionである。

6.2解説かいせつ

全射ぜんしゃsurjectionでは、任意にんいの終域しゅういきcodomainの元げんelementから始はじめ、対応たいおうする入力にゅうりょくinputを構成こうせいする。

6.3よくある誤あやまり

$$n+1$$n+1 の形かたちだけを見みて、$$0$$0 に到達とうたつしないと判断はんだんする誤あやまりである。定義域ていぎいきが $$\mathbb{Z}$$\mathbb Z なので $$-1$$-1 が使つかえる。

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.

7問題もんだい 4

$$f:\mathbb{N}\to \mathbb{N}$$f:\mathbb N\to\mathbb N を $$f\left(n\right)=n+1$$f(n)=n+1 とする。ここで $$\mathbb{N}=\{0,1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{0,1,2,\dots\} とする。$$f$$f は単射たんしゃinjectionか、全射ぜんしゃsurjectionか。

7.1解答かいとう

$$f\left(n_1\right)=f\left(n_2\right)$$f(n_1)=f(n_2) なら $$n_1+1=n_2+1$$n_1+1=n_2+1 なので $$n_1=n_2$$n_1=n_2 である。したがって単射たんしゃinjectionである。

しかし $$0\in \mathbb{N}$$0\in\mathbb N に対たいして $$f\left(n\right)=0$$f(n)=0 を満みたす $$n\in \mathbb{N}$$n\in\mathbb N は存在そんざいしない。したがって全射ぜんしゃsurjectionではない。

7.2解説かいせつ

同おなじ式しきでも定義域ていぎいきdomainと終域しゅういきcodomainが変かわると、全射性ぜんしゃせいsurjectivityの判定はんていが変かわる。

7.3よくある誤あやまり

問題もんだい 3 と同おなじ式しきだから同おなじ判定はんていになると考かんがえる誤あやまりである。

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.

8問題もんだい 5

$$f:A\to B$$f:A\to B、$$g:B\to C$$g:B\to C に対たいして、$$(g\circ f)\left(a\right)$$(g\circ f)(a) の意味いみを説明せつめいせよ。

8.1解答かいとう

$$(g\circ f)\left(a\right)=g\left(f\right(a\left)\right)$$(g\circ f)(a)=g(f(a)) である。つまり、先さきに $$f$$f を $$a$$a に適用てきようして $$f\left(a\right)\in B$$f(a)\in B を得える。次つぎに $$g$$g を $$f\left(a\right)$$f(a) に適用てきようして $$g\left(f\right(a\left)\right)\in C$$g(f(a))\in C を得える。

8.2解説かいせつ

合成写像ごうせいしゃぞうcomposite mapでは、記号きごうの左ひだりからではなく入力にゅうりょくに近ちかい右側みぎがわの写像しゃぞうmapから適用てきようする。

8.3よくある誤あやまり

$$g\circ f$$g\circ f を先さきに $$g$$g、後あとに $$f$$f と読よむ誤あやまりである。

8Problem 5

For $$f:A\to B$$f:A\to B and $$g:B\to C$$g:B\to C, explain the meaning of $$(g\circ f)\left(a\right)$$(g\circ f)(a).

8.1Answer

$$(g\circ f)\left(a\right)=g\left(f\right(a\left)\right)$$(g\circ f)(a)=g(f(a)). First apply $$f$$f to $$a$$a to obtain $$f\left(a\right)\in B$$f(a)\in B. Then apply $$g$$g to $$f\left(a\right)$$f(a) to obtain $$g\left(f\right(a\left)\right)\in C$$g(f(a))\in C.

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.”

9証明しょうめい演習えんしゅう：合成ごうせいで単射たんしゃinjectionと全射ぜんしゃsurjectionが保存ほぞんされること

9.1問題もんだい

$$f:X\to Y$$f:X\to Y、$$g:Y\to Z$$g:Y\to Z とする。$$f,g$$f,g がともに単射たんしゃinjectionなら $$g\circ f$$g\circ f も単射たんしゃinjectionであり、$$f,g$$f,g がともに全射ぜんしゃsurjectionなら $$g\circ f$$g\circ f も全射ぜんしゃsurjectionであることを証明しょうめいせよ。

9Proof exercise: composition preserves injections単射たんしゃ and surjections全射ぜんしゃ

9.1Problem

Let $$f:X\to Y$$f:X\to Y and $$g:Y\to Z$$g:Y\to Z. Prove that if $$f,g$$f,g are both injections単射たんしゃ, then $$g\circ f$$g\circ f is an injection, and if $$f,g$$f,g are both surjections全射ぜんしゃ, then $$g\circ f$$g\circ f is a surjection.

9.2解答かいとう

単射たんしゃinjectionについて、$$(g\circ f)\left(x_1\right)=(g\circ f)\left(x_2\right)$$(g\circ f)(x_1)=(g\circ f)(x_2) とする。$$g\left(f\right(x_1\left)\right)=g\left(f\right(x_2\left)\right)$$g(f(x_1))=g(f(x_2)) である。$$g$$g が単射たんしゃinjectionなので $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2)、さらに $$f$$f が単射たんしゃinjectionなので $$x_1=x_2$$x_1=x_2 である。

全射ぜんしゃsurjectionについて、$$z\in Z$$z\in Z を取とる。$$g$$g が全射ぜんしゃsurjectionなので $$g\left(y\right)=z$$g(y)=z となる $$y\in Y$$y\in Y がある。$$f$$f が全射ぜんしゃsurjectionなので $$f\left(x\right)=y$$f(x)=y となる $$x\in X$$x\in X がある。したがって $$(g\circ f)\left(x\right)=z$$(g\circ f)(x)=z である。

9.3解説かいせつ

単射たんしゃinjectionの証明しょうめいは等式とうしきを左ひだりから戻もどす議論ぎろんであり、全射ぜんしゃsurjectionの証明しょうめいは目標もくひょうの元げんelementから逆向ぎゃくむきに元げんelementを探さがす議論ぎろんである。

9.2Answer

For injectivity単射性たんしゃせい, suppose $$(g\circ f)\left(x_1\right)=(g\circ f)\left(x_2\right)$$(g\circ f)(x_1)=(g\circ f)(x_2). Then $$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 an injection単射たんしゃ, $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2). Since $$f$$f is an injection, $$x_1=x_2$$x_1=x_2.

For surjectivity全射性ぜんしゃせい, take $$z\in Z$$z\in Z. Since $$g$$g is a surjection全射ぜんしゃ, there is $$y\in Y$$y\in Y with $$g\left(y\right)=z$$g(y)=z. Since $$f$$f is a surjection, there is $$x\in X$$x\in X with $$f\left(x\right)=y$$f(x)=y. Therefore $$(g\circ f)\left(x\right)=z$$(g\circ f)(x)=z.

9.3Explanation

The injection proof pulls an equality backward through the two maps. The surjection proof starts with the target element元げん and searches backward for a preimage in each stage.