Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

$ \Sigma\sb n$ definable sets without $ \Sigma\sb n$ 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 $ {\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 [Enhancements On Off] (What's this?)

  • [1] C. T. Chong, Recursively enumerable sets in models of $ B{\Sigma _2}$, 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 $ {\Sigma _n}$ 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] -, $ {\Sigma _n}$ cuts in models without $ {\Sigma _n}$ 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] -, $ \beta $ 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 $ {\Sigma _1}$ induction (to appear).
  • [11] M. Mytilinaios, Finite injury and $ {\Sigma _1}$ induction, J. Symbolic Logic 54 (1989), 38-49. MR 987320 (90i:03067a)
  • [12] M. Mytilinaios and T. A. Slaman, $ {\Sigma _2}$ 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, $ {\Sigma _n}$ collection schemas in models of arithmetic, Logic Colloquium '77, North-Holland, 1978.
  • [14] G. E. Sacks and S. G. Simpson, The $ \alpha $-finite injury method, Ann. Math. Logic 4 (1972). MR 0369041 (51:5277)
  • [15] T. A. Slaman and W. H. Woodin, $ {\Sigma _1}$ 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)

Similar Articles

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

American Mathematical Society