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

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はその両方りょうほうを満みたすため、矢印やじるしを逆向ぎゃくむきに読よめる。

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であることである。

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を構成こうせいする。

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

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

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

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

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

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

$$A,B$$A,B を有限集合ゆうげんしゅうごうとする。有限集合ゆうげんしゅうごうの個数こすうについて、部分集合ぶぶんしゅうごう $$C\subseteq B$$C\subseteq B なら $$\left|C\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|C|\le |B| であり、$$\left|C\right|=\left|B\right|$$|C|=|B| なら $$C=B$$C=B である。これは $$B$$B の元げんを一列いちれつに並ならべたとき、$$C$$C がそのうちの一部いちぶだけを選えらぶこと、同おなじ個数こすうを選えらぶには全部ぜんぶを選えらぶ必要ひつようがあることによる。

また、$$\left|A\right|=\left|B\right|$$|A|=|B| であることは、$$A$$A と $$B$$B の元げんをそれぞれ同おなじ長ながさの列れつに並ならべ、同おなじ位置いちどうしを対応たいおうさせる全単射ぜんたんしゃbijectionが存在そんざいすることと同値どうちである。逆ぎゃくに、全単射ぜんたんしゃbijectionは重複ちょうふくも余あまりもなく元げんを対応たいおうさせるので、両集合りょうしゅうごうの個数こすうは等ひとしい。

単射たんしゃinjection $$f:A\to B$$f:A\to B が存在そんざいするなら、$$f$$f は $$A$$A と像ぞうimage $$f\left(A\right)$$f(A) の間あいだの全単射ぜんたんしゃbijectionである。したがって

である。

全射ぜんしゃsurjection $$f:A\to B$$f:A\to B が存在そんざいするなら、各かく $$b\in B$$b\in B の逆像ぎゃくぞうpreimage

は空からでない。これらの逆像ぎゃくぞうpreimageは互たがいに交まじわらず、その和集合わしゅうごうunionは $$A$$A である。$$B=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$B=\varnothing のときは写像しゃぞうmap $$A\to B$$A\to B が存在そんざいすることから $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing であり、結論けつろんは直ただちに従したがう。$$B\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$B\ne\varnothing のとき、$$A$$A は $$\left|B\right|$$|B| 個この空からでない部分ぶぶんに分わかれ、$$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B| となる。

特とくに $$\left|A\right|=\left|B\right|$$|A|=|B| なら、単射たんしゃinjection $$f:A\to B$$f:A\to B について $$\left|f\right(A\left)\right|=\left|B\right|$$|f(A)|=|B| であり、$$f\left(A\right)\subseteq B$$f(A)\subseteq B だから $$f\left(A\right)=B$$f(A)=B、すなわち $$f$$f は全射ぜんしゃsurjectionである。逆ぎゃくに $$f$$f が全射ぜんしゃsurjectionなら、$$A$$A を $$\left|B\right|$$|B| 個この空からでない逆像ぎゃくぞうpreimageに分わけ、その個数こすうの合計ごうけいが $$\left|A\right|=\left|B\right|$$|A|=|B| になる。したがって各かく逆像ぎゃくぞうpreimageの元げんはちょうど 1 個こであり、$$f$$f は単射たんしゃinjectionである。

よって、同おなじ個数こすうの有限集合ゆうげんしゅうごうの間あいだでは、単射性たんしゃせいinjectivityと全射性ぜんしゃせいsurjectivityは同値どうちである。この結論けつろんでは「有限ゆうげん」と「$$\left|A\right|=\left|B\right|$$|A|=|B|」の両方りょうほうを使つかっている。

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

無限集合むげんしゅうごうでは、定義域ていぎいきと終域しゅういきが同おなじ濃度のうどcardinalityでも、単射性たんしゃせいinjectivityと全射性ぜんしゃせいsurjectivityは同値どうちにならない。ここでは $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\} とする。$$s\left(n\right)=n+1$$s(n)=n+1 は $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N の単射たんしゃinjectionだが、$$1$$1 に到達とうたつしないため全射ぜんしゃsurjectionではない。

逆ぎゃくに、$$q\left(n\right)=\lceil n/2\rceil$$q(n)=\lceil n/2\rceil は $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N の全射ぜんしゃsurjectionである。任意にんいの $$m\in \mathbb{N}$$m\in\mathbb N に対たいして $$q\left(2m\right)=m$$q(2m)=m だからである。しかし $$q\left(1\right)=q\left(2\right)=1$$q(1)=q(2)=1 なので単射たんしゃinjectionではない。この 2 例れいは、有限性ゆうげんせいの仮定かていを外はずすと両方向りょうほうこうの含意がんいがともに壊こわれることを示しめす。

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かを判定はんていせよ。

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でもない。

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

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

9演習えんしゅうリンク