Abstract In this paper, we study the employment of $\Sigma _1$ -sentences with certificates, i.e., $\Sigma _1$ -sentences where a number of principles is added to ensure that the witness is sufficiently number-like. We develop certificates in some detail and illustrate their use by reproving some classical results and proving some new ones. An example of such a classical result is Vaught’s theorem of the strong effective inseparability of $\mathsf {R}_0$ . We also develop the new idea of a theory being $\mathsf {R}_{0\mathsf {p}}$ -sourced . Using this notion, we can transfer a number of salient results from $\mathsf {R}_0$ to a variety of other theories.

Abstract We show that there is no theory that is minimal with respect to interpretability among recursively enumerable essentially undecidable theories.

In the present paper, we explore an idea of Harvey Friedman to obtain a coordinate-free presentation of consistency. For some range of theories, Friedman's idea delivers actual consistency statements (modulo provable equivalence). For a wider range, it delivers consistency-like statements. We say that a sentence C is an interpreter of a finitely axiomatised A over U iff it is the weakest statement C over U, with respect to U-provability, such that U+C interprets A. A theory U is Friedman-reflexive iff every finitely axiomatised A has an interpreter over U. Friedman shows that Peano Arithmetic, PA, is Friedman-reflexive. We study the question which theories are Friedman-reflexive. We show that a very weak theory, Peano Corto, is Friedman-reflexive. We do not get the usual consistency statements here, but bounded, cut-free, or Herbrand consistency statements. We illustrate that Peano Corto as a base theory has additional desirable properties. We prove a characterisation theorem for the Friedman-reflexivity of sequential theories. We provide an example of a Friedman-reflexive sequential theory that substantially differs from the paradigm cases of Peano Arithmetic and Peano Corto. Interpreters over a Friedman-reflexive U can be used to define a provability-like notion for any finitely axiomatised A that interprets U. We explore what modal logics this idea gives rise to. We call such logics interpreter logics. We show that, generally, these logics satisfy the Löb Conditions, aka K4. We provide conditions for when interpreter logics extend S4, K45, and Löb's Logic. We show that, if either U or A is sequential, then the condition for extending Löb's Logic is fulfilled. Moreover, if our base theory U is sequential and if, in addition, its interpreters can be effectively found, we prove Solovay's Theorem. This holds even if the provability-like operator is not necessarily representable by a predicate of Gödel numbers. At the end of the paper, we briefly discuss how successful the coordinate-free approach is.

Abstract In this paper, we study finitely axiomatizable conservative extensions of a theoryUin the case whereUis recursively enumerable and not finitely axiomatizable. Stanisław Krajewski posed the question whether there are minimal conservative extensions of this sort. We answer this question negatively. Consider a finite expansion of the signature ofUthat contains at least one predicate symbol of arity ≥ 2. We show that, for any finite extensionαofUin the expanded language that is conservative overU, there is a conservative extensionβofUin the expanded language, such that $\alpha \vdash \beta$ and $\beta \not \vdash \alpha$ . The result is preserved when we consider eitherextensionsormodel-conservative extensionsofUinstead ofconservative extensions. Moreover, the result is preserved when we replace $\dashv$ as ordering on the finitely axiomatized extensions in the expanded language by a relevant kind of interpretability, to witinterpretability that identically translates the symbols of the U-language. We show that the result fails when we consider an expansion with only unary predicate symbols for conservative extensions ofUordered by interpretability that preserves the symbols ofU.

Abstract In this paper, we provide a fairly general self-reference-free proof of the second incompleteness theorem from Tarski’s theorem on the undefinability of truth.

In this paper we study the theory Q. We prove a basic result that says that, in a sense explained in the paper, Q can be split into two parts. We prove some consequences of this result. (i) Q is not a poly-pair theory. This means that, in a strong sense, pairing cannot be defined in Q. (ii) Q does not have the Pudlák Property. This means that there two interpretations of $$\mathsf{S}^1_2$$ in Q which do not have a definably isomorphic cut. (iii) Q is not sententially equivalent with $$\mathsf{PA}^-$$ . This tells us that we cannot do much better than mutual faithful interpretability as a measure of sameness of Q and $$\mathsf{PA}^-$$ . We briefly consider the idea of characterizing Q as the minimal-in-some-sense theory of some kind modulo some equivalence relation. We show that at least one possible road towards this aim is closed.

Sergei Adian, Lev Beklemishev, Albert Visser; Proof and Computation, Journal of Logic and Computation, Volume 21, Issue 4, 1 August 2011, Pages 541–542, https:/

Is it possible to give a coordinate-free formulation of the Second Incompleteness Theorem? We pursue one possible approach to this question. We show that (i) cutfree consistency for finitely axiomatized theories can be uniquely characterized modulo EA-provable equivalence and (ii) consistency for finitely axiomatized sequential theories can be uniquely characterized modulo EA-provable equivalence. The case of infinitely axiomatized RE theories is more delicate. We carefully discuss this in the article.

Abstract In this paper we give a new proof of the characterization of the closed fragment of the provability logic of Heyting's Arithmetic. We also provide a characterization of the closed fragment of the provability logic of Heyting's Arithmetic plus Markov's Principle and Heyting's Arithmetic plus Primitive Recursive Markov's Principle.

Abstract In this paper, we show that the predicate logics of consistent extensions of Heyting's Arithmetic plus Church's Thesis with uniqueness condition are complete . Similarly, we show that the predicate logic of HA*. i.e. Heyting's Arithmetic plus the Completeness Principle (for HA*) is complete . These results extend the known results due to Valery Plisko. To prove the results we adapt Plisko's method to use Tennenbaum's Theorem to prove ‘categoricity of interpretations’ under certain assumptions.

Abstract We investigate the theory IΔ0+Ω1 and strengthen [Bu86, Theorem 8.6] to the following: if NP ≠ co-NP, then Σ-completeness for witness comparison foumulas is not provable in bounded arithmetic. i.e., Next we study a “small reflection principle” in bounded arithmetic. We prove that for all sentences φ The proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudlák in [Pu86]. Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable Σ-completeness for witness comparison formulas.

Abstract In this paper I give a characterization of the closed fragment of the provability logic of I Δ0 + EXP with a propositional constant for EXP. In three appendices many details on arithmetization are provided.