We study Basic Arithmetic, $$\textsf{BA}$$ introduced by Ruitenburg (Notre Dame J Formal Logic 39:18–46, 1998). $$\textsf{BA}$$ is an arithmetical theory based on basic logic which is weaker than intuitionistic logic. We show that the class of the provably total recursive functions of $$\textsf{BA}$$ is a proper sub-class of the primitive recursive functions. Three extensions of $$\textsf{BA}$$, called $$\textsf{BA}+\mathsf U$$, $$\mathsf {BA_{\mathrm c}}$$ and $$\textsf{EBA}$$ are investigated with relation to their provably total recursive functions. It is shown that the provably total (...) recursive functions of these three extensions of $$\textsf{BA}$$ are exactly the primitive recursive functions. Moreover, among other things, it is shown that the well-known MRDP theorem does not hold in $$\textsf{BA}$$, $$\textsf{BA}+\mathsf U$$, $$\mathsf {BA_{\mathrm c}}$$, but holds in $$\textsf{EBA}$$. (shrink)

A new proof is given of the celebrated theorem of M. Davis, H. Putnam and J. Robinson concerning exponential Diophantine representation of recursively enumerable predicates. The proof goes by induction on the defining scheme of a partial recursive function.

We study the relative strength of the two axioms Every Pell equation has a nontrivial solution Exponentiation is total over weak fragments, and we show they are equivalent over IE1. We then define the graph of the exponential function using only existentially bounded quantifiers in the language of arithmetic expanded with the symbol #, where # = x[log2y]. We prove the recursion laws of exponentiation in the corresponding fragment.

We study the strength of weak forms of the Regularity Principle in the presence of equation image relative to other subsystems of equation image. In particular, the Bounded Weak Regularity Principle is formulated, and it is shown that when applied to E1 formulas, this principle is equivalent over equation image to equation image.

This paper proves some independence results for weak fragments of Heyting arithmetic by using Kripke models. We present a necessary condition for linear Kripke models of arithmetical theories which are closed under the negative translation and use it to show that the union of the worlds in any linear Kripke model of HA satisfies PA. We construct a two-node PA-normal Kripke structure which does not force iΣ2. We prove i∀1 ⊬ i∃1, i∃1 ⊬ i∀1, iΠ2 ⊬ iΣ2 and iΣ2 ⊬ (...) iΠ2. We use Smorynski's operation Σ′ to show HA ⊬ lΠ1. (shrink)

We study the parameterized complexity of the problem to decide whether a given natural number n satisfies a given $\Delta _0$ -formula $\varphi (x)$ ; the parameter is the size of $\varphi $. This parameterization focusses attention on instances where n is large compared to the size of $\varphi $. We show unconditionally that this problem does not belong to the parameterized analogue of $\mathsf {AC}^0$. From this we derive that certain natural upper bounds on the complexity of our parameterized (...) problem imply certain separations of classical complexity classes. This connection is obtained via an analysis of a parameterized halting problem. Some of these upper bounds follow assuming that $I\Delta _0$ proves the MRDP theorem in a certain weak sense. (shrink)

A generalization is given of McAloon's result on initial segments ofmodels of GlΔ0, the fragment of Peano Arithmetic where the induction scheme is restricted to formulas with bounded quantifiers.

A generalization is given of McAloon's result on initial segments ofmodels of GlΔ0, the fragment of Peano Arithmetic where the induction scheme is restricted to formulas with bounded quantifiers.

We study variants of Buss’s theories of bounded arithmetic axiomatized by induction schemes disallowing the use of parameters, and closely related induction inference rules. We put particular emphasis on \ induction schemes, which were so far neglected in the literature. We present inclusions and conservation results between the systems and \ of a new form), results on numbers of instances of the axioms or rules, connections to reflection principles for quantified propositional calculi, and separations between the systems.

In [4] it is shown that only using exponentiation can one prove the existence of non trivial solutions of Pell equations in IΔ 0 . However, in this paper we will prove that any Pell equation has a non trivial solution modulo m for every m in IΔ 0.

We consider the theory and its weak fragments in the language of arithmetic expanded with the functional symbol . We prove that and its weak fragments, down to and , are subject to the Tennenbaum phenomenon with respect to , , and . For the last two theories it is still unknown if they may have nonstandard recursive models in the usual language of arithmetic.

We study the strength (over bounded induction) of axioms expressing particular cases of the Chinese Remainder Theorem with respect to the axiom ∀ x, y∃ z (z = xy).

Hilbert's tenth problem for a theory T asks if there is an algorithm which decides for a given polynomial p() from [] whether p() has a root in some model of T. We examine some of the model-theoretic consequences that an affirmative answer would have in cases such as T = Open Induction and others, and apply these methods by providing a negative answer in the cases when T is some particular finite fragment of the weak theories IE1 or IU-1.