逆関係としての関数の単射性、全射性 - コンピュータってすごいらしい

概要

単射性は関数性の、全射性は全域性の逆関係であり、関数を考えるときは自然に現れる。
単射性、全射性は集合の要素の個数と関連している。

本文

数学で関数を考えると単射や全射といった概念が表れます。こういった概念はなぜ重要なのでしょうか。

2項関係としての関数

例として、2乗するという関数を考えます。関数を以下のように書くことができます。

$\displaystyle f(x)=x^2$

これは変数 $x$ を含んでいますが、関数とは $(x, x^2)$ の集まり、つまり $(1,1), (2,4), (3,9),\ldots$ といったペア*1の集まりと考えることができます。
これに含まれるペアを本稿では以下のように書きます。

$\displaystyle 1 \rhd_f 1,\quad 2 \rhd_f 4,\quad 3 \rhd_f 9, \ldots$

このように書くと、関数とは2項関係の一種であることがわかります。2項関係(あるいは単に「関係」)とは、関係のあるペアの集まりです。2項関係の例としては、等しいという関係 $(=)$ や小なりという関係 $(<)$ などがあります。

$\displaystyle 1 = 1,\quad 2 = 2,\quad 3 = 3, \ldots\\ 1<2,\quad 1<3,\quad 2<3,\ldots$

2項関係が関数になる条件

すべての関数は2項関係ですが、2項関係は一般には関数であるとは限りません。上の例では $(=)$ という2項関係は関数ですが、 $(<)$ という関係は関数ではありません。 $1$ より大きい数は複数ありますし、 $3$ より小さい数も複数あります。

2項関係を決めるには、2つの集合、定義域と値域を定める必要があります。ここでは $X$ を定義域、 $Y$ を値域とします。
必ずしも関数とは限らない $X$ と $Y$ 上の2項関係 $(\rhd_f)$ が関数であるための条件を考えます。

2項関係が関数になるひとつめの条件は、 $X$ の任意の要素 $x$ について、行先(ペアになる $Y$ の要素)がたかだかひとつに定まることです。
この条件を関数性と呼ぶことにします。
述語論理で書くと以下のようになります。

$\displaystyle\forall x \in X,\ y_1, y_2 \in Y,\,\\ x \rhd_f y_1,\, x \rhd_f y_2 \Rightarrow y_1 = y_2 \tag{1}$

2項関係が関数になるふたつめの条件は、定義域 $X$ のすべての要素について、行先が存在することです。
この条件を全域性と呼ぶことにします。
述語論理で書くと以下のようになります。

$\displaystyle \forall x \in X,\ \exists y \in Y,\,\\ x \rhd_f y \tag{2}$

(1)を満たしているが、(2)を満たしているとは限らない2項関係のことを部分関数と呼びます。これに対して、(1)と(2)の両方を満たしている2項関係を関数または全域関数という呼び方をします。

単射性、全射性

必要な準備ができました。ここからが本題になります。

関数が単射であるとは、関数の条件(1) (2)に加えて、
行先が重なることがないという性質を持っていることです。
以下の条件で表されるこの条件(1')を、ここでは単射性と呼ぶことにします。

$\displaystyle\forall y \in Y,\ x_1, x_2 \in X,\,\\ y \lhd_f x_1,\, y \lhd_f x_2 \Rightarrow x_1 = x_2 \tag{1'}$

いっぽう、関数が全射であるとは、関数の条件(1) (2)に加えて、
関数のありうる行先が値域 $Y$ すべてを含んでいるということです。
以下の条件で表されるこの条件(2')を、ここでは全射性と呼ぶことにします。

$\displaystyle\forall y \in Y,\ \exists x \in X,\,\\ y \lhd_f x \tag{2'}$

ここで、説明せずに使いましたが、 $(\lhd_f)$ とは $(\rhd_f)$ の逆関係で、 $(\rhd_f)$ を使って $y \lhd_f x \Leftrightarrow x \rhd_f y$ で定義することができます。

(1)と(1')、そして(2)と(2') を見比べてみると、 $X$ と $Y$ の役割と、記号の左右 $(\rhd_f)$ と $(\lhd_f)$ が入れ替わっていることがわかります*2。

$(\lhd_f)$ を新しい記号 $(\rhd_{\overline f})$ で置き換えてみるとよりわかりやすくなるかもしれません*3。

$\displaystyle\forall y \in Y,\ x_1, x_2 \in X,\,\\ y \rhd_{\overline f} x_1,\, y \rhd_{\overline f} x_2 \Rightarrow x_1 = x_2 \tag{1'}$

$\displaystyle\forall y \in Y,\ \exists x \in X,\,\\ y \rhd_{\overline f} x \tag{2'}$

以上より、

$(\rhd_f)$ の単射性とは、 $(\rhd_{\overline{f}})$ の関数性
$(\rhd_{\overline{f}})$ の単射性とは、 $(\rhd_f)$ の関数性
$(\rhd_f)$ の全射性とは、 $(\rhd_{\overline{f}})$ の全域性
$(\rhd_{\overline{f}})$ の全射性とは、 $(\rhd_f)$ の全域性

という関連がわかりました。単射性、全射性は、関数の条件であるところの関数性、全域性の裏返しなので、関数について考えると自然に表れてくる概念だということがわかります。

この関連がわかると、以下の主張も明らかなものとなります。

単射な部分関数は単射な逆部分関数をもつ。
単射かつ全射な全域関数は単射かつ全射な逆全域関数をもつ。

単射な部分関数というのは(1) (1') をみたす2項関係ですので、逆関係 $(\rhd_{\overline{f}})$ は単射な部分関数になり、これを逆関数と呼ぶことができます。
単射かつ全射な全域関数というのは(1) (2) (1') (2') をみたす2項関係ですので、逆関係 $(\rhd_{\overline{f}})$ は単射かつ全射な全域関数になり、これを逆関数と呼ぶことができます。

単射、全射と集合の要素数

単射、全射は集合の要素数と関連があります。

集合の要素数とは、集合に含まれる要素の、相異なるものの数のことです。
$X$ から $Y$ への全射部分関数が存在すると、 $X$ の要素数( $|X|$ とかきます)が $Y$ の要素数 $|Y|$ より小さくないことがわかります。

全射部分関数とは、(1)と(2')をみたす2項関係のことでした。(1)は関数の記法で書くと以下のようにも書けます*4。

$\displaystyle\forall x_1, x_2 \in X,\ \\ f(x_1) \neq f(x_2) \Rightarrow x_1 \neq x_2 \tag{3}$

すなわち,

$|Y|=m$ とすると*5、相異なる $m$ 個の $Y$ の要素 $y_1, y_2, \ldots, y_m$ が存在して、(2')より
$x_1 \rhd_f y_1,\ x_2 \rhd_f y_2, \ldots, x_m \rhd_f y_m$ となる $x_1,\ x_2,\ldots,x_m$ が存在することがわかります。
(1) の書き換えである(3)より、この $x_1,\ldots,x_m$ は相異なることがわかります。すなわち、 $|X| \geq m = |Y|$ となります。