重なりを許さない単射、すきまを許さない全射と逆写像

単射は「行き先が重ならない」、全射は「行き先を余らせない」。写像 $f:X\to Y$ を、矢印の出方と届き方の 2 方向から見た条件です。

どちらも $f$ の計算規則だけでは決まりません。$X$ と $Y$ をどう選んだかで、同じ $x\mapsto x^2$ が単射になったり全射になったりする^[1]。

単射は行き先が重ならない

$f:X\to Y$ が単射であるとは、$Y$ のどの元にも、矢印が高々 1 本しか届かないことをいいます。

$$x_1\ne x_2⟹f(x_1)\ne f(x_2)$$

証明では対偶のほうを使います。$f(x_1)=f(x_2)$ から $x_1=x_2$ を導く形^[3]。

$f(x)=2x+1$ なら $2x_1+1=2x_2+1$ から $x_1=x_2$ が出ます。単射です。

全射は行き先を余らせない

$f:X\to Y$ が全射であるとは、$Y$ のどの元にも、矢印が少なくとも 1 本は届くことをいいます。

$$\forall y\in Y,\exists x\in X,f(x)=y$$

言いかえると $f(X)=Y$。像が終域と一致するという条件です。

単射は「重なりを禁じる」、全射は「余りを禁じる」。禁じている場所が $Y$ の同じ元に対する矢印の本数の上と下で、ちょうど裏返しになっています。

両方を満たすと、どの元にもちょうど 1 本。これが全単射です。

矢印の本数で見分ける

下の図は 4 通りの写像を順に映します。緑が矢印の届いた元、灰色が余った元、橙が矢印を 2 本以上集めた元です。

$X$ の各元からは必ず 1 本ずつ矢印が出ます。写像の定義がそれを要求するので、判定に使うのは $Y$ 側だけ。

例：矢印で数える

$X=\{1,2,3\}$、$Y=\{A,B,C,D\}$ とし、$1\mapsto A$、$2\mapsto B$、$3\mapsto C$ と定めます。

重なりはないので単射。ところが $D$ に矢印が届かないので全射ではありません。

矢印の本数を全部足すと $|X|$ になる。$|X|=3$ で $|Y|=4$ なら、届く元は多くても 3 個なので、全射になりようがありません。

定義域と終域まで込みで写像

写像を決めるには、計算規則のほかに定義域と終域が要ります。この 3 つのうち 1 つでも違えば、別の写像です^[1]。

「$y=x^2$ は単射ですか」という問いには答えられません。どこからどこへの写像かが決まっていないためです。

横線を引いて確かめる

実数上の写像なら、グラフに横線を引くだけで判定できます。高さ $y$ の横線とグラフの交点の個数が、$y$ に届く矢印の本数です。

$y=1$ の横線は 2 回交わるので単射が壊れ、$y=-0.7$ の横線は交わらないので全射が壊れます。壊し方が別々なところが要点。

例：$x^2$ は 4 通りに化ける

定義域と終域を $\mathbb{R}$ と ${\mathbb{R}}_{\ge 0}$ で切り替えると、$x\mapsto x^2$ の性質が 4 通りに分かれます^[1]。

左は放物線が両側に伸びるので、同じ高さに 2 点が乗る。右は右半分だけを使うため、高さと点が 1 対 1 に対応します。

定義域を狭めると単射に近づき、終域を狭めると全射に近づく。効く向きが逆です。

例：指数関数

$f(x)=e^x$ を $\mathbb{R}\to \mathbb{R}$ と見ると、狭義単調増加なので単射。ただし負の値をとらないので全射ではありません。

終域を $(0,\infty )$ にとりかえると全射になり、全単射に変わります。逆写像は $\log$。

対数が定義できる理由がここにあります。$\mathbb{R}\to \mathbb{R}$ のままでは逆写像が作れません。

全単射と逆写像

$f:X\to Y$ が全単射なら、各 $y\in Y$ に対して $f(x)=y$ となる $x$ がちょうど 1 つ決まります。

その $x$ を $f^{-1}(y)$ と書くと $f^{-1}:Y\to X$ が定まる。これが逆写像です^[2]。

$$f^{-1}\circ f={\mathrm{id}}_X,f\circ f^{-1}={\mathrm{id}}_Y$$

逆写像も全単射で、$(f^{-1}{)}^{-1}=f$ が成り立ちます。

片側だけの逆写像

全単射でなくても、片側だけなら逆が作れることがあります^[2]。

$g\circ f={\mathrm{id}}_X$ となる $g$ を左逆写像、$f\circ h={\mathrm{id}}_Y$ となる $h$ を右逆写像と呼びます。

単射なら $f(x)$ から $x$ が復元でき、余った $y$ は適当な一点へ送ればよい。逆に左逆があれば $f(x_1)=f(x_2)$ から $x_1=x_2$ が出ます。

全射のほうは右逆写像に対応します。ただし各 $y$ に対して行き先の候補から 1 つずつ選ぶので、無限集合では選択公理が要る^[2]。

合成すると受け継がれる

$f:X\to Y$ と $g:Y\to Z$ を合成した $g\circ f$ について、次が成り立ちます。

逆向きは成り立ちません。$g\circ f$ が単射でも $g$ が単射とは限らず、言えるのは $f$ が単射だということだけ^[2]。

有限集合では個数が効く

$X$ と $Y$ が有限集合のとき、単射があれば $|X|\le |Y|$、全射があれば $|X|\ge |Y|$ が従います。

$|X|>|Y|$ なら単射は作れません。鳩の巣原理と呼ばれる言い分と同じ内容です。

そして $|X|=|Y|$ のときは、単射と全射が同値になる。有限だからこそ言える性質です。

無限集合では単射と全射がずれる

$\mathbb{N}\to \mathbb{N}$、$n\mapsto n+1$ を考えます。単射ですが、$0$ に届く矢印がないので全射ではありません。

自分自身への単射でありながら全射でない写像を持つこと。これが無限集合の特徴づけの 1 つです^[2]。

$\mathbb{N}\to 2\mathbb{N}$、$k\mapsto 2k$ は全単射なので、偶数全体は $\mathbb{N}$ と同じ濃度。部分なのに減っていません。

よくある誤り

「グラフが右上がりなら単射」は正しくありません。$\tan$ は定義域のどの区間でも増加しますが、$\tan 0=\tan \pi =0$ なので単射ではない。増加が言えるのは区間ごとで、定義域全体ではないためです。

「$f(X)=Y$ を示せばよい」と書いて、実際には $f(X)\subseteq Y$ しか示していない答案も多い。示すべきは $Y\subseteq f(X)$ のほうです。

$f^{-1}$ の記号も混乱のもとです。全単射のときの逆写像と、集合の逆像 $f^{-1}(B)=\{x:f(x)\in B\}$ は別物で、逆像のほうは単射でも全射でなくても定義できます。

矢印の本数が多くても少なくても困る。多いほうを禁じるのが単射、少ないほうを禁じるのが全射という 2 方向で覚えると、判定の手が止まりません。

参考