グジェゴルチク階層（ぐじぇごるちくかいそう、英: Grzegorczyk hierarchy、発音：[??????rt???k]
）は計算可能性理論に基づく関数の階層である。（Wagner and Wechsung 1986:43）。名称はポーランドの論理学者アンジェイ・グジェゴルチク（英語版）に因む。グジェゴルチク階層に属す任意の関数は原始帰納的関数であり、逆に任意の原始帰納的関数はこの階層のあるレベルに現れる。この階層は関数値の増大の度合いを扱う。直観的にいえば、低い階層の関数はより高い階層の関数よりも緩やかに増加する。まず自然数 i で添字付けられた関数族 Ei を導入する。まず次のように定義する： E 0 ( x , y ) = x + y {\displaystyle E_{0}(x,y)=x+y} E 1 ( x ) = x 2 + 2 {\displaystyle E_{1}(x)=x^{2}+2} E n ( x ) = E n − 1 x ( 2 ) {\displaystyle E_{n}(x)=E_{n-1}^{x}(2)} （ただし n > 1）
これらの関数からグジェゴルチク階層を定義する。 E n {\displaystyle {\mathcal {E}}^{n}} は n番目の階層であり、次の関数からなる：
Ek （ただし k < n）
ゼロ関数 (Z(x) = 0);
後者関数 (S(x) = x + 1);
射影関数 ( p i m ( t 1 , t 2 , … , t m ) = t i {\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}} );
（一般）合成関数 （もし h, g1, g2, ... と gm が E n {\displaystyle {\mathcal {E}}^{n}} に属すならば f ( u ¯ ) = h ( g 1 ( u ¯ ) , g 2 ( u ¯ ) , … , g m ( u ¯ ) ) {\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))} も同様）[note 1]; および
限定（原始）再帰 （もし g, h と j が E n {\displaystyle {\mathcal {E}}^{n}} に属し f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} , f ( 0 , u ¯ ) = g ( u ¯ ) {\displaystyle f(0,{\bar {u}})=g({\bar {u}})} , f ( t + 1 , u ¯ ) = h ( t , u ¯ , f ( t , u ¯ ) ) {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))} ならば、 f もまた E n {\displaystyle {\mathcal {E}}^{n}} に属す)[note 1]
換言すれば E n {\displaystyle {\mathcal {E}}^{n}} は B n = { Z , S , ( p i m ) i ≤ m , E k : k < n } {\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}} を含み関数合成と限定原始再帰で閉じた最小の集合（閉包）である。 これらの集合は明らかに階層を成す。 E 0 ⊆ E 1 ⊆ E 2 ⊆ ⋯ {\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots } 実際これらは B n {\displaystyle B_{n}} の閉包であって B 0 ⊆ B 1 ⊆ B 2 ⊆ ⋯ {\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots } となっているからである。 これらは強い意味での包含関係が成り立つ（Rose 1984; Gakwaya 1997）。換言すれば E 0 ⊊ E 1 ⊊ E 2 ⊊ ⋯ {\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots } というのも、ハイパー演算子 H n {\displaystyle H_{n}} は E n {\displaystyle {\mathcal {E}}^{n}} に属すが E n − 1 {\displaystyle {\mathcal {E}}^{n-1}} には属さないからである。
性質
E 0 {\displaystyle {\mathcal {E}}^{0}} は次を含む： x+1, x+2, ...
E 1 {\displaystyle {\mathcal {E}}^{1}} は全ての加法関数を備える： x+y, 4x, ...
E 2 {\displaystyle {\mathcal {E}}^{2}} は全ての乗法関数を備える： xy, x4, ...