Weak theories of concatenation and arithmetic. (English) Zbl 1251.03075

Summary: We define a new theory of concatenation WTC which is much weaker than Grzegorczyk’s well-known theory TC. We prove that WTC is mutually interpretable with the weak theory of arithmetic R. The latter is, in a technical sense, much weaker than Robinson’s arithmetic Q, but still essentially undecidable. Hence, as a corollary, WTC is also essentially undecidable.


03F25 Relative consistency and interpretations
03F30 First-order arithmetic and fragments
03B25 Decidability of theories and sets of sentences
Full Text: DOI Euclid


[1] Čačić, V., P. Pudlák, G. Restall, A. Urquhart, and A. Visser, ”Decorated linear order types and the theory of concatenation”, pp. 1-13 in Logic Colloquium 2007 , edited by F. Delon, U. Kohlenbach, P. Maddy, and F. Stephan, vol. 35 of Lecture Notes in Logic , Association for Symbolic Logic, La Jolla, 2010. · Zbl 1244.03162
[2] Friedman, H., ”Interpretation, according to Tarski”, Lecture note of Nineteenth Annual Tarski Lectures at the University of California at Berkeley, http://www.math.ohio-state.edu/  friedman/pdf/Tarski1,052407.pdf. URL:
[3] Ganea, M., ”Arithmetic on semigroups”, The Journal of Symbolic Logic , vol. 74 (2009), pp. 265-78. · Zbl 1160.03038
[4] Grzegorczyk, A., ”Undecidability without arithmetization”, Studia Logica , vol. 79 (2005), pp. 163-230. · Zbl 1080.03004
[5] Grzegorczyk, A., and K. Zdanowski, ”Undecidability and concatenation”, pp. 72-91 in Andrzej Mostowski and Foundational Studies , edited by A. Ehrenfeucht, V. W. Marek, and M. Srebrny, IOS, Amsterdam, 2008. · Zbl 1150.03014
[6] Hájek, P., and P. Pudlák, Metamathematics of First-Order Arithmetic , Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1993. · Zbl 0781.03047
[7] Jones, J. P., and J. C. Shepherdson, ”Variants of Robinson’s essentially undecidable theory \({\mathrm R}\)”, Archiv für mathematische Logik und Grundlagenforschung , vol. 23 (1983), pp. 61-64. · Zbl 0511.03015
[8] Lindström, P., Aspects of Incompleteness , vol. 10 of Lecture Notes in Logic , Springer-Verlag, Berlin, 1997. · Zbl 0882.03054
[9] Nelson, E., Predicative Arithmetic , vol. 32 of Mathematical Notes , Princeton University Press, Princeton, 1986. · Zbl 0617.03002
[10] Quine, W. V., ”Concatenation as a basis for arithmetic”, The Journal of Symbolic Logic , vol. 11 (1946), pp. 105-14. · Zbl 0063.06362
[11] Solovay, R. M., ”Interpretability in set theories”, (1976). unpublished letter to P. H\(\Acute{}\)jek, www.cs.cas.cz/hajek/RSolovayZFGB.pdf.
[12] Sterken, R., Concatenation as a basis for \(\QQ\) and the intuitionistic variant of Nelson’s classic result , Ph.D. thesis, Universiteit van Amsterdam, 2008.
[13] Švejdar, V., ”Relatives of Robinson Arithmetic”, pp. 253-63 in The Logica Yearbook 2008: Proceedings of the Logica 08 International Conference , 2009. · Zbl 1275.03155
[14] Švejdar, V., ”Degrees of interpretability”, Commentationes Mathematicae Universitatis Carolinae , vol. 19 (1978), pp. 789-813. · Zbl 0407.03020
[15] Švejdar, V., ”An interpretation of Robinson arithmetic in its Grzegorczyk’s weaker variant”, Fundamenta Informaticae , vol. 81 (2007), pp. 347-54. · Zbl 1135.03023
[16] Švejdar, V., ”On interpretability in the theory of concatenation”, Notre Dame Journal of Formal Logic , vol. 50 (2009), pp. 87-95. · Zbl 1190.03051
[17] Tarski, A., A. Mostowski, and R. M. Robinson, Undecidable Theories , Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, 1953. · Zbl 0053.00401
[18] Tarski, A., ”The concept of truth in formalized languages. (Der Wahrheitsbegriff in den formalisierten Sprachen)”, Studia Philosophica , vol. 1 (1935), pp. 261-405. · Zbl 0013.28903
[19] Vaught, R. L., ”On a theorem of Cobham concerning undecidable theories”, pp. 14-25 in Logic, Methodology and Philosophy of Science (Proceedings 1960 International Congress) , edited by E. Nagel, P. Suppes, and A. Tarski, Stanford University Press, Stanford, 1962. · Zbl 0178.32303
[20] Visser, A., ”An overview of interpretability logic”, pp. 307-59 in Advances in Modal Logic, Vol. 1 (AiML ’96, Berlin), edited by M. Kracht, M. de Rijke, H. Wansing, and M. Zakharyaschev, vol. 87 of CSLI Lecture Notes , CSLI Publications, Stanford, 1998. · Zbl 0915.03020
[21] Visser, A., ”Growing commas. A study of sequentiality and concatenation”, Notre Dame Journal of Formal Logic , vol. 50 (2009), pp. 61-85. · Zbl 1190.03052
[22] Visser, A., ”Why the theory \(\mathsf{R}\) is special”, Logic Group Preprint Series 267, Department of Philosophy, Utrecht University, 2009.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.