単射たんしゃ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.

An injection does not collapse information, while a surjection leaves no element of the codomain unused. A bijection has both properties, so its arrows can be read backward.

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.

In an arrow diagram, injectivity means that two input arrows never merge at one output, while surjectivity means that every codomain point has at least one incoming arrow.

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|」の両方りょうほうを使つかっている。

5Counting viewpoint for finite sets

Let $$A,B$$A,B be finite sets有限集合ゆうげんしゅうごう. For finite sets, if $$C\subseteq B$$C\subseteq B, then $$\left|C\right|\text{[PARSE ERROR: Undefined("Command("le")")]}\left|B\right|$$|C|\le |B|, and equality implies $$C=B$$C=B. Indeed, after listing the elements of $$B$$B, the subset $$C$$C selects some of them; selecting the same number requires selecting all of them.

Also, $$\left|A\right|=\left|B\right|$$|A|=|B| is equivalent to the existence of a bijection全単射ぜんたんしゃ between $$A$$A and $$B$$B: list both sets in sequences of the same length and match equal positions. Conversely, a bijection matches elements without duplication or leftovers, so the two finite sets have the same number of elements.

If an injection単射たんしゃ $$f:A\to B$$f:A\to B exists, then $$f$$f is a bijection全単射ぜんたんしゃ between $$A$$A and its image像ぞう $$f\left(A\right)$$f(A). Hence

If a surjection全射ぜんしゃ $$f:A\to B$$f:A\to B exists, every preimage逆像ぎゃくぞう

is nonempty. These preimages are pairwise disjoint and their union和集合わしゅうごう is $$A$$A. If $$B=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$B=\varnothing, the existence of a map $$A\to B$$A\to B forces $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing, and the conclusion is immediate. If $$B\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$B\ne\varnothing, then $$A$$A is partitioned into $$\left|B\right|$$|B| nonempty parts, so $$\left|A\right|\text{[PARSE ERROR: Undefined("Command("ge")")]}\left|B\right|$$|A|\ge |B|.

In particular, suppose $$\left|A\right|=\left|B\right|$$|A|=|B|. If $$f:A\to B$$f:A\to B is injective, then $$\left|f\right(A\left)\right|=\left|B\right|$$|f(A)|=|B| and $$f\left(A\right)\subseteq B$$f(A)\subseteq B, so $$f\left(A\right)=B$$f(A)=B and $$f$$f is surjective. Conversely, if $$f$$f is surjective, it partitions $$A$$A into $$\left|B\right|$$|B| nonempty preimages whose sizes sum to $$\left|A\right|=\left|B\right|$$|A|=|B|. Every preimage must therefore contain exactly one element, so $$f$$f is injective.

Hence injectivity and surjectivity are equivalent for finite sets of the same size. This conclusion uses both finiteness and the hypothesis $$\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 例れいは、有限性ゆうげんせいの仮定かていを外はずすと両方向りょうほうこうの含意がんいがともに壊こわれることを示しめす。

6Warning for infinite sets

For infinite sets無限集合むげんしゅうごう, injectivity and surjectivity need not be equivalent even when the domain and codomain have the same cardinality濃度のうど. Here let $$\mathbb{N}=\{1,2,3,\text{[PARSE ERROR: Undefined("Command("dots")")]}\}$$\mathbb N=\{1,2,3,\dots\}. The map $$s\left(n\right)=n+1$$s(n)=n+1 is an injection単射たんしゃ $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N, but it is not a surjection全射ぜんしゃ because $$1$$1 is not reached.

Conversely, $$q\left(n\right)=\lceil n/2\rceil$$q(n)=\lceil n/2\rceil is a surjection $$\mathbb{N}\to \mathbb{N}$$\mathbb N\to\mathbb N because $$q\left(2m\right)=m$$q(2m)=m for every $$m\in \mathbb{N}$$m\in\mathbb N. It is not injective because $$q\left(1\right)=q\left(2\right)=1$$q(1)=q(2)=1. These examples show that both implications fail when the finiteness hypothesis is removed.

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.

9演習えんしゅうリンク

9Exercise links