§D2.1帰納法と再帰的な定義

証明.$S = \{\, n \in \N : P(n) \text{ が偽} \,\}$とおき、$S \ne \varnothing$と仮定する。最小数原理により$S$は最小元$n_0$をもつ。$P(0)$は真であるから$n_0 \ne 0$であり、$n_0 = m + 1$を満たす$m \in \N$が存在する。$m < n_0$であり$n_0$は$S$の最小元であるから$m \notin S$、すなわち$P(m)$は真である。仮定した含意$P(m) \Rightarrow P(m+1)$から$P(n_0)$が真になるが、これは$n_0 \in S$に矛盾する。したがって$S = \varnothing$であり、すべての$n \in \N$について$P(n)$が真である。▨

証明.(1)$\Rightarrow$(2)を示す。述語$P$が累積帰納法の仮定を満たすとする。述語$Q$を「$n$より小さいすべての$m$について$P(m)$が真である」と定める。$0$より小さい自然数は存在しないので、$Q(0)$は空虚に真である。次に$Q(n)$を仮定する。$Q(n)$は「$n$より小さいすべての$m$で$P(m)$」であり、$P$についての仮定からただちに$P(n)$が従う。したがって$n+1$より小さいすべての$m$、すなわち$m < n$である$m$と$m = n$の両方について$P(m)$が真であり、$Q(n+1)$が成り立つ。(1)により、すべての$n$について$Q(n)$が真である。任意の$n$に対して$Q(n+1)$を用いれば$P(n)$が得られる。

(2)$\Rightarrow$(1)を示す。述語$P$が$P(0)$を満たし、かつすべての$n$で$P(n) \Rightarrow P(n+1)$を満たすとする。$n$を任意にとり、$n$より小さいすべての$m$について$P(m)$が真であると仮定する。$n = 0$のときは、仮定によらず$P(0)$が真である。$n \ge 1$のときは$n = k+1$となる非負整数$k$があり、$k < n$なので$P(k)$が真であり、含意$P(k) \Rightarrow P(k+1)$から$P(n) = P(k+1)$が真である。したがって$P$は累積帰納法の仮定を満たし、(2)からすべての$n$について$P(n)$が真である。▨

証明.$S = \{\, x \in A : P(x) \text{ が偽} \,\}$とおき、$S \ne \varnothing$と仮定する。$\prec$が整礎であることから、$S$には極小元$x_0$が存在する。極小元の定義により、$y \prec x_0$を満たす$y$は$S$に属さない。すなわち、$y \prec x_0$を満たすすべての$y \in A$について$P(y)$が真である。仮定した含意を$x = x_0$に適用すると$P(x_0)$が真になるが、これは$x_0 \in S$に矛盾する。したがって$S = \varnothing$であり、すべての$x \in A$について$P(x)$が真である。▨

証明. そのような列$x_0, x_1, \dots$が存在すると仮定し、$S = \{\, x_n : n \in \N \,\}$とおく。$S$は$x_0$を含むので空ではない。$S$の任意の要素は、ある$n$について$x_n$と書くことができ、$x_{n+1} \in S$かつ$x_{n+1} \prec x_n$が成り立つ。したがって$S$のどの要素も極小元ではなく、$S$は極小元をもたない。これは$\prec$が整礎であることに矛盾する。▨

証明. 定義から$G_0 \subseteq G_1 \subseteq G_2 \subseteq \cdots$である。実際、$G_{n+1}$は$G_n$との合併として定められている。

(1)を示す。$B = G_0 \subseteq G$である。$f \in F$を引数の個数$k$の構成子とし、$x_1, \dots, x_k \in G$とする。各$i$について$x_i \in G_{n_i}$となる$n_i$を選び、$n = \max\{n_1, \dots, n_k\}$とおく。引数は有限個なので最大値が存在し、列が増加することからすべての$i$について$x_i \in G_n$である。したがって$f(x_1, \dots, x_k) \in G_{n+1} \subseteq G$である。

(2)を示す。$H$を$B$を含み$F$について閉じている$U$の部分集合とし、$G_n \subseteq H$を$n$について示す。$n = 0$のときは$G_0 = B \subseteq H$である。$G_n \subseteq H$を仮定する。$G_{n+1}$の要素は$G_n$の要素であるか、$f \in F$と$x_1, \dots, x_k \in G_n$について$f(x_1, \dots, x_k)$の形をしている。前者は仮定から$H$に属する。後者については、仮定から$x_i \in H$であり、$H$が$F$について閉じているので$f(x_1, \dots, x_k) \in H$である。よって$G_{n+1} \subseteq H$が成り立ち、命題 1.1によりすべての$n$について$G_n \subseteq H$である。合併をとって$G \subseteq H$を得る。▨

証明.$S = \{\, x \in G : P(x) \text{ が真} \,\}$とおく。条件 (a)から$B \subseteq S$である。$f \in F$と$x_1, \dots, x_k \in S$をとると、$S \subseteq G$より$x_i \in G$であり、$P(x_i)$はすべて真である。条件 (b)から$P(f(x_1, \dots, x_k))$が真であり、命題 3.2 (1)から$f(x_1, \dots, x_k) \in G$なので、$f(x_1, \dots, x_k) \in S$である。したがって$S$は$B$を含み$F$について閉じているので、命題 3.2 (2)により$G \subseteq S$である。すなわち$G$のすべての要素$x$について$P(x)$が真である。▨

証明.$S$を$G$の空でない部分集合とする。集合$\{\, \mathrm{rk}(x) : x \in S \,\}$は自然数の空でない集合なので、最小数原理により最小元$n_0$をもつ。$\mathrm{rk}(x_0) = n_0$を満たす$x_0 \in S$を一つとると、$y \in S$に対して$\mathrm{rk}(y) \ge n_0 = \mathrm{rk}(x_0)$なので、$y \prec x_0$を満たす$y \in S$は存在しない。よって$x_0$は$S$の極小元である。▨

証明.$\varphi$と$\psi$がともに上の二つの等式を満たすとし、述語$P(x)$を「$\varphi(x) = \psi(x)$」と定めて定理 3.3を適用する。$b \in B$については$\varphi(b) = g(b) = \psi(b)$である。$f \in F$と$x_1, \dots, x_k \in G$について$\varphi(x_i) = \psi(x_i)$がすべて成り立つとすると、

である。構造的帰納法により、$G$のすべての要素で$\varphi$と$\psi$は一致する。したがって、上の二つの等式をともに満たす写像は高々一つである。

以下、$G^{\le n} = \{\, x \in G : \mathrm{rk}(x) \le n \,\}$とおき、二つの等式をともに満たす写像を構成する。

$x \in G$に対して$\varphi(x) = \varphi_{\mathrm{rk}(x)}(x)$と定める。$m \le n$のとき、$\varphi_n$の$G^{\le m}$への制限は主張 4.4.1により主張 4.4.2の二つの条件を$m$について満たすので、$m$についての一意性から$\varphi_m$に一致する。したがって$\varphi$は各$\varphi_n$の拡張であり、主張 4.4.2の二つの条件がそのまま$\varphi$の二つの等式になる。高々一つであることは先に示したので、$\varphi$はただ一つ存在する。▨

証明.$v$と$w$を固定し、述語$P(u)$を「$(u \cdot v) \cdot w = u \cdot (v \cdot w)$」と定めて定理 3.3を$u$について適用する。

基底の場合、$u = \varepsilon$とすると$(\varepsilon \cdot v) \cdot w = v \cdot w = \varepsilon \cdot (v \cdot w)$である。両端の等号は、いずれも連結の定義の第一の等式による。

構成子の場合、$a \in \Sigma$と$u \in \Sigma^{*}$について$P(u)$を仮定する。連結の定義の第二の等式を三回用いると

となる。三つめの等号で帰納法の仮定$P(u)$を用いた。よって$P(au)$が成り立つ。構造的帰納法により、すべての$u \in \Sigma^{*}$について$P(u)$が真である。▨

証明. 述語$P(t)$を「$\lambda(t) = \iota(t) + 1$」と定めて定理 3.3を適用する。

基底の場合、$\lambda(\ell) = 1$かつ$\iota(\ell) + 1 = 0 + 1 = 1$なので$P(\ell)$が成り立つ。

構成子の場合、二分木$L, R$について$P(L)$と$P(R)$を仮定する。定義と帰納法の仮定から

である。よって$P((L, R))$が成り立つ。構造的帰納法により、すべての二分木$t$について$\lambda(t) = \iota(t) + 1$である。▨