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)

Akama et al. [1] introduced a hierarchical classification of first-order formulas for a hierarchical prenex normal form theorem in semi-classical arithmetic. In this paper, we give a justification for the hierarchical classification in a general context of first-order theories. To this end, we first formalize the standard transformation procedure for prenex normalization. Then we show that the classes $$\textrm{E}_k$$ and $$\textrm{U}_k$$ introduced in [1] are exactly the classes induced by $$\Sigma _k$$ and $$\Pi _k$$ respectively via the transformation procedure in (...) any first-order theory. (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)

The intersection of a linearly ordered set of total subrelations of a total relation with range 2 need not be total, constructively.

This paper presents a novel proof of the conservativity of the intuitionistic theory of strictly positive fixpoints, $$\widehat{{\textrm{ID}}}{}_{1}^{{\textrm{i}}}{}$$ ID ^ 1 i, over Heyting arithmetic ($${\textrm{HA}}$$ HA ), originally proved in full generality by Arai (Ann Pure Appl Log 162:807–815, 2011. https://doi.org/10.1016/j.apal.2011.03.002). The proof embeds $$\widehat{{\textrm{ID}}}{}_{1}^{{\textrm{i}}}{}$$ ID ^ 1 i into the corresponding theory over Beeson’s logic of partial terms and then uses two consecutive interpretations, a realizability interpretation of this theory into the subtheory generated by almost negative fixpoints, and (...) a direct interpretation into Heyting arithmetic with partial terms using a hierarchy of satisfaction predicates for almost negative formulae. It concludes by applying van den Berg and van Slooten’s result (Indag Math 29:260–275, 2018. https://doi.org/10.1016/j.indag.2017.07.009) that Heyting arithmetic with partial terms plus the schema of self realizability for arithmetic formulae is conservative over $${\textrm{HA}}$$ HA. (shrink)