North-Holland Publishing Company RECURSMLY TNIVARTANT p-RECURSTON THEORY

'We int¡oduce recursively invariant p-recursion theory as a new approach towards recursion theory on an arbitrary limit ordinal É. We follow Friedman and Sacks and call a subset of BB-recursively enumerable if it is.Xr-definable over Lu. Since Friedman-Sacks'notion of a p-finite set is not invariant under p-recursive permutations of p we turn to a different notion. Under all possible invariant generalizations of finite there is a canonical one which we call i-finite. We consider fu¡ther in the inadmissible case those criteria for the adequacy of generalizations of finite which have earlier been developed by Kreisel, Moschovakis and others. We look at infinitary languages over inadmissible sets Lu and the compactness theorem for these languages, the characterization of the basic notions of p-recursion theory in terms of model theo¡etic invariance, the deflnition of B-recursion theory via an equation calculus and axioms for computation theories. In turns out that in all these approaches the i-finite sets are those subsets of B respectively Lu which behave like finite sets. Invariant B-recursion theory contains classical recursion theory and c-recursion theory as special cases. We start in the second half of this paper the systematic development of invariant B-recursion theory for all lfunit ordinals B. We study in particular i-degrees, which generaliz