グジェゴルチク階層

グジェゴルチク階層（ぐじぇごるちくかいそう、、発音：）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者に因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。
定義.
まず自然数 "i" で添字付けられた関数族 "Ei" を導入する。まず次のように定義する：
これらの関数からグジェゴルチク階層を定義する。formula_4 は "n"番目の階層であり、次の関数からなる：
換言すれば formula_4 は formula_14 を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。
性質.
これらの集合は明らかに階層を成す。
実際これらは formula_16 の閉包であって formula_17 となっているからである。
これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば
というのも、ハイパー演算子 formula_19 は formula_4 に属すが formula_21 には属さないからである。
原始帰納的関数との関係.
formula_4 の定義は再帰が限定 （ある "j" formula_28 に対して formula_9）されていることと、formula_30 が明示的に導入されることを除けば 原始帰納的関数のクラス "PR" の定義に似ている。グジェゴルチク階層は原始再帰の強さを制限しているものと見ることができる。
この事実からグジェゴルチク階層に属す全ての関数は原始帰納的関数であること（すなわち formula_31）が示される。したがって
さらに全ての原始帰納的関数が何れかの階層に属すことも示される（Rose 1984; Gakwaya 1997）。つまり
また formula_34 は原始帰納的関数のクラス "PR" の分割となっている。さらに各々の領域は潰れていない。
拡張.
グジェゴルチク階層は超限順序数に一般化できる。そのような拡張として急成長階層が定義される。それには、極限順序数に対する生成関数 formula_35 を帰納的に定義しなければならない（後続型順序数に対しては formula_36 とすればよい。) もし極限順序数 formula_37 の基本列 formula_38 を作る一般的な方法があれば、 生成関数は formula_39 と定義できる。ところがこの定義は基本列を作る方法に依存する。Rose（1984）は任意の順序数 α < ε0 に対する基本列の一般的な構成法を提案した。
独自の拡張としては Martin Löb と Stan S. Wainer（1970）による Löb–Wainer 階層がある。