Abstract
In this paper we show that the degrees of interpretability of finitely axiomatized extensions-in-the-same-language of a finitely axiomatized sequential theory—like Elementary Arithmetic EA, IΣ1, or the Gödel–Bernays theory of sets and classes GB—have suprema. This partially answers a question posed by Švejdar in his paper (Commentationes Mathematicae Universitatis Carolinae 19:789–813, 1978). The partial solution of Švejdar’s problem follows from a stronger fact: the convexity of the degree structure of finitely axiomatized extensions-in-the-same-language of a finitely axiomatized sequential theory in the degree structure of the degrees of all finitely axiomatized sequential theories. In the paper we also study a related question: the comparison of structures for interpretability and derivability. In how far can derivability mimic interpretability? We provide two positive results and one negative result.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Buss, S.: Cut elimination in situ (2011). http://math.ucsd.edu/~sbuss/
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/Tarski1,052407.pdf (2007)
Gerhardy, P.: Refined complexity analysis of cut elimination. In: Baaz, M., Makovsky, J. (eds.) Proceedings of the 17th International Workshop CSL 2003, LNCS, vol. 2803, pp. 212–225. Springer, Berlin (2003)
Gerhardy P.: The role of quantifier alternations in cut elimination. Notre Dame J. Formal Logic 46(2), 165–171 (2005)
Hájek P., Pudlák P.: Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic. Springer, Berlin (1993)
Hodges W.: Model Theory. Encyclopedia of Mathematics and its Applications, vol. 42.. Cambridge University Press, Cambridge (1993)
Krajíček J.: A note on proofs of falsehood. Archiv für Mathematische Logik und Grundlagenforschung 26(1), 169–176 (1987)
Lindström P., Shavrukov V.Y.: The \({\forall\exists}\) theory of Peano Σ1 sentences. J. Math. Logic 8(2), 251–280 (2008)
Mycielski, J., Pudlák, P., Stern, A. (1990) A lattice of chapters of mathematics (interpretations between theorems). Memoirs of the American Mathematical Society, vol. 426. AMS, Providence, RI
Pudlák P.: Some prime elements in the lattice of interpretability types. Trans. Am. Math. Soc. 280, 255–275 (1983)
Pudlák P.: Cuts, consistency statements and interpretations. J. Symb. Logic 50(2), 423–441 (1985)
Shavrukov V.: Effectively inseparable boolean algebras in lattices of sentences. Arch. Math. Logic 49(1), 69–89 (2010)
Smoryński C.: Nonstandard models and related developments. In: Harrington, L., Morley, M., Scedrov, A., Simpson, S. (eds) Harvey Friedman’s Research on the Foundations of Mathematics, pp. 179–229. North Holland, Amsterdam (1985)
Stern A.: Sequential theories and infinite distributivity in the lattice of chapters. J. Symb. Logic 54, 190–206 (1989)
Švejdar V.: Degrees of interpretability. Commentationes Mathematicae Universitatis Carolinae 19, 789–813 (1978)
Visser A.: An inside view of EXP. J. Symb. Logic 57(1), 131–165 (1992)
Visser A.: The unprovability of small inconsistency. Arch. Math. Logic 32(4), 275–298 (1993)
Visser A.: Faith & falsity: a study of faithful interpretations and false \({{\Sigma}^0_1}\) -sentences. Ann. Pure Appl. Logic 131(1–3), 103–131 (2005)
Visser A.: Pairs, sets and sequences in first order theories. Arch. Math. Logic 47(4), 299–326 (2008)
Visser A.: Cardinal arithmetic in the style of baron von Münchhausen. Rev. Symb. Logic 2(3), 570–589 (2009). doi:10.1017/S1755020309090261
Visser, A.: What is the right notion of sequentiality? Logic Group preprint series 288. Department of Philosophy, Utrecht University, Janskerkhof 13A, 3512 BL Utrecht (2010). http://www.phil.uu.nl/preprints/lgps/
Visser, A.: Can we make the second incompleteness theorem coordinate free. J. Logic Comput. 21(4), 543–560 (2011). First published online 12 Aug 2009. doi:10.1093/logcom/exp048
Visser, A.: The arithmetics of a theory. Logic Group preprint series 293. Department of Philosophy, Utrecht University, Janskerkhof 13A, 3512 BL Utrecht (2012). http://www.phil.uu.nl/preprints/lgps/
Wilkie, A.: On sentences interpretable in systems of arithmetic. In: Logic Colloquium ’84, Studies in Logic and the Foundations of Mathematics, vol. 120, pp. 329–342. Elsevier (1986). doi:10.1016/S0049-237X(08)70469-5. http://www.sciencedirect.com/science/article/B8GY3-4V40WBV-P/2/d1b5abfef30d1817f5cde479d7e8d313
Wilkie A., Paris J.: On the scheme of induction for bounded arithmetic formulas. Ann. Pure Appl. Logic 35, 261–302 (1987)
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Dirk van Dalen on the occasion of his 80th birthday.
Rights and permissions
About this article
Cite this article
Visser, A. Interpretability degrees of finitely axiomatized sequential theories. Arch. Math. Logic 53, 23–42 (2014). https://doi.org/10.1007/s00153-013-0353-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-013-0353-8