写像しゃぞう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.

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.

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:\{1,2\}\to \{a,b\}$$f:\{1,2\}\to\{a,b\} を $$f\left(1\right)=a$$f(1)=a、$$f\left(2\right)=b$$f(2)=b で定さだめ、$$g:\{a,b\}\to \{0,1\}$$g:\{a,b\}\to\{0,1\} を $$g\left(a\right)=1$$g(a)=1、$$g\left(b\right)=0$$g(b)=0 で定さだめる。$$(g\circ f)\left(1\right)$$(g\circ f)(1) と $$(g\circ f)\left(2\right)$$(g\circ f)(2) を求もとめ、合成ごうせいcompositionの適用順てきようじゅんを説明せつめいせよ。

8.1解答かいとう

である。つまり、先さきに $$f$$f を適用てきようし、その出力しゅつりょくoutputに $$g$$g を適用てきようする。

8.2解説かいせつ

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

8.3よくある誤あやまり

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

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

9証明しょうめい演習えんしゅう：合成写像ごうせいしゃぞうcomposite mapから各写像かくしゃぞうへ戻もどれる性質せいしつ

9.1問題もんだい

$$f:X\to Y$$f:X\to Y、$$g:Y\to Z$$g:Y\to Z とする。次つぎを証明しょうめいせよ。

1. $$g\circ f$$g\circ f が単射たんしゃinjectionなら、$$f$$f は単射たんしゃinjectionである。
2. $$g\circ f$$g\circ f が全射ぜんしゃsurjectionなら、$$g$$g は全射ぜんしゃsurjectionである。

さらに、「$$g\circ f$$g\circ f が単射たんしゃinjectionなら $$g$$g も単射たんしゃinjection」「$$g\circ f$$g\circ f が全射ぜんしゃsurjectionなら $$f$$f も全射ぜんしゃsurjection」は一般いっぱんには成立せいりつしないことを、有限集合ゆうげんしゅうごうの反例はんれいで示しめせ。

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.2解答かいとう

1. $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2) とする。すると

である。$$g\circ f$$g\circ f の単射性たんしゃせいinjectivityより $$x_1=x_2$$x_1=x_2 だから、$$f$$f は単射たんしゃinjectionである。

1. $$z\in Z$$z\in Z を任意にんいに取とる。$$g\circ f$$g\circ f が全射ぜんしゃsurjectionなので、ある $$x\in X$$x\in X が存在そんざいして $$g\left(f\right(x\left)\right)=z$$g(f(x))=z である。$$y=f\left(x\right)\in Y$$y=f(x)\in Y と置おけば $$g\left(y\right)=z$$g(y)=z だから、$$g$$g は全射ぜんしゃsurjectionである。

残のこる 2 つの推論すいろんには、1 つの反例はんれいを共通きょうつうに使つかえる。$$X=\left\{1\right\}$$X=\{1\}、$$Y=\{a,b\}$$Y=\{a,b\}、$$Z=\left\{0\right\}$$Z=\{0\} とし、

とする。$$g\circ f:X\to Z$$g\circ f:X\to Z は 1 元集合げんしゅうごうどうしの全単射ぜんたんしゃbijectionなので、単射たんしゃinjectionかつ全射ぜんしゃsurjectionである。しかし $$g$$g は $$g\left(a\right)=g\left(b\right)$$g(a)=g(b) なので単射たんしゃinjectionでなく、$$f$$f は $$b\in Y$$b\in Y に到達とうたつしないので全射ぜんしゃsurjectionでない。

9.3解説かいせつ

合成写像ごうせいしゃぞうcomposite mapが観測かんそくするのは、$$g$$g を $$f\left(X\right)$$f(X) に制限せいげんした振ふる舞まいだけである。そのため、少すくなくとも一方いっぽうが $$f\left(X\right)$$f(X) の外そとにある 2 元げんを $$g$$g が衝突しょうとつさせても、$$g\circ f$$g\circ f の単射性たんしゃせいinjectivityには現あらわれない。また、$$f$$f が $$Y$$Y 全体ぜんたいへ到達とうたつしなくても、その像ぞう $$f\left(X\right)$$f(X) だけで $$g$$g を通とおじて $$Z$$Z を覆おおえば、$$g\circ f$$g\circ f は全射ぜんしゃsurjectionになりうる。

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.