Provability in predicate product logic

We sharpen Hájek’s Completeness Theorem for theories extending predicate product logic, ${\Pi\forall}$ . By relating provability in this system to embedding properties of ordered abelian groups we construct a universal BL-chain L in the sense that a sentence is provable from ${\Pi\forall}$ if and only if it is an L-tautology. As well we characterize the class of lexicographic sums that have this universality property.     

Provability logic and the completeness principle

The logic $\mathsf{iGLC}$ is the intuitionistic version of Löb's Logic plus the completeness principle $A\to \square A$. In this paper, we prove an arithmetical completeness theorems for $\mathsf{iGLC}$ for theories equipped with two provability predicates □ and △ that prove the schemes $A\to △A$ and $\square △S\to \square S$ for $S\in {\mathrm{\Sigma }}_1$. We provide two salient instances of the theorem. In the first, □ is fast provability and △ is ordinary provability and, in the second, □ is ordinary provability and △ is slow provability.Using the second instance, we reprove a theorem previously obtained by Mohammad Ardeshir and Mojtaba Mojtahedi [1] determining the ${\mathrm{\Sigma }}_1$-provability logic of Heyting Arithmetic.     

Two-dimensional modal logic

Prepositional logics with many modalites, characterized by two-dimensional Kripke models, are investigated. The general problem can be formulated as follows: from two modal logics describing certain classes of Kripke modal lattices construct a logic describing all products of Kripke lattices from these classes. For a large number of cases such a logic is obtained by joining to the original logics an axiom of the form _{ijp jip} and _{ijp jjp}. A special case of this problem, leading to the logic of a torus S5×S5 was solved by Segerberg [1].Translated from Matematieheskie Zametki, Vol. 23, No. 5, pp. 759–772, May, 1978.     

The modal logic of forcing

A set theoretical assertion is forceable or possible, written , if holds in some forcing extension, and necessary, written , if holds in all forcing extensions. In this forcing interpretation of modal logic, we establish that if is consistent, then the ZFC-provable principles of forcing are exactly those in the modal theory .

     

Normal derivability in modal logic

The standard rule of necessitation in systems of natural deduction for the modal logic S4 concludes □A from A whenever all assumptions A depends on are modal formulas. This condition prevents the composability and normalization of derivations, and therefore modifications of the rule have been suggested. It is shown that both properties hold if, instead of changing the rule of necessitation, all elimination rules are formulated in the manner of disjunction elimination, i.e. with an arbitrary consequence. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Deep sequent systems for modal logic

We see a systematic set of cut-free axiomatisations for all the basic normal modal logics formed by some combination the axioms d, t, b, 4, 5. They employ a form of deep inference but otherwise stay very close to Gentzen’s sequent calculus, in particular they enjoy a subformula property in the literal sense. No semantic notions are used inside the proof systems, in particular there is no use of labels. All their rules are invertible and the rules cut, weakening and contraction are admissible. All systems admit a straightforward terminating proof search procedure as well as a syntactic cut elimination procedure.      

A Sahlqvist theorem for distributive modal logic

In this paper we consider distributive modal logic, a setting in which we may add modalities, such as classical types of modalities as well as weak forms of negation, to the fragment of classical propositional logic given by conjunction, disjunction, true, and false. For these logics we define both algebraic semantics, in the form of distributive modal algebras, and relational semantics, in the form of ordered Kripke structures. The main contributions of this paper lie in extending the notion of Sahlqvist axioms to our generalized setting and proving both a correspondence and a canonicity result for distributive modal logics axiomatized by Sahlqvist axioms. Our proof of the correspondence result relies on a reduction to the classical case, but our canonicity proof departs from the traditional style and uses the newly extended algebraic theory of canonical extensions.     

Decidable modal logic with undecidable admissibility problem

Translated from Algebra i Logika, Vol. 31, No. 1, pp. 83–93, January–February, 1992.     

The modal logic of the countable random frame

 We study the modal logic M L ^r of the countable random frame, which is contained in and `approximates' the modal logic of almost sure frame validity, i.e. the logic of those modal principles which are valid with asymptotic probability 1 in a randomly chosen finite frame. We give a sound and complete axiomatization of M L ^r and show that it is not finitely axiomatizable. Then we describe the finite frames of that logic and show that it has the finite frame property and its satisfiability problem is in EXPTIME. All these results easily extend to temporal and other multi-modal logics. Finally, we show that there are modal formulas which are almost surely valid in the finite, yet fail in the countable random frame, and hence do not follow from the extension axioms. Therefore the analog of Fagin's transfer theorem for almost sure validity in first-order logic fails for modal logic. Received: 1 May 2000 / Revised version: 29 July 2001 / Published online: 2 September 2002 Mathematics Subject Classification (2000): 03B45, 03B70, 03C99 Key words or phrases: Modal logic – Random frames – Almost sure frame validity – Countable random frame – Axiomatization – Completeness