Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-12-01T01:09:54.490Z Has data issue: false hasContentIssue false
  • English
  • Français

On the role of Ramsey quantifiers in first order arithmetic1

Published online by Cambridge University Press:  12 March 2014

James H. Schmerl  and
Stephen G. Simpson
James H. Schmerl
Affiliation:
University of Connecticut, Storrs, Connecticut 06268
Stephen G. Simpson
Affiliation:
Pennsylvania State University, University Park, Pennsylvania 16802
Get access Rights & Permissions [Opens in a new window]

Extract

The purpose of this paper is to study a formal system PA(Q2) of first order Peano arithmetic, PA, augmented by a Ramsey quantifier Q2 which binds two free variables. The intended meaning of Q2xx′φ(x, x′) is that there exists an infinite set X of natural numbers such that φ(a, a′) holds for all a, a′ Є X such that a ≠ a′. Such an X is called a witness set for Q2xx′φ(x, x′). Our results would not be affected by the addition of further Ramsey quantifiers Q3, Q4, …, Here of course the intended meaning of Qkx1 … xkφ(x1,…xk) is that there exists an infinite set X such that φ(a1…, ak) holds for all k-element subsets {a1, … ak} of X.

Ramsey quantifiers were first introduced in a general model theoretic setting by Magidor and Malitz [13]. The system PA{Q2), or rather, a system essentially equivalent to it, was first defined and studied by Macintyre [12]. Some of Macintyre's results were obtained independently by Morgenstern [15]. The present paper is essentially self-contained, but all of our results have been directly inspired by those of Macintyre [12].

After some preliminaries in §1, we begin in §2 by giving a new completeness proof for PA(Q2). A by-product of our proof is that for every regular uncountable cardinal k, every consistent extension of PA(Q2) has a k-like model in which all classes are definable. (By a class we mean a subset of the universe of the model, every initial segment of which is finite in the sense of the model.)

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 47 , Issue 2 , June 1982 , pp. 423 - 435
Copyright
Copyright © Association for Symbolic Logic 1982

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

This research was performed in the fall of 1979 while Simpson was a visiting faculty member at the University of Connecticut. Schmerl and Simpson were partially supported by NSF grants MCS 79-05028 and MCS 77-13935, respectively.

References

BIBLIOGRAPHY

[1]Baldwin, J. T. and Kueker, D. W., Ramsey quantifiers and the finite cover property, Pacific Journal of Mathematics, vol. 90 (1980), pp. 11–19.CrossRefGoogle Scholar
[2]Baudisch, A., Decidability of the theory of abelian groups with Ramsey quantifiers, Bulletin de I'Académic Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 25 (1977), pp. 733–739.Google Scholar
[3]Cowles, J. R., The theory of Archimedean real closed fields in logic with Ramsey quantifiers, Fundamenta Mathematicae, vol. 103 (1979), pp. 65–76.CrossRefGoogle Scholar
[4]Enderton, H. B., A mathematical introduction to logic, Academic Press, New York, 1972.Google Scholar
[5]Feferman, S., Formal theories for transfinite iterations of generalized inductive definitions and some subsystems of analysis, Intuitionism and proof theory (Kino, A., Myhill, J., and Vesley, R. E. Editors), North-Holland, Amsterdam, 1970, pp. 303–326.Google Scholar
[6]Feferman, S., Theories of finite type related to mathematical practice, Handbook of mathematical logic (Barwise, J., Editor), North-Holland, Amsterdam, 1977, pp. 913–971.CrossRefGoogle Scholar
[7]Friedman, H., The analysis of mathematical texts and their calibration in terms of intrinsic strength. I-IV, informal notes, SUNY Buffalo, 1975.Google Scholar
[8]Friedman, H., Systems of second order arithmetic with restricted induction (abstracts), this Journal, vol. 41 (1976), pp. 557–559.Google Scholar
[9]Friedman, H., McAloon, K. and Simpson, S. G., A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis, preprint, Penn State University, 1981; Logic Symposion I (G. Metakides, Editor), Patras, Greece, 1980, North-Holland, Amsterdam (to appear).Google Scholar
[10]Jockusch, C. G. Jr., and Simpson, S. G., A degree theoretic definition of the ramified analytical hierarchy, Annals of Mathematical Logic, vol. 10 (1976), pp. 1–32.CrossRefGoogle Scholar
[11]MacDowell, R. and Specker, E., Modelle der Arithmetik, Inftnitistic methods, Proceedings of the Symposium on the Foundations of Mathematics (Warsaw 1959), Pergamon, 1961, pp. 257–263.Google Scholar
[12]Macintyre, A., Ramsey quantifiers in arithmetic, Model theory of algebra and arithmetic (Pacholski, L., Wierzejewski, J. and Wilkie, A. J., Editors), Lecture Notes in Mathematics, vol. 834 Springer-Verlag, Berlin and New York, 1980, pp. 186–210.CrossRefGoogle Scholar
[13]Magidor, M. and Malitz, J. I., Compact extensions of L(Q). Part 1(a), Annals of Mathematical Logic, vol. 11 (1977), pp. 217–261.CrossRefGoogle Scholar
[14]Mills, G., Substructure lattices of models of arithmetic, Annals of Mathematical Logic, vol. 16 (1979), pp. 145–180.CrossRefGoogle Scholar
[15]Morgenstern, C., On generalized quantifiers in arithmetic, this Journal, vol. 47 (1982), pp. 187–190.Google Scholar
[16]Morley, M., Partitions and models, Proceedings of the Summer School in Logic (Leeds 1967), (Löb, M. H., Editor), Lecture Notes in Mathematics, vol. 70, Springer-Verlag, Berlin and New York, 1967, pp. 109–158.CrossRefGoogle Scholar
[17]Paris, J. and Harrington, L., A mathematical incompleteness in Peano arithmetic, Handbook of Mathematical Logic(Barwise, J., Editor), North-Holland, Amsterdam, 1977, pp. 1133–1142.CrossRefGoogle Scholar
[18]Presburger, M., Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Comptes Rendus du 1er Congrès des Mathématiciens des Pays Slaves, Warszawa, 1929, pp. 92–101.Google Scholar
[19]Ramsey, F. P., On a problem of formal logic, Proceedings of the London Mathematical Society, vol. 30 (1929), pp. 264–286.Google Scholar
[20]Schmerl, J. H., Peano models with many generic classes, Pacific Journal of Mathematics, vol. 46 (1973), pp. 523–536; erratum, Pacific Journal of Mathematics, vol. 92 (1981), pp. 195–198.CrossRefGoogle Scholar
[21]Simpson, S. G., Notes on subsystems of analysis, lecture notes, University of California, Berkeley, 1973, 38 pp.Google Scholar
[22]Zucker, J. I., Iterated inductive definitions, trees, and ordinals, Metamathematical investigation of intuitionistic arithmetic and analysis, (Troelstra, A. S., Editor), Lecture Notes in Mathematics, vol. 344, Springer-Verlag, Berlin and New York, 1973, pp. 392–453.CrossRefGoogle Scholar
[23]Aczel, P., Another elementary treatment of Girard's results connecting the slow and fast growing hierarchies of number theoretic functions, handwritten notes, 1980.Google Scholar
[24]Cichon, E. A. ans Wainer, S. S., The slow-growing and the Grzegorczyk hierarchies, preprint, Leeds, 1981; this Journal (to appear).Google Scholar
[25]Girard, J.-Y., Π21-logic, Annals of Mathematical Logic (to appear).Google Scholar
[26]Schmerl, U. R.The composition of functions in the slow-growing hierarchy and a comparison to the fast-growing one, preprint, 1980.Google Scholar
[27]Schütte, K., Proof Theory, Springer-Verlag, Berlin and New York, 1977.CrossRefGoogle Scholar
[28]Takeuti, G.Consistency proofs of subsystems of classical analysis, Annals of Mathematics (2), vol. 86 (1967), pp. 299–348.CrossRefGoogle Scholar