急成長階層

急増加関数から転送)

急成長階層(きゅうせいちょうかいそう、: fast-growing hierarchy急増加関数(きゅうぞうかかんすう)とも訳される)および拡張グジェゴルチク階層(かくちょうぐじぇごるちくかいそう、: extended Grzegorczyk hierarchy)とは、順序数 α に対して fα: NNN自然数 )を定める関数の階層である。最も標準的なものは、全てのα< ε0に対しての拡張である Wainer階層である。

定義編集

急成長階層fαは、次のように定義される。

 

ここで、 とし、 は、極限順序数αの基本列のn番目とする。

Wainer階層編集

Wainer階層は、α ≤ ε0となるαに対し、次のように基本列を定義する事によって得られる急成長階層である。

カントール標準形で書かれている極限順序数λ<ε0 の基本列λ[n]は

  1. λ=ωα1+...+ωαk-1αk のとき、 λ[n]=ωα1+...+ωαk-1αk[n] (但し、α1≥...≥αk-1≥αk)
  2. λ=ωα+1のとき、λ[n]=ωαn
  3. λ=ωα(αは極限順序数)のとき、λ[n]=ωα[n]
  4. λ=ε0のとき、基本列λ[n]は、
  • λ[0]=1
  • λ[n+1]=ωλ[n]

編集

 (1.を使用)

 (3.を使用)

 

 (2.を使用)

他の巨大数の表記法との比較編集