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

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

MathSciNet review:
1117216

Full-text PDF

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*, Mathematical Logic and Its Applications, Lecture Notes in Math., vol. 1388, Springer-Verlag, 1989. MR**1015723 (90i:03067d)****[2]**C. T. Chong and K. J. Mourad,*The degree of a**cut*, Ann. Pure Appl. Logic**48**(1990), 227-235. MR**1073220 (92f:03067)****[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]**S. D. Friedman,*Negative solutions to Post's problem*, Ann. of Math. (2)**113**(1981), 25-43. MR**604041 (82k:03075)****[7]**-,*recursion theory*, Trans. Amer. Math. Soc.**235**(1979), 173-200. MR**542876 (81g:03055)****[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]**M. Mytilinaios,*Finite injury and**induction*, J. Symbolic Logic**54**(1989), 38-49. MR**987320 (90i:03067a)****[12]**M. Mytilinaios and T. A. Slaman,*collection and the infinite injury priority method*, J. Symbolic Logic**53**(1988), 212-221. MR**929386 (88m:03066)****[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). MR**0369041 (51:5277)****[15]**T. A. Slaman and W. H. Woodin,*collection and the finite injury priority method*, Mathematical Logic and Its Applications, Lecture Notes in Math., vol. 1388, Springer-Verlag, 1989. MR**1015729 (91j:03075)**

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