$\Sigma _ n$ definable sets without $\Sigma _ n$ induction
HTML articles powered by AMS MathViewer
- by C. T. Chong and K. J. Mourad PDF
- Trans. Amer. Math. Soc. 334 (1992), 349-363 Request permission
Abstract:
We prove that the Friedberg-Muchnik Theorem holds in all models of ${\Sigma _1}$ collection under the base theory ${P^- } + I{\Sigma _0}$. Generalizations to higher dimensional analogs are discussed. We also study the splitting of r.e. sets in these weak models of arithmetic.References
- Michael Mytilinaios, Finite injury and $\Sigma _1$-induction, J. Symbolic Logic 54 (1989), no. 1, 38–49. MR 987320, DOI 10.2307/2275013
- C. T. Chong and K. J. Mourad, The degree of a $\Sigma _n$ cut, Ann. Pure Appl. Logic 48 (1990), no. 3, 227–235. MR 1073220, DOI 10.1016/0168-0072(90)90021-S —, Positive Solutions to Post’s problem, Recursion Theory Week, Lecture Notes in Math., vol. 1432, Springer-Verlag, 1990. —, Post’s problem and singularity (in preparation). —, ${\Sigma _n}$ cuts in models without ${\Sigma _n}$ induction (in preparation).
- Sy D. Friedman, Negative solutions to Post’s problem. II, Ann. of Math. (2) 113 (1981), no. 1, 25–43. MR 604041, DOI 10.2307/1971132
- Sy D. Friedman, $\beta$-recursion theory, Trans. Amer. Math. Soc. 255 (1979), 173–200. MR 542876, DOI 10.1090/S0002-9947-1979-0542876-7 M. J. Groszek and T. A. Slaman, Foundations of the priority method I: Finite and infinite injury (to appear). —, On Turing reducibility (to appear). K. J. Mourad, The Sacks Splitting Theorem and ${\Sigma _1}$ induction (to appear).
- Michael Mytilinaios, Finite injury and $\Sigma _1$-induction, J. Symbolic Logic 54 (1989), no. 1, 38–49. MR 987320, DOI 10.2307/2275013
- Michael E. Mytilinaios and Theodore A. Slaman, $\Sigma _2$-collection and the infinite injury priority method, J. Symbolic Logic 53 (1988), no. 1, 212–221. MR 929386, DOI 10.2307/2274439 J. B. Paris and L. A. Kirby, ${\Sigma _n}$ collection schemas in models of arithmetic, Logic Colloquium ’77, North-Holland, 1978.
- 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
- Theodore A. Slaman and W. Hugh Woodin, $\Sigma _1$-collection and the finite injury priority method, Mathematical logic and applications (Kyoto, 1987) Lecture Notes in Math., vol. 1388, Springer, Berlin, 1989, pp. 178–188. MR 1015729, DOI 10.1007/BFb0083670
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 334 (1992), 349-363
- MSC: Primary 03D25; Secondary 03C62, 03F30
- DOI: https://doi.org/10.1090/S0002-9947-1992-1117216-1
- MathSciNet review: 1117216