今、シリーズでオートマトンと言語に関する話を書いている。
初回は以下だ。
前回は証明をざっとではあるが解説した。
これは数をこなせばこなすほど、RPGのレベルのように実力が上がっていくので、是非色々調べてチャレンジして頂きたい。
以下がその記事だ。
さて、今回はちょっと話が集合に戻る。
このオマケシリーズの初回で解説した集合だが、その時は定義だったり演算の性質だったりを述べたに過ぎない。
そこで、重要な概念である写像というものを解説していこう。
これも本編で使っていて、決定性有限オートマトンの同型あたりで登場したやつだ。
その時にもざっとは説明したが、今回改めてしっかり定義していこうと思う。
念のため、集合の解説のリンクも貼っておこう。
で、前回は使わなかったが、今回は以下の参考書を使っている。
ただ、やはり本編に使用しない部分は省略したりしているので、その点はご了承いただきたい。
中学・高校でやった「関数」
ちょっと、先に中学時代の内容を思い出してもらおう。
二つの数\(x, y\)があり、\(x\)の値を一つに決めると、それに伴って\(y\)の値もただ一つに確定するとき、\(y\)は\(x\)の関数であるという。
例えば、正方形の面積。
正方形の一辺の長さを\(x\)、その正方形の面積を\(y\)とすると、\(y\)は以下の式で表すことができる。
$$y = x^2$$
このとき、\(x\)の値…つまり、正方形の一辺の長さが確定すれば、面積である\(y\)の値も一つに決まる。
このような関係が、関数だ。
このとき、\(x\)のことを独立変数、\(y\)のことを従属変数と呼ぶ。
また、\(y\)が\(x\)の関数であるとき、以下のような表記をすることが多い。
$$y = f(x)$$
括弧内に独立変数を入れ、それによって決まる従属変数の値を表している。
ちなみに、独立変数が取りうる範囲のことを定義域、従属変数が取りうる範囲のことを値域と呼び、独立・従属に関わらずある変数が取りうる範囲のことを変域と呼ぶ。
正方形の例で言えば、定義域、値域ともに0より大きい実数だ。
用語は聞き馴染みがないかもしれないが、やっていることは中学までの復習なので問題ないと思う。
写像
ここから、今回の内容だ。
二つの集合\(A, B\)を考える。
ある集合\(A\)の要素\(a\)について、集合\(B\)の一つの要素\(b\)を対応させることを考える。
この対応のことを、部分写像と呼ぶ。
また、集合\(A\)の全ての要素に対し、対応が定義されているとき、単に写像と呼ぶ。
記法は関数と同じく\(f\)を使って、\(a \in A\)に対して\(b \in B\)が対応していることを、以下のように書き表す。
$$f(a) = b$$
このとき、\(a\)を独立変数、\(b\)を従属変数と呼ぶのは関数のときと同じ。
さて、写像元となる集合のことを始集合、写像先となる集合のことを終集合と呼ぶ。
写像が定義されているような始集合の要素の集合を、定義域という。
つまり、部分写像における定義域は、始集合の部分集合だ。
写像では、始集合と定義域が一致する。
それに対し、任意の始集合内の要素からの写像先を一つの集合にしたものが、値域だ。
これは部分写像、写像ともに終集合の部分集合、あるいは終集合とイコールになっている。
ちなみに、部分写像において、定義域に含まれないような始集合の要素は部分写像が未定義であるといい、それを集めた集合を未定義域と呼ぶ。
…用語を一気に出してしまったので、具体例で見てみよう。
今、二つの集合を\(A = \{1, 2, 3\}\)、\(B = \{1, 2, 3, 4, 5, 6\}\)としよう。
そして、\(A\)から\(B\)への部分写像\(f\)を考える。
二つ定義されているとしよう。
- \(f(1) = 2\)
- \(f(2) = 4\)
このとき、\(A\)が始集合、\(B\)が終集合。
また、定義域は\(\{1, 2\}\)、値域は\(\{2, 4\}\)だ。
そして、\(3 \in A\)は未定義で、集合\(\{3\}\)が未定義域となる。
次に、部分写像\(f\)に一つ定義を加える。
- \(f(3) = 6\)
こうすると定義域は\(\{1, 2, 3\}\)に変わり、つまり\(A\)に等しくなるので、この\(f\)は写像となる。
このときの値域は\(\{2, 4, 6\}\)で、未定義域は空集合だ。
大体、感覚は掴めただろうか。
特殊な写像
ここから先は、未定義域が存在しない写像について考えることとしよう。
部分写像が必要になったら、そのことを明記する。
さて、写像を考えるときに三つほど特別な写像がある。
全射、単射、全単射というものだ。
それぞれ見ていこう。
全射
まず、全射とは値域と終集合がイコールであるような写像のこと。
例えば、二つの集合\(A = \{1, 2, 3\}\)、\(B = \{0, 1\}\)で以下のような写像を考える。
- \(f(1) = 1\)
- \(f(2) = 0\)
- \(f(3) = 1\)
イメージとしては、\(A\)の奇数を\(B\)の1に、\(A\)の偶数を\(B\)の0に写像させている。
このとき、値域を見ると\(\{0, 1\} = B\)であり、このような写像を全射と呼ぶのだ。
言葉で言うと、写像先が終集合の全ての要素を網羅しているような写像だ。
より砕くと、「写像先にもれがない写像」、といった感じだろうか。
単射
次に、単射とは異なる定義域内の要素について、その写像先も異なるような写像のこと。
…ちょっと言葉では分かりづらいが、要するに「写像先がだぶっていない写像」だ。
これも例を出してみよう。
実は、用語の説明時に出した例が単射の例にもなっている。
二つの集合を\(A = \{1, 2, 3\}\)、\(B = \{1, 2, 3, 4, 5, 6\}\)とし、\(A\)から\(B\)への写像\(f\)を以下で定義する。
- \(f(1) = 2\)
- \(f(2) = 4\)
- \(f(3) = 6\)
このとき、始集合である\(A\)内のどの異なる2要素を見ても、写像先が異なっている。
このような写像を、単射と呼ぶのだ。
全単射
もう名前からお分かりかもしれないが、全単射とは全射かつ単射であるような写像のこと。
よく言われるのは、「もれもだぶりもない写像」だ。
例を出そう。
二つの集合を、今度は\(A = \{1, 2, 3\}\)、\(B = \{2, 4, 6\}\)として、写像を以下のように定義する。
- \(f(1) = 2\)
- \(f(2) = 4\)
- \(f(3) = 6\)
こうすると、まず値域が\(\{2, 4, 6\} = B\)なので、全射。
そして、異なる写像元を比べると、その写像先も異なっているので単射。
よって、この写像は全単射である、という感じだ。
全射、単射、全単射が作れるときの要素数
さて、ここまで説明してきた写像が作れるとき、始集合、終集合となるそれぞれの集合の要素数を比較することができる。
それぞれ、見ていこう。
全射
集合\(A\)から集合\(B\)への全射が作れるとき、この\(A\)と\(B\)の要素数について、以下の関係が成り立つ。
$$|A| \geq |B|$$
証明というほど厳密なものではないが、なぜこうなるのか説明してみよう。
まず、説明の都合上、\(B\)の要素数を\(n\)としておく。
さて、前提より\(A\)から\(B\)への全射は作れることが分かっている。
写像の定義から、\(A\)の一つの要素について、\(B\)の要素がただ一つ対応している。
で、全射なので、\(B\)の全ての要素に向かうような写像元が\(A\)に存在する。
つまり、この時点で\(A\)には最低でも\(n\)個の要素が必要だ。
しかし、複数の\(A\)内の要素から、同じ一つの\(B\)の要素へ写像することはできるので、\(A\)の要素数は\(n\)以上となる。
ということで、上に書いたような要素数の関係になるのだ。
単射
今度は単射。
集合\(A\)から集合\(B\)への単射が作れるとき、この\(A\)と\(B\)の要素数について、以下の関係が成り立つ。
$$|A| \leq |B|$$
これも説明してみよう。
今度は写像先がだぶってはいけない、かつ\(A\)内の全要素が写像先を持つので、その時点で\(B\)には\(A\)と同じだけの要素数が必要。
だが、今回は全射ではなくてもいいので、写像元が存在しない要素が\(B\)にあってもいい。
だから、要素数は\(B\)が\(A\)の要素数以上となる。
全単射
最後、全単射だ。
集合\(A\)から集合\(B\)への全単射が作れるとき、この\(A\)と\(B\)の要素数について、以下の関係が成り立つ。
$$|A| = |B|$$
さて、全単射は全射かつ単射であるような写像のことだった。
つまり、全射であるので\(|A| \geq |B|\)、単射であるので\(|A| \leq |B|\)が分かっている。
ということは、もう\(|A| = |B|\)しかあり得ないだろう。
というわけで、全単射が作れるなら、その二つの集合の要素数は一致するのだ。
これはなかなかに重要な性質であり、二つの集合の要素数が等しいことの証明によく全単射を作るという手法が使われる。
以前、自然数や整数、有理数の要素数(厳密には濃度)が等しいことを証明したが、その時も言い方は違えどこの方法だ。
是非覚えておいて欲しい。
関数と写像の関係
最初に関数の復習をしたが、写像の定義を見ると非常に似ていることが分かるだろう。
実際、関数は写像の特別な場合と考えることができる。
例えば、以下の二次関数。
$$y = x^2$$
上の例では正方形に関する式として使っていたが、一旦それは忘れて欲しい。
このとき、定義域は実数全体、値域は0以上の実数と見てみよう。
すると、一つの実数\(x\)に対し、ただ一つの実数\(y\)が対応しているので、これも写像として見ることができる。
ちょっとオマケ的な内容だが、知っておいて損はないかと思う。
対応
ここで、今解説した内容をより一般的にしてみよう。
参考書では多価関数という用語で解説されているが、本編でも対応という言葉を使っているので、そちらを使わせてもらう。
対応とは、写像先が要素ではなく、終集合の部分集合になっているような関係のことだ。
例えば、始集合\(A = \{1, 2, 3\}\)、終集合\(B = \{1, 2, 3, 4, 5, 6\}\)としたとき、以下のような対応を考える。
- \(f(1) = \{1, 2\}\)
- \(f(2) = \{3, 4\}\)
- \(f(3) = \{5, 6\}\)
このような\(f\)を、対応と呼ぶのだ。
また、写像の時と同じように、対応が定義されていないような始集合の要素が存在するとき、部分対応と呼ぶ。
逆写像
ある写像について、その逆向きの関係を逆写像と呼ぶ。
よく、写像\(f\)の逆写像を\(f^{-1}\)と表記することが多い。
で、一般的には逆写像も写像になるとは限らない。
多くの場合は、対応になるだろう。
が、一つ綺麗な性質がある。
全単射の逆写像は、これまた全単射となる。
ここで証明はしないので、よかったらチャレンジしてみてもらいたい。
おわりに
今回は、写像に焦点を当てて解説を行った。
今のところ本編では有限オートマトンの同型で使っただけだが、今後も出てくる…かもしれない。
その時は、是非今回の内容を思い出してもらいたい。
さて、今回でオマケシリーズは終わり…のつもりだったのだが、今ちょっと解説するか迷っているものがある。
本編では名前を出していないが、同値類という考え方がある。
別にこれを解説しなくても大丈夫そうな気がしているが、考え方としては知っておいて損はない、くらいの内容だ。
もし解説したら、ここにリンクを貼ることとしよう。
次回は、本編であるオートマトンの話に戻ろう。
間が空いてしまったので、よかったら過去の記事で復習もしておいてもらいたい。
コメント