4.3 関数

4.3.1 始域・終域・像

関数 (function) は始域 (domain) と呼ばれる集合の要素を終域 (codomain) と呼ばれる集合の要素に割り当てる。関数 \(f\) が始域 \(A\) と終域 \(B\) を持つことは次の記法で表される:

\[ f\colon A \to B \]

関数 \(f\) の始域と終域はそれぞれ \(\operatorname{domain}(f)\), \(\operatorname{codomain}(f)\) と表記される。

見慣れているであろう記法 \(f(a) = b\) は関数 \(f\) が \(a \in A\) を \(b \in B\) に割り当てることを意味する。このとき \(b\) は関数 \(f\) の引数 (argument) \(a\) に対する値 (value) と呼ばれる。

関数は数式で定義されることが多い。いくつか例を示す:

\[ f_{1}(x) ::= \frac{1}{x^{2}} \]

\(f_{1}\) は任意の実数 \(x\) を引数に取ると定める。

\[ f_{2}(y, z) ::= y \texttt{10} yz \]

\(f_{2}\) の引数 \(y\), \(z\) の変域はビット列全体の集合と定める。

\[ f_{3}(x, n) ::= \text{長さ \(n\) の列 } (\underbrace{x, \ldots, x}_{n \text{ 個の } x}) \]

\(f_{3}\) は任意の \(x\) と任意の非負整数 \(n\) を引数に取ると定める。

始域が有限集合である関数は、始域の各要素に対する関数の値を並べた表で記述できる。例えば、次の表は命題変数 \(P\), \(Q\) を引数に取る関数 \(f_{4}(P, Q)\) を定義する:

\[ \def\arraystretch{1.2}\begin{array}{ccc} P & Q & f_{4}(P, Q) \\ \hline \textbf{T} & \textbf{T} & \textbf{T} \\ \textbf{T} & \textbf{F} & \textbf{F} \\ \textbf{F} & \textbf{T} & \textbf{T} \\ \textbf{F} & \textbf{F} & \textbf{T} \end{array} \]

\(f_{4}\) は命題論理式を使っても定義できる:

\[ f_{4} (P, Q) ::= P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q \]

始域の任意の要素に対する値を計算する手続き (あるいは値が満たすべき仕様) を示すことでも関数は定義できる。例えば、\(f_{5}(y)\) を「ビット列 \(y\) を左から右に走査したとき、\(\texttt{1}\) が初めて見つかる位置」と定義すれば、次のような関数が定義される:

\[ \begin{aligned} f_{5} (\texttt{0010}) &= 3 \\ f_{5} (\texttt{100}) &= 1 \\ f_{5} (\texttt{0000}) &= \text{未定義} \\ \end{aligned} \]

\(f_{5}\) は \(1\) を含まないビット列に対して定義されないことに注意してほしい。これは関数の重要な特徴を示している: 関数は始域の全ての要素に値を割り当てなくても構わない。実は、この事実は最初に示した例 \(f_{1} (x) = 1/x^{2}\) が \(x=0\) で定義されないことからも分かる。一般に、始域の一部の要素に対して値が未定義である関数を部分関数 (partial function) と呼ぶ。関数が定義される始域の要素全体の集合を関数の台 (support) と呼ぶ。始域の全ての要素に値を割り当てる関数 (言い換えれば、始域と台が等しい関数) を全域関数 (total function) と呼ぶ。

引数の集合 (始域の部分集合) の各要素に対する関数の値全体の集合を扱う状況がよくある。そのため、\(f \colon A \to B\) と \(S \subset A\) に対して、\(S\) の各要素に対する \(f\) の値全体の集合を \(f(S)\) と表記する慣習がある。言い換えれば、次のように定義される:

\[ f(S) ::= \left\{b \in B \; | \; \exists s \in S.\ f(s) = b \right\} \]

例えば、数直線上で \(r\) から \(s\) の間にある実数全体の集合を \([r, s]\) と表すことにすれば、\(f_{1}([1,2]) = [1/4, 1]\) が成り立つ。もう一つ例を示すと、偶数個の \(\texttt{0}\) の後に \(\texttt{1}\) 個の \(\texttt{1}\) を付けたビット列全体の集合を \(X\) とするとき、\(f_{5}(X)\) は非負奇数全体の集合となる。

引数の集合 \(S\) の各要素に関数 \(f\) を適用することを「点ごとに (pointwise) \(f\) を \(S\) に適用する」と表現し、\(f(S)\) を \(f\) による \(S\) の像 (image) と呼ぶ¹。始域の全ての要素に \(f\) を適用して得られる値全体の集合を \(f\) の値域 (range) と呼び、\(\operatorname{range}(f)\) と表記する。つまり、値域は次のように定義される:

\[ \operatorname{range} (f) ::= f(\operatorname{domain}(f)) \]

本書が終域 (codomain) と呼ぶ概念を値域 (range) と呼ぶ文献もあるものの、これは望ましくない。両者を区別する重要性は第 4.5 節で関数の性質を使って集合の要素数を考えるとき明らかになる。

4.3.2 関数の合成

何らかの処理をステップごとに実行するのは自然な考え方である。文字通りの例として歩行がある。他にもレシピを読みながらの料理、コンピュータープログラムの実行、式の評価、薬物乱用からの回復などもステップごとに行われる。

抽象的に考えると、ステップの実行は関数の適用に、ステップごとの実行は複数の関数を一つずつ適用することに対応する。この考え方を捉える概念が関数の合成である。関数 \(f\), \(g\) を合成すると、引数 \(x\) にまず \(f\) を適用し、その結果を \(g\) に適用した \(g(f(x))\) を値とする関数が得られる。

定義 4.3.1

関数 \(f \colon A \to B\) と \(g\colon B \to C\) の合成 (composition) \(g \circ f\) とは、始域 \(A\) と終域 \(C\) を持ち、全ての \(x \in A\) に対する値が次のように定義される関数を言う:

\[ (g \circ f)(x) ::= g(f(x)) \]

関数の合成は高校レベルの微分積分で重要な概念なので、その意味を知っている読者がほとんどだろう。離散数学でも同様に重要な役割を果たす。

細かいことを言うと、「集合 \(A\) の要素に値を割り当てる関数 \(f\)」と「\(A\) の部分集合に \(f\) を点ごとに適用する関数」は異なるので、両方を同じ記号 \(f\) で表すのは記号の濫用と言える。前者の始域は \(A\) であるのに対して、後者の始域は \(\operatorname{pow}(A)\) である。ただ、通常は \(f\) がどちらを意味するのか明らかなので、記号 \(f\) が二つの異なる意味で使われても問題は起こらない。 ↩︎