This paper is concerned with the logical structure of arithmetical theories. We survey results concerning logics and admissible rules of constructive arithmetical theories. We prove a new theorem: the admissible propositional rules of Heyting Arithmetic are the same as the admissible propositional rules of Intuitionistic Propositional Logic. We provide some further insights concerning predicate logical admissible rules for arithmetical theories.

This paper is concerned with notions of consequence. On the one hand, we study admissible consequence, specifically for substitutions of Σ 1 0 -sentences over Heyting arithmetic . On the other hand, we study preservativity relations. The notion of preservativity of sentences over a given theory is a dual of the notion of conservativity of formulas over a given theory. We show that admissible consequence for Σ 1 0 -substitutions over HA coincides with NNIL -preservativity over intuitionistic propositional logic . (...) Here NNIL is the class of propositional formulas with no nestings of implications to the left . The identical embedding of IPC -derivability into a consequence relation has in many cases a left adjoint. The main tool of the present paper will be an algorithm to compute this left adjoint in the case of NNIL -preservativity. In the last section, we employ the methods developed in the paper to give a characterization the closed fragment of the provability logic of HA. (shrink)

This paper is concerned with notions of consequence. On the one hand, we study admissible consequence, specifically for substitutions of Σ 1 0 -sentences over Heyting arithmetic . On the other hand, we study preservativity relations. The notion of preservativity of sentences over a given theory is a dual of the notion of conservativity of formulas over a given theory. We show that admissible consequence for Σ 1 0 -substitutions over HA coincides with NNIL -preservativity over intuitionistic propositional logic . (...) Here NNIL is the class of propositional formulas with no nestings of implications to the left . The identical embedding of IPC -derivability into a consequence relation has in many cases a left adjoint. The main tool of the present paper will be an algorithm to compute this left adjoint in the case of NNIL -preservativity. In the last section, we employ the methods developed in the paper to give a characterization the closed fragment of the provability logic of HA. (shrink)

Vardanyan's theorem states that the set of PA-valid principles of Quantified Modal Logic, QML, is complete Π0 2. We generalize this result to a wide class of theories. The crucial step in the generalization is avoiding the use of Tennenbaum's Theorem.

A theory T is trustworthy iff, whenever a theory U is interpretable in T, then it is faithfully interpretable. In this paper we give a characterization of trustworthiness. We provide a simple proof of Friedman’s Theorem that finitely axiomatized, sequential, consistent theories are trustworthy. We provide an example of a theory whose schematic predicate logic is complete Π20.

This is a book that every enthusiast for Gödel’s proofs of his incompleteness theorems will want to own. It gives an up-to-date account of connections between systems of modal logic and results on provability in formal systems for arithmetic, analysis, and set theory.

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)