Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories

Journal of Symbolic Logic 68 (1):262-266 (2003)
  Copy   BIBTEX

Abstract

A natural problem from elementary arithmetic which is so strongly undecidable that it is not even Trial and Error decidable (in other words, not decidable in the limit) is presented. As a corollary, a natural, elementary arithmetical property which makes a difference between intuitionistic and classical theories is isolated.

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1045861513

Other Versions

No versions found

Links

PhilArchive

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Generic Complexity of Undecidable Problems.Alexei G. Myasnikov & Alexander N. Rybalov - 2008 - Journal of Symbolic Logic 73 (2):656 - 673.
On first-order theories with provability operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
The undecidability of second order linear logic without exponentials.Yves Lafont - 1996 - Journal of Symbolic Logic 61 (2):541-548.
How Much Propositional Logic Suffices for Rosser's Essential Undecidability Theorem?Guillermo Badia, Petr Cintula, Petr Hajek & Andrew Tedder - forthcoming - Review of Symbolic Logic.
Reviews. Alfred Tarski. Preface. Undecidable theories, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1953, pp. VIII–IX. Alfred Tarski. A general method in proofs of undecidability. Undecidable theories, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1953, pp. 3–35. Andrzej Mostowski, Raphael M. Robinson, and Alfred Tarski. Undecidability and essential undecidability in arithmetic. Undecidable theories, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1953, pp. 39–74. Alfred Tarski. Undecidability of the elementary theory of groups. Undecidable theories, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1953, pp. 77–87. Bibliography. Undecidable theories, Studies in logic and the foundations of mathematics, North-Holland Publishing Company, Amsterdam 1953, pp. 89–91. Index. Undecidable theories. [REVIEW]Martin Davis - 1959 - Journal of Symbolic Logic 24 (2):167-169.
Undecidability and intuitionistic incompleteness.D. C. McCarty - 1996 - Journal of Philosophical Logic 25 (5):559 - 565.
How Much Propositional Logic Suffices for Rosser’s Essential Undecidability Theorem?Guillermo Badia, Petr Cintula, Petr Hajek & Andrew Tedder - 2022 - Review of Symbolic Logic 15 (2):487 - 504.
Strongly decidable properties of modal and intuitionistic calculi.L. Maksimova - 2000 - Logic Journal of the IGPL 8 (6):797-819.
The existential fragment of second-order propositional intuitionistic logic is undecidable.Ken-Etsu Fujita, Aleksy Schubert, Paweł Urzyczyn & Konrad Zdanowski - 2024 - Journal of Applied Non-Classical Logics 34 (1):55-74.
Some new results on decidability for elementary algebra and geometry.Robert M. Solovay, R. D. Arthan & John Harrison - 2012 - Annals of Pure and Applied Logic 163 (12):1765-1802.

Analytics

Added to PP
2009-01-28

Downloads
573 (#47,443)

6 months
104 (#58,593)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Panu Raatikainen
Tampere University

Citations of this work

No citations found.

Add more citations

References found in this work

The Logic of Reliable Inquiry.Kevin T. Kelly - 1996 - Oxford, England: Oxford University Press USA. Edited by Kevin Kelly.
The Logic of Reliable Inquiry.Kevin Kelly - 1998 - British Journal for the Philosophy of Science 49 (2):351-354.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

View all 7 references / Add more references