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)

We present axiom systems, and provide soundness and strong completeness theorems, for classes of Kripke models with restricted extension rules among the node structures of the model. As examples we present an axiom system for the class of cofinal extension Kripke models, and an axiom system for the class of end-extension Kripke models. We also show that Heyting arithmetic is strongly complete for its class of end-extension models. Cofinal extension models of HA are models of Peano arithmetic.

We define a class of first-order formulas $\mathsf{P}^{\ast }$ which exactly contains formulas $\varphi$ such that satisfaction of $\varphi$ in any classical structure attached to a node of a Kripke model of intuitionistic predicate logic deciding atomic formulas implies its forcing in that node. We also define a class of $\mathsf{E}$-formulas with the property that their forcing coincides with their classical satisfiability in Kripke models which decide atomic formulas. We also prove that any formula with this property is an $\mathsf{E}$-formula. (...) Kripke models of intuitionistic arithmetical theories usually have this property. As a consequence, we prove a new conservativity result for Peano arithmetic over Heyting arithmetic. (shrink)

We prove that all extensions of Heyting Arithmetic with a logic that has the finite frame property possess the de Jongh property.

In the first section of this paper we show that i Π1 ≡ W⌝⌝lΠ1 and that a Kripke model which decides bounded formulas forces iΠ1 if and only if the union of the worlds in any path in it satisflies IΠ1. In particular, the union of the worlds in any path of a Kripke model of HA models IΠ1. In the second section of the paper, we show that for equivalence of forcing and satisfaction of Πm-formulas in a linear Kripke (...) model deciding Δ0-formulas it is necessary and sufficient that the model be Σm-elementary. This implies that if a linear Kripke model forces PEMprenex, then it forces PEM. We also show that, for each n ≥ 1, iΦn does not prove ℋ(IΠn's are Burr's fragments of HA. (shrink)

We prove that all extensions of Heyting Arithmetic with a logic that has the finite frame property possess the de Jongh property.

We introduce the notion of bisimulation for first-order Kripke models. It is defined as a relation that satisfies certain zig-zag conditions involving back-and-forth moves between nodes of Kripke models and, simultaneously, between the domains of their underlying structures. As one of our main results, we prove that if two Kripke models bisimulate to a certain degree, then they are logically equivalent with respect to the class of formulae of the appropriate complexity. Two applications of the notion introduced in the paper (...) are given. First, we consider bisimulations in the context of Kripke models of Heyting Arithmetic. Next, we discuss the notion of elementary submodel of a Kripke model and provide a suitable example. (shrink)

In this paper we define a suitable version of the notion of homomorphism for Kripke models of intuitionistic first-order logic and characterize theories that are preserved under images and also those that are preserved under inverse images of homomorphisms. Moreover, we define a notion of union of chain for Kripke models and define a class of formulas that is preserved in unions of chains. We also define similar classes of formulas and investigate their behavior in Kripke models. An application to (...) intuitionistic first-order arithmetic is also given. (shrink)

In "Intuitionistic validity in -normal Kripke structures," Buss asked whether every intuitionistic theory is, for some classical theory , that of all -normal Kripke structures for which he gave an r.e. axiomatization. In the language of arithmetic and denote PA plus Open Induction or Open LNP, and are their intuitionistic deductive closures. We show is recursively axiomatizable and , while . If proves PEM but not totality of a classically provably total Diophantine function of , then and so . A (...) result due to Wehmeier then implies . We prove is not -conservative over . If , then is not closed under MR or Friedman's translation, so range (). Both and are closed under the negative translation. (shrink)

Given a classical theory T, a Kripke model K for the language L of T is called T-normal or locally PA just in case the classical L-structure attached to each node of K is a classical model of T. Van Dalen, Mulder, Krabbe, and Visser showed that Kripke models of Heyting Arithmetic (HA) over finite frames are locally PA, and that Kripke models of HA over frames ordered like the natural numbers contain infinitely many PA-nodes. We show that Kripke models (...) of the latter sort are in fact PA-normal. This result is extended to a somewhat larger class of frames. (shrink)

A Kripke model ? is a submodel of another Kripke model ℳ if ? is obtained by restricting the set of nodes of ℳ. In this paper we show that the class of formulas of Intuitionistic Predicate Logic that is preserved under taking submodels of Kripke models is precisely the class of semipositive formulas. This result is an analogue of the Łoś-Tarski theorem for the Classical Predicate Calculus.In Appendix A we prove that for theories with decidable identity we can take (...) as the embeddings between domains in Kripke models of the theory, the identical embeddings. This is a well known fact, but we know of no correct proof in the literature. In Appendix B we answer, negatively, a question posed by Sam Buss: whether there is a classical theory T, such that ℋT is HA. Here ℋT is the theory of all Kripke models ℳ such that the structures assigned to the nodes of ℳ all satisfy T in the sense of classical model theory. (shrink)

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 this paper, we consider, for a set \ of natural numbers, the following notions of finitenessFIN1:There are a natural number l and a bijection f between \\);FIN5:It is not the case that \\), and infinitenessINF1:There are not a natural number l and a bijection f between \\);INF5:\\). In this paper, we systematically compare them in the method of constructive reverse mathematics. We show that the equivalence among them can be characterized by various combinations of induction axioms and non-constructive principles, (...) including the axiom of bounded comprehension. (shrink)

A Kripke model for a first order language is called a partially-elementary extension model if its accessibility relation is not merely a submodel relation but a stronger relation of being an elementary submodel with respect to some class of fromulae. As a main result of the paper, we give a characterization of partially-elementary extension Kripke models. Throughout the paper we exploit a generalized version of the hierarchy of first order formulae introduced by W. Burr. We present some applications of partially-elementary (...) extension Kripke models to subtheories of Heyting Arithmetic and provide examples of their models and prove some of their properties. For example, we show that finite models of subtheories in question need not be normal . The presented results show that the properties of models of subtheories of Heyting Arithmetic differ much from the properties of models of the full theory. (shrink)

The aim of this paper is to describe from a semantic perspective the problem of conservativity of classical first-order theories over their intuitionistic counterparts. In particular, we describe a class of formulae for which such conservativity results can be proven in case of any intuitionistic theory T which is complete with respect to a class of T-normal Kripke models. We also prove conservativity results for intuitionistic theories which are closed under the Friedman translation and complete with respect to a class (...) of conversely well-founded Kripke models. The results can be applied to a wide class of intuitionistic theories and can be viewed as generalization of the results obtained by syntactic methods. (shrink)