エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

アッカーマン関数(3)

関数の再帰的定義

ここではある形の関数の再帰的定義について考えます。

 g: X \to X に対して  g^+: \mathbb{N} \times X \to \mathbb{N} \times X g^+(n, x) = (n+1, f(x)) と定義します。

 \mathcal{S}(g^+, (n, x)) = \{ S \mid S \subseteq \mathbb{N} \times X, (n, x) \in S, g^+(S) \subseteq S \} \overline{g^+}(n, x) = \bigcap \mathcal{S}(g^+, (n, x)) とおきます。

 \mathcal{S}_0 = \mathcal{S}(g^+, (0, a)) R = \overline{g^+}(0, a) = \bigcap \mathcal{S}_0 とおくと  R
 \begin{cases}
(0, a) \in R \\
(n, x) \in R \implies (n+1, g(x)) \in R
\end{cases}
を満たす最小の集合となります。

 S \subseteq \mathbb{N} \times X に対して  \pi_1(S) = \{ n \in \mathbb{N} \mid (n, x) \in S \ \text{を満たす} \ x \in X \ \text{が存在する}\} と定義します。

 R_1 = \pi_1(R) とおくと
 \begin{cases}
0 \in R_1 \\
n \in R_1 \implies n+1 \in R_1
\end{cases}
が成り立つので、自然数の性質より  R_1 = \mathbb{N} となります。

計算可能性の議論にはこれだけでも良いとは思うのですが
 f(n) = x \iff (n, x) \in R
によって関数  f: \mathbb{N} \to X を定義するには、任意の  n \in \mathbb{N} と任意の  x, y \in X に対して  (n, x) \in R かつ  (n, y) \in R ならば  x = y が成り立つ必要があります。以下でこれを示します。

 \{(0, a)\} \cup \overline{g^+}(g^+(0, a)) \in \mathcal{S}_0 となるので  R \subseteq \{(0, a)\} \cup \overline{g^+}(g^+(0, a)) となります。

 (0, x) \in R とすると  (0, x) \notin \overline{g^+}(g^+(0, a)) なので  (0, x) \in \{(0, a)\} となります。よって  x = a となります。

よって  n = 0 のときには成り立ちます。

次に  n のときには成り立つと仮定します。 (n, b) \in R とします。

 R_n = \{(k, x) \in R \mid k \le n\} c = g(b) とおくと  (n+1, c) \in R となります。

 R_n \cup \{(n+1, c)\} \cup \overline{g^+}(g^+(n+1, c)) \in \mathcal{S}_0 となるので  R \subseteq R_n \cup \{(n+1, c)\} \cup \overline{g^+}(g^+(n+1, c)) となります。

 (n+1, x) \in R とすると  (n+1, x) \notin R_n \cup \overline{g^+}(g^+(n+1, c)) なので  (n+1, x) \in \{(n+1, c)\} となります。よって  x = c となって  n+1 のときにも成り立ちます。

よって帰納法により任意の  n \in \mathbb{N} と任意の  x, y \in X に対して  (n, x) \in R かつ  (n, y) \in R ならば  x = y が成り立ちます。よって
 f(n) = x \iff (n, x) \in R
によって関数  f: \mathbb{N} \to X を定義することができます。