definable sets without induction

Authors:
C. T. Chong and K. J. Mourad

Journal:
Trans. Amer. Math. Soc. **334** (1992), 349-363

MSC:
Primary 03D25; Secondary 03C62, 03F30

MathSciNet review:
1117216

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that the Friedberg-Muchnik Theorem holds in all models of collection under the base theory . Generalizations to higher dimensional analogs are discussed. We also study the splitting of r.e. sets in these weak models of arithmetic.

**[1]**C. T. Chong,*Recursively enumerable sets in models of Σ₂ collection*, Mathematical logic and applications (Kyoto, 1987) Lecture Notes in Math., vol. 1388, Springer, Berlin, 1989, pp. 1–15. MR**1015723**, 10.1007/BFb0083664**[2]**C. T. Chong and K. J. Mourad,*The degree of a Σ_{𝑛} cut*, Ann. Pure Appl. Logic**48**(1990), no. 3, 227–235. MR**1073220**, 10.1016/0168-0072(90)90021-S**[3]**-,*Positive Solutions to Post's problem*, Recursion Theory Week, Lecture Notes in Math., vol. 1432, Springer-Verlag, 1990.**[4]**-,*Post's problem and singularity*(in preparation).**[5]**-,*cuts in models without**induction*(in preparation).**[6]**Sy D. Friedman,*Negative solutions to Post’s problem. II*, Ann. of Math. (2)**113**(1981), no. 1, 25–43. MR**604041**, 10.2307/1971132**[7]**Sy D. Friedman,*𝛽-recursion theory*, Trans. Amer. Math. Soc.**255**(1979), 173–200. MR**542876**, 10.1090/S0002-9947-1979-0542876-7**[8]**M. J. Groszek and T. A. Slaman,*Foundations of the priority method*I:*Finite and infinite injury*(to appear).**[9]**-,*On Turing reducibility*(to appear).**[10]**K. J. Mourad,*The Sacks Splitting Theorem and**induction*(to appear).**[11]**Michael Mytilinaios,*Finite injury and Σ₁-induction*, J. Symbolic Logic**54**(1989), no. 1, 38–49. MR**987320**, 10.2307/2275013**[12]**Michael E. Mytilinaios and Theodore A. Slaman,*Σ₂-collection and the infinite injury priority method*, J. Symbolic Logic**53**(1988), no. 1, 212–221. MR**929386**, 10.2307/2274439**[13]**J. B. Paris and L. A. Kirby,*collection schemas in models of arithmetic*, Logic Colloquium '77, North-Holland, 1978.**[14]**G. E. Sacks and S. G. Simpson,*The 𝛼-finite injury method*, Ann. Math. Logic**4**(1972), 343–367. MR**0369041****[15]**Theodore A. Slaman and W. Hugh Woodin,*Σ₁-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**, 10.1007/BFb0083670

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
03D25,
03C62,
03F30

Retrieve articles in all journals with MSC: 03D25, 03C62, 03F30

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1992-1117216-1

Keywords:
Recursively enumerable sets,
Friedberg-Muchnik Theorem,
Sacks Splitting Theorem,
fragments of Peano arithmetic

Article copyright:
© Copyright 1992
American Mathematical Society