大數學 维基
Advertisement

緩慢增長的層次結構是函數的層級。用可算序數\(\alpha\)和基本列系 \begin{eqnarray*} [ \ ] \colon \{(\beta,n) \in \textrm{On} \times \mathbb{N} \mid \beta \leq \alpha \land \textrm{cof}(\beta) = \aleph_0\} & \to & \textrm{On} \\ (\beta,n) & \mapsto & \beta[n], \end{eqnarray*} 緩慢增長層級 \begin{eqnarray*} (\alpha+1) \times \mathbb{N} & \to & \mathbb{N} \\ (\beta,n) & \mapsto & g_{\beta}(n) \end{eqnarray*} 被定義為:

  • 如果\(\beta = 0\)、\(g_{\beta}(n) = 0\)
  • 如果\(\beta = \beta'+1\)對於某些\(\beta' \in \textrm{On}\)、\(g_{\beta}(n) = g_{\beta'}(n)+1\)
  • 如果\(\beta\)是極限序數、\(g_{\beta}(n) = g_{\beta[n]}(n)\)

更加易懂的解释[]

第二条的解释可能不易懂,但是对于\(\beta\in\mathbb{N}\):

\(g_\beta(n)=\beta\)

示例[]

警告:讀者應注意互聯網上對緩慢增長的層次結構的許多解釋是不准確的。如果網頁在沒有固定基本列系的情況下引用緩慢增長的層次結構的近似值或比較,請懷疑結果。(參考: en:Slow-growing hierarchy#Warningen:Fast-growing hierarchy#Warning

\begin{eqnarray*} g_0(n) &=& 0 \\ g_1(n) &=& 1 \\ g_2(n) &=& 2 \end{eqnarray*}

Advertisement