全射・単射・全単射 | 試験に出ない科学の話

全射

定義1　全射

写像$f: X\rightarrow Y$において、すべての$y \in Y$に対応する$x \in X$が存在する場合の$f$を全射である（surjective）、または（$Y$の）上への写像である（onto）という。

補足

・定義の条件は以下のように表すことができます。

$f:X\twoheadrightarrow Y\\ \\$$ $$ $f:X \xrightarrow{\scriptsize onto} Y$$

・次は全射の例です。$Y$のすべての要素に$X$が対応しています。$1$つの$Y$の要素に複数の$X$の要素が対応している場合も全射です。

・次の例は全射ではありません。$Y$の要素の中に、$X$との対応がないものがあります。

単射

定義2　単射

写像$f: X\rightarrow Y$において、すべての$x_1,x_2 \in X$に対し、
$$x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$$ である場合の$f$を単射である（injective）、または$1$対$1$である（one-to-one）という。

補足

・単射の条件は次の条件と同値です。

すべての$x_1,x_2 \in X$に対し、
$$f(x_1)=f(x_2) \Rightarrow x1 = x2$$

f(x₁)=f(x₂) ⇒ x₁ = x₂が同値であることの確認

$p\Rightarrow q$という命題があった場合、その対偶$\neg q \Rightarrow \neg p$は必ず成り立ちます（$\neg$は否定の意味です）。
定義の、
$$x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$$
の対偶は、
$$f(x_1)=f(x_2) \Rightarrow x_1 = x_2$$
なので、後者を単射の定義とすることもできます。

図でも考えてみましょう。
定義の$x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$によって、次の図のように、異なる$X$の要素は異なる$Y$の要素に対応します。

つまり、複数の$X$の要素が同じ$Y$の要素に対応しないということでもあります。

これを単射と定義しました。

$f(x_1)=f(x_2) \Rightarrow x_1 = x_2$の場合、値が同じである複数の$Y$の要素は同じ$X$の要素に対応します。

やはりこれも、複数の$X$の要素が同じ$Y$の要素に対応しないということでもあります。

したがって、対偶も単射であるといえます。

・以下のように表す場合もあります。

$f:X\rightarrowtail Y\\ \\$$ $$ $f:X \xrightarrow{\scriptsize 1-1} Y$$

・下の図は単射の場合です。$X$の全ての要素が重複せずに$Y$の要素に対応しています。

・次は単射ではない場合です。$Y$への対応が重複している$X$の要素があります。

全単射

定義3　全単射

写像が全射かつ単射であるとき、これを全単射である（bijective）という。

補足

下の図は全単射の場合です。$X$の要素が$Y$の全ての要素と重複せずに対応しています。

例

例1

$f:\mathbb{Z}\rightarrow\mathbb{Z}$を$\ f(x)=x+1$で定義した場合

※$\mathbb{Z}$は整数全体の集合です。

・全射：〇
全ての$f(x) \in \mathbb{Z}$に対して$f(x)=x+1$が成り立つ$x \in \mathbb{Z}$が存在します。

・単射：〇
$f(x_1)=f(x_2)= \in \mathbb{Z}$のときは必ず$x_1=x_2 \in \mathbb{Z}$です。

・全単射：〇

例2

$f:\mathbb{N}\rightarrow\mathbb{N}$を$f(x)=x+1$で定義した場合

※$\mathbb{N}$は自然数全体の集合です。

全射：×
たとえば、$f(x)=1$とすると$f(x)=x+1$が成り立つ$x \in \mathbb{N}$が存在しません。

・単射：〇
$f(x_1)=f(x_2) \in \mathbb{N}$が成り立つ$x_1,x_2 \in \mathbb{N}$が存在する場合、必ず$x_1=x_2$です。

・全単射：×

例3

$f:\mathbb{N}\rightarrow\mathbb{N}$を$f(x)=2x$で定義した場合

・全射：×
たとえば、$f(x)=1$とすると$f(x)=2x$が成り立つ$x \in \mathbb{N}$が存在しません。

・単射：〇
$f(x_1)=f(x_2) \in \mathbb{N}$が成り立つ$x_1,x_2 \in \mathbb{N}$が存在する場合、必ず$x_1=x_2$です。

・全単射：×

例4

$f:\mathbb{R}\rightarrow\mathbb{R}$を$f(x)=2x$で定義した場合

・全射：〇
前項と$f$の定義は同じですが、この場合は全ての$f(x) \in \mathbb{R}$に対し$f(x)=2x$が成り立つ$x\in \mathbb{R}$が存在します。

・単射：〇
$f(x_1)=f(x_2) \in \mathbb{R}$のとき必ず$x_1=x_2 \in \mathbb{R}$です。

・全単射：〇

例5

$f:\mathbb{R}\rightarrow\mathbb{R}$を$\ f(x)=x^2$で定義した場合

・全射：×
たとえば、$f(x)=-1$とすると$\ f(x)=x^2$が成り立つ$x \in \mathbb{R}$が存在しません。

・単射：×

たとえば、$f(x_1)=f(x_2)=1$のとき、$\ x_1=-1,\ x_2=1$のいずれも$f(x)=x^2$が成り立ちます。

・全単射：×

例6

$f:\mathbb{R}\backslash\{-1\}\rightarrow\mathbb{R}\backslash\{1\}$を$\ f(x)=\frac{x}{x+1}$で定義した場合

※$\mathbb{R}\backslash\{-1\}$は$-1$を除く実数全体の集合です。

・全射：〇

$x=\frac{f(x)}{1-f(x)}$より、
全ての$f(x) \in \mathbb{R}\backslash\{1\}$に対し$f(x)=\frac{x}{x+1}$が成り立つ$x \in \mathbb{R}\backslash\{-1\}$が存在します。

・単射：〇
$x_1 = \frac{f(x_1)}{1-f(x_1)},\ x_2=\frac{f(x_2)}{1-f(x_2)}$より、
$f(x_1)=f(x_2) \in \mathbb{R}\backslash\{1\}$のとき、必ず$x_1=x_2 \in \mathbb{R}\backslash\{-1\}$です。

・全単射：〇

例7

$f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{Z}$を$\ f(x,y)=x-y$で定義した場合

※$\times$は直積を示します。

・全射：〇
全ての$f(x,y)\in \mathbb{Z}$に対し$x-y \in \mathbb{Z}$が成り立つ$(x,y) \in \mathbb{N}^2$が存在します。

・単射：×
たとえば、$f(x_1,y_1)=f(x_2,y_2)=1$のとき、$(x_1,y_1)=(2,1),\ (x_2,y_2)=(3,2)$のいずれも$\ f(x,y)=x-y$が成り立ちます。

・全単射：×