見出し画像
Photo by akari_n

プログラミングで学ぶ写像 後編 - 全射・単射・全単射・写像の合成

noppoman

この記事は
プログラミングで学ぶ写像 前編 - 集合の復習、写像の定義、像と逆像
の続きです。

前半では、集合の復習から始まり、写像の定義、像と逆像についての数学的な定義とそれらをJavaScriptで実装するということを行ってきました。後半では写像でも特に重要な全射・単射・全単射・写像の合成についての数学的な定義とJavaScriptを使った証明（弱めの）を行い、最後のほうでソフトウェアでどのように写像が使われているか（あるいはそれをどうやって写像と見出すか）といったことに触れていければと思います。

単射

f: A -> Bが単射(Injective)であるとは
∀a, a' ∈ A, a ≠ a' => f(a) ≠ f(a')
が成り立つことを言う。

記号がたくさんで混乱しそうですが、ひとつづつ噛み砕いていきましょう。まず、「∀」は「任意のxx」を意味する記号です。AnyのAがひっくり返ったものと覚えるといいです。「≠」はnot equalを表す記号で、プログラミング的には「!=」というと伝わりやすいでしょうか。最後に 「=>」ですが、これは「P ⇒ Q」という使い方をし、「命題Pが真なら必ず命題Qも真」ということを表します。これらを頭に入れた上で、単射の定義を日本語で言い換えれば、「Aに属する任意の元a, a'を取ってきて、それらが相異であれば、f(a)とf(a')も相異である」となります。一般的にはこれの対偶を取って

∀a, a′ ∈ A, f(a) = f(a′) ⇒ a = a′

と表すことが多いです。この記事でもこっちの対偶の方を使っていきます。
これも日本語で言い換えると、「Aに属する任意の元a, a'を取ってきて、f(a)とf(a')が一致するならば、aとa'も一致する」ということになります。
つまり単射とは、「全てのaにおいて行き先が被ってはいけない」ということを言っています。単射となるfが存在する時、集合の濃度の関係は|A| ≤ |B|です。
では、単射をJavaScriptを使って表現していきましょう。これまではある数学的な定義をJavaScriptを用いて実装するというアプローチでしたが、単射の定義はより抽象的で、どう実装していくか悩ましいです。また、単射な関数を実装するということは、同時にその関数が単射であることを証明する必要する必要性があります。なので、ここでは少し天下り的にすでに単射と知られている関数を使って、その関数が単射であるかを確認することにします。
単射な関数として有名なのは前編にも登場した１次関数f(x) = ax + bです。今回はプログラミングで学ぶ写像というタイトルですので、頭で考える前に、JavaScriptを使って、一次関数f(x) = ax + bが単射であることを確認してみましょう。
まずは、対象の関数が単射であるかチェックする関数、checkInjectiveを作ります。

const assert = require("assert")

/**
* @param {function} f 対象の関数
* @param {array} targetRange 定義域。整数に限定すること
*/
function checkInjective(f, targetRange) {
   // 単射であるとチェックされた元aの集合
   const injectiveElements = []

   for(const a of targetRange) {
       for(const aDash of targetRange) {
           if(f(a) === f(aDash)) {
               if(a === aDash) {
                   injectiveElements.push(a)
               } else {
                   throw new Error(`f is not injective: ${a} != ${aDash}`)
               }
           }
       }
   }

   assert.deepEqual(injectiveElements, A)

   console.log("f is injective.")
}

これはf(a)の行き先が被っていないことを証明するもので、単射の条件「f(a) = f(a')の時、a = a'」にマッチしたときに、各ループでただ一度だけinjectiveElementsにaがpushされるというプログラムになっています。
つまり、forを抜けた後に、fが単射であれば必ずtargetRangeとinjectiveElementsの長さと要素が一致します。そうでない場合、そもそもfは写像になっていない可能性があります。また、f(a) === f(aDash)であるが、a != aDashとなれば、行き先が被ってしまい単射の定義に反するので、Errorがthrowされることになります。fが単射であれば、最後に「f is injective.」​が表示されます。

では、早速f(x) = ax + bをcheckInjectiveにかけてみましょう。対象区間を整数の閉区間[-100, 100]とします。整数に限定する理由としては、コンピューターで[0, 1]の実数区間をそもそも表現することができないからです。実数域に拡大した途端に、0と1の間には無限の有理数と無理数がありますからね。。

// rangeはstartからendまでの整数の要素を持つ配列を生成する関数
function range(start, end) {
   const list = [];
   for (let i = start; i <= end; i++) {
       list.push(i)
   }
   return list
}

function f(x) {
   return x + 1
}

const A = range(-100, 100) // [-100, 100]を対象区間に
checkInjective(f, A) 
// f is injective.

このプログラムは無事checkInjectiveをパスし、単射であることが分かりました。しかし、xの定義域をかなり限定してしまっているので、本当に単射って言えるの？と思う方もいるかと思います。その場合は、ループの条件をNumber.MIN_SAFE_INTEGERからNumber.MAX_SAFE_INTEGERまでの整数に変更し、このプログラムを実行してみてください。

さらに理解を深めるために、次に単射ではない関数を見てみましょう。単射でない有名な関数はxの絶対値を返す関数f(x) = |x|です。これはx,y平面のグラフで考えると簡単です。先程の１次関数はxの増減に応じてひたすら伸び続ける直線でしたが、f(x) = |x|では、yは負の値を取らないので、負のxをfに入力しても行き先は常に正となり、原点を中心にV字を描きます。つまり、xと-xのときにyの値が一致します。
これも確認のため、checkInjectiveにかけてみましょう。JavaScriptで絶対値を返す関数はMath.absにより提供されています。

const A = range(-100, 100) // [-100, 100]を対象区間に
checkInjective(Math.abs, A) 
// Error: f is not injective: -100 != 100

結果はエラーで、無事Math.absは対象区間で単射ではないと判定されました。エラーから、f is not injective: -100 != 100 が出力され、|-100| = |100|であっても、-100 ≠ 100となっていることが確かめられます。しかし、f(x) = |x|はその特性から、x ≥ 0であれば単射となります。これも念のため確認しておきましょう。

const A = range(0, 100) // [0, 100]を対象区間に
checkInjective(Math.abs, A)
// f is injective.​

これを実行すると、無事f is injectiveが表示されました。このように、定義域により単射になったりそうでなくなることは往々にしてあります。この他に、f(x) = sinxなども単射ではない関数です。興味がある方は確認してみてください。

全射

f: A -> Bが全射(Surjective)であるとは
∀b ∈ B, ∃a ∈ A, b = f(a)
が成り立つことを言う。

ここで新たな記号「∃」が出てきました。これは、存在するという意味で、ExistsのEが反転したと思うといいです。この定義を日本語で言い換えると、「Bの任意の元bに対して、f(a) = b となる a が存在する」となります。さらに噛み砕けば、「集合 A の各元が集合 B の各元全てに対応する。」と考えることも出来ます。つまり異なるaから同一のbに対応することが許さるのです。全射となるfが存在する時、濃度の関係は|A| ≥ |B|です。
それを考えると、先程単射ではない例で登場したf(x) = |x|がまさに全射であるのです。これもJavaScriptで確認してみましょう。
まずは、fが全射であるかを判定する関数checkSurjectiveを単射と同様に作成します。

/**
* @param {function} f 対象の関数
* @param {array} A 定義域。整数に限定すること
*/
function checkSurjective(f, A) {
    // 値域を予め生成しておく
    const B = A.map(f).filter((value, index, self) => self.indexOf(value) === index)
    
    for(const b of B) {
        // ∃a ∈ A, b = f(a)に該当
        const hasMap = A.filter(a => b == f(a)).length > 0
        if(!hasMap) {
            throw new Error(`f is not surjective: There is no \`a\` that becomes \`f(a) = ${b}\``)
       }
    }
    console.log("f is surjective.")
}

checkSurjectiveは与えられた関数が定義域から値域への対応があるかをチェックします。１つでも対応がない（b = f(a)となるaが存在しない）場合、エラーをthrowします。
では早速、f(x) = |x|が全射か調べましょう。

const A = range(-100, 100)
checkSurjective(Math.abs, A, B)
// f is surjective.

Math.absは無事、対象の定義域で全射と判定されました。
逆に全射ではない関数に、実数全体におけるf(x) = x^2があげられます。コンピューターで実数全体を表すことは出来ないのでコードは割愛しますが、y = -1のときに、f(a) = -1となるaが存在しないためです。

全単射

写像f: A -> Bが全単射(bijective)であるとは、fが単射かつ全射であるこという

全単射は集合Aと集合Bの1対1対応というとさらにわかりやすいでしょうか。全単射となるfが存在する時、集合の濃度は|A| = |B|です。つまり、fが全単射のとき、集合Aと集合Bの元の個数が一致します。
全単射の例はすでに登場していて、１次関数f(x) = ax+bがまさにそうです。
早速、JavaScriptでfが全単射であるかを確認していきましょう。新たにcheckBijectiveを作らなくても、以前作ったcheckInjectiveとcheckSurjectiveを使って、fが全単射であることを確認できます。つまり、fが単射かつ全射であることを確認できればよいのです。

function f(x) {
    return x + 1
}

const A = range(-100, 100)
checkInjective(f, A)
checkSurjective(f, A)

これを実行すると

$ f is injective.
$ f is surjective.

が表示されます。したがって、f(x) = ax+bは対象の区間で全単射であるということが証明されました。

また自身から自身への写像f: A -> Aは明らかに全単射です。不要と思われますが、コードで表すと次のようになります。

function f(x) {
    return x
}

const A = range(-100, 100)
checkInjective(f, A)
checkSurjective(f, A)

このような写像を恒等写像といい、Aの恒等写像をid_Aと書きます。このような話をする意図として、群などでは写像の合成がid_Xになったときにいいことがおきてくれます。その話に関しては、商群が分かると、群の準同型定理が自然と分かるという話 でしているので、群の基礎と準同型に関して知識があり、かつ興味がある方は読んでみてください。

写像の合成

f: A -> B, g: B -> Cが写像なら、AからCへの写像g ◦ fをg ◦ f(a) = g(f(a))と定義し、f, gの合成という。

写像の合成は関数の合成と同義です。この定義では、2つの関数を合成していますが、いくつの関数を合成しても構いません。注意点として、右側の関数から順に評価していきます。JavaScriptでさっそく表現してみましょう。
fとgを整数全体から整数全体への写像と捉えてfとgを合成します。

function f(x) {
    return x+1
}

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

// g ◦ f
const gof = (x) => g(f(x))

// A ⊂ Zと考える
const A = range(1, 100)

A.map(gof) // => [4, ..., 10201]

新たにgofという関数をfとgを合成して作っただけなのであまり面白みが無いかもしれません。ただし、合成関数では以下の性質が非常に重要になります。

■合成写像における単射性
(1) f と g が単射ならば、g ◦ f は単射である
(2) g ◦ f が単射ならば、f は単射である
(3) g ◦ f が単射でも、g は単射であるとは限らない
(4) g ◦ f が単射で、f が全射ならば、g は単射である

■合成写像における全射性
(1) f と g が全射ならば、g ◦ f は全射である
(2) g ◦ f が全射ならば、g は全射である
(3) g ◦ f が全射でも、f が全射とは限らない
(4) g ◦ f が全射で、g が単射ならば、f は全射である

たとえばfとgがぞれぞれ１次関数f(x) = ax+bであれば、g ◦ fも単射かつ全射つまり全単射になるということを言っています。合成する関数どうしがどういった構造であるかで合成後の構造が決定します。ひとつひとつをコードにしませんが、これは非常に重要なポイントです。

逆写像

写像の解説もいよいよ最後です。

A, B を集合とし、写像 f : A → B とする。f に対して、ある g : B → A が存在し、g ◦ f = id_A、f ◦ g = id_B が成立するとき、f は逆写像を持つという。このとき、g は f の逆写像という。これを g = f^{-1} または f = g^{-1} と書く。

これを簡単に言えば、「fが全単射であれば、fは逆写像を持つ」ということを言っています。前編で、「一般的に逆像は写像ではなく単なる集合である」と注意していましたが、fが全単射であればBの逆像も1対1の対応が作れるので、写像になるのです。このような逆像を逆写像と言うことが出来ます。また、表記が f^{-1} と逆像と一緒なので、混同しないように注意が必要です。（数学はこういうことが往々にしてあります。）

また、逆写像は逆関数とも呼ばれます。前編では逆操作と濁していましたが、あれは本来fが全単射であるかわからないので、逆関数と言い切ることが出来ませんでした。ちなみに、その時の例で使った f(x) = ax+b は全単射ですので、f^{-1} = f(x) - b / a は f(x) = ax+b の逆関数となります。

ここまでで、写像の解説は一区切りがつきました。最後に、ソフトウェアでは写像がどのように使われているのか2つの例を見ていきましょう。以降では数学的な数から数への写像は登場しませんが、集合とは「ものの集まり」であったのですから、数ではなくても写像を構成できるはずです。

RDBMSの1対1関連に見る逆写像

逆写像では具体的な例をまだ見ていなかったので、RDBMSにおける1対1のテーブルの関連で逆写像を見ていきましょう。
今回は、銀行口座におけるユーザーと口座の関連を考えてみることにします。この関連を選んだ理由として、異なるユーザーから同一の銀行口座を開設することは出来ませんから、この対応は全単射であると言えるからです。
ユーザーをusersテーブル、口座をbank_accountsテーブルとして用意します。usersとbank_accountsはhas_oneとbelongs_toの関係であり、FKとして、bank_accountsにusers.idがuser_idとして存在します。ではまず、usersからbank_accountsを取得する写像fを
f: users -> bank_accounts
と定め

const f = (x) => {
    let sql = `SELECT * FROM bank_accounts`

    if(x.length > 0) {
        sql += ` WHERE user_id IN(${x.map(x => x.id).join(",")})`
    }

    return query(sql)
}

としましょう。(query関数は、SQLをRDBに送信し、その結果をJavaScriptのコレクションとして取得することができるものという設定です。問い合わせは同期的に行われ、ネットワーク起因のエラーは起こりません。なお。これは解説のための仮想的なものなので、JavaScriptの標準ライブラリには存在しません。)
続いて、bank_accountsからusersを取得する写像gを
g: bank_accounts -> users
と定め

const g = (x) => {
    let sql = `SELECT users.* FROM users LEFT JOIN bank_accounts
                ON users.id = bank_accounts.user_id`

    if(x.length > 0) {
        sql += ` WHERE bank_accounts.id IN(${x.map(x => x.id).join(",")})`
    }

    return query(sql)
}

として定義すると、gはfの、fはgの逆写像となります。確かめてみましょう。

const assert = require("assert")

// 定義域
const x = f() // bank_accounts全体
const y = g() // users全体

// g ◦ f は users -> usersの恒等写像
const users = g(f(y))

// f ◦ g は bank_accounts -> bank_accountsの恒等写像
const bankAccounts = f(g(x))

assert.deepEqual(users, y) // => true
assert.deepEqual(bankAccounts, x) // => true

assert.deepEqualは配列の要素のi番目同士をオブジェクトの深さに関係なく等価比較するものですので、右辺と左辺が完全に一致しない限りtrueを返しません。（オブジェクトのメモリアドレスではなく、プロパティが完全に同一かを比較します）よって、g ◦ f = id_A、f ◦ g = id_B が証明され、f, gそれぞれに逆写像が存在することが確認できました。このように、1対1の対応のRDBMSのテーブルは互いが逆写像の関係になっています。

符号化にみる全射の有用性

符号化アルゴリズムは全射の例として非常に有用です。有名なものはzip化やJPEGの圧縮で我々が大変お世話になっているハフマン符号があります。
符号化とは一般的に、出現頻度の高いデータに短い符号を、逆に出現頻度の低いデータに長い符号を割り当てることで、データ量の削減を実現するようなことを指します。あまりぱっとしない人は、sig: String -> Stringで
sig(ドラゴンクエストウォーク) -> DQW
sig(ファイナルファンタジー) -> FF
のように頻出単語を短くすればその分データ量が減るみたいな感じで捉えていてだければと思います。
ここで、符号化におけるプロセスを考えると、写像f: D -> Sが構成されていると想像することが出来ます。このとき、Dはあるルールにおいて分割された元のデータとその位置情報の集合、Sは分割後のデータに割り当てられた符号の集合を指しています。このとき、|D| ≥ |S|で、DからSには必ず対応があるので、fは全射になっていることが分かるかと思います。
この例から、いかなる集合でも全射を構成できれば、符号化のようなサイズ削減を行えるというのがソフトウェアにおける全射の有用な利用用途であると言えるのではないでしょうか。

先に上げたRDBMSの関連においても全射は有用で、例えば記事とカテゴリーの関係がDB上にあるとしましょう。この関連は全射ですから、カテゴリーをvarcharとして記事テーブルに持つよりは、カテゴリーをテーブルとして独立させ、記事テーブルとリレーションするように構成すれば、テーブルの正規化を図ることが出来ます。また、いずれの場合もインデックスを張るでしょうが、リレーションを用いれば文字列に比べて明らかにディスクスペースの削減につながります。

最後に

どうでしたでしょうか。前後編に分けた大変長い記事でしたので、最後まで読んでいただけた方には本当に感謝しかありません。
なんにせよ、プログラミングやソフトウェアを通じて、多少は写像の理解を助けられていれば本望です。

次回もプログラミングやコンピューターサイエンスと数学を絡めた記事を書ければなーと思っております。

いいなと思ったら応援しよう！