## The $\alpha$-union theorem and generalized primitive recursion

HTML articles powered by AMS MathViewer

- by Barry E. Jacobs PDF
- Trans. Amer. Math. Soc.
**237**(1978), 63-81 Request permission

## Abstract:

A generalization to $\alpha$-recursion theory of the McCreight-Meyer Union Theorem is proved. Theorem.*Let*$\Phi$

*be an*$\alpha$-

*computational complexity measure and*$\{ {f_\varepsilon }|\varepsilon < \alpha \}$ an $\alpha$-

*r.e. strictly increasing sequence of*$\alpha$-

*recursive functions*.

*Then there exists an*$\alpha$-

*recursive function k such that*$C_k^\Phi = { \cup _{\varepsilon < \alpha }}C_{{f_\varepsilon }}^\Phi$. The proof entails a no-injury cancellation atop a finite-injury priority construction and necessitates a blocking strategy to insure proper convergence. Two infinite analogues to ($\omega$-) primitive recursive functions are studied. Although these generalizations coincide at $\omega$, they diverge on all admissible $\alpha > \omega$. Several well-known complexity properties of primitive recursive functions hold for one class but fail for the other. It is seen that the Jensen-Karp ordinally primitive recursive functions restricted to admissible $\alpha > \omega$ cannot possess natural analogues to Grzegorczyk’s hierarchy.

## References

- Manuel Blum,
*A machine-independent theory of the complexity of recursive functions*, J. Assoc. Comput. Mach.**14**(1967), 322–336. MR**235912**, DOI 10.1145/321386.321395 - Robert L. Constable,
*The operator gap*, J. Assoc. Comput. Mach.**19**(1972), 175–183. MR**314608**, DOI 10.1145/321679.321692 - Martin Davis,
*Computability and unsolvability*, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR**0124208** - Kurt Gödel,
*The Consistency of the Continuum Hypothesis*, Annals of Mathematics Studies, No. 3, Princeton University Press, Princeton, N. J., 1940. MR**0002514** - Andrzej Grzegorczyk,
*Some classes of recursive functions*, Rozprawy Mat.**4**(1953), 46. MR**60426**
Leo Harrington, - Barry E. Jacobs,
*On generalized computational complexity*, J. Symbolic Logic**42**(1977), no. 1, 47–58. MR**505383**, DOI 10.2307/2272317 - Ronald B. Jensen and Carol Karp,
*Primitive recursive set functions*, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 143–176. MR**0281602**
S. C. Kleene, - G. Kreisel,
*Set theoretic problems suggested by the notion of potential totality.*, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959) Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw, 1961, pp. 103–140. MR**0146073** - G. Kreisel and Gerald E. Sacks,
*Metarecursive sets*, J. Symbolic Logic**30**(1965), 318–338. MR**213233**, DOI 10.2307/2269621
S. Kripke, - Manuel Lerman,
*Least upper bounds for minimal pairs of $\alpha$-r.e. $\alpha$-degrees*, J. Symbolic Logic**39**(1974), 49–56. MR**357091**, DOI 10.2307/2272342 - Manuel Lerman and Gerald E. Sacks,
*Some minimal pairs of $\alpha$-recursively enumerable degrees*, Ann. Math. Logic**4**(1972), 415–442. MR**439605**, DOI 10.1016/0003-4843(72)90007-1 - M. Machover,
*The theory of transfinite recursion*, Bull. Amer. Math. Soc.**67**(1961), 575–578. MR**142448**, DOI 10.1090/S0002-9904-1961-10696-4
E. McCreight and A. Meyer, - G. E. Sacks and S. G. Simpson,
*The $\alpha$-finite injury method*, Ann. Math. Logic**4**(1972), 343–367. MR**369041**, DOI 10.1016/0003-4843(72)90004-6 - Richard A. Shore,
*$\sum _{n}$ sets which are $\Delta _{n}$-incomparable (uniformly)*, J. Symbolic Logic**39**(1974), 295–304. MR**419197**, DOI 10.2307/2272642 - Richard A. Shore,
*Splitting an $\alpha$-recursively enumerable set*, Trans. Amer. Math. Soc.**204**(1975), 65–77. MR**379154**, DOI 10.1090/S0002-9947-1975-0379154-1
—, - Gaisi Takeuti,
*Construction of the set theory from the theory of ordinal numbers*, J. Math. Soc. Japan**6**(1954), 196–220. MR**67827**, DOI 10.2969/jmsj/00620196 - Gaisi Takeuti,
*On the theory of ordinal numbers*, J. Math. Soc. Japan**9**(1957), 93–113. MR**86751**, DOI 10.2969/jmsj/00910093 - Tosiyuki Tugué,
*On the partial recursive functions of ordinal numbers*, J. Math. Soc. Japan**16**(1964), 1–31. MR**167404**, DOI 10.2969/jmsj/01610001 - Paul Young,
*Easy constructions in complexity theory: Gap and speed-up theorems*, Proc. Amer. Math. Soc.**37**(1973), 555–563. MR**312768**, DOI 10.1090/S0002-9939-1973-0312768-7

*Some contributions to the theory of recursion on higher types*, Ph.D. Thesis, Massachusetts Institute of Technology, 1972. B. E. Jacobs, $\alpha$-

*computational complexity*, Ph.D. Thesis; Tech. Report IMM-408, Courant Inst. Math. Sci., New York Univ., New York, 1975.

*Introduction to metamathematics*, North-Holland, Amsterdam, 1971.

*Transfinite recursion on admissible ordinals*. I, II (abstracts), J. Symbolic Logic

**29**(1964), 161-162. —,

*The theory of transfinite recursions*, Class Notes by A. Thomas Tymoczko (unpublished). A. Leggett and R. Shore,

*Types of simple*$\alpha$-

*recursively enumerable sets*(to appear).

*Classes of computable functions defined by bounds on computation*, Preliminary report, Proc. ACM Sympos. on Theory of Computing, 1969, pp. 79-88. R. Platek,

*Foundations of recursion theory*, Ph.D. Thesis, Stanford Univ., 1966.

*The recursively enumerable*$\alpha$-

*degrees are dense*, Ann. Math. Logic (to appear). —, $\alpha$-

*recursion theory*(to appear).

## Additional Information

- © Copyright 1978 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**237**(1978), 63-81 - MSC: Primary 03D60; Secondary 68C25
- DOI: https://doi.org/10.1090/S0002-9947-1978-0479362-8
- MathSciNet review: 479362