A note on paths through 0

A note on paths through $0$
HTML articles powered by AMS MathViewer

by Rohit Parikh

Proc. Amer. Math. Soc. 39 (1973), 178-180

DOI: https://doi.org/10.1090/S0002-9939-1973-0311468-7

PDF | Request permission

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

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
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
G. Kreisel, J. Shoenfield, and Hao Wang, Number theoretic concepts and recursive well-orderings, Arch. Math. Logik Grundlag. 5 (1960), 42–64. MR 115911, DOI 10.1007/BF01977642
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462