像ぞうimageと逆像ぎゃくぞうpreimageの演習えんしゅう

Exercises on images像ぞう and preimages逆像ぎゃくぞう

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

1Corresponding lectures講義こうぎ

2問題もんだい1：像ぞうimageを求もとめる

$$A=\{1,2,3,4\}$$A=\{1,2,3,4\}、$$B=\{0,1\}$$B=\{0,1\} とし、写像しゃぞうmap $$f:A\to B$$f:A\to B を、$$f\left(x\right)$$f(x) は $$x$$x を 2 で割わった余あまり、と定さだめる。$$S=\{1,2,4\}$$S=\{1,2,4\} の像ぞうimage $$f\left(S\right)$$f(S) を求もとめよ。

2.1解答かいとう

$$f\left(1\right)=1$$f(1)=1、$$f\left(2\right)=0$$f(2)=0、$$f\left(4\right)=0$$f(4)=0 なので、

である。

2.2解説かいせつ

像ぞうimageは、部分集合ぶぶんしゅうごうsubsetの各かく元げんelementを実際じっさいに写うつして得えられる集合しゅうごうsetである。重複ちょうふくして同おなじ値あたいになっても、集合しゅうごうsetでは 1 回かいだけ数かぞえる。

2Problem 1: find an image像ぞう

Let $$A=\{1,2,3,4\}$$A=\{1,2,3,4\} and $$B=\{0,1\}$$B=\{0,1\}. Define the map写像しゃぞう $$f:A\to B$$f:A\to B by letting $$f\left(x\right)$$f(x) be the remainder when $$x$$x is divided by $$2$$2. Find the image像ぞう $$f\left(S\right)$$f(S) of $$S=\{1,2,4\}$$S=\{1,2,4\}.

2.1Answer

Since $$f\left(1\right)=1$$f(1)=1, $$f\left(2\right)=0$$f(2)=0, and $$f\left(4\right)=0$$f(4)=0,

2.2Explanation

The image像ぞう is the set集合しゅうごう actually obtained by applying the map to each element元げん of the subset部分集合ぶぶんしゅうごう. If several inputs give the same value, that value appears only once in the set.

3問題もんだい2：逆像ぎゃくぞうpreimageを求もとめる

問題もんだい1の写像しゃぞうmap $$f$$f について、$$T=\left\{0\right\}$$T=\{0\} の逆像ぎゃくぞうpreimage $$f^{-1}\left(T\right)$$f^{-1}(T) を求もとめよ。

3.1解答かいとう

$$f\left(x\right)=0$$f(x)=0 となるのは $$x=2,4$$x=2,4 である。したがって

である。

3.2解説かいせつ

逆像ぎゃくぞうpreimageは、終域しゅういきcodomain側がわの指定していされた集合しゅうごうに入はいる出力しゅつりょくoutputを持もつ入力にゅうりょくinput全体ぜんたいである。逆写像ぎゃくしゃぞうinverse mapとは別べつの概念がいねんなので、写像しゃぞうmapが全単射ぜんたんしゃbijectionでなくても求もとめられる。

3Problem 2: find a preimage逆像ぎゃくぞう

For the map写像しゃぞう $$f$$f in Problem 1, find the preimage逆像ぎゃくぞう $$f^{-1}\left(T\right)$$f^{-1}(T) of $$T=\left\{0\right\}$$T=\{0\}.

3.1Answer

The inputs with $$f\left(x\right)=0$$f(x)=0 are $$x=2,4$$x=2,4. Therefore

3.2Explanation

A preimage逆像ぎゃくぞう is the set of all inputs入力にゅうりょく whose outputs出力しゅつりょく lie in the specified codomain終域しゅういき-side set. It is different from an inverse map逆写像ぎゃくしゃぞう, so a preimage can be found even when the map is not a bijection全単射ぜんたんしゃ.

4問題もんだい3：逆像ぎゃくぞうpreimageが補集合ほしゅうごうcomplementを保たもつことを示しめす

$$f:A\to B$$f:A\to B、$$T\subseteq B$$T\subseteq B とする。

を示しめせ。

4.1解答かいとう

任意にんいの $$x\in A$$x\in A について、

任意にんいの $$x\in A$$x\in A で所属条件しょぞくじょうけんが同値どうちなので、2 つの集合しゅうごうsetは等ひとしい。

4.2解説かいせつ

補集合ほしゅうごうcomplementでは、どの全体集合ぜんたいしゅうごうに対たいする補集合ほしゅうごうかが重要じゅうようである。$$B\setminus T$$B\setminus T は出力側しゅつりょくがわの補集合ほしゅうごうcomplementであり、その逆像ぎゃくぞうpreimageは入力側にゅうりょくがわの補集合ほしゅうごうcomplement $$A\setminus f^{-1}\left(T\right)$$A\setminus f^{-1}(T) になる。

4Problem 3: prove that preimages逆像ぎゃくぞう preserve complements補集合ほしゅうごう

Let $$f:A\to B$$f:A\to B and $$T\subseteq B$$T\subseteq B. Prove

4.1Answer

For arbitrary $$x\in A$$x\in A,

Since the membership conditions are equivalent for every $$x\in A$$x\in A, the two sets集合しゅうごう are equal.

4.2Explanation

For a complement補集合ほしゅうごう, the ambient set matters. The set $$B\setminus T$$B\setminus T is the output-side complement, and its preimage逆像ぎゃくぞう is the input-side complement $$A\setminus f^{-1}\left(T\right)$$A\setminus f^{-1}(T).

5証明しょうめい演習えんしゅう：像ぞうimageと逆像ぎゃくぞうpreimageの往復おうふく

5.1問題もんだい

$$f:A\to B$$f:A\to B とする。次つぎを証明しょうめいせよ。

1. 任意にんいの $$S\subseteq A$$S\subseteq A について $$S\subseteq f^{-1}\left(f\right(S\left)\right)$$S\subseteq f^{-1}(f(S)) である。すべての $$S\subseteq A$$S\subseteq A で等号とうごうが成立せいりつすることと、$$f$$f が単射たんしゃinjectionであることは同値どうちである。
2. 任意にんいの $$T\subseteq B$$T\subseteq B について $$f\left(f^{-1}\right(T\left)\right)=T\cap f\left(A\right)\subseteq T$$f(f^{-1}(T))=T\cap f(A)\subseteq T である。すべての $$T\subseteq B$$T\subseteq B で $$f\left(f^{-1}\right(T\left)\right)=T$$f(f^{-1}(T))=T が成立せいりつすることと、$$f$$f が全射ぜんしゃsurjectionであることは同値どうちである。

5Proof exercise: round trips through images像ぞう and preimages逆像ぎゃくぞう

5.1Problem

Let $$f:A\to B$$f:A\to B. Prove the following statements.

1. For every $$S\subseteq A$$S\subseteq A, $$S\subseteq f^{-1}\left(f\right(S\left)\right)$$S\subseteq f^{-1}(f(S)). Equality holds for every $$S\subseteq A$$S\subseteq A if and only if $$f$$f is an injection単射たんしゃ.
2. For every $$T\subseteq B$$T\subseteq B, $$f\left(f^{-1}\right(T\left)\right)=T\cap f\left(A\right)\subseteq T$$f(f^{-1}(T))=T\cap f(A)\subseteq T. The equality $$f\left(f^{-1}\right(T\left)\right)=T$$f(f^{-1}(T))=T holds for every $$T\subseteq B$$T\subseteq B if and only if $$f$$f is a surjection全射ぜんしゃ.

5.2解答かいとう

1. $$x\in S$$x\in S なら $$f\left(x\right)\in f\left(S\right)$$f(x)\in f(S) なので、$$x\in f^{-1}\left(f\right(S\left)\right)$$x\in f^{-1}(f(S)) である。よって $$S\subseteq f^{-1}\left(f\right(S\left)\right)$$S\subseteq f^{-1}(f(S)) である。

$$f$$f が単射たんしゃinjectionで、$$x\in f^{-1}\left(f\right(S\left)\right)$$x\in f^{-1}(f(S)) とする。ある $$s\in S$$s\in S が存在そんざいして $$f\left(x\right)=f\left(s\right)$$f(x)=f(s) だから、単射性たんしゃせいinjectivityより $$x=s\in S$$x=s\in S である。したがってすべての $$S$$S で等号とうごうが成立せいりつする。

逆ぎゃくに、すべての $$S$$S で等号とうごうが成立せいりつするとする。$$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2) とし、$$S=\left\{x_1\right\}$$S=\{x_1\} と置おく。すると $$x_2\in f^{-1}\left(f\right(S\left)\right)=S$$x_2\in f^{-1}(f(S))=S なので $$x_2=x_1$$x_2=x_1 である。よって $$f$$f は単射たんしゃinjectionである。

1. $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)) なら、ある $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T) が存在そんざいして $$y=f\left(x\right)$$y=f(x) である。逆像ぎゃくぞうpreimageの定義ていぎより $$f\left(x\right)\in T$$f(x)\in T であり、また $$y=f\left(x\right)\in f\left(A\right)$$y=f(x)\in f(A) だから、$$y\in T\cap f\left(A\right)$$y\in T\cap f(A) である。

逆ぎゃくに $$y\in T\cap f\left(A\right)$$y\in T\cap f(A) なら、ある $$x\in A$$x\in A が存在そんざいして $$f\left(x\right)=y$$f(x)=y である。$$y\in T$$y\in T なので $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T)、したがって $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)) である。よって

である。

$$f$$f が全射ぜんしゃsurjectionで、$$y\in T$$y\in T とする。ある $$x\in A$$x\in A が存在そんざいして $$f\left(x\right)=y$$f(x)=y である。すると $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T) なので $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)) であり、すべての $$T$$T で等号とうごうが成立せいりつする。

逆ぎゃくに、すべての $$T$$T で等号とうごうが成立せいりつするとする。$$T=B$$T=B と置おけば

だから、$$f$$f は全射ぜんしゃsurjectionである。

5.3解説かいせつ

入力側にゅうりょくがわから「像ぞうimageを取とって逆像ぎゃくぞうpreimageで戻もどす」と、同おなじ出力しゅつりょくoutputへ送おくられる入力にゅうりょくが追加ついかされうる。その追加ついかが起おきないための条件じょうけんが単射性たんしゃせいinjectivityである。

出力側しゅつりょくがわから「逆像ぎゃくぞうpreimageを取とって像ぞうimageで戻もどす」と、もともと写像しゃぞうmapが到達とうたつしない元げんelementが失うしなわれうる。その欠落けつらくが起おきないための条件じょうけんが全射性ぜんしゃせいsurjectivityである。

ここで単射性たんしゃせいinjectivity・全射性ぜんしゃせいsurjectivityと同値どうちなのは、「特定とくていの 1 つの部分集合ぶぶんしゅうごうで等号とうごうが成立せいりつすること」ではなく、「すべての部分集合ぶぶんしゅうごうで等号とうごうが成立せいりつすること」である。量化りょうかの違ちがいに注意ちゅういする。

5.2Answer

1. If $$x\in S$$x\in S, then $$f\left(x\right)\in f\left(S\right)$$f(x)\in f(S), so $$x\in f^{-1}\left(f\right(S\left)\right)$$x\in f^{-1}(f(S)). Hence $$S\subseteq f^{-1}\left(f\right(S\left)\right)$$S\subseteq f^{-1}(f(S)).

Suppose $$f$$f is injective and $$x\in f^{-1}\left(f\right(S\left)\right)$$x\in f^{-1}(f(S)). There exists $$s\in S$$s\in S with $$f\left(x\right)=f\left(s\right)$$f(x)=f(s). Injectivity gives $$x=s\in S$$x=s\in S, so equality holds for every $$S$$S.

Conversely, suppose equality holds for every $$S$$S. If $$f\left(x_1\right)=f\left(x_2\right)$$f(x_1)=f(x_2), set $$S=\left\{x_1\right\}$$S=\{x_1\}. Then $$x_2\in f^{-1}\left(f\right(S\left)\right)=S$$x_2\in f^{-1}(f(S))=S, so $$x_2=x_1$$x_2=x_1. Thus $$f$$f is injective.

1. If $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)), there exists $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T) with $$y=f\left(x\right)$$y=f(x). By the definition of preimage, $$f\left(x\right)\in T$$f(x)\in T, and $$y=f\left(x\right)\in f\left(A\right)$$y=f(x)\in f(A), so $$y\in T\cap f\left(A\right)$$y\in T\cap f(A).

Conversely, if $$y\in T\cap f\left(A\right)$$y\in T\cap f(A), there exists $$x\in A$$x\in A with $$f\left(x\right)=y$$f(x)=y. Since $$y\in T$$y\in T, one has $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T) and hence $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)). Therefore

Suppose $$f$$f is surjective and $$y\in T$$y\in T. There exists $$x\in A$$x\in A with $$f\left(x\right)=y$$f(x)=y. Then $$x\in f^{-1}\left(T\right)$$x\in f^{-1}(T), so $$y\in f\left(f^{-1}\right(T\left)\right)$$y\in f(f^{-1}(T)). Thus equality holds for every $$T$$T.

Conversely, suppose equality holds for every $$T$$T. Taking $$T=B$$T=B gives

so $$f$$f is surjective.

5.3Explanation

Starting on the input side, taking an image像ぞう and then pulling it back by a preimage逆像ぎゃくぞう may add inputs that share an output. Injectivity単射性たんしゃせい is exactly the condition preventing this addition.

Starting on the output side, taking a preimage and then pushing it forward by an image may lose elements that the map never reaches. Surjectivity全射性ぜんしゃせい is exactly the condition preventing this loss.

The condition equivalent to injectivity or surjectivity is not equality for one particular subset, but equality for every subset. Keep this difference in quantification explicit.

6次つぎの講義こうぎlecture

6Next lecture講義こうぎ