Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T21:31:49.676Z Has data issue: false hasContentIssue false
  • English
  • Français

CARDINAL ARITHMETIC IN THE STYLE OF BARON VON MÜNCHHAUSEN

Published online by Cambridge University Press:  05 October 2009

ALBERT VISSER
ALBERT VISSER*
Affiliation:
Department of Philosophy, Utrecht University
*
*DEPARTMENT OF PHILOSOPHY, UTRECHT UNIVERSITY, HEIDELBERGLAAN 8, 3584 CS UTRECHT, THE NETHERLANDS E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we show how to interpret Robinson’s arithmetic Q and the theory R of Tarski, Mostowski, and Robinson as theories of cardinals in very weak theories of relations over a domain.

Bei der Verfolgung eines Hasen wollte ich mit meinem Pferd über einen Morast setzen. Mitten im Sprung musste ich erkennen, dass der Morast viel breiter war, als ich anfänglich eingeschätzt hatte. Schwebend in der Luft wendete ich daher wieder um, wo ich hergekommen war, um einen größeren Anlauf zu nehmen. Gleichwohl sprang ich zum zweiten Mal noch zu kurz und fiel nicht weit vom anderen Ufer bis an den Hals in den Morast. Hier hätte ich unfehlbar umkommen müssen, wenn nicht die Stärke meines Armes mich an meinem eigenen Haarzopf, samt dem Pferd, welches ich fest zwischen meine Knie schloss, wieder herausgezogen hätte.

Baron von Münchhausen

Type
Research Article
Information
The Review of Symbolic Logic , Volume 2 , Issue 3 , September 2009 , pp. 570 - 589
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

BIBLIOGRAPHY

Büchi, J. R. (1960). Weak second order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6, 66–92.Google Scholar
Büchi, J. R., & Elgot, C. C. (1959). Decision problems of weak second order arithmetics and finite automata, part I (abstract). American Mathematical Society Notices, 5, 834.Google Scholar
Burgess, J. (2005). Fixing Frege. Princeton Monographs in Philosophy. Princeton, NJ: Princeton University Press.Google Scholar
Cégielski, P., & Richard, D. (2001). Decidability of the natural integers equipped with the Cantor pairing function and successor. Theoretical Computer Science, 257(1–2), 51–77.Google Scholar
Collins, G. E., & Halpern, J. D. (1970). On the interpretability of arithmetic in set theory. The Notre Dame Journal of Formal Logic, 11, 477–483.Google Scholar
Elgot, C. C. (1961). Decision problems of finite automata design and related arithmetics. Transactions of the American Mathematical Society, 98, 21–51.Google Scholar
Elgot, C. C., & Rabin, M. O. (1966). Decidability and undecidability of extensions of second (first) order theory of (generalized) successor. Journal of Symbolic Logic, 31, 169–181.Google Scholar
Hájek, P., & Pudlák, P. (1991). Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic. Berlin: Springer.Google Scholar
Jones, J. P., & Shepherdson, J. C. (1983). Variants of Robinson’s essentially undecidable theory r. Archiv für Mathematische Logik und Grundlagenforschung, 23, 61–64.Google Scholar
Montagna, F., & Mancini, A. (1994). A minimal predicative set theory. The Notre Dame Journal of Formal Logic, 35, 186–203.Google Scholar
Mycielski, J., Pudlák, P., & Stern, A. S. (1990). A Lattice of Chapters of Mathematics (Interpretations Between Theorems), volume 426 of Memoirs of the American Mathematical Society. Providence, RI: AMS.Google Scholar
Nelson, E. (1986). Predicative Arithmetic. Princeton, NJ: Princeton University Press.CrossRefGoogle Scholar
Pudlák, P. (1983). Some prime elements in the lattice of interpretability types. Transactions of the American Mathematical Society, 280, 255–275.Google Scholar
Solovay, R. M. (1976). Interpretability in Set Theories. Unpublished letter to P. Hájek, August 17, 1976. Available from: http://www.cs.cas.cz/~hajek/RyZFGB.pdf.Google Scholar
Stern, A. S. (1989). Sequential theories and infinite distributivity in the lattice of chapters. Journal of Philosophical Logic, 54, 190–206.Google Scholar
Švejdar, V. (2007). An interpretation of Robinson’s arithmetic in Grzegorczyk’s weaker variant. Fundamenta Informaticae, 81, 347–354.Google Scholar
Szmielew, W., & Tarski, A. (1950). Mutual interpretability of some essentially undecidable theories. In Proceedings of the International Congress of Mathematicians (Cambridge, Massachusetts, 1950), Vol. 1. Providence, RI: American Mathematical Society, p. 734.Google Scholar
Tarski, A., Mostowski, A., & Robinson, R. M. (1953). Undecidable Theories. Amsterdam, The Netherlands: North-Holland.Google Scholar
Tenney, R. L. (unpublished). Decidable Pairing Functions. Unpublished.Google Scholar
Vaught, R. A. (1967). Axiomatizability by a schema. The Journal of Symbolic Logic, 32(4), 473–479.Google Scholar
Vaught, R. L. (1962). On a theorem of Cobham concerning undecidable theories. In Nagel, E., Suppes, P., and Tarski, A., editors. Logic, Methodology and Philosophy of Science. Proceedings of the 1960 International Congress. Stanford, CA: Stanford University Press, pp. 14–25.Google Scholar
Visser, A. (2008). Pairs, sets and sequences in first order theories. Archive for Mathematical Logic, 47(4), 299–326.Google Scholar