写像の定義とその応用

順列、組み合わせなど場合の数の問題で、解答までの流れはおぼろげながら理解できるものの、全体像が今一つすっきりとしない、少し複雑な問題に出くわすと途方に暮れてしまう、ということが起こります。良い方法はないかと模索しているうちに、写像という概念に出会いました。写像の考え方を使うと順列、組み合わせなどの場合の数を少し違った角度から整理することができ、解答への見通しが立てやすくなります。

写像

写像の定義と写像ではないもの

写像とは

写像の定義: 集合 X から集合 Y への写像 $f: X \to Y$ とは、集合 X のそれぞれの要素に対して集合 Y の要素がただ一つ対応する規則のことです。このとき、集合 X をその写像の定義域（domain）、集合 Y を終域（codomain）と呼びます。また、X の各要素が対応するY の要素全体の集合を写像の値域（image）といいます。写像は次の通り定義されます。

定義域は集合X、終域は集合Yというように英大文字を使って表記しますが、N、KのようにX、Y以外の文字を使う場合もあります。写像はfなどの文字で表し、$f:X\longrightarrow Y$のように表記します。

例えば、X={1, 2, 3 , 4}、Y={1, 4, 9, 16}として、$y=x^2$という対応を考えます。どの$x$に対しても、$y$が1つ決まるので明らかに写像になります。

次にX={1, 2, 3 , -3}、Y={1, 4, 9, 16}とし、写像$f\colon X \longrightarrow Y$を$y=x^2$と定義すると、f(1)=1、f(2)=4、f(3)=9、f(-3)=9となります。この対応関係を表したのが図表1です。ここで、集合Yの要素{9}は集合Xの2つの要素{3},{-3}に対応付けられていますが、これも写像の定義を満たしています。

また、集合Yの中には{16}のように集合Xから対応付けられない要素がありますが、これも写像の定義を満たしています。なお、{1, 4, 9}のようにXの要素$x$に対応するYの要素$y$を、fによるXの像（image）または値域（range）といい、$y=f(x)$と表記します。したがって、値域は終域の部分集合といえます。

写像でないもの

写像の定義を確認してみましょう。すると、次のような対応は写像とは言えません。つまり、ある値 𝑥 に対して f(x) を計算しようとしても、対応する値が見つからなかったり、複数あって選べなかったりする場合、その対応は写像とはみなされません。

①　集合Xの要素に対応する要素が集合Ｙに存在しない

集合Xの要素$x$に対して、集合Yの中に対応する$y$が存在しないものがある

X={1, 2, 3, 4}、Y={1, 4, 9}と定義し、$y=x^2$を対応させると、集合Yには16が含まれていないので、f(4)の計算をすることができません。このような対応は写像にはなりません。

②　1つの集合Ｘの要素に対して複数の集合Yの要素が対応する。

X={1, 4, 9}、Y={1, 2, 3, -3}と定義し、「$y$は$x$の平方根」という対応を考えます。集合Xの要素9に対して集合Yの要素が2つ対応していて、どちらを選んでいいのかわからないので、やはり写像にはなりません。

集合Xの要素を１つ選ぶと、それに対応するYの要素が0でも複数でもなく、1つだけ決まるような対応を写像と考えます。

写像の特殊な形態、単射　全射

写像の中には、特別な性質を持つものがあります。それが全射、単射、および両方の性質をもつ全単射です。以下、図表3を見ながらみていきます。

全射

集合 Y のすべての要素に対して、必ず集合 X のどれか1つの要素が対応しているような写像を「全射」と呼びます。対応する X の要素が複数あっても問題ありません。

例えばX={1, 2, 3, -3}、Y={1, 4, 9}と定義し、$y=x^2$を対応させると、集合Yに集合Xに対応する要素$y$は存在しません。このような写像を全射といいます。集合xの-3と3が同じ集合Yの9に対応しますが、全射という上では問題になりません。

少しむつかしいですが記号で書くと次のように定義します。

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

（任意の y が Y に属するならば、ある x が X に属して y=f(x) を満たすものが存在する"For all y in Y, there exists an x in X such that f(x) = y）

全射は「上へ対応」と呼ぶこともあり、英語ではsurjection, surjective mapping、onto mappingといいます。全射では集合X、Yの要素の数をn(X)、n(Y)とすると、$n(X)\geqq n(Y)$という関係が成り立ちます。

単射

$f: X \to Y$ が単射であるとは、異なる入力が必ず異なる出力に対応することを意味します。より正式には、任意の2つの異なる X の要素 $x_1, x_2$ に対して常に $f(x_1) \neq f(x_2)$ が成り立つとき、$f$ は単射です。言い換えると、集合 X の異なる要素同士が同じ集合 Y の要素に対応することが一切ないということです。つまり、集合 X の各要素に対応する集合 Y の要素はそれぞれ固有で、他の入力と共有されません

図1.3には単射の具体例が示されています。図では、集合 X の異なる要素から出た矢印が必ず異なる集合 Y の要素に向かっています。また、どの出力も他の入力とは重複していないことが確認できます。したがって、この写像は単射であると言えます。一方、図1.4には全射の例が示されています。図のとおり、集合 Y の各要素には必ず集合 X から矢印が1本届いています。そして、集合 Y 内に集合 X からの矢印が届いていない要素は一つも存在しません。したがって、この写像は全射であると言えます。

X={1, 2, 3}、Y={1, 4, 9, 16}再び、$y=x^2$という対応を考えます。

Xの異なる要素が、必ずYの異なる要素に対応しているような写像を単射といいます。集合Yには集合Xに対応しない16という要素がありますが、単射と呼ぶ上では問題ありません。

少し難しくなりますが、記号では次のように記述します。

$\forall x,x^{\prime }\in X:\left[ x\not=x^{\prime}\Rightarrow f\left(x\right)\not=f\left(x^{\prime }\right) \right] $

任意の x と x' が X に属するならば、x と x' が等しくないならば、f(x) と f(x') も等しくない。

"For all x and x' in X, if x is not equal to x', then f(x) is not equal to f(x')."

単射は英語ではinjection, injective mapping、one-to-one mapping（一対一写像）といいます。

集合X、集合Yの要素の数を$n(X)$、$n(Y)$とすると、単射の場合は$n(X)\leqq n(Y)$となります。

全単射

全射と単射、両方の条件を満たす写像を全単射といいます。すなわち、集合X の各要素が集合 Y の要素1つに正確に対応し、また集合Yの各要素が集合 Xの要素1つに正確に対応するものをいいます。

英語では、bijective function, bijection、one-to-one onto mapping（1対1上への写像、上への1対1写像）、one-to-one correspondence（1対1対応）といいます。細かいところですが、単射は1対1写像、全単射は1対1対応と紛らわしいので注意が必要です。

全単射は全射と単射の両方を兼ねており、全射は$n(X)\geqq n(Y)$、単射は$n(X)\leqq n(Y)$なので、必然的に全単射であるということは、$n(X)=n(Y)$になります。

逆写像

最後に、逆写像という考え方をご紹介します。図のとおり集合Xから集合Yへの$y=x^2$という写像を考えます。

定義域Xの各要素に対して、終域Yの要素がちょうど1つ対応しているので、この対応関係は写像の条件を満たしています。逆に、$x=\sqrt y$という対応を考えます。集合Yの全ての要素に対して集合Xの1つの要素が対応しているので写像の要件を満たしています。f の逆写像は 集合Yの要素を集合Xの要素に対応させるものであり、$f^{-1}$とあらわします。

ここで、写像fが逆写像$f^{-1}$を持つ意味を考えます。

①逆写像が写像の要件を満たしているということは、集合Yに対して集合Xの要素が複数対応することはありません。ということは、Xの異なる要素が、必ずYの異なる要素に対応することになるので、写像fは単射になります。

②集合Yの中に集合Xと対応していない要素は存在しません。ということは、集合Yのすべての要素が、集合Xの要素のどれかと対応しているので、元の写像fは全射になります。

①、②のことから、逆写像が存在する写像は、全単射であるといえます。

集合Xの個数を数えるのが難しい場合、集合Yと全単射の関係にあることを使い計算する方法があります。この際、全単射であることを証明するために逆写像を使うことがよくあります。

写像ではあるが、全射でも単射でもないケース

写像の条件は満たしているものの、集合 Y に未対応の要素があったり、複数のx が同じy に対応していたりすることがあります。このような対応は、一般に特に名称はありませんが、今後一般の写像（general mapping）と呼ぶようにします。

写像の応用

ここまで写像の基本を説明しました。次に、写像が威力を発揮する具体例を２つご紹介します。

鳩の巣原理

直観的には、うまく配置すればすべての点が$\sqrt 2$より離れた点を打つこともできそうな気もしますし、狭い空間に10個もの点を打ち込むのだから、どこかのペアは $\sqrt 2$より近くならざるを得ないような気もします。いずれにしても、その納得のいく証明方法はなかなか思いつきません。このようなときに、単射の考え方が役に立ちます。

次のように正方形を3×3で9個の縦横1㎝のマスに区分けし、10個の点Xから9個のマスYへの写像を考えます。$n(X)\geqq n(Y)$から単射にはならないので、少なくとも2つの点が1つのマスに入ることになります。ところでマス内の2点の距離は、どんな工夫をしても対角線の長さ$\sqrt 2$ より短くなります。したがって、距離が $\sqrt 2$​ 以下となる点のペアが必ず存在します。

このように、鳩の数が巣の数を超えると必ずあぶれる鳩が出るという当たり前の考え方を鳩の巣原理（Pigeonhole Principle）といい、複雑な問題をすっきり整理するのに有効な場合があります。

逆写像の考え方を使うと解ける問題

逆写像による証明方法を理解するため次の問題を考えます。

(1)オイラーの分割数という有名な問題です。次の通り 11通りになります。

1+ 1+ 1+ 1+ 1+ 1

2+ 1+ 1+ 1+ 1

2+ 2+ 1+ 1

2+ 2+ 2

3+ 1+ 1+ 1

3+ 2+ 1

3+ 3

4+ 1+ 1

4+ 2

5+ 1

6

たかだか6のような小さな整数も、正しく数え上げるのは大変です。今後、このサイトではPythonを使って分割を生成する興味深いプログラムをご紹介します。

(2)では図表8にそって逆写像の考え方を使い証明します。

集合Xを6の分割数のうち奇数の和だけで表す数として、[5+ 1] [3+ 3] [3+ 1+ 1+ 1][1+ 1+ 1+ 1+ 1+ 1]の4通りとなります。

一方、集合Yをすべて異なる数の和で表す数として [6][5+ 1] [4+ 2] [3+ 2+ 1]の4通りとなります。確かにn(X)=n(Y)=4となり確かに問題文の通りとなります。しかし、これは6という小さな値だからたまたまそうなっただけで、もっと大きな数となると何とも言えません。どうすれば証明することができるか途方に暮れてしまいます。

そこで、次のような対応を考えます：

集合Xから集合Yへの写像

要素で同じ数nがあれば2nに置き換える。その結果さらに同じ数があれば同じ操作を繰り返すという操作を、同じ数がなくなるまで行います。この操作では各要素の和が6であることを保ったまま、同じ数字をなくしていくので、最終的には相異なる数の組み合わせになり、写像である要件を満たしています。

集合Yから集合Xへの写像

これまでの逆で、偶数2nがあれば、それを2で割り、その結果の中に偶数があればさらに2で割る操作を偶数がなくなるまで繰り返します。最終的には、偶数がなくなり奇数だけの組み合わせになります。この操作では、各要素の和が6であることを保ったまま、偶数をなくしていくので、最終的には奇数の組み合わせとなり、写像である要件を満たしています。

これらのことから集合Xと集合Yの対応は全単射といえます。つまり、n(X) = n(Y) になります。

確かにその通りという気もしますが、騙されたような感覚も拭えません。今後、このサイトでは、もっと大きな整数の分割でも同じルールが成り立つことを確かめていきます。

区別ありと区別なし

写像を使って場合の数について整理するうえで、全射や単射などとは異なる視点として、区別あり(labeled)と区別なし(unlabeled)という考え方があります。その違いを見るために、次の問題を考えます。

(1)は順列の例になります。集合Nは{0,1,2}、集合K{青,黄,赤,紫,緑}　というようにラベルがついているもの(labeled)と考えます。0,1,2がどの色を選んだかで(青、赤、緑)、(青、緑、赤)、(赤、青、緑)、(赤、緑、青)、(緑、赤、青)、(緑、青、赤)は別の順列として考えます。このように

一方、(2)は組み合わせになり、集合Nに区別がなくなります。この結果、前の6つは同じ組み合わせとなります。例えば(青、赤、緑)がこの6つを代表します。このように、区別なし(unlabeled)といいます。このように、同じ単射の写像でも集合の中でラベルがあるか無いかで全く異なる対応になります。

分類の切り口と写像12相（Twelvefold way）

これまで見てきた写像の分類は、対応の種類（単射、全射、一般写像）と、定義域（集合$N$）および終域（集合$K$）のラベルの有無という2つの切り口によって行われます。

具体的には、対応の種類が3通り、ラベルの有無がそれぞれ集合$N$のラベルの有無および集合$K$のラベルの有無の組み合わせで4通りあり、合わせて3×4＝12通りの写像が定義されます。

これらをまとめて分類する考え方を12通りの分類法という意味で写像12相（Twelvefold way）といいます。以下の一覧表では、定義域$N$のラベルの有無および終域$K$のラベルの有無ごとに、単射、全射、一般写像の3種類を整理しています。