単射

同義語：全射全単射逆写像

概要

前提知識: 写像、像、逆像、写像のグラフ, 写像の合成、写像の拡大と制限

定義

集合 $X,Y$ と写像 $f\colon X\to Y$ を考える。単射・全射・全単射は、対応規則だけでなく定義域 $X$ と終域 $Y$ を含めた写像の性質である。

入力の重複がない写像

$f$ が単射（injection, injective map）であるとは、任意の $x,x'\in X$ に対して
$$ f(x)=f(x')\Longrightarrow x=x' $$
が成り立つことをいう。対偶をとれば、$x\ne x'$ ならば $f(x)\ne f(x')$ という条件と同値である。単射を $f\colon X\hookrightarrow Y$ と書くことがある。

終域をすべて覆う写像

$f$ が全射（surjection, surjective map）であるとは、任意の $y\in Y$ に対して $f(x)=y$ を満たす $x\in X$ が少なくとも一つ存在することをいう。同じ条件は $f(X)=Y$ と書ける。全射を $f\colon X\twoheadrightarrow Y$ と書くことがある。

過不足のない写像

$f$ が 全単射（bijection, bijective map）であるとは、$f$ が単射かつ全射であることをいう。すなわち、各 $y\in Y$ に対して $f(x)=y$ を満たす $x\in X$ がただ一つ存在する。

対応を逆向きに戻す写像

写像 $g\colon Y\to X$ が
$$ g\circ f=\mathrm{id}_X,\qquad f\circ g=\mathrm{id}_Y $$
を満たすとき、$g$ を $f$ の 逆写像（inverse map）といい、$f^{-1}$ と書く。ここで $\mathrm{id}_X$ は $X$ の恒等写像、$g\circ f$ は合成写像である。$r\circ f=\mathrm{id}_X$ だけを満たす $r\colon Y\to X$ を $f$ の左逆写像（left inverse）、$f\circ s=\mathrm{id}_Y$ だけを満たす $s\colon Y\to X$ を $f$ の右逆写像（right inverse）という。

逆写像は、部分集合 $B\subset Y$ から部分集合 $f^{-1}(B)=\{x\in X\mid f(x)\in B\}$ を作る逆像とは別の概念である。逆像はどの写像にも定義できるが、逆写像は以下で示すように全単射に対してちょうど存在する。

直感

単射は異なる入力を同じ出力へ潰さず、全射は終域に取りこぼしを残さない。全単射では両方が成り立つので、$X$ と $Y$ の元は一対一に対応する。この対応は二つの集合が同じ集合の濃度を持つという定義の基礎になる。逆写像は「対応を逆向きにたどる」写像であり、たどり先が必ずあって（全射）ただ一つに決まる（単射）ときに限って定義できる。片側だけの逆写像は、単射性または全射性の一方だけを保証する。

例と反例

同じ規則 $x\mapsto x^2$ でも定義域・終域によって性質が変わる。

反例：実数全体での二乗写像

$f\colon\mathbb{R}\to\mathbb{R}$、$f(x)=x^2$ とする。$f(1)=f(-1)$ だが $1\ne-1$ なので単射でない。また、$-1$ は値として現れないので全射でない。満たす条件は「実数から実数への写像であること」、破れる結論は単射性と全射性であり、「二乗という規則なら単射である」および「二乗という規則なら全射である」という含意を破る。

全射だが単射でない二乗写像

$f\colon\mathbb{R}\to[0,\infty)$、$f(x)=x^2$ は全射だが、$f(1)=f(-1)$ なので単射でない。

単射だが全射でない二乗写像

$f\colon[0,\infty)\to\mathbb{R}$、$f(x)=x^2$ は単射だが、負の実数を値にとらないので全射でない。

全単射になる二乗写像

$f\colon[0,\infty)\to[0,\infty)$、$f(x)=x^2$ は全単射である。逆写像は平方根 $f^{-1}(y)=\sqrt{y}$ である。

性質

左逆写像と右逆写像

左逆写像と右逆写像は向きが異なり、一方だけでは逆写像にならない。

左逆写像による単射性の特徴づけ

$f\colon X\to Y$ が左逆写像 $r\colon Y\to X$、すなわち $r\circ f=\mathrm{id}_X$ を持てば $f$ は単射である。逆に、$X\ne\emptyset$ で $f$ が単射ならば左逆写像が存在する。

左逆写像による特徴づけの証明

左逆写像 $r$ があるとする。$f(x)=f(x')$ ならば両辺に $r$ を施して
$$ x=(r\circ f)(x)=(r\circ f)(x')=x' $$
となるので $f$ は単射である。
逆に $X\ne\emptyset$ とし、$f$ が単射であるとする。一つの元 $x_0\in X$ を固定し、$r\colon Y\to X$ を
$$ r(y)=\begin{cases} x & (y=f(x)\text{ となる }x\in X\text{ が存在するとき}),\\ x_0 & (y\notin f(X)) \end{cases} $$
で定める。前者の場合の $x$ は単射性により一意なので $r$ は写像として定まる。任意の $x\in X$ について $r(f(x))=x$ だから $r\circ f=\mathrm{id}_X$ である。ここでは一つの $x_0$ を固定するだけであり、選択公理は使わない。$\square$

$X=\emptyset$ という条件を除外できない。たとえば唯一の写像 $\emptyset\to\{0\}$ は単射だが、左逆写像 $\{0\}\to\emptyset$ は存在しない。

右逆写像から従う全射性

$f\colon X\to Y$ が右逆写像 $s\colon Y\to X$、すなわち $f\circ s=\mathrm{id}_Y$ を持てば $f$ は全射である。

右逆写像から従う全射性の証明

任意の $y\in Y$ に対して $x=s(y)\in X$ と置けば
$$ f(x)=f(s(y))=(f\circ s)(y)=y $$
である。したがって終域の各元は $f$ の値として現れ、$f$ は全射である。$\square$

逆向きの「任意の全射が右逆写像を持つ」という主張は、各ファイバー $f^{-1}(y)$ から元を同時に選ぶ選択関数の存在を要し、選択公理と同値である。この同値とその証明は選択公理の記事の命題「選択公理の同値な言い換え」が扱う。左逆写像と右逆写像は一般に一意ではない。

全単射と逆写像

逆写像の存在と一意性

$f\colon X\to Y$ が全単射であることと、逆写像 $g\colon Y\to X$ が存在することは同値である。存在するとき逆写像は一意である。

逆写像の存在と一意性の証明

$f$ が全単射なら、各 $y\in Y$ に対して $f(x)=y$ を満たす $x\in X$ がただ一つ存在する。その元を $g(y)$ と定めると $g\colon Y\to X$ が定まり、定義から $g(f(x))=x$ と $f(g(y))=y$ が成り立つ。したがって $g\circ f=\mathrm{id}_X$ かつ $f\circ g=\mathrm{id}_Y$ である。この構成では各 $y$ に対する元が一意なので選択公理を使わない。
逆に $g\circ f=\mathrm{id}_X$ と $f\circ g=\mathrm{id}_Y$ が成り立つなら、前者から $f$ は単射（prop-injection-left-inverse）、後者から $f$ は全射（prop-surjection-right-inverse）である。よって $f$ は全単射である。
一意性を示す。$g\colon Y\to X$ を左逆写像、$h\colon Y\to X$ を右逆写像とすると、合成の結合律と恒等写像の性質により
$$ g=g\circ\mathrm{id}_Y=g\circ(f\circ h)=(g\circ f)\circ h=\mathrm{id}_X\circ h=h. $$
したがって両側逆写像は一意である。$\square$

逆写像の対合性

$f\colon X\to Y$ が全単射ならば $f^{-1}\colon Y\to X$ も全単射であり、$(f^{-1})^{-1}=f$ が成り立つ。

逆写像の対合性の証明

$g=f^{-1}$ とする。逆写像の定義から $g\circ f=\mathrm{id}_X$ かつ $f\circ g=\mathrm{id}_Y$ である。したがって $f$ は $g$ の逆写像である。prop-bijection-inverse を $g$ に適用すると $g$ は全単射で、その一意な逆写像は $f$ である。ゆえに $(f^{-1})^{-1}=f$ である。$\square$

合成に対する性質

単射・全射・全単射の合成

$f\colon X\to Y$ と $g\colon Y\to Z$ について次が成り立つ。

$f,g$ が単射ならば $g\circ f$ も単射である。
$f,g$ が全射ならば $g\circ f$ も全射である。
$f,g$ が全単射ならば $g\circ f$ も全単射である。

合成に対する性質の証明

1 について、$(g\circ f)(x)=(g\circ f)(x')$ とする。$g$ の単射性から $f(x)=f(x')$、さらに $f$ の単射性から $x=x'$ を得る。
2 について、$z\in Z$ を任意にとる。$g$ が全射なので $g(y)=z$ となる $y\in Y$ があり、$f$ が全射なので $f(x)=y$ となる $x\in X$ がある。このとき $(g\circ f)(x)=z$ である。
3 は 1 と 2 から従う。$\square$

この命題は写像の合成を使うが、反復合成、制限、拡大の性質ではない。それらは写像の合成、写像の拡大と制限の記事が扱う。

有限集合の自己写像

有限集合では単射・全射が一致する

$X$ を有限集合とし、$f\colon X\to X$ を自己写像とする。このとき次は同値である。

$f$ は単射である。
$f$ は全射である。
$f$ は全単射である。

有限集合では単射・全射が一致することの証明

有限集合の元の個数について、次の三つの事実を用いる（いずれも Matsusaka68 による。本記事では証明しない）。

(i) 有限集合 $A,B$ の間に全単射 $A\to B$ があれば、$A$ と $B$ の元の個数は等しい。
(ii) 有限集合 $A$ の真部分集合 $A'\subsetneq A$ の元の個数は、$A$ の元の個数より小さい。
(iii) 有限集合 $A$ から集合 $B$ への写像 $h\colon A\to B$ の像 $h(A)$ の元の個数は、$A$ の元の個数以下である。
(ii) は鳩の巣原理の言い換えである。$X$ の元の個数を $n$ とする。
（1 ⇒ 2）$f$ が単射であるとする。終域を像に取り替えた写像 $X\to f(X)$、$x\mapsto f(x)$ は、単射であり、像の定義から全射でもあるので全単射である。(i) により $f(X)$ の元の個数は $n$ である。もし $f(X)\ne X$ ならば $f(X)$ は $X$ の真部分集合なので、(ii) により $f(X)$ の元の個数は $n$ より小さく、矛盾する。よって $f(X)=X$、すなわち $f$ は全射である。
（2 ⇒ 1）$f$ が全射だが単射でないと仮定する。相異なる $x,x'\in X$ で $f(x)=f(x')$ となるものがある。$X':=X\setminus\{x'\}$ とおき、制限 $h:=f|_{X'}\colon X'\to X$ を考える。任意の $y\in X$ に対して、全射性から $f(z)=y$ となる $z\in X$ があり、$z\ne x'$ ならば $z\in X'$、$z=x'$ ならば $f(x)=f(x')=y$ かつ $x\in X'$ なので、いずれにせよ $y\in h(X')$ である。よって $h(X')=X$ であり、(iii) により $n$ は $X'$ の元の個数以下である。一方 $X'$ は $X$ の真部分集合なので、(ii) により $X'$ の元の個数は $n$ より小さい。これは矛盾である。よって全射なら単射である。
単射かつ全射であることが全単射の定義なので、1、2、3 は同値である。$X=\emptyset$ の場合も唯一の自己写像が三条件をすべて満たす。$\square$

有限性は外せない。$s\colon\mathbb{N}\to\mathbb{N}$、$s(n)=n+1$ は単射だが $0$ を値にとらず全射でない。一方、$q\colon\mathbb{N}\to\mathbb{N}$、$q(n)=\lfloor n/2\rfloor$（床関数）は全射だが $q(0)=q(1)$ なので単射でない。これらは「無限集合の自己写像でも単射なら全射」および「無限集合の自己写像でも全射なら単射」という含意をそれぞれ破る。

補足

集合の圏 $\mathsf{Set}$ では、単射はモノ射と一致し、全射はエピ射と一致し、全単射は同型射と一致する。しかし、モノ射・エピ射・同型射は任意の圏で合成によって定義される概念であり、集合の元を使う単射・全射・全単射の定義と同じものではない。両者が一致するかは圏ごとに確かめる必要がある。
本記事の範囲を扱う標準的な入門書として Hara20 と Matsusaka68 がある。