Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-19T10:03:28.975Z Has data issue: false hasContentIssue false
  • English
  • Français

Arithmetic on semigroups

Published online by Cambridge University Press:  12 March 2014

Mihai Ganea
Mihai Ganea*
Affiliation:
Department of Philosophy, Boston University, Boston, Ma 02215, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Relations between some theories of semigroups (also known as theories of strings or theories of concatenation) and arithmetic are surveyed. In particular Robinson's arithmetic Q is shown to be mutually interpretable with TC, a weak theory of concatenation introduced by Grzegorczyk. Furthermore, TC is shown to be interpretable in the theory F studied by Tarski and Szmielewa, thus confirming their claim that F is essentially undecidable.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 1 , March 2009 , pp. 265 - 278
Copyright
Copyright © Association for Symbolic Logic 2009

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]Bennett, J., On spectra, Ph.D. thesis, Department of Mathematics, Princeton University, 1962.Google Scholar
[2]Čačić, V., Pudlák, P., Restall, G., Urquhart, A., and Visser, A., Decorated linear order types and the theory of concatenation, LGPS preprint 258 (10 4, 2007), available online at http://www.phil.uu.nl/preprints/preprints/PREPRINTS/preprint258.pdf.Google Scholar
[3]Corcoran, J., Frank, W., and Maloney, M., String theory, this Journal, vol. 39 (1974), no. 4, pp. 625–636.Google Scholar
[4]De Bouvère, K., Logical synonymity, Indagationes mathematicae, vol. 27 (1965), pp. 622–629.CrossRefGoogle Scholar
[5]Ganea, M., Arithmetic without numbers, Ph.D. thesis, Department of Philosophy, University of Illinois at Chicago, 2005.Google Scholar
[6]Grzegorczyk, A., Undecidability without arithmetization, Studio Logica, vol. 79 (2005), no. 1, pp. 163–230.CrossRefGoogle Scholar
[7]Grzegorczyk, A. and Zdanowski, K., Undecidability and concatenation, Andrzej Mostowski and foundational studies (Ehrenfeucht, A., Marek, V.W., and Srebrny, M., editors), IOS Press, 2008, pp. 72–91.Google Scholar
[8]Hájek, P. and Pudlák, P., Metamathematics of first-order arithmetic, Springer, 1993.CrossRefGoogle Scholar
[9]Hermes, H., Semiotik, Eine Theorie der Zeichengestalten als Grundlage fur Untersuchungen von formalisierten Sprachen, Forschungen zur Logik undzur Grundlage derexakten Wissenschaften, n.s., vol. 5 (1938), pp. 5–22, Leipzig.Google Scholar
[10]Hilbert, D. and Bernays, P., Grundlagen der Mathematik, vol. I, Springer, 1934.Google Scholar
[11]Jones, J.P. and Shepderson, J.C., Variants of Robinson's essentially undecidable theory R, Archive for Mathematical Logic, vol. 23 (1983), pp. 61–64.CrossRefGoogle Scholar
[12]Quine, W., Concatenation as a basis for arithmetic, this Journal, vol. 11 (1946), no. 4, pp. 105–114.Google Scholar
[13]Švejdar, V., An interpretation of Robinson Arithmetic in its Grzegorczyk's weaker variant, Fundamenta Informaticae, vol. 81 (2007), pp. 347–354.Google Scholar
[14]Švejdar, V., Weak theories and essential incompleteness, The Logica Yearbook 2007: Proceedings of the Logica '07 International Conference, Hejnice, Czech Republic (Praha) (Peliš, M., editor), Filosofia, 2008, to appear.Google Scholar
[15]Švejdar, V., On interpretability in the theory of concatenation, Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 1, pp. 87–95.CrossRefGoogle Scholar
[16]Tarski, A., The concept of truth in formalized languages, Logic, semantics, metamathematics (Corcoran, J., editor), Hackett, 1983, English translation by Woodger, J.H., pp. 152–278.Google Scholar
[17]Tarski, A., Mostowski, A., and Robinson, R., Undecidable theories, second ed., North Holland, 1968.Google Scholar
[18]Visser, A., Growing commas — A study of sequentiality and concatenation, Notre Dame Journal of Formal Logic, vol. 50 (2009), no. 1.CrossRefGoogle Scholar