μ-作用素について

$\mu$-作用素について

ある原始的述語 $p(\overrightarrow{x}, y)$ に $\mu$-作用素を施したもの$\mu z < y. ~ p(\overrightarrow{x}, z)$ が原始(帰納)的関数となることの証明に，理解できないことがあるので質問させてください. そのために，まず原始的関数と, 原始的述語 (とその特性関数) を定義します.

定義. 原始的関数を次の (1) から (5) で再帰的に定義する.

1. 零関数 $\text{zero} : \mathbb{N}^{0} \to \mathbb{N} \quad \text{zero}(\,) = 0$

2. 後者関数 $\text{suc} : \mathbb{N} \to \mathbb{N} \quad \text{suc}(x) = x + 1$

3. 射影関数 $p_{i}^{n} : \mathbb{N}^{n} \to \mathbb{N} \quad p_{i}^{n}(x_{1}, \dots, x_{n}) = x_{i}$

4. 合成 : 原始的関数 $g : \mathbb{N}^{m} \to \mathbb{N}$ と $g_{i} : \mathbb{N}^{n} \to \mathbb{N} ~ (1 \leqq i \leqq m)$ に対して
   $$ f(\overrightarrow{x}) = g(g_{1}(\overrightarrow{x}), \dots, g_{m}(\overrightarrow{x})) $$
   で定義される $f : \mathbb{N}^{n} \to \mathbb{N}$ は原始的関数である.

5. 原始再帰法 : 原始的関数 $g : \mathbb{N}^{n} \to \mathbb{N}$ と $h : \mathbb{N}^{n + 2} \to \mathbb{N}$ に対して
   $$ f(\overrightarrow{x}, 0) = g(\overrightarrow{x}) $$
   $$ f(\overrightarrow{x}, y + 1) = h(\overrightarrow{x}, y, f(\overrightarrow{x}, y)) $$
   で定義される $f : \mathbb{N}^{n + 1} \to \mathbb{N}$ は原始的関数である.

例として, 定数関数や前者関数, 足し算 $+$, 引き算 $\dot{-}$ (ただし$x < y$ のとき $x \dot{-} y$ は $0$ を返す), かけ算 $\times$ は原始的関数です.

補題. $f(\overrightarrow{x}, y)$ が原始的関数ならば, 限定和
$$ \displaystyle \sum_{z < y} f(\overrightarrow{x}, z) = f(\overrightarrow{x}, 0) + f(\overrightarrow{x}, 1) + \cdots + f(\overrightarrow{x}, y - 1) $$
と, 限定積
$$ \displaystyle \prod_{z < y} f(\overrightarrow{x}, z) = f(\overrightarrow{x}, 0) \times f(\overrightarrow{x}, 1) \times \cdots \times f(\overrightarrow{x}, y - 1) $$
も原始的関数である. ただし $\sum_{z < 0} f(\overrightarrow{x}, z) = 0$，$\prod_{z < 0} f(\overrightarrow{x}, z) = 1$ とする.

定義. ある関数 $\mathbb{N}^{n} \to \{ \text{true}, \text{false} \}$ を ($n$ 項) 述語と呼ぶ. ある述語 $p$ の特性関数 $\chi_{p}$ は$\mathbb{N}^{n} \to \{ 0, 1 \}$ であって,
$$ \chi_{p}(\overrightarrow{x}) = \begin{cases} 0 & (p(\overrightarrow{x}) = \text{true}) \\ 1 & (p(\overrightarrow{x}) = \text{false}) \end{cases} $$
と定義される. ある述語の特性関数が原始的であるとき，その述語を原始的述語と呼ぶ.

たとえば, $p(x) : x = 0$ の特性関数は $1 \dot{-} (1 \dot{-} x)$ と原始的関数で表わせるので原始的述語と言えます. 実際計算してみると，$x = 0$ のとき,
$$ 1 \dot{-} (1 \dot{-} x) = 1 \dot{-} 1 = 0 $$
$1 \leqq x$ のとき
$$ 1 \dot{-} (1 \dot{-} x) = 1 \dot{-} 0 = 1 $$
となります.

原始的述語 $p(\overrightarrow{x})$ が真のとき, その特性関数の値が零元となることは，$\exists z \leqq y ~ p(\overrightarrow{x}, z)$ の特性関数が $\prod_{z \leqq y} \chi_{p} (\overrightarrow{x}, z)$ と表わせて, このときひとつでも $\text{true}$ があるならば積として書かれるこの述語の特性関数の値が $0$となって好ましいです. でも $p(\overrightarrow{x}) = \text{true}$ のときその特性関数の値が $1$ だとして定義しても, $p$の否定をとれば結果は変わりません. いずれにしてもこの $\text{true}$ がひとつでもあればすべてが $0$ となる性質は重要になってきます.

ところで先の補題から $\exists z \leqq y ~ p(\overrightarrow{x}, z)$ の特性関数
$$ \displaystyle \prod_{z \leqq y} \chi_{p}(\overrightarrow{x}, z) $$
は原始的関数の限定積なので原始的関数であって, 原始的述語です.

ひとつ疑問なのは, ある原始的述語に対してその特性関数は一意に定まるのか，ということです.この疑問はのちに述べる疑問にも関係しているような気もします. たとえばある原始的関数が “偶然” ある述語の特性関数となったとき，その述語の “本質(?)” と関係しているのでしょうか. あるいはある述語の“本質(?)” が理解できたとき，必然的にその特性関数を構成することはできるのでしょうか. 理由はよくわかりませんが, わたしはこんな質問をして，なんだか恥ずかしい気持ちがします. よくわかっていないのです. わたしはよくわかっていないのです.

$\mu$-作用素を定義します. $p$ を $n + 1$ 項述語として,
$$ \mu z < y. ~ p(\overrightarrow{x}, z) \stackrel{\mathrm{def}}= \min(\{ w \in \mathbb{N} \mid w < y ~ \text{かつ} ~ p(\overrightarrow{x}, w) = \text{true} \} \cup \{ y \}) $$
$\mu$ は述語 $p$ と $\overrightarrow{x} \in \mathbb{N}^{n}$, そして上界 $y \in \mathbb{N}$ が与えられたとき, 自然数の値を返す関数です. なにを返すかというと, その述語が真となる最小の自然数です. ただし，述語を走る自然数 (上でいう $z$) には上界があって, それが上における $y$ です. なので $y$ 未満を走って述語を真ならしめる最小の自然数を探索し，そのような最小の $w$ がなければ $y$ を返します.

たとえば割り算 $x \div y$ は $\mu z < x ~ (x < y \times (z + 1))$ と表わせます. お気持ちとしては $x, y \in \mathbb{N}$ が与えられたとき，$x \div y$ は「 $y$ とかけ算をして $x$ を超えてしまうような最小の自然数のひとつ前の自然数」を返してほしいものです. $10 \div 3$ は $3$ にかけ算をして $10$ を超えてしまう自然数 $(4, 5, 6, \cdots)$ の最小 $4$ のひとつ前の自然数 $3$ を返してほしいのです. このお気持ちを表わした述語 $p(x, y, z) : x < y \times (z + 1)$ において, 動いてほしい $z$ のなかで最小のものを返してほしいので $\mu z < x. ~ p(x, y, z)$ と書けます. $z$ の上界が $x$ であるのはうまく説明できませんが，いろいろな $\mu$-作用素の例をみてみると, 上界は適切であれば適切です.

たとえば不適切な例として, 上の割り算の $\mu$ の上界をある自然数 $n$ としてみると, ある大きな数 $x = n + 1$ と $y = 1$ に対して，$\mu z < n. ~ p(n + 1, 1, z) = \mu z < n. ~ (n + 1) < 1 \times (z + 1)$ は $z < n$ で述語を真にする自然数がないので, $n$ を返します. これは好ましくありません. そうして上界を $x$ にすると安心なのです.

ここからわたしが質問したいところに入ります. $p$ を $n + 1$ 項原始述語とし, ある $\overrightarrow{x} \in \mathbb{N}^{n}$ と $y \in \mathbb{N}$ が与えられ, $\mu$-作用素を施したもの $\mu z < y. ~ p(\overrightarrow{x}, z)$ を考えます. ここで定義から $\mu z < 0. ~ p(\overrightarrow{x}, z) = 0$ です.
次に $y = 1$ としてみましょう. $p(\overrightarrow{x}, 0) = \text{true}$ か, あるいは$p(\overrightarrow{x}, 0) = \text{false}$ のいずれかです. 前者ならば $\mu z < 1. ~ p(\overrightarrow{x}, z) = 0$ で, 後者ならば $\mu z < 1. ~ p(\overrightarrow{x}, z) = 1$ です.

次に $y = 2$ を考えてみます :
$$ \mu z < 2. ~ p(\overrightarrow{x}, z) = \begin{cases} 0 & (p(\overrightarrow{x}, 0) = \text{true}) \\ 1 & (p(\overrightarrow{x}, 0) = \text{false}, ~ p(\overrightarrow{x}, 1) = \text{true}) \\ 2 & (p(\overrightarrow{x}, 0) = p(\overrightarrow{x}, 1) = \text{false}) \end{cases} $$

$y = 3$ は次のようになります :
$$ \mu z < 3. ~ p(\overrightarrow{x}, z) = \begin{cases} 0 & (p(\overrightarrow{x}, 0) = \text{true}) \\ 1 & (p(\overrightarrow{x}, 0) = \text{false}, ~ p(\overrightarrow{x}, 1) = \text{true}) \\ 2 & (p(\overrightarrow{x}, 0) = p(\overrightarrow{x}, 1) = \text{false}, ~ p(\overrightarrow{x}, 2) = \text{true}) \\ 3 & (p(\overrightarrow{x}, 0) = p(\overrightarrow{x}, 1) = p(\overrightarrow{x}, 2) = \text{false}) \end{cases} $$

$\text{true}$ になった以後の真偽は関係ありませんので省略してあります. こうしてみると，$\mu z < y. ~ p(\overrightarrow{x}, z)$ の値は, はじめて $\text{true}$ になる前の $\text{false}$ の個数と一致しています. そして, 初めて $\text{true}$ になった以後の真偽とは関係ありません. このおのおのの場合分けはそれらの積で表現することが可能です.

$y = 3$と固定して, それぞれの場合のそれぞれの述語の特性関数 $\chi_{p} (\overrightarrow{x}, z)$ の積の値を調べてみると,

1. $p(\overrightarrow{x}, 0) = \text{true}$ のとき $\chi_{p}(\overrightarrow{x}, 0) = 0$ なので，
   $$ \displaystyle \prod_{z \leqq 0} \chi_{p}(\overrightarrow{x}, z) = \prod_{z \leqq 1} \chi_{p}(\overrightarrow{x}, z) = \prod_{z \leqq 2} \chi_{p} (\overrightarrow{x}, z) = 0 $$
   このときすべてを足すと，
   $$ \displaystyle \prod_{z \leqq 0} \chi_{p}(\overrightarrow{x}, z) + \prod_{z \leqq 1} \chi_{p}(\overrightarrow{x}, z) + \prod_{z \leqq 2} \chi_{p}(\overrightarrow{x}, z) = \sum_{v < 3} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 0 $$

2. $p(\overrightarrow{x}, 0) = \text{false}, ~ p(\overrightarrow{x}, 1) = \text{true}$ のとき
   $$ \displaystyle \prod_{z \leqq 0} \chi_{p} (\overrightarrow{x}, z) = 1, \quad \prod_{z \leqq 1} \chi_{p} (\overrightarrow{x}, z) = \prod_{z \leqq 2} \chi_{p}(\overrightarrow{x}, z) = 0 $$
   総和は，
   $$ \displaystyle \sum_{v < 3} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 1 $$

3. $p(\overrightarrow{x}, 0) = p(\overrightarrow{x}, 1) = \text{false}, ~ p(\overrightarrow{x}, 2) = \text{true}$ のとき，
   $$ \displaystyle \prod_{z \leqq 0} \chi_{p}(\overrightarrow{x}, z) = \prod_{z \leqq 1} \chi_{p}(\overrightarrow{x}, z) = 1, \quad \prod_{z \leqq 2} \chi_{p}(\overrightarrow{x}, 2) = 0 $$
   $$ \sum_{v < 3} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 2 $$

4. $p(\overrightarrow{x}, 0) = p(\overrightarrow{x}, 1) = p(\overrightarrow{x}, 2) = \text{false}$ のとき
   $$ \displaystyle \prod_{z \leqq 0} \chi_{p} (\overrightarrow{x}, z) = \prod_{z \leqq 1} \chi_{p} (\overrightarrow{x}, z) = \prod_{z \leqq 2} \chi_{p} (\overrightarrow{x}, z) = 1 $$
   $$ \displaystyle \sum_{v < 3} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 3 $$

なので，先に述べた “はじめて $\text{true}$ になる前の $\text{false}$ の個数” と, 上の $y = 3$ 個の積の限定和
$$ \displaystyle \sum_{v < 3} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) $$
は一致します.

一般化して, 最小解が存在するとして, 先に $\mu z < y. ~ p(\overrightarrow{x}, z) = \varepsilon$ とおくと (すなわちはじめて $\text{true}$ となるのが $\varepsilon < y$ であるとすると)，
$$ \chi_{p} (\overrightarrow{x}, z) = 1 \quad (\forall z < \varepsilon) $$
$$ \chi_{p} (\overrightarrow{x}, \varepsilon) = 0 $$

以後の真偽は関係ありません.

このとき限定積は，
$$ \displaystyle \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 1 \quad (\forall v < \varepsilon) $$
$$ \displaystyle \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 0 \quad (\varepsilon \leqq \forall v < y) $$

すべてを足すと，
$$ \displaystyle \sum_{v < y} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = \varepsilon $$

最小解が存在しないとすると，
$$ \chi_{p} (\overrightarrow{x}, z) = 1 \quad (0 \leqq \forall z < y) $$
であって，限定積は
$$ \displaystyle \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = 1 \quad (\forall v < y) $$

すべてを足すと，
$$ \displaystyle \sum_{v < y} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = y $$

いずれの場合も
$$ \displaystyle \sum_{v < y} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z) = \mu z < y. ~ p(\overrightarrow{x}, z) $$
ところで $p$ は原始的述語であったので, $\chi_{p} (\overrightarrow{x}, z)$は原始的関数です. したがってその有限積は原始的であり，その有限積の有限和もまた原始的です. ゆえ, それに等しい $\mu z < y. ~ p(\overrightarrow{x}, z)$ も原始的関数となります.

わたしの疑問は, なぜこんなにもうまくいくのかわからない, ということです. だから疑問と呼べるのかさえわからないのです. 鍵となるのはたぶん “はじめて $\text{true}$ となる数の前の $\text{false}$ の個数” が遺伝子を保つ積の和として書けるというところにあると思うのですが，いずれにしてもうまく Yes / No で言える質問ができません.

それと，わたしはこうも考えてみました. $\sum_{v < y} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z)$ が “偶然” $\mu z < y. ~ p(\overrightarrow{x}, z)$ と一致する, と. ふたつの関数の引数は同じく $\overrightarrow{x}, y$ です. “偶然” うまくいってしまったように感じられるのです，特に, $y$ 個の限定和をとるというところに. 限定和をとるということに必然性を感じられるほど妥当な議論ではないように思えますし，かといってまったく偶然というふうにも思えません. それに，偶然であってほしくはないのです.

たとえば, 神さまがふたつの “本質的に” 異なる関数をわたしたちに与えてくれたとします. そうしてわたしたちはある入力をして，いずれのときもそのふたつの関数は同じ値を出力してくれるとします. けれどもわたしたちは有限の対象なのだから, 有限個の確認しかできずに，そのふたつの関数が等しいと思って死んでゆくのです. $\mu z < y. ~ p(\overrightarrow{x}, z)$ と $\sum_{v < y} \prod_{z \leqq v} \chi_{p} (\overrightarrow{x}, z)$ のふたつの関数も，わたしには区別できません. なぜなら同じ入力に対して同じ出力をしてくれるのですから. わたしはすこしおかしいですか ? かなり疲れています. うまく言葉にできない疑問を持つことはとてもつらいです. 願わくば誰かやさしいひとが, わたしのこの気持ちを悟ってくれますように.