構造的帰納法
概要
構造的帰納法（structural induction）とは、基本の元の集合 $B$ から有限個の引数をとる構成子で帰納的に生成される集合 $C$ の元すべてについて性質を示すとき、$B$ の元で成り立つことと、構成子で性質が保たれることを確かめればよいという原理である。$C$ は $B$ を含み構成子で閉じた最小の集合であり、段階的に構成子を当てて得る集合の合併とも一致する。各元の組み立て方が一通りである自由な生成のもとでは、組み立て方に沿って関数がただ一つ定まり（構造的再帰）、論理式の真理値や木の大きさの定義を支える。自然数の数学的帰納法はその特別な場合である。
論理式・項・正規表現・木・リストのように、「基本の対象から出発し、決まった組み立て方を有限回使って作ったものだけ」からなる集合は、数学と計算機科学のいたるところに現れる。このような集合の元すべてについて性質を示すには、基本の対象で成り立つことと、組み立て方で性質が保たれることを確かめればよい。これが 構造的帰納法 である。自然数の数学的帰納法は、基本の対象 $0$ と組み立て方 $n\mapsto n+1$ の場合にあたる。
構造的帰納法は、組み立てで閉じた最小の集合という定義から直ちに従う。一方、組み立て方に沿って関数を定義する 構造的再帰 には、各元の組み立て方がただ一通りであること（自由な生成）が必要になる。この記事では、生成された集合の二通りの記述を一致させ、構造的帰納法を示したうえで、自由な生成のもとで構造的再帰定理を証明し、条件を外すと再帰が破綻する例を挙げる。
定義
$U$ を集合、$B\subset U$ を部分集合とし、$\mathcal{F}$ を写像の集合で、各 $f\in\mathcal{F}$ はある自然数 $n_f\geq1$ について $f\colon U^{n_f}\to U$ であるとする。
- $Y\subset U$ が $\mathcal{F}$ で閉じている とは、すべての $f\in\mathcal{F}$ と $y_1,\dots,y_{n_f}\in Y$ について $f(y_1,\dots,y_{n_f})\in Y$ となることをいう。
- $B$ を含み $\mathcal{F}$ で閉じた $U$ の部分集合すべての共通部分を
$$ C:=\bigcap\{Y\subset U\mid B\subset Y,\ Y\text{ は }\mathcal{F}\text{ で閉じている}\} $$
と書き、$B$ から $\mathcal{F}$ で帰納的に生成される集合 という。$B$ の元を 基本の元、$\mathcal{F}$ の元を 構成子 という。
$U$ 自身が条件を満たすので共通部分をとる族は空でなく、閉じた集合の共通部分はまた閉じているので、$C$ は「$B$ を含み $\mathcal{F}$ で閉じた最小の集合」である。$U$ は「組み立てに使う材料の全体」で、たとえば論理式を作るときは記号列全体をとる。$C$ の元は $U$ の元のうち規則で作れるものだけである。
$\mathbb{N}$ 上の再帰で
$$
C_0:=B,\qquad C_{k+1}:=C_k\cup\bigl\{f(x_1,\dots,x_{n_f})\ \big|\ f\in\mathcal{F},\ x_1,\dots,x_{n_f}\in C_k\bigr\}
$$
と定める。$x\in\bigcup_kC_k$ について、$x\in C_k$ となる最小の $k$ を $x$ の 段数 といい、$s(x)$ と書く。
「上から」の定義 $C$ と「下から」の定義 $\bigcup_kC_k$ は一致する。
$C=\bigcup_{k\in\mathbb{N}}C_k$ である。
$C_k\subset C$ を $k$ についての帰納法で示す。$C_0=B\subset C$ であり、$C_k\subset C$ なら、$C$ は $\mathcal{F}$ で閉じているので $C_{k+1}\subset C$ である。
逆に、$D:=\bigcup_kC_k$ が $B$ を含み $\mathcal{F}$ で閉じていることを示せば、$C$ の最小性から $C\subset D$ となる。$B=C_0\subset D$ である。$f\in\mathcal{F}$ と $x_1,\dots,x_{n_f}\in D$ をとると、$x_i\in C_{k_i}$ となる $k_i$ がある。$C_0\subset C_1\subset\cdots$ なので、$k:=\max_ik_i$ とおけば $x_1,\dots,x_{n_f}\in C_k$ であり、$f(x_1,\dots,x_{n_f})\in C_{k+1}\subset D$ である。$\square$
証明で引数の段数の最大値をとったところで、各構成子の引数が 有限個 であることを使っている。無限個の引数をとる構成子では、この一致が崩れることがある（下の反例の表の 1 行目）。
構造的帰納法
$C$ を $B$ から $\mathcal{F}$ で帰納的に生成される集合とし、$P\subset U$ とする。
(i) $B\subset P$ であり、
(ii) すべての $f\in\mathcal{F}$ と $x_1,\dots,x_{n_f}\in C\cap P$ について $f(x_1,\dots,x_{n_f})\in P$ である
ならば、$C\subset P$ である。
$Y:=C\cap P$ とおく。$B\subset C$ と (i) から $B\subset Y$ である。$x_1,\dots,x_{n_f}\in Y$ なら、$C$ が閉じていることから $f(x_1,\dots,x_{n_f})\in C$、(ii) から $f(x_1,\dots,x_{n_f})\in P$ なので、$Y$ は $\mathcal{F}$ で閉じている。$C$ の最小性から $C\subset Y\subset P$ である。$\square$
(ii) で引数を $C\cap P$ に限っているので、「$C$ の元で、すでに性質をもつもの」から組み立てた元だけを調べればよい。性質が論理式 $\varphi(x)$ で与えられるときは $P=\{x\in U\mid\varphi(x)\}$ とおく。thm-si-stages を使えば、構造的帰納法は段数 $s(x)$ についての累積帰納法としても読める。
- 自然数：$U=\mathbb{N}$、$B=\{0\}$、$\mathcal{F}=\{n\mapsto n+1\}$ とすると $C=\mathbb{N}$ であり、thm-si-induction は数学的帰納法そのものである。
- 文字列：アルファベット $\Sigma$ について、$U=\Sigma^*$（有限列全体）、$B=\{\varepsilon\}$（空列）、$\mathcal{F}=\{w\mapsto aw\mid a\in\Sigma\}$（先頭に文字を一つ付ける）とすると $C=\Sigma^*$ である。リストの帰納法とも呼ばれる。
- 命題論理の論理式：$U$ を命題変数 $p_0,p_1,\dots$ と記号 $\lnot,\land,\lor,\to,(,)$ からなる記号列全体、$B$ を命題変数の全体、構成子を $u\mapsto(\lnot u)$ と $(u,v)\mapsto(u\ast v)$（$\ast\in\{\land,\lor,\to\}$）とすると、$C$ は命題論理の論理式の全体である。
- 正規表現・文法：正規表現は 3 つの基本の形と、連接・和・Kleene 閉包の 3 つの構成子から生成される記号列の集合であり、BNF で定めた言語も各生成規則を構成子とみて同じ形になる（Backus–Naur記法の系「生成規則に沿った帰納法」）。
- 二分木：$U=V_\omega$（遺伝的有限集合の全体。その有限部分集合はまた元になる。ZFC公理系の定理「遺伝的有限集合の宇宙 $V_\omega$」の証明）、$B=\{\emptyset\}$、構成子を順序対 $(s,t)\mapsto\langle s,t\rangle=\{\{s\},\{s,t\}\}$ とする。$\emptyset$ を葉、$\langle s,t\rangle$ を「左の部分木 $s$、右の部分木 $t$ をもつ節点」と読めば、$C$ の元は全二分木（各節点がちょうど 2 つの子をもつ木）を表す。
命題論理の論理式 $\varphi$ について、命題変数の出現の個数を $a(\varphi)$、記号 $\land,\lor,\to$ の出現の個数を $c(\varphi)$ とすると、$a(\varphi)=c(\varphi)+1$ である。
実際、$P:=\{w\in U\mid a(w)=c(w)+1\}$ とおくと、命題変数 $p_i$ は $a=1$、$c=0$ なので $P$ に入る。$u\in P$ なら $(\lnot u)$ は $a,c$ が $u$ と同じなので $P$ に入る。$u,v\in P$ なら
$$
a((u\ast v))=a(u)+a(v)=c(u)+c(v)+2=c((u\ast v))+1
$$
なので $(u\ast v)\in P$ である。thm-si-induction により、すべての論理式が $P$ に入る。
この例は記号の個数を数えるだけなので、論理式の読み方が一通りかどうかを使っていない。構造的帰納法は組み立て方が一通りでなくても使える。
連接と和だけを使い Kleene 閉包を使わずに作った正規表現 $\alpha$ について、$\alpha$ が表す言語 $L(\alpha)$ は有限集合である。基本の形 $\emptyset$、$\varepsilon$、$a$ の言語は高々 1 元であり、有限言語 $L_1,L_2$ の連接 $L_1L_2$ と和 $L_1\cup L_2$ は有限なので、thm-si-induction（構成子を連接と和の 2 つに限って生成した集合に適用する）により従う。逆は成り立たない：$(\emptyset)^*$ は Kleene 閉包を使うが、$L((\emptyset)^*)=\{\varepsilon\}$ は有限である。
自由な生成と構造的再帰
組み立て方に沿って値を決める定義、たとえば論理式の真理値や木の葉の個数は、各元の組み立て方が一通りでなければ意味をもたない。
$C$ を $B$ から $\mathcal{F}$ で帰納的に生成される集合とする。次の (F1)〜(F3) が成り立つとき、$C$ は $B$ と $\mathcal{F}$ から 自由に生成される という。
(F1) 各 $f\in\mathcal{F}$ の $C^{n_f}$ への制限は単射である。
(F2) $f\neq g$ なら、$f(C^{n_f})$ と $g(C^{n_g})$ は交わらない。
(F3) 各 $f\in\mathcal{F}$ について、$f(C^{n_f})$ は $B$ と交わらない。
まとめると、$C$ の元は「基本の元」か「ある構成子 $f$ と $C$ の元の組 $(x_1,\dots,x_{n_f})$ による $f(x_1,\dots,x_{n_f})$」のどちらかちょうど一方の形で、後者のとき $f$ と $x_1,\dots,x_{n_f}$ は一通りに決まる。命題論理の論理式についてはこれが命題論理の定理「一意読み取り」の内容であり、一階述語論理の論理式と項については論理式の定理「一意読み取り」である。
$k\geq1$ と $x\in C_k\setminus B$ について、$f\in\mathcal{F}$ と $x_1,\dots,x_{n_f}\in C_{k-1}$ で $x=f(x_1,\dots,x_{n_f})$ となるものがある。
$k$ についての帰納法による。$x\in C_k\setminus B$ は、定義から $x\in C_{k-1}$ であるか、$C_{k-1}$ の元から構成子で作られる。後者ならよい。前者なら $k\geq2$ で $x\in C_{k-1}\setminus B$ なので、帰納法の仮定から $C_{k-2}\subset C_{k-1}$ の元による分解がある。$\square$
$C$ が $B$ から $\mathcal{F}$ で自由に生成されるとする。集合 $V$、写像 $h\colon B\to V$、各 $f\in\mathcal{F}$ についての写像 $G_f\colon C^{n_f}\times V^{n_f}\to V$ が与えられたとき、写像 $\hat{h}\colon C\to V$ で
$$
\hat{h}(b)=h(b)\quad(b\in B),\qquad\hat{h}\bigl(f(\vec{x})\bigr)=G_f\bigl(\vec{x},\ \hat{h}(\vec{x})\bigr)\quad(f\in\mathcal{F},\ \vec{x}\in C^{n_f})
$$
を満たすものがただ一つ存在する。ここで $\vec{x}=(x_1,\dots,x_{n_f})$、$\hat{h}(\vec{x})=(\hat{h}(x_1),\dots,\hat{h}(x_{n_f}))$ である。
準備。 (F1)(F2) により、$x\in C\setminus B$ の分解 $x=f(\vec{x})$（$\vec{x}\in C^{n_f}$）は一通りである。lem-si-decomp と合わせると、$x\in C_k\setminus B$ のこの分解では $\vec{x}\in C_{k-1}^{n_f}$ となる。
段階ごとの定義。 写像 $h_k\colon C_k\to V$ を $k$ についての再帰で定め、次の性質 $(\mathrm{I}_k)$ をもつことを示す：$h_k|_B=h$、$k\geq1$ なら $h_k|_{C_{k-1}}=h_{k-1}$、そして各 $x\in C_k\setminus B$ について、その分解 $x=f(\vec{x})$ に対し $h_k(x)=G_f(\vec{x},h_k(\vec{x}))$。
$h_0:=h$ とすると $(\mathrm{I}_0)$ が成り立つ。$h_k$ が $(\mathrm{I}_k)$ を満たすとき、$x\in C_k$ では $h_{k+1}(x):=h_k(x)$ とし、$x\in C_{k+1}\setminus C_k$ では、$x\notin B$ なので分解 $x=f(\vec{x})$ が一通りに定まり、しかも定義から $\vec{x}\in C_k^{n_f}$ ととれるので、$h_{k+1}(x):=G_f(\vec{x},h_k(\vec{x}))$ とする。分解が一通りなので $h_{k+1}$ は写像として定まる。$(\mathrm{I}_{k+1})$ を確かめる。$x\in C_{k+1}\setminus B$ をとる。$x\in C_k$ なら分解の $\vec{x}$ は $C_{k-1}$ に入り、$(\mathrm{I}_k)$ から $h_{k+1}(x)=h_k(x)=G_f(\vec{x},h_k(\vec{x}))=G_f(\vec{x},h_{k+1}(\vec{x}))$ である。$x\notin C_k$ なら、定義と $\vec{x}\in C_k^{n_f}$ から同じ等式が成り立つ。
合併。 各 $h_{k+1}$ は $h_k$ の拡張なので、$\hat{h}:=\bigcup_kh_k$ は $\bigcup_kC_k=C$（thm-si-stages）上の写像で、$\hat{h}|_B=h$ である。$f\in\mathcal{F}$ と $\vec{x}\in C^{n_f}$ について $z:=f(\vec{x})$ とおくと、(F3) から $z\notin B$ であり、$z\in C_k$ となる $k\geq1$ がある。$z$ の分解は $(f,\vec{x})$ なので、$(\mathrm{I}_k)$ から $\hat{h}(z)=h_k(z)=G_f(\vec{x},h_k(\vec{x}))=G_f(\vec{x},\hat{h}(\vec{x}))$ である。
一意性。 $\hat{h}'$ も条件を満たすとし、$P:=\{x\in C\mid\hat{h}(x)=\hat{h}'(x)\}$ とおく。$B\subset P$ であり、$\vec{x}\in P^{n_f}$ なら $\hat{h}(f(\vec{x}))=G_f(\vec{x},\hat{h}(\vec{x}))=G_f(\vec{x},\hat{h}'(\vec{x}))=\hat{h}'(f(\vec{x}))$ なので、thm-si-induction により $P=C$ である。$\square$
(F1)(F2) は値を定めるときの分解の一意性に、(F3) は基本の元での値 $h(b)$ と構成子の式が衝突しないことに使われている。どれか一つを外すと、値が二通りに要求されて再帰が破綻する例がある（下の反例の表）。$\mathbb{N}$ の場合、この定理は帰納的定義の再帰定理であり、命題論理の場合、付値 $v$ から論理式全体の真理値を定める定義（命題論理の定義「付値と真理値」）はこの定理の特別な場合である。
ex-si-examples の 5 の二分木の集合 $C$ は自由に生成される。(F1) は順序対の性質 $\langle s,t\rangle=\langle s',t'\rangle\Rightarrow s=s',\ t=t'$、(F2) は構成子が一つであること、(F3) は $\emptyset$ が元をもたず順序対（元 $\{s\}$ をもつ）でないことによる。thm-si-recursion により
$$
\ell(\emptyset)=1,\quad\ell(\langle s,t\rangle)=\ell(s)+\ell(t),\qquad m(\emptyset)=\emptyset,\quad m(\langle s,t\rangle)=\langle m(t),m(s)\rangle
$$
を満たす写像 $\ell\colon C\to\mathbb{N}$（葉の個数）と $m\colon C\to V_\omega$（左右を入れ替えた鏡像）がただ一つずつ定まる。
構造的帰納法で次が分かる：すべての $t\in C$ について $m(t)\in C$、$\ell(m(t))=\ell(t)$、$m(m(t))=t$。たとえば最後の等式は、$t=\emptyset$ で成り立ち、$s,t$ で成り立てば
$$
m(m(\langle s,t\rangle))=m(\langle m(t),m(s)\rangle)=\langle m(m(s)),m(m(t))\rangle=\langle s,t\rangle
$$
となる。ここで 2 番目の等号には $m(s),m(t)\in C$ を使っている。
整礎関係との関係
自由に生成された集合では、「直接の構成要素である」という関係が整礎になり、構造的帰納法はその上の整礎帰納法（整礎関係の定理「整礎帰納法」）と同じものになる。
$C$ が自由に生成されるとし、$C$ 上の関係 $\triangleleft$ を「$y\triangleleft x\iff$ ある $f\in\mathcal{F}$ と $\vec{x}\in C^{n_f}$ について $x=f(\vec{x})$ かつ $y$ は $x_1,\dots,x_{n_f}$ のどれか」で定める。このとき $y\triangleleft x$ なら $s(y)< s(x)$ であり、$\triangleleft$ は整礎である。
$y\triangleleft x$、$x=f(\vec{x})$ とする。(F3) から $x\notin B$ なので $k:=s(x)\geq1$ であり、lem-si-decomp から $x=g(\vec{z})$、$\vec{z}\in C_{k-1}^{n_g}$ と書ける。(F1)(F2) から $g=f$、$\vec{z}=\vec{x}$ なので、$y$ は $C_{k-1}$ に入り、$s(y)\leq k-1< s(x)$ である。段数 $s$ は $\triangleleft$ に沿って真に増える $\mathbb{N}$ への写像なので、整礎関係の定理「順序数への写像による特徴づけ」により $\triangleleft$ は整礎である。$\square$
$\triangleleft$ に関して $x\in B$ は前者をもたず、$x=f(\vec{x})$ の前者はちょうど $x_1,\dots,x_{n_f}$ である。したがって「$\triangleleft$ に関する前者がすべて $P$ に入れば $x\in P$」という整礎帰納法の仮定は、thm-si-induction の (i)(ii) と同じことを言っている。自由でない場合には、$\triangleleft$ は整礎とは限らない（下の表の最後の行）。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 構成子の引数が有限個 | $U=\omega+1$、$B=\{0\}$、後者 $x\mapsto x+1$（$\omega\mapsto\omega$）と可算列の上限 | 上からと下からの一致 $C=\bigcup_kC_k$ |
| (F3) 像が基本の元と交わらない | $U=\mathbb{Z}/2\mathbb{Z}$、$B=\{0\}$、$f(x)=x+1$ | 構造的再帰（$h(0)=0$、$G_f(x,v)=v+1$） |
| (F2) 異なる構成子の像が交わらない | $U=\mathbb{Z}$、$B=\{0\}$、$f(x)=x+1$、$g(x)=x+2$ | 構造的再帰（$g$ を使った回数を数える） |
| (F1) 構成子が単射 | $U=\mathbb{N}$、$B=\{1\}$、$f(x,y)=x+y$ | 構造的再帰（左の成分の深さを数える） |
| 自由な生成 | 2 行目の $\mathbb{Z}/2\mathbb{Z}$ | 直接の構成要素の関係の整礎性 |
各行の確かめを開く
1 行目：$C_k=\{0,1,\dots,k\}$ なので $\bigcup_kC_k=\omega$ だが、$0$ を含み 2 つの演算で閉じた集合は $0,1,2,\dots$ とその上限 $\omega$ を含むので、上からの定義では $C=\omega+1$ である。上限をとる演算は可算無限個の引数をとるので、def-si-generated の条件 $n_f$ が有限であることを満たさない。
2 行目：$C=\{0,1\}$ で (F1)(F2) は成り立つが、$f(1)=0\in B$。再帰の式は $\hat{h}(1)=\hat{h}(f(0))=1$、$\hat{h}(0)=\hat{h}(f(1))=2$ を要求し、$\hat{h}(0)=h(0)=0$ と矛盾する。
3 行目：$C=\mathbb{N}$ で (F1)(F3) は成り立つが、$f(1)=g(0)=2$。$h(0)=0$、$G_f(x,v)=v$、$G_g(x,v)=v+1$ とすると、$\hat{h}(1)=0$ から $\hat{h}(2)=\hat{h}(f(1))=0$ と $\hat{h}(2)=\hat{h}(g(0))=1$ が要求される。
4 行目：$C$ は正の整数の全体で、$1$ は正の整数 2 つの和でないので (F3) は成り立つが、$f(1,2)=f(2,1)=3$。$h(1)=0$、$G_f(x,y,v,w)=v+1$ とすると、$\hat{h}(2)=1$ であり、$\hat{h}(3)$ は $\hat{h}(1)+1=1$ と $\hat{h}(2)+1=2$ の両方を要求される。
5 行目：$0=f(1)$、$1=f(0)$ なので $0\triangleleft1$ かつ $1\triangleleft0$ であり、長さ 2 の循環がある（整礎関係の命題「整礎関係の基本性質」の 1）。
自由でない生成は実際の文法でも起こる。括弧を省いて $u\land v$ のように書く規則では、$p\land q\lor r$ が二通りに組み立てられ、真理値が読み方によって変わる（Backus–Naur記法の注意「反例：曖昧な文法」）。
補足
不動点としての見方。 $Y\mapsto B\cup\{f(\vec{y})\mid f\in\mathcal{F},\ \vec{y}\in Y^{n_f}\}$ は $U$ の部分集合の上の単調な写像で、$C$ はその最小不動点である（Knaster–Tarskiの定理）。thm-si-stages は、構成子の引数が有限個なら $\omega$ 回の繰り返しで最小不動点に達することを述べている。
同時に定める複数の種類。 項と論理式、BNF の複数の非終端記号のように、いくつかの種類の対象を同時に生成する場合も、種類ごとの集合の組を考えれば同じ議論が成り立つ（Backus–Naur記法の命題「生成言語と規則の方程式の最小解」）。
生成される集合の上からと下からの記述の一致、帰納法、自由な生成と構造的再帰（一意な準同型拡張定理）、自由でない生成の例は Gal15 §2.3, Lemma 2.3.1–2.3.3, Theorem 2.3.1, Example 2.3.3（pp. 17–23）にある。thm-si-recursion は構成子ごとの式が引数そのものにも依存してよい形にしてあり、証明もこの形で書いた。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
