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)

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)

We define two notions for intuitionistic predicate logic: that of a submodel of a Kripke model, and that of a universal sentence. We then prove a corresponding preservation theorem. If a Kripke model is viewed as a functor from a small category to the category of all classical models with morphisms between them, then we define a submodel of a Kripke model to be a restriction of the original Kripke model to a subcategory of its domain, where every node in (...) the subcategory is mapped to a classical submodel of the corresponding classical model in the range of the original Kripke model. We call a sentence universal if it is built inductively from atoms using ∧, ∨, ∀, and →, with the restriction that antecedents of → must be atomic. We prove that an intuitionistic theory is axiomatized by universal sentences if and only if it is preserved under Kripke submodels. We also prove the following analogue of a classical model-consistency theorem: The universal fragment of a theory Γ is contained in the universal fragment of a theory Δ if and only if every rooted Kripke model of Δ is strongly equivalent to a submodel of a rooted Kripke model of Γ. Our notions of Kripke submodel and universal sentence are natural in the sense that in the presence of the rule of excluded middle, they collapse to the classical notions of submodel and universal sentence. (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)