I survey the syntactic technique of tiering which can be used to restrict the power of a recursion scheme. I show how various results can be obtained entirely proof theoretically without the use of a model of computation.

Zaionc, M., λ-Definability on free algebras, Annals of Pure and Applied Logic 51 279-300. A λ-language over a simple type structure is considered. There is a natural isomorphism which identifies free algebras with nonempty second-order types. If A is a free algebra determined by the signature SA = [α1,...,αn], then by a type τA we mean τ1,...,τn→0 where τi=0αi→0. It can be seen that closed terms of the type τA reflex constructions in the algebra A. Therefore any term of the (...) type n→τA defines some n-ary mapping in algebra A. The problem is to characterize λ-definable mappings in any free algebra. It is proved that the set of λ-definable operations is the minimal set that contains constant functions and projections and is closed under composition and limited recursion. This result is a generalization of the result of Schwichtenberg and Statman which characterize the λ-definable functions over the natural number type →, i.e algebra [1, 0], as well as of the result of Zaionc for λ-definable word operations over type n→, i.e algebra [1,...,1,0], and of the results about λ-definable tree operations , i.e in algebra [2, 0]. Some of the examples in Section 5 are based on a publication of Zaionc. (shrink)

We show that the number-theoretic functions definable in the atomic polymorphic system are exactly the extended polynomials. Two proofs of the above result are presented: one, reducing the functions’ definability problem in ${\mathbf{F}}_{\mathbf{at}}$ to definability in the simply typed lambda calculus and the other, directly adapting Helmut Schwichtenberg’s strategy for definability in $\lambda ^{\rightarrow }$ to the atomic polymorphic setting. The uniformity granted in the polymorphic system, when compared with the simply typed lambda calculus, is emphasized.

We define ordinal representations in the simply typed lambda calculus, and consider the ordinal functions representable with respect to these notations. The results of this paper have the same flavor as those of Schwichtenberg and Statman on numeric functions representable in the simply typed lambda calculus. We define four families of ordinal notations; in order of increasing generality of the type of notation, the representable functions consist of the closure under composition of successor and α ωα, addition and α ωα, (...) addition and multiplication, and addition, multiplication, and a “weak” discriminator. (shrink)