単射たんしゃinjection・全射ぜんしゃsurjection・全単射ぜんたんしゃbijection

Injections単射たんしゃ, surjections全射ぜんしゃ, and bijections全単射ぜんたんしゃ

1導入どうにゅう

写像しゃぞうmap $$f:A\to B$$f:A\to B を理解りかいするとき、次つぎに問とうべきことは「この写像しゃぞうmapは情報じょうほうinformationを潰つぶしているか」「終域しゅういきcodomainの全体ぜんたいに届とどいているか」である。

単射たんしゃinjectionは異ことなる入力にゅうりょくinputを異ことなる出力しゅつりょくoutputへ送おくる性質せいしつpropertyである。全射ぜんしゃsurjectionは終域しゅういきcodomainの全すべての元げんelementへ到達とうたつする性質せいしつpropertyである。全単射ぜんたんしゃbijectionはその両方りょうほうであり、一対一対応いちたいいちたいおうとして逆写像ぎゃくしゃぞうinverse mapを持もつ。

単射たんしゃinjectionは情報じょうほうを潰つぶさないこと、全射ぜんしゃsurjectionは終域しゅういきcodomainを余あまらせないことを表あらわす。全単射ぜんたんしゃbijectionはその両方りょうほうを満みたすため、矢印やじるしを逆向ぎゃくむきに読よめる。

1Introduction

For a map写像しゃぞう $$f:A\to B$$f:A\to B, the next questions are whether the map collapses information情報じょうほう and whether it reaches the whole codomain終域しゅういき.

An injection単射たんしゃ sends distinct inputs入力にゅうりょく to distinct outputs出力しゅつりょく. A surjection全射ぜんしゃ reaches every element元げん of the codomain. A bijection全単射ぜんたんしゃ has both properties and has an inverse map逆写像ぎゃくしゃぞう as a one-to-one correspondence.

2用語ようごと定義ていぎ

写像しゃぞうmap $$f:A\to B$$f:A\to B が単射たんしゃinjectionであるとは、任意にんいの $$a_1,a_2\in A$$a_1,a_2\in A について

が成なり立たつことである。同値どうちに、$$a_1\ne a_2$$a_1\ne a_2 なら $$f\left(a_1\right)\ne f\left(a_2\right)$$f(a_1)\ne f(a_2) である。

写像しゃぞうmap $$f:A\to B$$f:A\to B が全射ぜんしゃsurjectionであるとは、任意にんいの $$b\in B$$b\in B に対たいして、ある $$a\in A$$a\in A が存在そんざいし $$f\left(a\right)=b$$f(a)=b を満みたすことである。これは $$f\left(A\right)=B$$f(A)=B と同値どうちである。

写像しゃぞうmap $$f:A\to B$$f:A\to B が全単射ぜんたんしゃbijectionであるとは、$$f$$f が単射たんしゃinjectionかつ全射ぜんしゃsurjectionであることである。

2Terms and definitions

A map写像しゃぞう $$f:A\to B$$f:A\to B is an injection単射たんしゃ if for all $$a_1,a_2\in A$$a_1,a_2\in A,

Equivalently, $$a_1\ne a_2$$a_1\ne a_2 implies $$f\left(a_1\right)\ne f\left(a_2\right)$$f(a_1)\ne f(a_2).

A map $$f:A\to B$$f:A\to B is a surjection全射ぜんしゃ if for every $$b\in B$$b\in B there exists $$a\in A$$a\in A such that $$f\left(a\right)=b$$f(a)=b. This is equivalent to $$f\left(A\right)=B$$f(A)=B.

A map $$f:A\to B$$f:A\to B is a bijection全単射ぜんたんしゃ if it is both an injection and a surjection.

3方針ほうしん

単射たんしゃinjectionを示しめすときは、$$f\left(a_1\right)=f\left(a_2\right)$$f(a_1)=f(a_2) と仮定かていして $$a_1=a_2$$a_1=a_2 を導みちびく。これは「出力しゅつりょくが同おなじなら、入力にゅうりょくも同おなじ」という方向ほうこうの証明しょうめいである。

全射ぜんしゃsurjectionを示しめすときは、任意にんいの $$b\in B$$b\in B を取とり、$$f\left(a\right)=b$$f(a)=b を満みたす $$a\in A$$a\in A を構成こうせいする。ここでは終域しゅういきcodomain $$B$$B の任意にんいの元げんelementから始はじめることが重要じゅうようである。

全単射ぜんたんしゃbijectionを示しめすには、単射たんしゃinjectionと全射ぜんしゃsurjectionを別々べつべつに確認かくにんするか、明示的めいじてきな逆写像ぎゃくしゃぞうinverse mapを構成こうせいする。

3Strategy

To prove injectivity単射性たんしゃせい, assume $$f\left(a_1\right)=f\left(a_2\right)$$f(a_1)=f(a_2) and derive $$a_1=a_2$$a_1=a_2. This proves the direction “same output implies same input.”

To prove surjectivity全射性ぜんしゃせい, take arbitrary $$b\in B$$b\in B and construct $$a\in A$$a\in A satisfying $$f\left(a\right)=b$$f(a)=b. The important point is to start with an arbitrary element元げん of the codomain終域しゅういき $$B$$B.

To prove bijectivity全単射性ぜんたんしゃせい, either check injection and surjection separately, or construct an explicit inverse map逆写像ぎゃくしゃぞう.

4直感的ちょっかんてきな説明せつめい

単射たんしゃinjectionは、入力側にゅうりょくがわの区別くべつを保存ほぞんする。異ことなる入力にゅうりょくinputが同おなじ出力しゅつりょくoutputへ潰つぶれないため、出力しゅつりょくoutputを見みれば入力にゅうりょくを区別くべつできる。

全射ぜんしゃsurjectionは、終域しゅういきcodomainを覆おおう。終域しゅういきcodomainに指定していした元げんelementが、実際じっさいに何なにかの入力にゅうりょくinputから到達とうたつされることを要求ようきゅうする。

全単射ぜんたんしゃbijectionは、潰つぶれも余あまりもない対応たいおうcorrespondenceである。有限集合ゆうげんしゅうごうでは、全単射ぜんたんしゃbijectionが存在そんざいすることは両集合りょうしゅうごうの元げんelementの個数こすうが等ひとしいことと対応たいおうする。

矢印図やじるしずでは、単射たんしゃinjectionは 2 つの入力にゅうりょくが同おなじ出力しゅつりょくへ合流ごうりゅうしないこと、全射ぜんしゃsurjectionは終域しゅういきの点てんに矢印やじるしが少すくなくとも 1 本ぽんは入はいることとして見みえる。

4Intuitive explanation

An injection単射たんしゃ preserves distinctions on the input side. Different inputs入力にゅうりょく do not collapse to the same output出力しゅつりょく, so the output can distinguish the input.

A surjection全射ぜんしゃ covers the codomain終域しゅういき. Every element元げん declared in the codomain must actually be reached from some input.

A bijection全単射ぜんたんしゃ is a correspondence対応たいおう with no collisions and no unused codomain elements. For finite sets, the existence of a bijection corresponds to the two sets having the same number of elements.

5有限集合ゆうげんしゅうごうでの個数こすうの見方みかた

$$A,B$$A,B が有限集合ゆうげんしゅうごうの場合ばあい、単射たんしゃinjection $$A\to B$$A\to B が存在そんざいするなら $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|A|\le |B| である。異ことなる入力にゅうりょくinputが異ことなる出力しゅつりょくoutputを必要ひつようとするからである。

全射ぜんしゃsurjection $$A\to B$$A\to B が存在そんざいするなら $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B| である。終域しゅういきcodomainの全すべてを覆おおうには、少すくなくとも $$B$$B の元げんelementの数かずだけ到達先とうたつさきが必要ひつようだからである。

$$\left|A\right|=\left|B\right|$$|A|=|B| の有限集合ゆうげんしゅうごうでは、単射たんしゃinjectionなら全射ぜんしゃsurjectionであり、全射ぜんしゃsurjectionなら単射たんしゃinjectionである。ただし、この結論けつろんは有限性ゆうげんせいを使つかう。

有限集合ゆうげんしゅうごうで定義域ていぎいきdomainと終域しゅういきcodomainの個数こすうが同おなじとき、単射たんしゃinjectionと全射ぜんしゃsurjectionは同値どうちになる。ただし、この個数こすうの議論ぎろんは有限ゆうげんかつ同おなじ大おおきさの場合ばあいに限かぎって使つかう。

5Counting viewpoint for finite sets

When $$A,B$$A,B are finite sets有限集合ゆうげんしゅうごう, the existence of an injection単射たんしゃ $$A\to B$$A\to B implies $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|A|\le |B|, because distinct inputs入力にゅうりょく require distinct outputs出力しゅつりょく.

The existence of a surjection全射ぜんしゃ $$A\to B$$A\to B implies $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B|, because covering the whole codomain終域しゅういき requires at least as many reached values as elements of $$B$$B.

For finite sets with $$\left|A\right|=\left|B\right|$$|A|=|B|, injection implies surjection, and surjection implies injection. This conclusion uses finiteness.

6無限集合むげんしゅうごうでの注意ちゅうい

無限集合むげんしゅうごうでは、有限集合ゆうげんしゅうごうの個数こすうの直感ちょっかんがそのまま使つかえない。たとえば $$\mathbb{N}=\{0,1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{0,1,2,\dots\} とすると、$$n\mapsto n+1$$n\mapsto n+1 は $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N の単射たんしゃinjectionだが、$$0$$0 に到達とうたつしないため全射ぜんしゃsurjectionではない。

6Warning for infinite sets

For infinite sets無限集合むげんしゅうごう, finite counting intuition does not directly apply. For example, if $$\mathbb{N}=\{0,1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{0,1,2,\dots\}, then $$n\mapsto n+1$$n\mapsto n+1 is an injection単射たんしゃ $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N, but it is not a surjection全射ぜんしゃ because $$0$$0 is not reached.

7例題れいだい：単射たんしゃinjectionと全射ぜんしゃsurjectionを判定はんていする

7.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か、全単射ぜんたんしゃbijectionかを判定はんていせよ。

7Worked example: decide injection単射たんしゃ and surjection全射ぜんしゃ

7.1Problem

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. Decide whether $$f$$f is an injection単射たんしゃ, a surjection全射ぜんしゃ, or a bijection全単射ぜんたんしゃ.

7.2解説かいせつ

$$f\left(2\right)=b$$f(2)=b かつ $$f\left(3\right)=b$$f(3)=b であり、$$2\ne 3$$2\ne3 である。異ことなる入力にゅうりょくinputが同おなじ出力しゅつりょくoutputへ送おくられているので、$$f$$f は単射たんしゃinjectionではない。

また、終域しゅういきcodomainの元げんelement $$c$$c に対たいして、$$f\left(x\right)=c$$f(x)=c を満みたす $$x\in \{1,2,3\}$$x\in\{1,2,3\} は存在そんざいしない。したがって $$f$$f は全射ぜんしゃsurjectionでもない。

全単射ぜんたんしゃbijectionは単射たんしゃinjectionかつ全射ぜんしゃsurjectionでなければならないので、$$f$$f は全単射ぜんたんしゃbijectionでもない。

7.2Explanation

We have $$f\left(2\right)=b$$f(2)=b and $$f\left(3\right)=b$$f(3)=b with $$2\ne 3$$2\ne3. Different inputs入力にゅうりょく are sent to the same output出力しゅつりょく, so $$f$$f is not an injection単射たんしゃ.

Also, for the codomain終域しゅういき element $$c$$c, there is no $$x\in \{1,2,3\}$$x\in\{1,2,3\} such that $$f\left(x\right)=c$$f(x)=c. Therefore $$f$$f is not a surjection全射ぜんしゃ.

Since a bijection全単射ぜんたんしゃ must be both injective and surjective, $$f$$f is not a bijection.

8見分みわけ方かたと関連かんれんリンク

• 単射たんしゃinjectionは「出力しゅつりょくの衝突しょうとつがないか」を確認かくにんする。
• 全射ぜんしゃsurjectionは「終域しゅういきcodomainに届とどかない元げんelementがないか」を確認かくにんする。
• 全単射ぜんたんしゃbijectionは「衝突しょうとつも未到達みとうたつもないか」を確認かくにんする。
• 終域しゅういきcodomainを変かえると、全射性ぜんしゃせいsurjectivityの判定はんていは変かわりうる。

8How to identify them and related links

• For an injection単射たんしゃ, check whether any output collision occurs.
• For a surjection全射ぜんしゃ, check whether any codomain終域しゅういき element is missed.
• For a bijection全単射ぜんたんしゃ, check for both no collisions and no missed codomain elements.
• Changing the codomain can change whether surjectivity全射性ぜんしゃせい holds.