This paper is a comparative study of the propositional intuitionistic (non-modal) and classical modal languages interpreted in the standard way on transitive frames. It shows that, when talking about these frames rather than conventional quasi-orders, the intuitionistic language displays some unusual features: its expressive power becomes weaker than that of the modal language, the induced consequence relation does not have a deduction theorem and is not protoalgebraic. Nevertheless, the paper develops a manageable model theory for this consequence and its extensions (...) which also reveals some unexpected phenomena. The balance between the intuitionistic and modal languages is restored by adding to the former one more implication. (shrink)

We characterize the first-order formulas with one free variable that are preserved under bisimulation and persistence or strong persistence over the class of Kripke models with transitive frames and unary persistent predicates.

Once the Kripke semantics for normal modal logics were introduced, a whole family of modal logics other than the Lewis systems S1 to S5 were discovered. These logics were obtained by changing the semantics in natural ways. The same can be said of the Kripke-style semantics for relevant logics: a whole range of logics other than the standard systems R, E and T were unearthed once a semantics was given (cf. Priest and Sylvan [6], Restall [7], and Routley et al. (...) [8]). In a similar way, weakening the structural rules of the Gentzen formulation of classical logic gives rise to other ‘substructural’ logics such as linear logic (as in Girard [4]). This process of ‘strategic weakening’ is becoming popular today, with the discovery of applications of these logics to areas such as linguistics and the theory of computation (cf. van Benthem [1]). Until now no-one has (to my knowledge) examined what the process of weakening does to the Kripke-style semantics of intuitionistic logic. This paper remedies the deficiency, introducing the family of subintuitionistic logics. These systems have some appealing features. Unlike other substructural logics such as linear logic (which lack distribution of extensional disjunction over conjunction) they have a very natural Kripke-style worlds semantics. Also, the difficulties with regard to modelling quantification in these systems may be able to shed some light on the difficulties in naturally modelling quantification in relevant logics, as it must be admitted that the semantics currently available for quantified relevant logics are rather baroque (cf. Fine [3]). But most importantly, delving in the undergrowth of logics such as intuitionistic logic gives us a ‘feel’ for how such systems are put together, and what job is being done by each aspect of the modelling conditions in.. (shrink)

C. I. Lewis intended his systems S1–S5 as contributions to the study of “strict implication”, but in his formulation, strict implication is so thoroughly intertwined with other notions, such as possibility and negation, that it remains a problem, to separate out the properties of strict implication itself. I shall solve this problem for S2–5 and von Wright's M. The results for S3–5 are given below, while the implicative parts of S2 and M, which are rather more complicated, are given in (...) §5.In this presentation, ‘⊃’ stands for strict implication, and missing brackets for ‘⊃’ are restored by associationtothe right. Astrictformula is one of the form A ⊃ B. Axiom schemes are used throughout. (shrink)

We present an axiomatization for Basic Propositional Calculus BPC and give a completeness theorem for the class of transitive Kripke structures. We present several refinements, including a completeness theorem for irreflexive trees. The class of intermediate logics includes two maximal nodes, one being Classical Propositional Calculus CPC, the other being E1, a theory axiomatized by T → ⊥. The intersection CPC ∩ E1 is axiomatizable by the Principle of the Excluded Middle A V ∨ ⌝A. If B is a formula (...) such that → B is not derivable, then the lattice of formulas built from one propositional variable p using only the binary connectives, is isomorphically preserved if B is substituted for p. A formula → B is derivable exactly when B is provably equivalent to a formula of the form → A) →. (shrink)

Let ℒ and ? be propositional languages over Basic Propositional Calculus, and ℳ = ℒ∩?. Weprove two different but interrelated interpolation theorems. First, suppose that Π is a sequent theory over ℒ, and Σ∪ {C⇒C′} is a set of sequents over ?, such that Π,Σ⊢C⇒C′. Then there is a sequent theory Φ over ℳ such that Π⊢Φ and Φ, Σ⊢C⇒C′. Second, let A be a formula over ℒ, and C 1, C 2 be formulas over ?, such that A∧C 1⊢C (...) 2. Then there exists a formula B over ℳ such that A⊢B and B∧C 1⊢C 2. (shrink)

We present an axiomatization for Basic Propositional Calculus BPC and give a completeness theorem for the class of transitive Kripke structures. We present several refinements, including a completeness theorem for irreflexive trees. The class of intermediate logics includes two maximal nodes, one being Classical Propositional Calculus CPC, the other being E1, a theory axiomatized by T → ⊥. The intersection CPC ∩ E1 is axiomatizable by the Principle of the Excluded Middle A V ∨ ⌝A. If B is a formula (...) such that → B is not derivable, then the lattice of formulas built from one propositional variable p using only the binary connectives, is isomorphically preserved if B is substituted for p. A formula → B is derivable exactly when B is provably equivalent to a formula of the form → A) →. (shrink)

Visser's propositional logic was first considered in Visser [5] as the propositional logic embedded into the modal logic {\bf K4} by G\"odel's translation. He gave a natural deduction system $\vdash_V$ for the consequence relation of {\bf VPL}. An essential difference from the consequence relation $\vdash_I$ of intuitionistic propositional logic is $\{a,a\supset b\}\not \vdash_Vb$ while $\{ a,a\supset b\}\vdash_Ib$. In other words, in $\vdash_V$, modus ponens does not hold in general. So, we may well say that systems for the consequence relation of (...) {\bf VPL} are obtained from the systems for $\vdash_I$ by replacing the inference rule, which corresponds to modus ponens, by other inference rules. For instance, Visser's system $ \vdash_V$ was obtained from Gentzen's natural deduction system $\vdash_{ NJ}$ by replacing implication elimination rule by three other inference rules. Ardeshir [1] and [2] gave sequent style systems for $\vdash_V$ by replacing the inference rule in Gentzen's sequent system {\bf LJ} by other inference rules. However, it seems difficult to give a finite Hilbert style system for the consequence relation of {\bf VPL} because modus pones in Hilbert style system for $\vdash_I$ has the role of translating axioms into inference rules, and so, we have to find another inference rule having the same role in $\vdash_V$. This problem was raised in Suzuki, Wolter and Zakharyaschev [4]. Here we introduce a restricted modus ponens, which mostly has the same role as modus ponens in Hilbert style system for $\vdash_I$ has. Using the restricted modus ponens and adjunction, we give a formalization for $ \vdash_V$, and at the same time we show that $\vdash_V$ can not be formalized by any systems with a restricted modus ponens as only one inference rule. (shrink)