Goodsteinの定理

同義語:Goodstein's theorem

概要

Goodsteinの定理(Goodstein's theorem)とは、自然数を底 $2$ の遺伝的表示で書き、底を $1$ ずつ上げて $1$ を引く操作をくり返すと、どの自然数から始めてもいつか $0$ に達するという定理である。数は途方もなく大きくなるが、底を $\omega$ に置き換えた $\varepsilon_0$ 未満の順序数は毎回真に減る。自然数だけの主張でありながら Peano算術では証明できないことが Kirby と Paris により示され、算術の強さと順序数 $\varepsilon_0$ の関係を示す代表例になっている。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 順序数, Cantor標準形, 超限帰納法, Peano算術

自然数を底 $2$ で書き、指数も底 $2$ で書き、さらにその指数も底 $2$ で書く。すべての $2$ を $3$ に置き換えて $1$ を引き、同じことを底 $3$ から $4$ へ、$4$ から $5$ へとくり返す。数は途方もない速さで大きくなるように見えるが、どの自然数から始めても、この操作はいつか $0$ に達する。 これが Goodstein の定理(Goodstein's theorem)である。R. L. Goodstein が 1944 年に証明した(Cai07 p. 382)。
主張は自然数の有限の操作だけで述べられているのに、証明には無限の順序数を使う。底を $\omega$ に置き換えると、数列は増えていても、対応する順序数は毎回真に減るからである。Kirby と Paris は 1982 年に、この定理が Peano算術 では証明できないことを示した(Cai07 p. 382)。
この記事では、定理を $\varepsilon_0$ 未満の順序数への写像で完全に証明する。さらに、列が $0$ に達するまでの長さを、順序数で添字づけた関数の値として正確に求める。$m=4$ の場合の長さは $3\cdot2^{402653211}-3$ である。Peano算術で証明できないことは文献の結果を引用し、そこから主張が導かれる部分だけを証明する。

定義

$b\ge2$ を自然数とする。正の整数 $m$ は
$$ m=b^{e_1}c_1+\cdots+b^{e_r}c_r\qquad(e_1>\cdots>e_r\ge0,\ 0< c_i< b) $$
とただ一通りに書ける。これを $m$ の 底 $b$ の展開 という。指数 $e_i$ も底 $b$ で展開し、そこに現れる指数もまた展開することをくり返して、$b$ より大きい数が残らないようにした表示を 底 $b$ の遺伝的表示 という。たとえば $35=2^5+2+1=2^{2^2+1}+2+1$ である。

底の取り替えと Goodstein 列

$B_b\colon\mathbb N\to\mathbb N$ を、$B_b(0)=0$ と、$m>0$ の底 $b$ の展開について
$$ B_b(m):=\sum_{i=1}^r(b+1)^{B_b(e_i)}c_i $$
で定める。$e_i< b^{e_i}\le m$ なので、この再帰は定まる。$B_b(m)$ は $m$ の遺伝的表示の $b$ をすべて $b+1$ に置き換えた数である。
自然数 $m$ から始まる Goodstein 列 $(G_k)_{k\ge0}$ を、$G_0:=m$ と
$$ G_{k+1}:=\begin{cases}B_{k+2}(G_k)-1&(G_k>0)\\0&(G_k=0)\end{cases} $$
で定める。$G_k$ を $0$ にする最小の $k$ が存在するとき、それを $\ell(m)$ と書く。

$B_b(m)\ge m\ge1$ なので、$1$ を引いても自然数である。$k$ 番目の項は底 $k+2$ で読み、底を $k+3$ に上げて $1$ を引く。$m=3$ と $m=4$ の最初の項は次のとおりである。右の列の順序数の意味は次の節で述べる。

$m$$k$底$G_k$底の展開対応する順序数
$3$$0$$2$$3$$2+1$$\omega+1$
$3$$1$$3$$3$$3$$\omega$
$3$$2$$4$$3$$3$$3$
$3$$3$$5$$2$$2$$2$
$3$$4$$6$$1$$1$$1$
$3$$5$$7$$0$$0$$0$
$4$$0$$2$$4$$2^2$$\omega^\omega$
$4$$1$$3$$26$$3^2\cdot2+3\cdot2+2$$\omega^2\cdot2+\omega\cdot2+2$
$4$$2$$4$$41$$4^2\cdot2+4\cdot2+1$$\omega^2\cdot2+\omega\cdot2+1$
$4$$3$$5$$60$$5^2\cdot2+5\cdot2$$\omega^2\cdot2+\omega\cdot2$
$4$$4$$6$$83$$6^2\cdot2+6+5$$\omega^2\cdot2+\omega+5$
$4$$5$$7$$109$$7^2\cdot2+7+4$$\omega^2\cdot2+\omega+4$

$m=4$ の行で見るとおり、数 $G_k$ は増えているが、右の順序数は毎回減っている。

Goodstein の定理

すべての自然数 $m$ について、$m$ から始まる Goodstein 列はある項で $0$ になる。

順序数への写像

底を $\omega$ に置き換える写像

$b\ge2$ について、$o_b\colon\mathbb N\to\mathrm{Ord}$ を、$o_b(0)=0$ と、$m>0$ の底 $b$ の展開について
$$ o_b(m):=\omega^{o_b(e_1)}\cdot c_1+\cdots+\omega^{o_b(e_r)}\cdot c_r $$
で定める。$o_b(m)$ は $m$ の遺伝的表示の $b$ をすべて $\omega$ に置き換えた順序数である。

$\varepsilon_0$ は $\omega,\omega^\omega,\omega^{\omega^\omega},\dots$ の上限である。$\varepsilon_0$ 未満の順序数の全体は、$\omega$ の冪と和で閉じているので、$m$ についての帰納法で $o_b(m)<\varepsilon_0$ である。

$o_b$ の 2 つの性質

$b\ge2$ とする。

  1. $o_b$ は狭義単調増加である。特に $m>0$ の底 $b$ の展開を置き換えた上の式は、$o_b(m)$ の Cantor標準形 である。
  2. すべての $m$ について $o_{b+1}(B_b(m))=o_b(m)$ である。

1:$m< m'$ のとき $o_b(m)< o_b(m')$ であることを $m'$ についての強い帰納法で示す。$m=0$ なら $o_b(m')>0$ なので明らかである。$m>0$ とする。$m,m'$ の展開に現れる指数 $e$ は $e< b^e\le m'$ を満たすので、帰納法の仮定からそれらの上で $o_b$ は狭義単調である。したがって $o_b(m)$、$o_b(m')$ の式の指数は狭義に減少し、係数は正の自然数であって、どちらも Cantor 標準形である。
底 $b$ の展開どうしの大小は、最大の指数から順に比べたときの最初の違いで決まる。指数の組と係数の組を並べて比べ、指数が大きいほうか、指数が等しければ係数が大きいほうが大きく、一方が他方の途中までと一致するなら長いほうが大きい。Cantor 標準形どうしの大小も同じ規則で決まる(Cantor標準形)。指数の大小は $o_b$ で保たれるので、$m< m'$ から $o_b(m)< o_b(m')$ を得る。
2:$m$ についての強い帰納法で示す。$m=0$ は明らかである。$m=\sum_ib^{e_i}c_i$ とする。帰納法の仮定から $o_{b+1}(B_b(e_i))=o_b(e_i)$ であり、1 によりこれは $i$ について狭義に減少する。$o_{b+1}$ は 1 により狭義単調だから、$B_b(e_1)>\cdots>B_b(e_r)$ である。係数は $c_i< b< b+1$ を満たす。よって $B_b(m)=\sum_i(b+1)^{B_b(e_i)}c_i$ はそのまま底 $b+1$ の展開であり、
$$ o_{b+1}(B_b(m))=\sum_i\omega^{o_{b+1}(B_b(e_i))}c_i=\sum_i\omega^{o_b(e_i)}c_i=o_b(m) $$
である。$\square$

2 が証明の要である。底を上げても、底を $\omega$ に置き換えた順序数は変わらない。数が増えるのは底が大きくなったことの見かけにすぎず、順序数はそれを感じない。

Goodstein の定理

$\alpha_k:=o_{k+2}(G_k)$ とおく。$G_k>0$ なら、lem-gs-two の 1 と 2 から
$$ \alpha_{k+1}=o_{k+3}\bigl(B_{k+2}(G_k)-1\bigr)< o_{k+3}\bigl(B_{k+2}(G_k)\bigr)=o_{k+2}(G_k)=\alpha_k $$
である。もしすべての $k$ で $G_k>0$ なら、$\alpha_0>\alpha_1>\cdots$ は順序数の無限降下列となり、順序数の整列性に反する。よってある $k$ で $G_k=0$ である。$\square$

列はすべて $\varepsilon_0$ 未満の順序数に写る。この事実が、次節以降で見るように、証明の強さの正確な尺度になる。

長さの公式

定理の証明を精密にすると、順序数がどのように減るかが分かり、$\ell(m)$ の値が求まる。順序数 の降下の 1 歩を記述する関数を用意する。
$0<\alpha<\varepsilon_0$ の Cantor 標準形を、同じ冪をくり返して $\alpha=\omega^{\beta_1}+\cdots+\omega^{\beta_n}$($\beta_1\ge\cdots\ge\beta_n$)と書き、$\nu:=\omega^{\beta_1}+\cdots+\omega^{\beta_{n-1}}$ とおく。$\beta_n=0$ のとき $\alpha$ は後続順序数で、$\beta_n>0$ のとき極限順序数である。

基本列・降下の関数・Hardy 関数

極限順序数 $\alpha<\varepsilon_0$ と $x\ge1$ について、$\alpha[x]$ を指数についての再帰で定める。
$$ \alpha[x]:=\begin{cases}\nu+\omega^\gamma\cdot x&(\beta_n=\gamma+1)\\\nu+\omega^{\beta_n[x]}&(\beta_n\text{ は極限順序数})\end{cases} $$
$0<\alpha[x]<\alpha$ である。$\alpha<\varepsilon_0$ について、$P_x(\alpha)$ と $H_\alpha(x)$ を $\alpha$ についての超限再帰で定める。

  • $P_x(0):=0$、$P_x(\beta+1):=\beta$、極限順序数 $\lambda$ について $P_x(\lambda):=P_x(\lambda[x])$
  • $H_0(x):=x$、$H_{\beta+1}(x):=H_\beta(x+1)$、極限順序数 $\lambda$ について $H_\lambda(x):=H_{\lambda[x]}(x)$
    $H_\alpha$ を Hardy 関数 という。

たとえば $\omega[x]=x$ だから、$P_x(\omega)=x-1$、$H_\omega(x)=H_x(x)=2x$ である。$\beta$ が $0$ か、Cantor 標準形の指数がすべて $1$ 以上の順序数なら $H_{\beta+\omega}(x)=H_\beta(2x)$ であり、くり返すと $H_{\beta+\omega\cdot c}(x)=H_\beta(2^cx)$ となる。特に $H_{\omega\cdot c}(x)=2^cx$ となり、$\omega^2[x]=\omega\cdot x$ から $H_{\omega^2}(x)=2^xx$ となる。順序数が上がるごとに増大の速さが一段ずつ上がる。
$\alpha[x]$ の定義の流儀は文献で少しずつ違い、Hardy 関数の添字の置き方も変わる。Cai07 Definition 1.13 は極限順序数で $x$ の代わりに $x+1$ を使う。下の公式はこの記事の定義についてのものである。

$1$ を引くことと $P$ の対応

$B\ge2$、$n\ge1$ とする。$0<\varepsilon<\varepsilon_0$ とする。

  1. $\nu+\delta$ を、$\delta>0$ の最大の指数が $\nu$ の最小の指数以下である和とする。このとき $P_x(\nu+\delta)=\nu+P_x(\delta)$ である。
  2. $P_B(\omega^\varepsilon)=\omega^{P_B(\varepsilon)}\cdot(B-1)+P_B\bigl(\omega^{P_B(\varepsilon)}\bigr)$ である。
  3. $o_B(n-1)=P_B(o_B(n))$ である。

1:$\delta$ についての超限帰納法で示す。$\nu+\delta$ の Cantor 標準形の最後の項は $\delta$ の最後の項である。$\delta=\delta'+1$ なら、どちらの辺も $\nu+\delta'$ である。$\delta$ が極限順序数なら $(\nu+\delta)[x]=\nu+\delta[x]$ で、$\delta[x]>0$ の最大の指数は $\delta$ の最大の指数以下であるから、帰納法の仮定により $P_x(\nu+\delta)=P_x(\nu+\delta[x])=\nu+P_x(\delta[x])=\nu+P_x(\delta)$ である。
2:$\varepsilon$ についての超限帰納法で示す。$\varepsilon=\gamma+1$ なら $\omega^\varepsilon[B]=\omega^\gamma\cdot B=\omega^\gamma(B-1)+\omega^\gamma$ で、1 から $P_B(\omega^\varepsilon)=\omega^\gamma(B-1)+P_B(\omega^\gamma)$ である。$P_B(\varepsilon)=\gamma$ だからこれが主張である。$\varepsilon$ が極限順序数なら $\omega^\varepsilon[B]=\omega^{\varepsilon[B]}$ で、$0<\varepsilon[B]<\varepsilon$ だから帰納法の仮定を $\varepsilon[B]$ に使える。$P_B(\varepsilon[B])=P_B(\varepsilon)$ なので主張を得る。
3:次の 2 つを $n\ge1$ についての強い帰納法で、この順に同時に示す。
$$ \mathrm{(a)}_n\colon\ o_B(n-1)=P_B(o_B(n)),\qquad\mathrm{(b)}_n\colon\ o_B(B^n-1)=P_B\bigl(\omega^{o_B(n)}\bigr) $$
$\mathrm{(a)}_n$ を示す。$n$ の底 $B$ の展開の最小の指数を $e$、その係数を $c$ として $n=M+B^ec$ と書く。$N:=M+B^e(c-1)$、$\mu:=o_B(N)$ とおく。$e=0$ なら $n-1=N$ で、$o_B(n)=\mu+1$ だから成り立つ。$e\ge1$ なら $n-1=N+(B^e-1)$ で、$B^e-1$ の指数は $e$ より小さいので、この和は底 $B$ の展開をつなげたものである。よって $o_B(n-1)=\mu+o_B(B^e-1)$、$o_B(n)=\mu+\omega^{o_B(e)}$ である。$e< B^e\le n$ だから $\mathrm{(b)}_e$ が使え、1 と合わせて $\mathrm{(a)}_n$ を得る。
$\mathrm{(b)}_n$ を示す。$\varepsilon:=o_B(n)>0$、$\varepsilon':=o_B(n-1)$ とおくと、$\mathrm{(a)}_n$ から $\varepsilon'=P_B(\varepsilon)$ である。$B^n-1=B^{n-1}(B-1)+(B^{n-1}-1)$ は展開をつなげたものだから
$$ o_B(B^n-1)=\omega^{\varepsilon'}(B-1)+o_B(B^{n-1}-1) $$
である。第 2 項は、$n=1$ なら $0=P_B(1)=P_B(\omega^0)$ で、$n\ge2$ なら $\mathrm{(b)}_{n-1}$ により $P_B(\omega^{\varepsilon'})$ である。いずれの場合も、2 により右辺は $P_B(\omega^\varepsilon)$ に等しい。$\square$

長さの公式

すべての自然数 $m$ について
$$ \ell(m)=H_{o_2(m)}(3)-3 $$
である。

まず、$0<\alpha<\varepsilon_0$、$x\ge1$ なら $H_\alpha(x)=H_{P_x(\alpha)}(x+1)$ であることを $\alpha$ についての超限帰納法で示す。$\alpha=\beta+1$ なら定義そのものである。$\alpha$ が極限順序数なら、$\alpha[x]>0$ だから帰納法の仮定により
$$ H_\alpha(x)=H_{\alpha[x]}(x)=H_{P_x(\alpha[x])}(x+1)=H_{P_x(\alpha)}(x+1) $$
である。
$\alpha_k:=o_{k+2}(G_k)$ とする。$G_k>0$ なら、lem-gs-two の 2 と lem-gs-pred の 3($B=k+3$)により
$$ \alpha_{k+1}=o_{k+3}\bigl(B_{k+2}(G_k)-1\bigr)=P_{k+3}\bigl(o_{k+3}(B_{k+2}(G_k))\bigr)=P_{k+3}(\alpha_k) $$
である。したがって $k<\ell(m)$ では $H_{\alpha_k}(k+3)=H_{\alpha_{k+1}}(k+4)$ となり、$H_{\alpha_0}(3)=H_{\alpha_{\ell(m)}}(\ell(m)+3)=H_0(\ell(m)+3)=\ell(m)+3$ を得る。$\square$

$m\le4$ の長さ

$o_2(0)=0$、$o_2(1)=1$、$o_2(2)=\omega$、$o_2(3)=\omega+1$ である。$H_1(3)=4$、$H_\omega(3)=6$、$H_{\omega+1}(3)=H_\omega(4)=8$ なので、$\ell(0),\ell(1),\ell(2),\ell(3)$ は $0,1,3,5$ である。
$m=4$ では $o_2(4)=\omega^\omega$ である。$(\omega^\omega)[3]=\omega^3$、$\omega^3[3]=\omega^2\cdot3$ であり、上の計算から
$$ H_{\omega^\omega}(3)=H_{\omega^2\cdot3}(3)=H_{\omega^2\cdot2}(2^3\cdot3)=H_{\omega^2}(2^{24}\cdot24) $$
である。$N:=2^{24}\cdot24=3\cdot2^{27}$ とおくと、これは $2^NN=3\cdot2^{N+27}=3\cdot2^{402653211}$ に等しい。よって
$$ \ell(4)=3\cdot2^{402653211}-3 $$
である。この数は $10^{121210694}$ の程度である。列の番号を $1$ から数える Cai07 p. 384 では同じ値が $3\cdot2^{402653211}-2$ と書かれている。

弱い版

指数を書き直さない版を 弱い Goodstein 列 という。$k$ 番目の項の底 $k+2$ の展開 $\sum_ib^{e_i}c_i$ の底 $b=k+2$ だけを $k+3$ に置き換え(指数 $e_i$ はそのまま)、$1$ を引く。$m=4$ の列は $4,8,9,10,11,11,\dots$ と進み、$21$ 歩で $0$ になる。
順序数としては $\sum_i\omega^{e_i}c_i$ を対応させればよい。指数がもとの自然数のままなので順序数は $\omega^\omega$ 未満にとどまり、thm-gs-main の証明と同じ議論で列は $0$ に達する。この形は HJ99 Chapter 6 の Theorem 6.5(p. 126)にあり、遺伝的表示の版は同じ節の Theorem 6.7(p. 127)にある。
$\varepsilon_0$ 未満の順序数 $\alpha$ を固定すれば、$\alpha$ までの超限帰納法を使う有限の議論は Peano算術の中で実行できる(Cai07 p. 383)。だから弱い版は Peano算術で証明できる。遺伝的な書き直しの深さを固定した版も同様に算術の部分体系で全域性が証明でき(Cai07 §3、pp. 390–391)、深さを制限しないことで初めて順序数が $\varepsilon_0$ まで届く。

Peano算術で証明できないこと

「$m$ から始まる Goodstein 列が $k$ で $0$ である」という $m,k$ の関係は原始再帰的で、算術の $\Sigma_1$ 論理式 $\mathrm{Gd}(m,k)$ で書ける。thm-gs-main は文 $\forall m\,\exists k\,\mathrm{Gd}(m,k)$ である。
次の支配の結果を引用する。関数 $f$ が Peano算術で全域と証明できる とは、$f$ のグラフが $\Sigma_1$ 論理式 $A$ で書け、$\mathsf{PA}\vdash\forall\vec x\,\exists!y\,A(\vec x,y)$ となることをいう。

Kirby–Paris の定理

関数 $m\mapsto\ell(m)+1$ は、Peano算術で全域と証明できるどの関数 $f$ についても、十分大きいすべての $m$ で $f(m)<\ell(m)+1$ を満たす。

これは Cai07 p. 385 に Kirby と Paris の結果として述べられている(同文献の Goodstein 関数は $\ell+1$ である)。Kirby と Paris の元の証明はモデル理論によるものである(同 p. 382)。Cai07 は Goodstein 関数を Löb–Wainer の急増加階層で書き表し(同 Theorem 1.11)、Wainer の定理(同 Theorem 1.9)から同じ結果を導く。thm-gs-length と同じ型の公式は Cichoń が Hardy 階層で与えた(同 pp. 386–387)。この記事では thm-gs-kp を証明しない。

独立性

$\forall m\,\exists k\,\mathrm{Gd}(m,k)$ は真であるが、Peano算術では証明できない。その否定も証明できない。

真であることは thm-gs-main である。$\mathsf{PA}$ で証明できたとする。$\mathsf{PA}$ は最小数原理を証明するから(Peano算術)、「$k$ は $\mathrm{Gd}(m,\cdot)$ を満たす最小の数である」という論理式で $\ell$ のグラフが書け、$\ell$ は全域と証明できる。すると $f(m):=\ell(m)+1$ も全域と証明できる。thm-gs-kp をこの $f$ に使うと、十分大きい $m$ で $\ell(m)+1<\ell(m)+1$ となり矛盾する。
否定は、$\mathbb N$ が $\mathsf{PA}$ のモデルであって偽の文は証明できないことから証明できない。$\square$

反例:数値ごとの証明と全称の証明

「すべての数値 $\bar m$ について $T\vdash A(\bar m)$ なら $T\vdash\forall m\,A(m)$」という含意は成り立たない。$T=\mathsf{PA}$、$A(m):=\exists k\,\mathrm{Gd}(m,k)$ がその反例である。

  • 満たすこと:各 $m$ について $A(\bar m)$ は真な $\Sigma_1$ 文なので、Robinson算術 で、したがって $\mathsf{PA}$ で証明できる。
  • 満たさないこと:$\forall m\,A(m)$ は cor-gs-independent により $\mathsf{PA}$ で証明できない。
  • 成り立たない含意:数値ごとの証明は別々の証明であり、それらを 1 本の全称の証明にまとめられるとは限らない。

条件を変えた反例

変える条件反例成り立たなくなること
毎回 $1$ を引く(引かない)$m=1$ で $G_{k+1}:=B_{k+2}(G_k)$ とすると、列は $1,1,1,\dots$$0$ に達すること
係数は変えない(係数にも $1$ を足す)$m=1$ で $G_{k+1}:=\sum_i(b+1)^{B_b(e_i)}(c_i+1)-1$($b=k+2$)とすると、列は $1,1,1,\dots$$0$ に達すること
順序数で測る(数 $G_k$ そのもので測る)$m=4$ で $G_0=4< G_1=26$列が各段で減ること
遺伝的な書き直し(指数を書き直さない)弱い版結論は保たれるが、Peano算術で証明できない主張ではなくなる

係数にも $1$ を足す場合は、$c_i+1$ が $\omega$ の冪の係数を増やすので順序数が減らない。lem-gs-two の 2 が係数を保つことに依存していることが分かる。弱い版の行は結論が成り立たないことを示す反例ではなく、遺伝的な書き直しこそが強さの源であることを示す比較である。

底の増やし方

底を $1$ ずつ上げる必要はない。列の底を任意の広義増加列 $b_0\le b_1\le\cdots$($b_0\ge2$)とし、$b_k$ を $b_{k+1}$ に置き換えて $1$ を引いても、lem-gs-two と同じ証明で順序数は毎回真に減る。底の増え方をどれほど速くしても列は $0$ に達する。

関連項目

参考文献

[1]
Andrés Eduardo Caicedo, Goodstein's function, Revista Colombiana de Matemáticas, 2007, pp. 381–391(p. 382、p. 383、p. 384、p. 385、Theorem 1.9、Theorem 1.11、Definition 1.13、pp. 386–387、§3 pp. 390–391)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する