2つの集合の関係を記述する写像において，非常に重要な概念である｢全射｣と｢単射｣について述べる．
全射と単射の定義
全射の定義
$X$を集合，$Y$を空でない集合とし，$f:X\to Y$を写像とする．
任意の$y\in Y$に対して，ある$x\in X$が存在して，$y=f(x)$となるとき，$f$を全射(または全写)(surjection, surjective mapping)(または上への写像(onto mapping))という．
全射の定義は，次のように言い換えることができる．
$X$を集合，$Y$を空でない集合とし，$f:X\to Y$を写像とする．
$f$が全射であるための必要十分条件は，$f(X)=Y$が成り立つことである．
必要性を示す．
$f$が全射ならば，任意の$y\in Y$に対して，ある$x\in X$が存在して，$y=f(x)$となる．
よって，$Y\subset f(X)$である．
$f(X)\subset Y$であるから，$f(X)=Y$である．
十分性を示す．
$f(X)=Y$ならば，任意の$y\in Y$に対して，$y\in f(X)$であるから，ある$x\in X$が存在して，$y=f(x)$となる．
これは，$f$が全射であることに他ならない．
以上より，示された．$\blacksquare$
全射は，以下の図1のようなイメージで捉えると良い．
単射の定義
$X$を集合，$Y$を空でない集合とし，$f:X\to Y$を写像とする．
任意の$x_1,x_2\in X$に対して，$x_1\neq x_2$ならば$f(x_1)\neq f(x_2)$であるとき，$f$を単射(injection, injective mapping)(または一対一写像(one-to-one mapping))という．
単射の定義は，次のように言い換えることができる．
$X$を集合，$Y$を空でない集合とし，$f:X\to Y$を写像とする．
次の3つの命題は互いに同値である．
- $f$は単射である．
- 任意の$x_1,x_2\in X$に対して，$f(x_1)=f(x_2)$ならば$x_1=x_2$である．
- 任意の$y\in f(X)$に対して，ある$x\in X$がただ1つ存在して，$y=f(x)$となる．
②は①の対偶であるから，①$\iff$②は明らか．
②$\implies$③を示す．
任意の$y\in f(X)$に対して，ある$x\in X$が存在して，$y=f(x)$となる．
また，ある$x_1,x_2\in X$が存在して，$y=f(x_1)=f(x_2)$となるとすると，②より$x_1=x_2$である．
よって，③が成り立つ．
③$\implies$②を示す．
任意の$x_1,x_2\in X$に対して，$y\coloneqq f(x_1)=f(x_2)$ならば，$y\in f(X)$であるから，③より$x_1=x_2$である．
以上より，示された．$\blacksquare$
単射は，以下の図2のようなイメージで捉えると良い．
全単射の定義
$X$を集合，$Y$を空でない集合とし，$f:X\to Y$を写像とする．
$f$が全射かつ単射であるとき，$f$を全単射(bijection)(または一対一写像(one-to-one mapping)1)という．
ただし，$\mathrm{id}_{\emptyset}$は全単射である．
全単射の定義は，次のように言い換えることができる．
$X$を集合，$Y$を空でない集合とし，$f:X\to Y$を写像とする．
$f$が全単射であるための必要十分条件は，任意の$y\in Y$に対して，ある$x\in X$がただ1つ存在して，$y=f(x)$となることである．
命題1より，$f$が全射であることと，$f(X)=Y$であることは同値である．
命題2より，$f$が単射であることと，任意の$y\in f(X)$に対して，ある$x\in X$がただ1つ存在して，$y=f(x)$となることは同値である．
以上より，$f$が全単射であることと，任意の$y\in Y$に対して，ある$x\in X$がただ1つ存在して，$y=f(x)$となることは同値である．$\blacksquare$
全単射は，以下の図3のようなイメージで捉えると良い．
全射と単射の例
まず，全射の例を挙げる．
- 写像$f:\mathbb{R}\to [-1,1]$を
\[ f(x)=\sin x\quad (x\in \mathbb{R})\]
により定める．
任意の$y\in [-1,1]$に対して，例えば
\[ x=\operatorname{Arcsin} y\in \mathbb{R}\]
とすると，$y=f(x)$となるから，$f$は全射である． - 写像$g:\mathbb{R}\to \mathbb{R}$を
\[ g(x)=\sin x\quad (x\in \mathbb{R})\]
により定める．
任意の$x\in \mathbb{R}$に対して，例えば$\sin x\neq 2$であるから，$g$は全射でない． - $X=\{ 1,2,3,4,5\} ,Y=\{ 1,2,3\}$とする．
写像$h:X\to Y$を
\[ h(x)=\begin{cases}1&(x=2,3)\\ 2&(x=5)\\ 3&(x=1,4)\end{cases}\]
により定めると，$h$は全射である．
次に，単射の例を挙げる．
- 包含写像は単射である2．
- 写像$f:\mathbb{R}\to \mathbb{R}$を
\[ f(x)=x^3\quad (x\in \mathbb{R})\]
により定める．
任意の$x_1,x_2\in \mathbb{R}$に対して，$x_1\neq x_2$ならば$x_1^3\neq x_2^3$であるから，$f$は単射である． - 写像$g:\mathbb{R}\to \mathbb{R}$を
\[ f(x)=x^2\quad (x\in \mathbb{R})\]
により定める．
例えば，$f(\pm 1)=1$であるから，$f$は単射でない． - $X=\{ 1,2,3\} ,Y=\{ 1,2,3,4,5\}$とする．
写像$h:X\to Y$を
\[ \begin{aligned}h(1)=&3\\ h(2)=&1\\ h(3)=&4\end{aligned}\]
により定めると，$h$は単射である．
最後に，全単射の例を挙げる．
- 恒等写像は全単射である．
- 写像$f:\mathbb{R}\to (0,\infty )$を
\[ f(x)=e^x\quad (x\in \mathbb{R})\]
により定める．
任意の$y\in (0,\infty )$に対して
\[ x=\log y\in \mathbb{R}\]
とすると，$y=f(x)$となるから，$f$は全射である．
また，$x_1,x_2\in \mathbb{R}$が
\[ e^{x_1}=e^{x_2}\]
を満たすならば
\[ e^{x_1-x_2}=1\]
であるから，$x_1=x_2$である．
よって，$f$は単射である．
以上より，$f$は全単射である． - 写像$g:\left( -\dfrac{\pi}{2},\dfrac{\pi}{2}\right) \to \mathbb{R}$を
\[ g(x)=\tan x\quad \left( x\in \left( -\dfrac{\pi}{2},\dfrac{\pi}{2}\right) \right) \]
により定める．
任意の$y\in \mathbb{R}$に対して
\[ x=\operatorname{Arctan}y\in \mathbb{R}\]
とすると，$y=g(x)$となるから，$g$は全射である．
また，$x_1,x_2\in \left( -\dfrac{\pi}{2},\dfrac{\pi}{2}\right)$が
\[ \tan x_1=\tan x_2\]
を満たすならば
\[ \begin{aligned}\frac{\sin x_1}{\cos x_1}-\frac{\sin x_2}{\cos x_2}=&0\\ \sin x_1\cos x_2-\cos x_1\sin x_2=&0\end{aligned}\]
すなわち
\[ \sin (x_1-x_2)=0\]
であるから，$x_1=x_2$である．
よって，$g$は単射である．
以上より，$g$は全単射である．
任意の写像から，全射，単射，全単射を作ることができる．
$X$を集合，$Y$を空でない集合，$f:X\to Y$を写像とする．
また，$X$上の同値関係を
\[ x_1\sim x_2\iff f(x_1)=f(x_2)\quad (x_1,x_2\in X)\]
により定める．
- 写像$g:X\to f(X)$を
\[ g(x)=f(x)\quad (x\in X)\]
により定めると，$g$は全射である． - 写像$g:X/\sim \to Y$を
\[ g([x])=f(x)\quad (x\in X)\]
により定めると，$g$は単射である． - 写像$g:X/\sim \to f(X)$を
\[ g([x])=f(x)\quad (x\in X)\]
により定めると，$g$は全単射である．
証明は以下の記事を参照していただきたい．
全射と単射の性質
全射や単射の下では，写像の像や逆像に関して，より強い性質が成り立つ．写像の像や逆像の性質については，以下の記事を参照していただきたい．
$X$を集合，$Y$を空でない集合，$A,A_1,A_2$を$X$の部分集合，$B$を$Y$の部分集合，$f:X\to Y$を写像とするとき，次が成り立つ．
- $f$が全射ならば，$f(f^{-1}(B))=B$
- $f$が単射ならば，$f(A_1\cap A_2)=f(A_1)\cap f(A_2)$
- $f$が単射ならば，$f(X\setminus A)=f(X)\setminus f(A)$
- $f$が単射ならば，$f^{-1}(f(A))=A$
- $B\subset f(f^{-1}(B))$を示せば良い．
任意の$y\in B$に対して，$f$の全射性より，ある$x\in f^{-1}(B)$が存在して，$y=f(x)$となる．
よって，$y\in f(f^{-1}(B))$であるから，$B\subset f(f^{-1}(B))$である．$\blacksquare$ - $f(A_1)\cap f(A_2)\subset f(A_1\cap A_2)$を示せば良い．
任意の$y\in f(A_1)\cap f(A_2)$に対して，$y\in f(A_1)$かつ$y\in f(A_2)$であるから，ある$x_1\in A_1$とある$x_2\in A_2$が存在して
\[ y=f(x_1)=f(x_2)\]
となる．
$f$の単射性より
\[ x_1=x_2\in A_1\cap A_2\]
であるから
\[ y=f(x_1)=f(x_2)\in f(A_1\cap A_2)\]
である．
よって，$f(A_1)\cap f(A_2)\subset f(A_1\cap A_2)$である．$\blacksquare$ - $f(X\setminus A)\subset f(X)\setminus f(A)$を示せば良い．
任意の$y\in f(X\setminus A)$に対して，ある$x\in X\setminus A$が存在して，$y=f(x)$となる．
このとき，$x\in X$かつ$x\not\in A$であるから
\[ y=f(x)\in X\]
である．
$y\in f(A)$であると仮定すると，ある$a\in A$が存在して，$y=f(a)$となる．
よって，$f$の単射性より，$x=a$となるが，これは$x\not\in A$に矛盾する．
ゆえに，$y\not\in f(A)$であるから，$y\in f(X)\setminus f(A)$である．
したがって，$f(X\setminus A)\subset f(X)\setminus f(A)$である．$\blacksquare$ - $f^{-1}(f(A))\subset A$を示せば良い．
任意の$x\in f^{-1}(f(A))$に対して，$f(x)\in f(A)$であるから，ある$a\in A$が存在して
\[ f(x)=f(a)\]
となる．
$f$の単射性より，$x=a$であるから，$x\in A$である．
よって，$f^{-1}(f(A))\subset A$である．$\blacksquare$
有限集合から有限集合への写像について，次の命題が成り立つ．
$X$を有限集合，$Y$を空でない有限集合，$m$を$X$の相異なる元の数，$n$を$Y$の相異なる元の数とするとき，次が成り立つ．
- 全射$f:X\to Y$が存在するための必要十分条件は，$m\ge n$である．
また，$X$から$Y$への全射の総数は第2種スターリング数
\[ S(m,n)=\frac{1}{n!}\sum _{k=0}^n(-1)^{n-k}\binom{n}{k}k^m\]
に等しい．ただし，$m<n$のとき，$S(m,n)=0$とする． - 単射$f:X\to Y$が存在するための必要十分条件は，$m\le n$である．
また，$X$から$Y$への単射の総数は
\[ {}_n\mathrm{P}_m=\frac{n!}{m!(n-m)!}\]
に等しい．ただし，$m>n$のとき，${}_n\mathrm{P}_m=0$とする． - 全単射$f:X\to Y$が存在するための必要十分条件は，$m=n$である．
また，$X$から$Y$への全単射の総数は
\[ m!=n!\]
に等しい． - $f:X\to Y$を写像とする．
$m=n$ならば，次の3つの命題は互いに同値である．- $f$は全射である．
- $f$は単射である．
- $f$は全単射である．
$X=\{ x_1,x_2,\dots ,x_m\} ,Y=\{ y_1,y_2,\dots ,y_n\}$とする．
- 必要性を示す．
$f$の全射性より，$1$以上$n$以下の任意の整数$j$に対して，$1$以上$m$以下のある整数$i(j)$が存在して
\[ y_j=f(x_{i(j)})\]
となる．
このとき，$x_{i(1)},x_{i(2)},\dots ,x_{i(n)}$は$n$個の相異なる$X$の元であるから，$m\ge n$である．
十分性を示す．
写像$f:X\to Y$を，$m=n$のとき
\[ f(x_i)=y_i\quad (i=1,2,\dots ,n)\]
により定め，$m>n$のとき
\[ f(x_i)=\begin{cases}y_i&(i=1,2,\dots ,n)\\ y_1&(i=n+1,n+2,\dots ,m)\end{cases}\]
により定めると，$f$は全射である．
全射$f:X\to Y$の総数を示す．$m,n\ge 2$とする．
$f|_{X\setminus \{ x_m\}}:X\setminus \{ x_m\} \to Y$が全射であるとき，このような全射の総数は$S(m-1,n)$であり，$f(x_m)$は$y_1,y_2,\dots ,y_n$の$n$通りの値をとり得る．
また，$f|_{X\setminus \{ x_m\}}:X\setminus \{ x_m\} \to Y$が全射でないとき，
$1$以上$n$以下のある整数$j$が存在して，$1$以上$m-1$以下の任意の整数$i$に対して，$f(x_i)\neq y_j$となる．
$f$は全射であるから，$j$は一意的であり，$j=n$として一般性を失わない．このとき
\[ f(x_m)=y_n\]
である．よって
\[ f|_{X\setminus \{ x_m\}}:X\setminus \{ x_m\} \to Y\setminus \{ y_n\} \]
は全射であり，このような全射の総数は$S(m-1,n-1)$である．
以上より，$2$以上の任意の整数$m,n$に対して
\[ S(m,n)=nS(m-1,n)+S(m-1,n-1)\]
が成り立つ．
次に
\[ S(m,n)=\begin{cases}\displaystyle \frac{1}{n!}\sum _{k=0}^n(-1)^{n-k}\binom{n}{k}k^m&(m\ge n)\\ 0&(m<n)\end{cases}\quad (\ast )\]
であることを示す．
命題$P(m)$を
\[ P(m):任意のn\in \mathbb{N}に対して，(\ast )が成り立つ．\]
により定め，任意の$m\in \mathbb{N}$に対して$P(m)$が成り立つことを，$m$に関する数学的帰納法で示す．
全射が存在するための必要十分条件より，$m<n$のとき，$S(m,n)=0$となることは明らかであるから，$m\ge n$の場合について示せば良い．
\[ \begin{aligned}&S(1,1)=1\\ &\frac{1}{1!}\sum _{k=0}^1(-1)^{1-k}\binom{1}{k}k^1=1\end{aligned}\]
であるから，$P(1)$が成り立つ．
また，$P(m)$が成り立つと仮定すると
\[ \begin{aligned}&S(m+1,n)=nS(m,n)+S(m,n-1)\\ =&\frac{1}{(n-1)!}\sum _{k=0}^n(-1)^{n-k}\binom{n}{k}k^m+\frac{1}{(n-1)!}\sum _{k=0}^{n-1}(-1)^{n-k-1}\binom{n-1}{k}k^m\\ =&\frac{n^m}{(n-1)!}+\frac{1}{(n-1)!}\left( \sum _{k=0}^{n-1}(-1)^{n-k}\binom{n}{k}nk^m+\sum _{k=0}^{n-1}(-1)^{n-k-1}\binom{n-1}{k}k^m\right) \\ =&\frac{n^m}{(n-1)!}+\frac{1}{(n-1)!}\sum _{k=0}^{n-1}(-1)^{n-k}\left( \frac{n!}{k!(n-k)!}-\frac{(n-1)!}{k!(n-k-1)!}\right) k^m\\ =&\frac{n^m}{(n-1)!}+\frac{1}{(n-1)!}\sum _{k=0}^{n-1}(-1)^{n-k}\frac{(n-1)!}{k!(n-k)!}k^{m+1}\\ =&\frac{n^{m+1}}{n!}+\frac{1}{n!}\sum _{k=0}^{n-1}(-1)^{n-k}\frac{n!}{k!(n-k)!}k^{m+1}\\ =&\frac{1}{n!}\sum _{k=0}^n(-1)^{n-k}\binom{n}{k}k^{m+1}\end{aligned}\]
であるから，$P(m+1)$も成り立つ．
以上より，示された．$\blacksquare$ - 必要性を示す．
$f$の単射性より，$f(x_1),f(x_2),\dots ,f(x_m)$は$m$個の相異なる$Y$の元であるから，$m\le n$である．
十分性を示す．
写像$f:X\to Y$を
\[ f(x_i)=y_i\quad (i=1,2,\dots ,n)\]
により定めると，$f$は単射である．
単射$f:X\to Y$の総数を示す．
$f(x_1),f(x_2),\dots ,f(x_m)$に$m$個の相異なる$Y$の元を対応させる方法の総数であるから，これは$n$個の相異なる$Y$の元から，$m$個の相異なる元を選んで並べる順列の総数に等しい．
よって，${}_n\mathrm{P}_m$である．$\blacksquare$ - 全射が存在するための必要十分条件は，①，②より直ちに従う．
全射の総数は，①で$m=n$とする，または②で$m=n$とすると，直ちに従う．$\blacksquare$ - ①$\iff$②を示せば良い．
①$\implies$②を示す．
$f$の全射性より，$1$以上$m$以下の任意の整数$j$に対して，$1$以上$m$以下のある整数$i(j)$が存在して，$y_j=f(x_{i(j)})$となる．
このとき，$x_{i(1)},x_{i(2)},\dots ,x_{i(m)}$は$m$個の相異なる$X$の元である．
$X$は相異なる$m$個の元からなるから，$f$は単射である．
②$\implies$①を示す．
$f$の単射性より，$f(x_1),f(x_2),\dots ,f(x_m)$は$m$個の相異なる$Y$の元である．
$Y$は相異なる$m$個の元からなるから，$f$は全射である．
以上より，示された．$\blacksquare$
定理2より，2つの集合の元の数の大小関係は，全射や単射を構成することによって調べることができる．これは，集合の濃度の概念へと発展する．詳しくは，以下の記事を参照していただきたい．
- ｢一対一写像｣という用語は，単射の意味でも全単射の意味でも用いられることがある．混同の恐れがあるため，当サイトでは特に断りのない限り，｢単射｣や｢全単射｣を用いる． ↩︎
- 包含写像は自然な単射や，標準単射とも呼ばれている．詳細は以下の記事を参照せよ．
https://mathabyss.com/mapping ↩︎