The Grzegorczyk hierarchy, named after the Polish logician Andrzej Grzegorczyk, is a system used in computability theory to classify functions. All functions in this hierarchy are primitive recursive functions, and all primitive recursive functions are included in the hierarchy at some level. The hierarchy focuses on how quickly the values of these functions increase. Functions in lower levels of the hierarchy increase more slowly than functions in higher levels.

Definition

We begin by introducing an infinite set of functions, labeled E_i, where i is a natural number (such as 1, 2, 3, and so on). These functions are defined as follows:

• E₀ is the addition function, which takes two numbers and returns their sum.
• E₁ is a unary function that takes one number, squares it, and then adds 2.
• For each natural number n greater than 1, E_n(x) is defined as the result of applying E_{n−1} to the number 2, repeated x times.

From these functions, we define the Grzegorczyk hierarchy. The n-th set in this hierarchy, denoted Eⁿ, includes the following functions:

• All functions E_k where k is less than n.
• The zero function, Z(x) = 0, which always returns 0 regardless of the input.
• The successor function, S(x) = x + 1, which adds 1 to its input.
• The projection functions, p_i^m(t₁, t₂, …, t_m) = t_i, which return the i-th input from a list of m inputs.
• All functions formed by composing functions from Eⁿ (for example, if h, g₁, g₂, …, g_m are in Eⁿ, then a new function f can be created as f(ū) = h(g₁(ū), g₂(ū), …, g_m(ū))).
• All functions created by applying limited (primitive) recursion to functions in Eⁿ. This includes functions f that satisfy the following conditions:
• f(0, ū) = g(ū), where g is in Eⁿ.
• f(t + 1, ū) = h(t, ū, f(t, ū)), where h is in Eⁿ.
• For all t and ū, f(t, ū) ≤ j(t, ū), where j is in Eⁿ.

In summary, Eⁿ is the set of all functions that can be generated by combining functions from the set B_n = {Z, S, (p_i^m)_{i ≤ m}, E_k : k < n} using function composition and limited recursion, as described above.

Properties

These sets form a clear hierarchy because they are built from the Bₙ sets, and each set is a smaller group inside the next one: B₀ ⊆ B₁ ⊆ B₂ ⊆ ⋯. Each set is strictly contained within the next. This is because the hyperoperation Hₙ is part of Eⁿ but not part of Eⁿ⁻¹.

• E⁰ includes functions like x + 1, x + 2, and so on.
• E¹ includes all addition functions, such as x + y and 4x.
• E² includes all multiplication functions, such as x × y and x⁴.
• E³ includes all exponentiation functions, such as xʸ and 2²²ˣ, and matches the elementary recursive functions.
• E⁴ includes all tetration functions, and this pattern continues.

The function U and the characteristic function of the predicate T from the Kleene normal form theorem can be defined in a way that places them in E⁰ of the Grzegorczyk hierarchy. This means that every computably enumerable set can be listed using an E⁰ function.

Relation to primitive recursive functions

The set E^n is defined similarly to the set of primitive recursive functions, PR, but with two key differences. First, recursion in E^n is limited by a condition: for any function f in E^n, its output must not exceed the output of another function j in E^n (f(t, ū) ≤ j(t, ū)). Second, the sets of functions (E_k) for all k less than n are explicitly included in E^n. This structure creates the Grzegorczyk hierarchy, which organizes primitive recursive functions into levels based on the complexity of their recursion.

This hierarchy shows that every function in any level of E^n is also a primitive recursive function (E^n ⊆ PR). Additionally, all primitive recursive functions belong to some level of the Grzegorczyk hierarchy. The sets E^0, E^1 − E^0, E^2 − E^1, …, E^n − E^{n−1}, … divide the entire set of primitive recursive functions into distinct groups.

Meyer and Ritchie created another classification of primitive recursive functions, based on the maximum depth of nested loops in a LOOP program that computes the function. For each natural number i, let L_i represent the set of functions computable by a LOOP program with loops nested no deeper than i levels. Fachini and Maggiolo-Schettini proved that L_i matches E^{i+1} for all integers i > 1.

Extensions

The Grzegorczyk hierarchy can be expanded to include infinite ordinals. This expansion creates a fast-growing hierarchy. To do this, the generating functions E_α must be defined step by step for limit ordinals. These functions were already defined for successor ordinals using the rule E_{α+1}(n) = E_α^n(2). If there is a standard way to define a sequence λ_m that approaches the ordinal λ, then the generating functions can be defined as E_λ(n) = E_{λ_n}(n). However, this definition relies on having a standard way to create the fundamental sequence. Rose (1984) proposed a standard method for all ordinals α less than ε0. The original extension was developed by Martin Löb and Stan S. Wainer and is sometimes referred to as the Löb–Wainer hierarchy.