We define notions of homomorphism, submodel, and sandwich of Kripke models, and we define two syntactic operators analogous to universal and existential closure. Then we prove an intuitionistic analogue of the generalized (dual of the) Lyndon-Łoś-Tarski Theorem, which characterizes the sentences preserved under inverse images of homomorphisms of Kripke models, an intuitionistic analogue of the generalized Łoś-Tarski Theorem, which characterizes the sentences preserved under submodels of Kripke models, and an intuitionistic analogue of the generalized Keisler Sandwich Theorem, (...) which characterizes the sentences preserved under sandwiches of Kripke models. We also define several intuitionistic formula hierarchies analogous to the classical formula hierarchies $\forall_n (= \Pi^0_n)$ and $\exists_n (=\Sigma^0_n)$ , and we show how our generalized syntactic preservation theorems specialize to these hierarchies. Each of these theorems implies the corresponding classical theorem in the case where the Kripke models force classical logic. (shrink)

Basic Predicate Logic, BQC, is a proper subsystem of Intuitionistic Predicate Logic, IQC. For every formula in the language {, , , , , , }, we associate two sequences of formulas 0,1,... and 0,1,... in the same language. We prove that for every sequent , there are natural numbers m, n, such that IQC , iff BQC n m. Some applications of this translation are mentioned.

Craig interpolation theorem implies that the derivability of X,X′ Y′ implies existence of an interpolant I in the common language of X and X′ Y′ such that both X I and I,X′ Y′ are derivable. For classical logic this extends to X,X′ Y,Y′, but for intuitionistic logic there are counterexamples. We present a version true for intuitionistic propositional logic, and more complicated version for the predicate case.

One criterion of constructive logics is the disjunction, property (DP). The Halldén-completeness is a weak DP, and is related to the relevance principle and variable separation. This concept is well-understood in the case of propositional logics. We extend this notion to predicate logics. Then three counterparts naturally arise. We discuss relationships between these properties and meet-irreducibility in the lattice of logics.

In this article we show that bi-intuitionistic predicate logic lacks the Craig Interpolation Property. We proceed by adapting the counterexample given by Mints, Olkhovikov and Urquhart for intuitionistic predicate logic with constant domains [13]. More precisely, we show that there is a valid implication $\phi \rightarrow \psi $ with no interpolant. Importantly, this result does not contradict the unfortunately named ‘Craig interpolation’ theorem established by Rauszer in [24] since that article is about the property (...) more correctly named ‘deductive interpolation’ (see Galatos, Jipsen, Kowalski and Ono’s use of this term in [5]) for global consequence. Given that the deduction theorem fails for bi-intuitionistic logic with global consequence, the two formulations of the property are not equivalent. (shrink)

One criterion of constructive logics is the disjunction, property (DP). The Halldén-completeness is a weak DP, and is related to the relevance principle and variable separation. This concept is well-understood in the case of propositional logics. We extend this notion to predicate logics. Then three counterparts naturally arise. We discuss relationships between these properties and meet-irreducibility in the lattice of logics.

The main part of the proof of Kripke's completeness theorem for intuitionistic logic is Henkin's construction. We introduce a new Kripke-type semantics with semilattice structures for intuitionistic logic. The completeness theorem for this semantics can he proved without Henkin's construction.

Some properties of Kripke-sheaf semantics for super-intuitionistic predicate logics are shown. The concept ofp-morphisms between Kripke sheaves is introduced. It is shown that if there exists ap-morphism from a Kripke sheaf 1 into 2 then the logic characterized by 1 is contained in the logic characterized by 2. Examples of Kripke-sheaf complete and finitely axiomatizable super-intuitionistic (and intermediate) predicate logics each of which is Kripke-frame incomplete are given. A correction to the author's previous paper (...) Kripke bundles for intermediate predicate logics and Kripke frames for intuitionistic modal logics (Studia Logica, 49(1990), pp. 289–306 ) is stated. (shrink)

Using the framework of categorical logic, this paper analyzes and streamlines Gabbay's semantical proof of the Craig interpolation theorem for intuitionistic predicate logic. In the process, an apparently new and interesting fact about the relation of coherent and intuitionistic logic is found.

In this paper we give a new proof of cut elimination in Gentzen's sequent system for intuitionistic first-order predicate logic. The point of this proof is that the elimination procedure eliminates the cut rule itself, rather than the mix rule.

Shehtman and Skvortsov introduced Kripke bundles as semantics of non-classical first-order predicate logics. We show the structural equivalence between Kripke bundles for intermediate predicate lógics and Kripke-type frames for intuitionistic modal propositional logics. This equivalence enables us to develop the semantical study of relations between intermediate predicate logics and intuitionistic modal propositional logics. New examples of modal counterparts of intermediate predicate logics are given.

Modal counterparts of intermediate predicate logics will be studied by means of algebraic devise. Our main tool will be a construction of algebraic semantics for modal logics from algebraic frames for predicate logics. Uncountably many examples of modal counterparts of intermediate predicate logics will be given.

This paper presents an intuitionistic proof of a statement which under a classical reading is logically equivalent to Gödel's completeness theorem for classical predicate logic.

We develop a predicate logical extension of a subintuitionistic propositional logic. Therefore a Hilbert type calculus and a Kripke type model are given. The propositional logic is formulated to axiomatize the idea of strategic weakening of Kripke''s semantic for intuitionistic logic: dropping the semantical condition of heredity or persistence leads to a nonmonotonic model. On the syntactic side this leads to a certain restriction imposed on the deduction theorem. By means of a Henkin argument strong (...) completeness is proved making use of predicate logical principles, which are only classically acceptable. (shrink)

The paper presents predicate logical extensions of some subintuitionistic logics. Subintuitionistic logics result if conditions of the accessibility relation in Kripke models for intuitionistic logic are dropped. The accessibility relation which interprets implication in models for the propositional base subintuitionistic logic considered here is neither persistent on atoms, nor reflexive, nor transitive. Strongly complete predicate logical extensions are modeled with a second accessibility relation, which is a partial order, for the interpretation of the universal quantifier.

We show how to interpret intuitionistic propositional logic into a predicative second-order intuitionistic propositional system having only the conditional and the universal second-order quantifier. We comment on this fact. We argue that it supports the legitimacy of using classical logic in a predicative setting, even though the philosophical cast of predicativism is nonrealistic. We also note that the absence of disjunction and existential quantifications allows one to have a process of normalization of proofs that avoids the (...) use of "commuting conversions.". (shrink)

A notion of strictly primitive recursive realizability is introduced by Damnjanovic in 1994. It is a kind of constructive semantics of the arithmetical sentences using primitive recursive functions. It is of interest to study the corresponding predicate logic. It was argued by Park in 2003 that the predicate logic of strictly primitive recursive realizability is not arithmetical. Park’s argument is essentially based on a claim of Damnjanovic that intuitionistic logic is sound with respect to (...) strictly primitive recursive realizability, but that claim was disproved by the author of this article in 2006. The aim of this paper is to present a correct proof of the result of Park. (shrink)

We give a syntactic translation from first-order intuitionistic predicate logic into second-order intuitionistic propositional logic IPC2. The translation covers the full set of logical connectives ∧, ∨, →, ⊥, ∀, and ∃, extending our previous work, which studied the significantly simpler case of the universal-implicational fragment of predicate logic. As corollaries of our approach, we obtain simple proofs of nondefinability of ∃ from the propositional connectives and nondefinability of ∀ from ∃ in the (...) second-order intuitionistic propositional logic. We also show that the ∀-free fragment of IPC2 is undecidable. (shrink)

It is proved in this paper that the predicate logic of each complete constructive arithmetic theory T having the existential property is Π1T-complete. In this connection, the techniques of a uniform partial truth definition for intuitionistic arithmetic theories is used. The main theorem is applied to the characterization of the predicate logic corresponding to certain variant of the notion of realizable predicate formula. Namely, it is shown that the set of irrefutable predicate formulas (...) is recursively isomorphic to the complement of the set ︀. The notion of Σn-realizability is defined on the basis of the notion of Σn-function. It is proved that the predicate logic of Σn-realizability is Πω+1-hard. (shrink)

We perform a proof-theoretical investigation of two modal predicate logics: global intuitionistic logic GI and global intuitionistic fuzzy logic GIF. These logics were introduced by Takeuti and Titani to formulate an intuitionistic set theory and an intuitionistic fuzzy set theory together with their metatheories. Here we define analytic Gentzen style calculi for GI and GIF. Among other things, these calculi allows one to prove Herbrand’s theorem for suitable fragments of GI and GIF.

In this article we deal with Glivenko type theorems for intuitionistic modal logics over Prior's MIPC. We examine the problems which appear in proving Glivenko type theorems when passing from the intuitionistic propositional logic Intto MIPC. As a result we obtain two different versions of Glivenko's theorem for logics over MIPC. Since MIPCcan be thought of as a one-variable fragment of the intuitionistic predicate logic Q-Int, one of the versions of Glivenko's theorem for logics (...) over MIPCis closely related to that for intermediate predicate logics obtained by Umezawa [27] and Gabbay [15]. Another one is rather surprising. (shrink)

The completeness w.r.t. Kripke frames with equality (or, equivalently, w.r.t. Kripke sheaves, [ 8 ] or [4, Sect. 3.6]) is established for three superintuitionistic predicate logics: ( Q - H + D *), ( Q - H + D *&K), ( Q - H + D *& K & J ). Here Q - H is intuitionistic predicate logic, J is the principle of the weak excluded middle, K is Kuroda’s axiom, and D * (cf. [ (...) 12 ]) is a weakened version of the well-known constant domains principle D . Namely, the formula D states that any individual has ancestors in earlier worlds, and D * states that any individual has $${\neg\neg}$$ -ancestors (i.e., ancestors up to $${\neg\neg}$$ -equality) in earlier worlds. In particular, the logic ( Q - H + D *& K & J ) is the Kripke sheaf completion of ( Q - H + E & K & J ), where E is a version of Markov’s principle (cf. [ 12 ]). On the other hand, we show that the logic ( Q - H + D *& J ) is incomplete w.r.t. Kripke sheaves. (shrink)

IPC, the intuitionistic predicate calculus, has the property(i) Vc(A c /x) xA.Furthermore, for certain important , IPC has the converse property (ii) xA Vc(A c /x). (i) may be given up in various ways, corresponding to different philosophic intuitions and yielding different systems of intuitionistic free logic. The present paper proves the strong completeness of several of these with respect to Kripke style semantics. It also shows that giving up (i) need not force us to abandon (...) the analogue of (ii). (shrink)

Along the same line as that in Ono (Ann Pure Appl Logic 161:246–250, 2009), a proof-theoretic approach to Glivenko theorems is developed here for substructural predicate logics relative not only to classical predicate logic but also to arbitrary involutive substructural predicate logics over intuitionistic linear predicate logic without exponentials QFLe. It is shown that there exists the weakest logic over QFLe among substructural predicate logics for which the Glivenko theorem holds. (...) Negative translations of substructural predicate logics are studied by using the same approach. First, a negative translation, called extended Kuroda translation is introduced. Then a translation result of an arbitrary involutive substructural predicate logics over QFLe is shown, and the existence of the weakest logic is proved among such logics for which the extended Kuroda translation works. They are obtained by a slight modification of the proof of the Glivenko theorem. Relations of our extended Kuroda translation with other standard negative translations will be discussed. Lastly, algebraic aspects of these results will be mentioned briefly. In this way, a clear and comprehensive understanding of Glivenko theorems and negative translations will be obtained from a substructural viewpoint. (shrink)

In so-called Kripke-type models, each sentence is assigned either to true or to false at each possible world. In this setting, every possible world has the two-valued Boolean algebra as the set of truth values. Instead, we take a collection of algebras each of which is attached to a world as the set of truth values at the world, and obtain an extended semantics based on the traditional Kripke-type semantics, which we call here the algebraic Kripke semantics. We introduce algebraic (...) Kripke sheaf semantics for super-intuitionistic and modal predicate logics, and discuss some basic properties. We can state the Gödel-McKinsey-Tarski translation theorem within this semantics. Further, we show new results on super-intuitionistic predicate logics. We prove that there exists a continuum of super-intuitionistic predicate logics each of which has both of the disjunction and existence properties and moreover the same propositional fragment as the intuitionistic logic. (shrink)

We give a simple proof-theoretic argument showing that Glivenko’s theorem for propositional logic and its version for predicate logic follow as an easy consequence of the deduction theorem, which also proves some Glivenko type theorems relating intermediate predicate logics between intuitionistic and classical logic. We consider two schemata, the double negation shift (DNS) and the one consisting of instances of the principle of excluded middle for sentences (REM). We prove that both schemata combined derive (...) classical logic, while each one of them provides a strictly weaker intermediate logic, and neither of them is derivable from the other. We show that over every intermediate logic there exists a maximal intermediate logic for which Glivenko’s theorem holds. We deduce as well a characterization of DNS, as the weakest (with respect to derivability) scheme that added to REM derives classical logic. (shrink)

Within a weak system \ of intuitionistic analysis one may prove, using the Weak Fan Theorem as an additional axiom, a completeness theorem for intuitionistic first-order predicate logic relative to validity in generalized Beth models as well as a completeness theorem for classical first-order predicate logic relative to validity in intuitionistic structures. Conversely, each of these theorems implies over \ the Weak Fan Theorem.

We present $\in_I$-Logic (Epsilon-I-Logic), a non-Fregean intuitionistic logic with a truth predicate and a falsity predicate as intuitionistic negation. $\in_I$ is an extension and intuitionistic generalization of the classical logic $\in_T$ (without quantifiers) designed by Sträter as a theory of truth with propositional self-reference. The intensional semantics of $\in_T$ offers a new solution to semantic paradoxes. In the present paper we introduce an intuitionistic semantics and study some semantic notions in (...) this broader context. Also we enrich the quantifier-free language by the new connective < that expresses reference between statements and yields a finer characterization of intensional models. Our results in the intuitionistic setting lead to a clear distinction between the notion of denotation of a sentence and the here-proposed notion of extension of a sentence (both concepts are equivalent in the classical context). We generalize the Fregean Axiom to an intuitionistic version not valid in $\in_I$. A main result of the paper is the development of several model constructions. We construct intensional models and present a method for the construction of standard models which contain specific (self-)referential propositions. (shrink)

Kolmogorov established the principle of the double negation translation by which to embed Classical Predicate Logic |${\operatorname {CQC}}$| into Intuitionistic Predicate Logic |${\operatorname {IQC}}$|⁠. We show that the obvious generalizations to the Basic Predicate Logic of [3] and to |${\operatorname {BQC}}$| of [12], a proper subsystem of |${\operatorname {IQC}}$|⁠, go through as well. The obvious generalizations of Kuroda’s embedding are shown to be equivalent to the Kolmogorov variant. In our proofs novel nontrivial techniques (...) are needed to overcome the absence of full modus ponens in Basic Predicate Logic. In [3] we argued that |${\operatorname {IQC}}$| is not the logic of constructive mathematics. Our doubts were far from new. New was that we put forward an alternative, |${\operatorname {BQC}}$|⁠. One concern is that |${\operatorname {BQC}}$| is too weak for serious mathematics, or even trivial. This paper is one step to alleviate such concerns. (shrink)

Girard introduced phase semantics as a complete set-theoretic semantics of linear logic, and Okada modified phase-semantic completeness proofs to obtain normal-form theorems. On the basis of these works, Okada and Takemura reformulated Girard’s phase semantics so that it became phase semantics for proof-terms, i.e., lambda-terms. They formulated phase semantics for proof-terms of Laird’s dual affine/intuitionistic lambda-calculus and proved the normal-form theorem for Laird’s calculus via a completeness theorem. Their semantics was obtained by an application of computability predicates. In (...) this paper, we first formulate phase semantics for proof-terms of second-order intuitionistic propositional logic by modifying Tait-Girard’s saturated sets method. Next, we prove the completeness theorem with respect to this semantics, which implies a strong normalization theorem. (shrink)

This paper treats a kind of a modal logic based on the intuitionistic propositional logic which arose from the provability predicate in the first order arithmetic. The semantics of this calculus is presented in both a relational and an algebraic way.Completeness theorems, existence of a characteristic model and of a characteristic frame, properties of FMP and FFP and decidability are proved.