zbMATH — the first resource for mathematics

Primitive recursive notations for infinitary formulas. (English) Zbl 0262.02014
Colloq. Math. 30, 1-5 (1974).
Using methods related to S. C. Kleene’s [ibid. 6, 67–78 (1958; Zbl 0085.24602)] it is shown that the functions used in assigning notations to certain formulas in \(L_{\omega_1\omega_1}\) by A. Kino and G. Takeuti [J. Math. Soc. Japan 15, 176–190 (1963; Zbl 0118.25001)] can be restricted to the primitive recursive functions without significantly altering the collection of formulas which receive notations. It is also shown that Kleene’s result concerning ordinal notations and the result above concerning formula notations can be extended to the case in which the functions utilized all belong to the class \(\mathcal E^4\) of the Grzegorczyk hierarchy.
Reviewer: Kenneth A. Bowen
03C75 Other infinitary logic
03D20 Recursive functions and relations, subrecursive hierarchies
03D55 Hierarchies of computability and definability