Abstract
We show that Matijasevič's Theorem on the diophantine representation of r.e. predicates is provable in the subsystem I ∃ - 1 of Peano Arithmetic formed by restricting the induction scheme to diophantine formulas with no parameters. More specifically, I ∃ - 1 ⊢ IE - 1 + E ⊢ Matijasevič's Theorem where IE - 1 is the scheme of parameter-free bounded existential induction and E is an ∀∃ axiom expressing the existence of a function of exponential growth. We conclude by examining the consequences of these results to the structure of countable nonstandard models of IE - 1
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(90)90076-e
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,339
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Existence and Feasibility in Arithmetic.Rohit Parikh - 1971 - Journal of Symbolic Logic 36 (3):494-508.
Bounded Existential Induction.George Wilmers - 1985 - Journal of Symbolic Logic 50 (1):72-90.
On Parameter Free Induction Schemas.R. Kaye, J. Paris & C. Dimitracopoulos - 1988 - Journal of Symbolic Logic 53 (4):1082-1097.
On the Complexity of Models of Arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
Existential Definability in Arithmetic.Julia Robinson - 1955 - Journal of Symbolic Logic 20 (2):182-183.

Add more references

Citations of this work BETA

Pell Equations and Exponentiation in Fragments of Arithmetic.Paola D'Aquino - 1996 - Annals of Pure and Applied Logic 77 (1):1-34.
Toward the Limits of the Tennenbaum Phenomenon.Paola D'Aquino - 1997 - Notre Dame Journal of Formal Logic 38 (1):81-92.
Solving Pell Equations Locally in Models of IΔ0.Paola D'Aquino - 1998 - Journal of Symbolic Logic 63 (2):402-410.

View all 12 citations / Add more citations

Similar books and articles

Diophantine Equivalence and Countable Rings.Alexandra Shlapentokh - 1994 - Journal of Symbolic Logic 59 (3):1068-1095.
Diophantine Properties of Finite Commutative Rings.Mihai Prunescu - 2003 - Archive for Mathematical Logic 42 (3):293-302.
Herbrand's Theorem and Term Induction.Matthias Baaz & Georg Moser - 2006 - Archive for Mathematical Logic 45 (4):447-503.
Some Problems of Counter‐Inductive Policy as Opposed to Inductive.Audun Öfsti - 1962 - Inquiry: An Interdisciplinary Journal of Philosophy 5 (1-4):267-283.
No Need to Justify Induction Generally.Kazuyoshi Kamiyama - 2008 - Proceedings of the Xxii World Congress of Philosophy 53:105-111.

Analytics

Added to PP index
2014-01-16

Total views
9 ( #922,642 of 2,448,744 )

Recent downloads (6 months)
1 ( #445,251 of 2,448,744 )

How can I increase my downloads?

Downloads

My notes