3.  The Grzegorczyk Hierarchy

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

Reprise

The PR functions are defined as the closure of R and C over a basic stock of functions.  Both the logician's diagonal argument and the double-recursion diagonal arguments involve functions that can "simulate" n nested primitive recursions when given an argument n.  Intuitively, the situation is that each PR function is allowed only finitely many nested primitive recursions, so functions that require arbitrarily many (without bound) are not PR.

This situation calls out for greater attention to which functions can be defined with a given, fixed number of primitive recursion operations.  In other words, it makes sense to look at the hierarchy of increasing classes En defined in terms of increasing numbers of primitive recursions, where each class is closed under composition.  Every PR function will be at some finite level of the hierarchy:

A natural idea would be to start with the basic functions closed under composition and then to add in successively more complex functions like addition, multiplication, exponentiation, etc., closing under composition each time.

But composition is a little weak.  Recall that some slow-growing functions like cutoff subtraction required the R schema for their definitions even though they don't really use it to generate faster growth. We would like to distinguish growth-generating applications of R from applications that don't generate growth.

We can get around the difficulty by closing each class under bounded recursion as well as composition. An application of R is bounded in a class of functions if the function resulting from the application is bounded everywhere by some other function already established to be in the class.

Bounded Recursion:  An application of R to g, f is bounded just in case there is a previously defined h such that for all x,

R(g, f)(x) £h(x).
For example, in the cases of decrementation and cutoff subtraction, we have
Dec(x) < p1,1(x);
x -. y < p2,2(x, y).
So both of these functions are definable by bounded recursion and composition from basic functions.  Similarly for -., quotient, remainder, sg and -sg, min,  and max.

The Grzegorczyk Hierarchy

We first introduce a "spine" {en: n Î N} of representative functions requiring increasing numbers of primitive recursions for their definition.  It doesn't matter that much which spine we choose, since the closure operations and bounded recursion will smooth out the resulting classes, yielding invariance.  We will follow Rose's development (pp. 31-36), keeping in mind that there are others.

Define

e0(x, y) = x + y;
e1(x) = x2 + 2;
en+2(0) = 2;
en + 2(x + 1) = en + 1(en + 2(x)).
Then define:
E0 = the least set X containing the basic functions and closed under composition and bounded recursion.
En+1 = the least set X containing the basic functions, ei, and closed under composition and bounded recursion.
Then the indexed collection {En: n Î N} is called the Grzegorczyk hierarchy.
Note that by the third level the higher functions iterate the lower functions on argument 2.

Proposition 0:  en + 3(x) = (en + 2)x(2).
Proof:

en + 3(0) = 2 = (en + 2)0(2);
en + 3(x) = (en + 2)x(2) Þ en + 3(x + 1)  = en + 2(en + 3(x)) = en + 2((en + 2)x(2)) = (en + 2)x + 1(2).

Double Induction

Many of the basic results about double recursion are proved by double induction.  As you know very well, induction is the schema:
0) [F(0)Ù"x (F(x) ®F(x + 1))] ®"x F(x).
What if we wish to prove that forall x, "y Y(x, y)?

If we substitute the desired conclusion "y Y(x, y) for F(x), then we obtain:

1) ["yY(0, y)Ù"x (("yY(x, y)) ® ("y Y(x + 1, y)))] ®"x ("yY(x, y)).
To get the first conjunct of the antecedent of (1), it suffices (by induction) to prove:
2) Y(0, 0) Ù "y (Y(0, y) ®Y(0, y + 1)).
To get the second conjunct, we can use induction to get the universal quantifier on y in the consequent, so it suffices to show:
(3) "x (("y Y(x, y)) ® [Y(x + 1, 0) Ù [Y(x + 1, y) ®Y(x + 1, y + 1)]].
Double Induction Schema: The technique is illustrated by the following result which will be of use shortly.

Proposition 1:  for all n ³ 1,

  1. en(x) ³ x + 1;
  2. en(x + 1) > en(x);
  3. en + 1(x) ³en(x);
  4. (en)k(x) £en+ 1(x + k).
Proof of 1:  By double induction.  Note: to fit the problem into the double induction schema, we rewrite the formula as
en + 1(x) ³x + 1.
Now we argue:.
DI 1, 2.  e0 + 1(x) = x2 + 2 ³ x + 1.
DI 3.  Suppose "x, en + 1(x) ³ x + 1.
a. en + 2(0) = 2  0 + 1.
b. Suppose en + 2(x) ³ x + 1.
Then en + 2(x + 1) = en + 1(en + 2(x)) ³ en + 2(x) + 1 ³ x + 2.
Exercise 0:  Prove the remaining clauses of the proposition.  The strict inequality in 1.2 will be used below, so I mean it.
Proof of 1.2:  peek only if you must.

The Elementary Functions (Kalmar)

The collection of elementary functions is defined by:
E = E3.
It is often repeated that almost all number theoretical functions that arise in practice are elementary.  This isn't surprising when one considers that composed exponentials (2 to the 2 to the 2... to the xth power) are all elementary.

The elementary functions have many alternative characterizations.

Exercise 1:  Show that the elementary functions are closed under bounded simultaneous recursion.  Hint:  first show that the exponential function 2x is in E.  Then use this to show that the Goedel coding and decoding  is elementary by checking all the functions involved in its derivation tree.  The crux of this argument is to show by induction that addition and multiplication are bounded by compositions of exponentiation.   Then use the coding to obtain an elementary reduction to bounded recursion.

Bounding functions in the Grzegorczyk classes.

We will now construct bounds on the functions in the classes En.  The first result says that functions in E0 can't achieve more than to add a fixed amount to a given input.  This makes sense, because compositions of successor and projection can only add a fixed amount to some argument and bounded recursion can't grow faster than that.

There is a weakness in this approach to negative results:  characteristic functions that run way beyond PR in complexity don't grow at all.  For example, d(x) = -sg(f[x, 1](x)).  This is a non-PR function since it differs from each unary PR function in at least one place.  But it doesn't grow at all.  Growth is only a symptom of complexity.

Proposition 2:  Each f in E0 satisfies:

$i £n$k"x, f(x) £xi + k.
Proof:  by induction on depth of E0 derivation trees.
Base case: Induction:
Suppose h = R(g, f), h is bounded by e,  and that g, f, e are in E0.  Then by the induction hypothesis, e satisfies the proposition.  So h does as well (let i and k be the same as for e).
Suppose h = C(f, g1, ..., gk), and that f, g1, ..., gk are in E0.  By the induction hypothesis, for each i < k, Then for each y,
f(g1(y), ..., gk(y)) < gm(y) + c < yj(m) + bm + c = yj(m) + d.
Notice that in the preceding proof, the only interesting case is composition.  That is because only composition is allowed to build growth rates, since primitive recursion is bounded.  The next result says that each function in E1 is everywhere bounded by a linear function of the same arguments, which is also not surprising, since compositions of additions yield linear functions.

Proposition 3:  Each f ÎE1 satisfies:

$ linear h "x,f(x) £h(x).
Proof:  by induction on depth of E1derivation trees.

Exercise 2:  Prove it.  Don't forget to add e0 to the base case!

The next result says that each function in E2 is bounded by a polynomial function.  That's not surprising either since compositions of linear functions and squared functions yield polynomial functions.

Proposition 4:  Each f in E2 satisfies:

 $ polynomial p"x, f(x) £p(x).
Proof: by induction on depth of E2 derivation trees.

Exercise 3:  prove it.

Finally, each of the successive classes En + 3 is bounded by iterates of its generating function en + 1.

Proposition 5:  Each f in En + 3 satisfies:

"x1, ..., xn, $k, f(x1, ..., xn) £ (en + 2)k(max(x1, ..., xn)).
Proof: by induction on depth of En + 3 derivation trees. Recall:
e0(x, y) = x + y;
e1(x) = x2 + 2;
en+2(0) = 2;
en + 2(x + 1) = en + 1(en + 2(x)).
Base case:  Observe that
e2(0) = 2;
e2(x + 1) = e1(e2(x)) = e2(x)2 + 2.
Since en + 1(x) ³en(x), by proposition 1.2, it suffices in the base case to show that all the basic functions are bounded by e2. This we do by induction on x. Induction:  we now deal with functions in En + 3 that are built up by C or R.
Suppose h = R(g, f), h is bounded by e,  and that g, f, e are in En + 3.  Then by the induction hypothesis, e satisfies the proposition.  So h does as well (let i and k be the same as for e).
Suppose h = C(f, g1, ..., gk), and that f, g1, ..., gk are in En + 3.  By the induction hypothesis, for each i £ k, Then for each y,
f(g1(y), ..., gk(y)) < (en + 2)m(max(g(y)) [by second hypothesis].
< (en + 2)m(en + 2)max(j(1), ..., j(k))(max(y)) [by first hypothesis and  proposition 1.2].
< (en + 2)m + max(j(1), ..., j(k)).
Proposition 6:  If f ÎEn  then the iteration f yÎEn + 1.

Proof:  The iteration of addition of a constant is bounded by a linear function, yielding the case for n = 0.  Similarly, the iteration of a linear function is a polynomial function, yielding the n = 1 case. Let f ÎEn + 1.  We will consider the case of binary f, with iteration on x.   When n > 1, we have by proposition 5 above, there is an m such that

f(x, y) £ (en -  1)m(max(x, y)).
Now by induction, we show:
(*) f z(x, y) £ (en - 1)mz(max(x, y)).
Base:
f 0(x, y) = x £ max(x, y) = (en -  1)0(max(x, y)).
Induction:  Now suppose that for all x, y,
f z(x, y) <  (en - 1)mz(max(x, y)).
Then:
f z + 1(x, y) = f z(f(x, y), y) [defn. iteration]
f z + 1(x, y) £f z((en -  1)m(max(x, y)), y) [hypothesis, proposition 1.2]
£ (en -  1)mz(max((en -  1)m(max(x, y)), y)) [induction hypothesis]
£ (en -  1)m(z + 1)(max(x, y)) [by proposition 1.2]
That completes the induction.  Observe, further, that
(**) (en -  1)mz(max(x, y)) £ (en)(max(x, y) + mz) [propositon 1.4].
So by chaining (*) with (**), we obtain
(***) f z(x, y) £ (en)(max(x, y) + mz).
Now the iteration f z is defined by primitive recursion in terms of f.
By (***), this primitive recursion is bounded by enÎEn + 1.
So f z ÎEn + 1.

Hierarchy Theorem

Proposition 7:  En is a subset of  En + 1.
Proof sketch: By proposition 1.3, each generating function for a class is in all the higher classes.  Then all the closure conditions of the lower class are satisfied by the higher class.

Proposition 8:  en is  in En + 1 -En.
Proof sketch:  Recall

e0(x, y) = x + y;
e1(x) = x2 + 2;
en+2(0) = 2;
en + 2(x + 1) = en + 1((en + 2)(x)).
The membership claims are all true by definition of En.  The non-memberships are established by induction on n.
Base cases:
By proposition 2, e0 is not in E0, since there is no constant bound on e0.
By proposition 3, e1 is not in E1, since e1 is not a linear function of x.
By proposition 4, e2 is not in E2, since e2 is not polynomial (its calculation involves arbitrarily high exponents).
Induction:
Suppose that en + 2 is not in En + 2.  Then by proposition 5,
"k $x en + 2(x) > (en + 1)k(x).
Now we show by induction on k that:
(*) "k $xen + 3(x) > (en + 2)k(x).
Base:  For k = 0, we have
en + 3(0) = 2 > 0 = (en + 2)0(0).
Induction:  Now suppose that for some x :
en + 3(x) > (en + 2)k(x).
Then
en + 3(x + 1)  = en + 2(en + 3(x)) >en + 2((en + 2)k'(x)) = (en + 2)k' + 1(x).
Observe that the red inequality is by proposition 1.2.

Proposition 9: ÈiEi = PR.
Proof sketch:  The basic functions and compositon are no problem because each En has them.  But none of the classes has primitive recursion, so we must show that somehow the effect of primitive recursion results from taking the union of the classes.  So why would we think it's true?  Because the successive generating functions provide increasing bounds so that each unbounded recursion becomes bounded by some level.   By proposition 6, the iteration f y of a function f in En is in En + 1.  Then one proves (nontrivial) that all unary primitive recursive functions can be defined by iteration and composition over some simple PR functions (cf. Rose pp. 17-22).  The idea, as usual, is to use an encoding to allow the iteration to simulate unary primitive recursion.  Then one reduces n-ary primitive recursion to unary primitive recursion.

An easier way to prove this proposition is to do it directly by induction on derivation complexity, bounding compositions and primitive recursions over functions in one class by compositions of higher generating functions.  This is more direct, but then one doesn't end up with nice results like proposition 7 along the way because the bounds are loose (e.g., jumping by 3).

Proposition 9:  The Péter function is not PR.
Proof:  The Péter function p outgrows each en.  Thus, by proposition 8, p is not in any class En.  By proposition 9, p is not PR.

Onward and Upward

If you like this kind of thing, the Grzegorczyk hierarchy can be extended by recursion on infinite ordinals to obtain classes corresponding to double recursion, triple recursion, etc.  See Rose for a systematic presentation. We are now going to leave the world of pure recursion for the more elegant theory of the partial recursive functions.

Next Lecture