Recursiveness in $P^1_1$ paths through $\mathcal {O}$
HTML articles powered by AMS MathViewer
- by Harvey Friedman PDF
- Proc. Amer. Math. Soc. 54 (1976), 311-315 Request permission
Abstract:
Kleene’s $\mathcal {O}$ is recursive in some $\Pi _1^1$ path through $\mathcal {O}$. If every hyp set is recursive in a given $\Pi _1^1$ set, then $\mathcal {O}$ is recursive in its triple jump.References
- S. Feferman and C. Spector, Incompleteness along paths in progressions of theories, J. Symbolic Logic 27 (1962), 383–390. MR 172793, DOI 10.2307/2964544
- R. O. Gandy, Proof of Mostowski’s conjecture, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 571–575 (English, with Russian summary). MR 126383
- Joseph Harrison, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc. 131 (1968), 526–543. MR 244049, DOI 10.1090/S0002-9947-1968-0244049-7 C. Jockusch, Jr., Recursiveness of initial segments of Kleene’s $0$ (to appear).
- G. Kreisel, Which number theoretic problems can be solved in recursive progressions on $\Pi ^{1}_{1}$-paths through $O$?, J. Symbolic Logic 37 (1972), 311–334. MR 369037, DOI 10.2307/2272975
- Rohit Parikh, A note on paths through $0$, Proc. Amer. Math. Soc. 39 (1973), 178–180. MR 311468, DOI 10.1090/S0002-9939-1973-0311468-7
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 54 (1976), 311-315
- DOI: https://doi.org/10.1090/S0002-9939-1976-0398812-2
- MathSciNet review: 0398812