グジェゴルチク数列

グジェゴルチク数列 (Grzegorczyk sequence) とは，新井で定義された数列でペアノ算術から停止性が証明できないことが知られている．

定義

以下$x{\dot {-}}y$を$x\geq y$のとき$x-y$，そうでないとき$0$を表すものとする． $f_{n}\colon \mathbb {N} \to \mathbb {N}$を添字が有限な急増加関数とし，$k_{1}\geq 2$とする．このとき自然数$x$の底$k_{1}$による$f$-表現 ($f$-representation) は$x{\dot {-}}k_{1}$に対する帰納法で定義される．

1. $x<k_{1}$のとき$x$の$f$-表現は$x$そのものである．
2. $k_{1}\leq x$とする．$x_{1}$を$k_{1}\leq x<f_{x_{1}+1}(k_{1})$を満たす最小のものとし，$i_{1}$を$f_{x_{1}}^{i_{1}}(k_{1})\leq x<f_{x_{1}}^{k_{1}}(k_{1})=f_{x_{1}+1}(k_{1})$を満たす最大のものとする．
   1. $x_{1}=0$のとき$[(0,i_{1})]_{k_{1}}$は$x$の$f$-表現である．
   2. $x_{1}\neq 0$のとき，$k_{2}:=f_{x_{1}}^{i_{1}}(k_{1})\leq x<f_{x_{1}}(k_{2})$とし，$x_{2}<x_{1}$を$k_{2}\leq x<f_{x_{2}+1}(k_{2})$を満たす最小のものとする．
      1. $x=k_{2}$のとき，$[(x_{1},i_{1})]_{k_{1}}$は$f$-表現である．
      2. $x\neq k_{2}$のとき，$[(x_{2},i_{2}),\ldots ,(x_{l},i_{l})]_{k_{2}}\neq [(0,0)]_{k_{2}}$を$k_{2}$を底とする，$f$-表現とするとき，$[(x_{1},i_{1}),(x_{2},i_{2}),\ldots ,(x_{l},i_{l})]_{k_{1}}$は$k_{1}$を底とする$f$-表現である．

ここで$x$の$f$-表現が$[(x_{1},i_{1}),\ldots ,(x_{l},i_{l})]_{k_{1}}$であるというのは，$x=f_{x_{l}}^{i_{l}}(\cdots (f_{x_{1}}^{i_{1}}(k_{1})\cdots ))$と表されるということである．これを対応する自然数という．

$x$の$k$を底とする$f$-表現を$[(x_{1},i_{1}),\ldots ,(x_{l},i_{l})]_{k}$としたとき，$x[k:=m]$を$x\geq k$のとき，$[(x_{1}[k:=m],i_{1}),\ldots ,(x_{l}[k:=m],i_{l})]_{m}$が表現する自然数を表すものとし，$x<k$のとき$x[k:=m]=x$とする．

このとき，自然数$z$に対し，グジェゴルチク数列 (Grzegorczyk sequence) ，$\{z_{k}\}_{k}$は以下のように定義される．

1. $z_{0}=z$．
2. \(\begin{align*}z_{k+1}=\begin{cases}z_k\dot{-}1 & \text{if $z_k<2+k$}\\ z_k[2+k:=3+k]\dot{-}1 & \text{otherwise}\end{cases}\end{align*}\)．

性質

グッドスタイン数列と同様に，グジェゴルチク数列の停止性，すなわち$(\forall z)(\exists k)[z_{k}=0]$は標準モデルで真であるが，ペアノ算術で証明できないことが知られている．しかし新井の証明からは$(\forall z)(\exists k)[z_{k}=0]$のスコーレム関数，すなわち，停止するまでに要するステップ数がペアノ算術の可証全域関数を支配するからペアノ算術で証明できない，という手法ではないため$f_{\varepsilon _{0}}$と同じくらいの増大度を持つかは分かっていない．しかし具体的な値を試してみるに，急増大する関数であることが分かる．

遺伝的グジェゴルチク数列

自然数$x$に対して$k_{1}$を底とする．完全$f$-表現 (total $f$-representation)は$x$の$f$-表現の要素も$f$-表現で表し，その要素も表し……，のように再帰的に定義される．このとき$x[k:=m]$を，$x$の完全$f$-表現，$[(x_{1},i_{1}),(x_{2},i_{2}),\ldots ,(x_{l},i_{l})]_{m}$に対し$[(x_{1}[k:=m],i_{1}[k:=m]),\ldots ,(x_{l}[k:=m],i_{l}[k:=m])]_{m}$を表すものとし，グジェゴルチク数列の定義を上の完全$f$-表現を用いたものを遺伝的グジェゴルチク数列 (hereditary Grzegorczyk sequence) という．遺伝的グジェゴルチク数列の停止性の証明論的強さは未解決である，特に${\mathsf {ID}}_{1}$で示せるかどうかも分かっていない．

解析

$\mathrm {step} (n):=\min\{k\mid n_{k}=0\}$とする．すなわち$n$から始まるグジェゴルチク数列が$0$になるような最小の$k$が$\mathrm {step} (n)$である．

Naruyokoは$f(n,k):=2^{k-1}(n+3)+n$，$g(n,0):=n,g(n,k+1):=g(f(n,k+1),k)$としたとき$16\leq n\leq 31$に対して$\mathrm {step} (n)=g(2^{n-13}(n-13)+n-16,2^{n-13}(n-13)+n-13)$であることを示した．

Koteitanが$f$-標準形を求めるプログラムを作成している．