Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Recursiveness in $ P^1_1$ paths through $ \mathcal{O}$


Author: Harvey Friedman
Journal: Proc. Amer. Math. Soc. 54 (1976), 311-315
DOI: https://doi.org/10.1090/S0002-9939-1976-0398812-2
MathSciNet review: 0398812
Full-text PDF

Abstract | References | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] S. Feferman and C. Spector, Incompleteness along paths in progressions of theories, J. Symbolic Logic 27 (1962), 383-390. MR 30 #3012. MR 0172793 (30:3012)
  • [2] R. O. Gandy, Proof of Mostowski's conjecture, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 571-575. MR 23 #A3679. MR 0126383 (23:A3679)
  • [3] J. Harrison, Recursive pseudo-well-orderings, Trans. Amer. Math. Soc. 131 (1968), 526-543. MR 39 #5366. MR 0244049 (39:5366)
  • [4] C. Jockusch, Jr., Recursiveness of initial segments of Kleene's 0 (to appear).
  • [5] G. Kreisel, Which number theoretic problems can be solved in recursive progressions on $ \Pi _1^1$ paths through 0?, J. Symbolic Logic 37 (1972), 311-334. MR 0369037 (51:5273)
  • [6] R. Parikh, A note on paths through 0, Proc. Amer. Math. Soc. 39 (1973), 178-180. MR 47 #30. MR 0311468 (47:30)
  • [7] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1976-0398812-2
Keywords: Kleene's $ \mathcal{O}$, $ \Pi _1^1$ path through $ \mathcal{O}$, hyperarithmetic, recursive
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society