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

Horihata, Yoshihiro

Notre Dame J. Formal Logic 53, No. 2, 203-222 (2012).

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.

MSC:

03F25	Relative consistency and interpretations
03F30	First-order arithmetic and fragments
03B25	Decidability of theories and sets of sentences

Keywords:

theory of concatenation; Robinson’s arithmetic; interpretation

References:

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