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)



A note on paths through 0

Author: Rohit Parikh
Journal: Proc. Amer. Math. Soc. 39 (1973), 178-180
MSC: Primary 02F35
MathSciNet review: 0311468
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that a hyperarithmetic set can be truth table reduced to a $ \Pi _1^1$-path through $ O$ iff it is truth table reducible to some r.e. set.

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] 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 0369037 (51:5273)
  • [3] G. Kreisel. J. Shoenfield and H. Wang, Number theoretic concepts and recursive well-orderings, Arch. Math. Logik Grundlagenforsch 5 (1960), 42-64. MR 22 #6709. MR 0115911 (22:6709)
  • [4] H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 37 #61. MR 0224462 (37:61)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02F35

Retrieve articles in all journals with MSC: 02F35

Additional Information

Keywords: Path through $ O$, truth table reducible, Turing degree, hyperarithmetic
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society