A polynomially bounded recursive realizability, in which the recursive functions used in Kleene's realizability are restricted to polynomially bounded functions, is introduced. It is used to show that provably total functions of Ruitenburg's Basic Arithmetic are polynomially bounded (primitive) recursive functions. This sharpens our earlier result where those functions were proved to be primitive recursive. Also a polynomially bounded schema of Church's Thesis is shown to be polynomially bounded realizable. So the schema is consistent with Basic Arithmetic, whereas it is (...) inconsistent with Heyting Arithmetic. (shrink)

This paper will introduce the notion of a naming convention and use this paradigm to both develop a new version of the Second Incompleteness Theorem and to describe when an axiom system can partially evade the Second Incompleteness Theorem.

We formalize the notion of Herbrand Consistency in an appropriate way for bounded arithmetics, and show the existence of a finite fragment of IΔ0 whose Herbrand Consistency is not provable in IΔ0. We also show the existence of an IΔ0-derivable Π1-sentence such that IΔ0 cannot prove its Herbrand Consistency.

In 1981, Paris and Wilkie raised the open question about whether and to what extent the axiom system did satisfy the Second Incompleteness Theorem under Semantic Tableaux deduction. Our prior work showed that the semantic tableaux version of the Second Incompleteness Theorem did generalize for the most common definition of appearing in the standard textbooks.However, there was an alternate interesting definition of this axiom system in the Wilkie–Paris article in the Annals of Pure and Applied Logic 35 , pp. 261–302 (...) which we did not examine in our year-2002 article in the Journal of Symbolic Logic. Our first goal is to show that the incompleteness results of our prior paper can generalize in this alternate context. We will also develop a formal analysis, using a new technique called Passive Induction, that is simpler than the formalism we had used before.A further reason our results are of interest is that we have shown in a companion paper published in Electronic Notes in Theoretical Computer Science 165 , pp. 213–226 that some very unorthodox axiomizations for are anti-thresholds for the Herbrandized version of the Second Incompleteness Theorem. Thus, different axiomizations for have nearly fully opposite incompleteness properties.This paper is self-contained. It will not require a knowledge of our earlier results. (shrink)