Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-21T17:50:19.243Z Has data issue: false hasContentIssue false
  • English
  • Français

Vaught's Theorem on Axiomatizability by a Scheme

Published online by Cambridge University Press:  15 January 2014

Albert Visser
Albert Visser*
Affiliation:
Department of Philosophy, Utrecht University, Janskerkhof 13A 3512BL Utrecht, The Netherlands, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In his 1967 paper Vaught used an ingenious argument to show that every recursively enumerable first order theory that directly interprets the weak system VS of set theory is axiomatizable by a scheme. In this paper we establish a strengthening of Vaught's theorem by weakening the hypothesis of direct interpretability of VS to direct interpretability of the finitely axiomatized fragment VS2 of VS. This improvement significantly increases the scope of the original result, since VS is essentially undecidable, but VS2 has decidable extensions. We also explore the ramifications of our work on finite axiomatizability of schemes in the presence of suitable comprehension principles.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 18 , Issue 3 , September 2012 , pp. 382 - 402
Copyright
Copyright © Association for Symbolic Logic 2012

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.)

References

REFERENCES

[1] Cégielski, P. and Richard, D., Decidability of the natural integers equipped with the Cantor pairing function and successor, Theoretical Computer Science, vol. 257 (2001), no. 1–2, pp. 51–77.Google Scholar
[2] Corcoran, J., Schemata: the concept of schema in the history of logic, this Bulletin, vol. 12 (2006), no. 2, pp. 219–240.Google Scholar
[3] Craig, W., On axiomatizability within a system, The Journal of Symbolic Logic, vol. 18 (1953), pp. 30–32.Google Scholar
[4] Craig, W. and Vaught, R. L., Finite axiomatizability using additional predicates, The Journal of Symbolic Logic, vol. 23 (1958), pp. 289–308.Google Scholar
[5] Ferrante, J. and Rackoff, C. W., The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979.Google Scholar
[6] Friedman, H., Interpretations according to Tarski, This is one of the 2007 Tarski Lectures at Berkeley. The lecture is available at http://www.math.osu.edu/~friedman.8/pdf/Tarskii,052407.pdf, 2007.Google Scholar
[7] Hájek, P. and Pudlák, P., Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer, Berlin, 1991.Google Scholar
[8] Kaye, R., Models of peano arithmetic, Oxford Logic Guides, Oxford University Press, 1991.Google Scholar
[9] Lindström, P., Aspects of Incompleteness, Lecture Notes in Logic, vol. 10, Association for Symbolic Logic / A K Peters, Natick, Massachusetts, 2002.Google Scholar
[10] Mycielski, J., Pudlák, P., and Stern, A. S., A lattice of chapters of mathematics (Interpretations between theorems), Memoirs of the American Mathematical Society, vol. 426, AMS, Providence, RI, 1990.Google Scholar
[11] Plisko, V.E., The nonarithmeticity of the class of realizable formulas, Math. of USSR Izv., vol. 11 (1977), pp. 453–471.Google Scholar
[12] Plisko, V.E., Arithmetic complexity of the predicate logics of certain complete arithmetic theories, Annals of Pure and Applied Logic, vol. 113 (2002), pp. 243–259.Google Scholar
[13] Švejdar, V., An interpretation of Robinsons Arithmetic in its Grzegorczyk's weaker variant, Fundamenta Informaticae, vol. 81 (2007), pp. 347–354.Google Scholar
[14] Tarski, A., Mostowski, A., and Robinson, R. M., Undecidable theories, North-Holland, Amsterdam, 1953.Google Scholar
[15] Tenney, R. L., Decidable pairing functions, Thesis, Cornell University, 1974.Google Scholar
[16] Vaught, R. A., Axiomatizability by a schema, The Journal of Symbolic Logic, vol. 32 (1967), no. 4, pp. 473–479.Google Scholar
[17] Visser, A., Categories of Theories and Interpretations, Logic in Tehran. Proceedings of the workshop and conference on Logic, Algebra and Arithmetic, held October 18–22, 2003 (Enayat, Ali, Kalantari, Iraj, and Moniri, Mojtaba, editors), Lecture Notes in Logic, vol. 26, Association for Symbolic Logic, A. K. Peters, Wellesley, Mass., 2006, pp. 284–341.Google Scholar
[18] Visser, A., Pairs, sets and sequences in first order theories, Archive for Mathematical Logic, vol. 47 (2008), no. 4, pp. 299–326.Google Scholar
[19] Visser, A., Fhe predicative Frege hierarchy, Annals of Pure and Applied Logic, vol. 160 (2009), no. 2, pp. 129–153.Google Scholar
[20] Visser, A., Can we make the Second Incompleteness Theorem coordinate free, Journal of Logic and Computation, vol. 21 (2011), no. 4, pp. 543–560.Google Scholar
[21] Wilkie, A. and Paris, J. B., On the scheme of of induction for bounded arithmetic formulas, Annals of Pure and Applied Logic, vol. 35 (1987), pp. 261–302.Google Scholar