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 show that two abelian-by-finite groups are elementarily equivalent if and only if they satisfy the same sentences with two alternations of quantifiers. We also prove that abelian-by-finite groups satisfy a quantifier elimination property. On the other hand, for each integer n, we give some examples of nilpotent groups which satisfy the same sentences with n alternations of quantifiers and do not satisfy the same sentences with n + 1 alternations of quantifiers.

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.

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.

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)

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 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).

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.

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.

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.

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.