The paper proves a predicate version of Solovay's well-known theorem on provability interpretations of modal logic: If a closed modal predicate-logical formula R is not valid in some finite Kripke model, then there exists an arithmetical interpretation f such that $PA \nvdash fR$ . This result implies the arithmetical completeness of arithmetically correct modal predicate logics with the finite model property (including the one-variable fragments of QGL and QS). The proof was obtained by adding "the predicate part" as a specific (...) addition to the standard Solovay construction. (shrink)
Dzhaparidze, G., A generalized notion of weak interpretability and the corresponding modal logic, Annals of Pure and Applied Logic 61 113-160. A tree Tr of theories T1,...,Tn is called tolerant, if there are consistent extensions T+1,...,T+n of T1,...,Tn, where each T+i interprets its successors in the tree Tr. We consider a propositional language with the following modal formation rule: if Tr is a tree of formulas, then Tr is a formula, and axiomatically define in this language the decidable logics TLR (...) and TLRω. It is proved that TLR yields exactly the schemata of PA-provable sentences, if Tr is understood as “Tr is tolerant”. In fact, TLR axiomatizes a considerable fragment of provability logic with quantifiers over ∑1-sentences, and many relations that have been studied in the literature can be expressed in terms of tolerance. We introduce and study two more relations between theories: cointerpretability and cotolerance which are, in a sense, dual to interpretability and tolerance. Cointerpretability is a characterization of ∑1-conservativity for essentially reflexive theories in terms of translations. (shrink)
Formulas of the propositional modal language with the unary modal operators □, Σ1, 1, Σ2, 2,… are considered as schemata of sentences of arithmetic , where □A is interpreted as “A is PA-provable”, ΣnA as “A is PA-equivalent to a Σn-sentence” and nA as “A is PA-equivalent to a Boolean combination of Σn-sentences”. We give an axiomatization and show decidability of the sets of the modal formulas which are schemata of: PA-provable, true arithmetical sentences.
A nonempty sequence T1,...,Tn of theories is tolerant, if there are consistent theories T 1 + ,..., T n + such that for each 1 i n, T i + is an extension of Ti in the same language and, if i n, T i + interprets T i+1 + . We consider a propositional language with the modality , the arity of which is not fixed, and axiomatically define in this language the decidable logics TOL and TOL. It is (...) shown that TOL (resp. TOL) yields exactly the schemata of PA-provable (resp. true) arithmetical sentences, if (A1,..., An) is understood as (a formalization of) PA+A1, ..., PA+An is tolerant. (shrink)
Predicate modal formulas are considered as schemata of arithmetical formulas, where is interpreted as the standard formula of provability in a fixed sufficiently rich theory T in the language of arithmetic. QL T(T) and QL T are the sets of schemata of T-provable and true formulas, correspondingly. Solovay's well-known result — construction an arithmetical counterinterpretation by Kripke countermodel — is generalized on the predicate modal language; axiomatizations of the restrictions of QL T(T) and QL T by formulas, which contain no (...) variables different from x, are given by means of decidable prepositional bimodal systems; under the assumption that T is 1-complete, there is established the enumerability of the restrictions of QL T(T) and QL T by: 1) formulas in which the domains of different occurrences of don't intersect and 2) formulas of the form n A. (shrink)
Predicate modal formulas with non-modalized quantifiers (call them Q-formulas) are considered as schemata of arithmetical formulas, where is interpreted as the provability predicate of some fixed correct extension T of arithmetic. A method of constructing 1) non-provable in T and 2) false arithmetical examples for Q-formulas by Kripke-like countermodels of certain type is given. Assuming the means of T to be strong enough to solve the (undecidable) problem of derivability in QGL, the Q-fragment of the predicate version of the logic (...) GL, we prove the recursive enumerability of the sets of Q-formulas all arithmetical examples of which are: 1) T-provable, 2) true. In. particular, the first one is shown to be exactly QGL and the second one to be exactly the Q-fragment of the predicate version of Solovay's logic S. (shrink)