プログラミングで学ぶ写像 前編 - 集合の復習、写像の定義、像と逆像

最近は機械学習ブームにより、ソフトウェアエンジニアが線形代数に再入門するといったことが増えてきているのではないでしょうか。線形代数を学ぶ上で線形空間(ベクトル空間)から線形空間への写像、つまり線形変換が最も大事な概念であるわけですが、いきなり写像という言葉が出てきて怯んでしまう方もいるかと思います。
しかし、実のところ我々プログラミング経験者にとって、写像はかなり馴染み深いものです。というのも、写像をプログラミング経験者に簡潔に伝えるとしたら、「いくつかルールがあるMap(連想配列、ディクショナリ)あるいはFunction(関数)」と言えるからです。英語でも写像は、map, mappingと書きます。つまり、ある対象からある対象への対応であるわけです。
この投稿では、線形代数を語る上で必要不可欠な写像の数学的定義をプログラミングを通して理解することを目指していきます。

この記事は2部構成のうちの前半部分です。
* プログラミングで学ぶ写像 前編 - 集合の復習、写像の定義、像と逆像
* プログラミングで学ぶ写像 後編 - 全射・単射・全単射・写像の合成

集合の復習

写像の前に集合についての復習をしておきましょう。写像は実は集合間の関係を議論するものですから、集合を避けて写像を理解することはできません。Wikipedia曰く、集合は「ものの集まり」だそうです。つまり、一般的には集合住宅は住宅の集合、生徒が集まる学校は生徒の集合、車がたくさん集まる駐車場は車の集合など、なんでもものが1つ以上集まっていれば集合と言えるでしょう。
では、数学における集合といったら我々がイメージしやすいのはなんでしょうか。数学では数を扱うわけですから、数を集めたものを集合と考えるのがもっともシンプルな発想な気がします。
つまり、整数の集合であれば、0, ±1, ±2から始まる無限個の数が集まったものですね。
もちろん、実数や有理数、複素数もこのように集めれば、それは集合となるわけです。（無限でも有限でも構いません。）
ではプログラミングでは集合はどのように扱うのかという話に入りましょう。以後はプログラミング言語にJavaScriptを利用します。JavaScriptを選定した理由としては、みなさんに広く利用されている言語で、Syntaxに大きな癖がない（主観です）ためで、特に深い理由はありません。また、JavaScriptは厳密に整数型と浮動小数点数型（ここでは実数とみなします）を分けることが出来ないので、実数を表すときは、1., 2., 3., 整数を表すときは1, 2, 3のようにリテラルで差別化していきます。

プログラミングでは配列(array)を使って集合を表現します。コンピューターで無限を表現することは出来ませんので、0から10までの整数の有限集合と、アルファベットのa-zまでの文字(Char)の有限集合を表現することを考えてみましょう。（※JavaScriptではChar型は無いので、一文字でもString型として扱われます。）

const intSet = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const stringSet = [
    "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", 
    "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
]

うーん。なんの味気もないですね。でもこれが集合です。
また、一般的に集合を構成する一つ一つの要素を元（げん）といいます。intSetであれば、それぞれの整数が元です。これを数学では、

a, b  ∈ StringSet,  0, 1  ∈ intSet

と表記します。
集合を構成する元の個数のことを濃度といい、intSetの濃度は11、stringSetの濃度は26です。数学的には、|A|や|B|と表記します。
これらは、JavaScriptでは以下のようなコードとなります。

// a ∈ intSet, b ∈ StringSet
const a = intSet[0], b = stringSet[3]
console.log(a, b) // => 0, "d"

// intSetとstringSetの濃度
console.log(intSet.length, stringSet.length) // => 11, 26

その他に集合には、共通部分、和集合などの概念がありますので、数学的な定義とプログラミングによる実現方法を書き下します。(今回、写像の解説に利用する集合の論理のみ)

数学における集合の論理

A, Bを集合とする。
(1) 空集合を φ(ファイ)と表す。空集合とは文字通り、元が０個の集合のこと
(2) A ∪ B で、A, B の和集合を表す。和集合とは、集合A,Bに対して、少なくともどちらか一方の集合に属する元全体の集合のこと
(3) A ∩ B で、A, Bの共通集合を表す。共通集合とは、集合A,Bに対して、どちらの集合にも属する元全体の集合のこと
(4) A ⊂ B で、A は B の部分集合を表す。部分集合とは、集合A,Bに対して、集合Aの元のすべてが集合Bの元になっている集合のこと

JavaScriptだと

const A = [1, 2, 4, 7, 9, 10]
const B = [0, 2, 5, 6, 8, 9]

// (1) 空集合
// [100, 1000, 10000]はAに含まれていないものとして、無作為に選んだだけ
const phai = A.filter(z => [100, 1000, 10000].includes(z))
console.log(phai) // => []

// (2) 和集合
// ※unique関数はjsには存在しません。配列内の要素のユニークを取るものと解釈ください
const union = unique(A.concat(B))
console.log(union) // => [1, 2, 4, 7, 9, 10, 0, 5, 6, 8]

// (3) 共通集合
const intersection = A.filter(z => B.includes(z))
console.log(intersection) // => [2, 9]

// (4) 部分集合
const subset = A.slice(1, 4)
console.log(subset) // => [2, 4, 7]

プログラミング言語で集合を表現すると、なんだこんなものかと感じるかと思います。数学における集合は論理式により難解に感じますが、プログラミングのレベルに持ち込むと、実はこういったシンプルなことなのです。集合について簡単に復習したところで、早速プログラミングで写像を表現することに挑戦していきたいと思います。

写像の定義

集合Aの任意の元aに対し、集合Bの元f(a)がただ１つ定まっているとき、fをAからBへの写像という。fが集合AからBへの写像なら次のように書く。

また論理記号かよ...と思ったかもしれません。しかし、fは関数と捉えると理解できます。AとBをそれぞれ整数全体の集合として、f(x) = ax+bという一次関数を例に考えましょう。つまり、Aの元xをfに入力すると、ax+bというBの元が返ってくる関数です。

これをJavaScriptで表現するなら

function f(x) {
    const a = 1, b = 2
    return ax + b
}
const y = f(3)
console.log(y) // => 5

となります。この写像は整数を入力すると整数を返す写像と捉えることが出来ます。（数学では、fは加法で閉じていると表現します。）
もちろん、JSにおける整数はNumber.MIN_SAFE_INTEGERからNumber.MAX_SAFE_INTEGERの範囲しか表現できないので、数学における整数全体から整数全体への写像を表現できるわけではありません。つまり、JSにおけるfはxの定義域、yの値域が有限であり、それを超えたfの挙動に関しては未定義（というか、ランタイム依存）の動作を引き起こし、それは写像とは呼べないものもあるのです。（オーバーフロー時に最大、最小値に丸め込まれたり、単純にクラッシュする等々）よって、このJSで実装されたfが上の写像で定義したfと完全に一致するというわけではなく、「写像fをコンピューター上で表現してみた」ということを忘れてはいけません。
なお、この例から、冒頭で触れた「写像は関数である」ということが伝わったかと思います。

像と逆像

ではもう少し写像に関しての理解を深めるべく、像と逆像をプログラミングを通して学んでいこうと思います。
ここで再び、AとBを集合とし、写像f: A -> Bを定義します。

f(a) = bとなるa ∈ Aが存在するとき、bはaの像(Image)であるという。
また、S ⊂ A, f(S) = {f(a) | a ∈ S} でこれをSの像という。

まずはbの像をJavaScriptで表します。写像fをf(x) = ax+bとしましょう。

function f(x) {
   return x + 1
}

// 0から999までの整数を要素に持つ配列を生成
const A = [...Array(1000).keys()]

for(const a of A) {
    // bはaの像
    const b = f(a)
}

この例では、 aの定義域は整数で[0, 999]、bの値域は整数で[1, 1000]です。整数の部分集合から整数の部分集合への写像となっていますね。
なお、[a, b]という表記は、閉区間を表しています。閉区間とは、数直線上で、aからbまでの数をすべて含む区間という意味です。逆に、開区間(a, b)というものもあり、これらはaからbまでの数でaとbを除くものすべてを含む区間となります。「整数で」と念押ししているのは、JavaScriptではArray<Int>のように型を定めることができないので、ルールで入力と出力を整数に限定すると決めないと、有理数や無理数を区間に含んでしまうためです。

次にSの像です。{f(a) | a ∈ S} のような見慣れない表記が出てきたと思いますが、これは集合の構成を表す論理式です。
{} は空集合です。{0, 1, 2, 3}は整数0, 1, 2, 3を元に持つ濃度4の有限集合です。{f(a)}はたとえば、f(x) = x^2という関数であれば、
{f(1), f(2), f(3)} = {1, 4, 9} となります。
この像の定義のように、パイプで繋ぐものは条件式であり、{x | 条件1 | ... | 条件n }と書かれていたら、この集合はxで構成されていて、そのxは条件1から条件nをすべて満たすと言っています。Sの像の定義は{f(a) | a ∈ S}ですから、「この集合はf(a)、つまりBの元で構成されていて、aはSに属するすべてのもの」と解釈することが出来ます。このように、数学的には集合を構成する元が先にあって、その元に色々条件がついてくるという順番で考えます。しかし、プログラミングでは条件n -> ... -> 条件1のように右から左へ条件の評価を進めて集合を構成する要素をフィルターしていくほうが考えやすいですし、無駄な計算を省くことができそうです。つまり、Sの像であれば、Sを先に作って、Sのすべての要素に対してfを適用するという順番で評価をしていくと無駄がなさそうです。JavaScriptで実装してみましょう。

// S ⊂ Aに該当
const S = A.slice(1, 500)
console.log(S) // => [1, ..., 499]

// f(S) = {f(a) | a ∈ S}に該当
const image = S.map(f)
console.log(image) // => [1, ..., 500]

論理式と評価の順番が異なっていますが、実際には同じことをコードで表現できていることがわかります。
余談ですが、今回は伝えやすさを重視したのと、Sのサイズが高々500未満なのでこのようなコードにしました。Sのサイズが大きいのであれば、Sを先に構成せずに、然るべきタイミングでAから条件にマッチするaを遅延的に評価するという方法も十分に考えられます。fが複雑であれば、RDBMSのように、予めindexを構築しておくこともあるでしょう。このように、プログラミングによる像の表現方法は性能やメンテナビリティを考慮すると数多のものがあります。大事なのは、像の定義が言うことを満たしていればそれは像となるということです。

次に逆像の定義とプログラミングによる表現方法を見ていきましょう。

S ⊂ A, T ⊂ B, f^{-1}(T) = { a ∈ A  | f(a) ∈ T}
のとき、これをTの逆像という。（ただし、一般的に逆像は写像ではなく単なる集合である。）

f^{-1}はtex的な表記なのですが、fインバースと読みます。本来はfの右肩に-1が乗るような指数表示だと考えていただきたいです。ではTの逆像の定義の意味を解釈していきましょう。「Tの逆像はAの元aで構成されていて、f(a)はBの元となるものすべてを満たす」です。
これをプログラミングで実装するとどうでしょうか。指数関数では-nが指数としてかかっていれば、それはnの逆数を意味することでした。写像にかかっている場合は、fの逆操作を意味すると考えられます。よって、fを具体的に定めれば、fの逆操作を具体的に定められそうです。たとえば、f(x) = ax+bであれば、f^{-1}(x) = x - b / a が逆操作に該当します。これをJavaScriptで実装してみましょう。

// BはAの元それぞれを二乗した整数の集合
const B = A.map(f)

// T ⊂ Bに該当
const T = B.slice(0, 200)

// fInverseはfの逆操作を施す
function fInverse(y) {
   return y - 1
}

// f^{-1}(T) = { a ∈ A  | f(a) ∈ T}に該当
const fInverseSet = T.map(fInverse).map(a => {
　　// Tの取り方によってはaはAの元かまだわからないので、Aに含まれているかチェック
   if(!A.includes(a)) {
       throw new Error(`${a} not in A`)
   }
   return a
})
console.log(fInverseSet) // => [0, ..., 200]

この実装は、f(x) = ax+b においてTの逆像の論理式が示していることと同様の結果が得られることがわかります。この実装であれば仮にTの範囲が動いてもTの逆像の定義に反しません。
もちろん、このコードは論理式を伝えやすいように実装しているので、性能的には最低レベルとなります。

また、関数以外にもmapも写像を表します。JavaScriptであれば

function f(x) {
    return Math.pow(x, 2)
}

const map = {
    1: f(1),
    2: f(2),
    3: f(3)
}
console.log(map) 
// {
//    1: 1,
//    2: 4,
//    3: 9
// }

とすれば、これも写像f: A -> Bを表します。つまり、集合{1, 2, 3}はf(x) = x^2という関数で、集合{1, 4, 9}に対応しています。
逆像を取るのであれば

const values = Object.values(map) // => [1, 4, 9]
const keys = [] // valuesの逆像を格納する配列
for(value of values) {
    for(const key in map) {
        if(map[key] === value) {
            keys.push(key)
        }
    }
}

console.log(keys) // => [1, 2, 3]

とすることが出来ます。よって、逆操作を定義しなくても予め対応が決まっていれば、このように逆像を取ることができるということですね。mapのkeysとvaluesは像と逆像の関係であったのです。

しかし、逆像の定義で、「ただし、一般的に逆像は写像ではなく単なる集合である」と記載があったのを覚えていますでしょうか。この注意が必要になるシチュエーションをJavaScriptで再現してみましょう。先程のmapに-2とその2乗数の対応を追加します。

const map = {
    1: f(1),
    2: f(2),
    3: f(3),
    -2: f(-2)
}
console.log(map) 
// {
//    1: 1,
//    2: 4,
//    3: 9,
//    -2: 4
// }

「mapにおいて、{1, 2, 3, -2}の逆像を取るプログラムを書いてください。と言われたらどう書きますか？ .......

実は、2と-2の像が4なので、その逆像を取るときに2と-2どっちを取ったらいいかわからなくなってしまうのです。
では配列やタプルで-2と2の双方を取ったらいいのでは？と思うかもしれません。しかし、それは写像にはなりません。なぜなら写像の定義は次であったからです。

集合Aの任意の元aに対し、集合Bの元f(a)がただ１つ定まっているとき、fをAからBへの写像という。

つまり、写像とはひとつの元の行き先が複数あってはいけないということです。よって、一般的に逆像は写像ではなく単なる集合であると注意がされています。
実際、逆像が写像になることがあるのですが、それは、「プログラミングで学ぶ写像 後編」で詳しく解説しますね。

どうでしたでしょうか。プログラムで学ぶと言っておきながら、やはり理論的な説明が長くなってしまいました。コンピューターで数学を語るのは難しいですね。それでも、プログラムを多少絡めたことで、写像に関する理解が以前よりも深まったという体験が届けられていれば嬉しいです。

それでは、また後編でお会いしましょう。