ABSTRACT

The idea is that by classifying the well-ordering, we might be able to get an orderly structure of all general recursive functions. It is easy to show that if < is general recursive, then all functions thus definable are general recursive. In fact, it is familiar that if we start from a given ordinal and proceed to smaller and smaller ordinals, we must come to a stop in a finite number of steps. Conversely, it is also known that any general recursive function can be so defined even if we restrict < to be primitive recursive ones or to be35 of order type (o9 and so on. The problem now is to classify well-order­ ings by some appropriate standard. And the known results just mentioned show that ‘extensional’ properties such as order type or primitive recursiveness o f the orderings are not sufficient in them­ selves to give an informative classification. We may have to consider how they are proven to be well-orderings. We seem to be led back to the question of classifying proofs, only this time the proofs are con­ cerned with establishing that certain given recursive relations are well-orderings. This may be a gain, but the prospect of finding an informative orderly structure over all general recursive functions seems remote.