The set of all indices of all functions provably recursive in any reasonable theory $T$ is shown to be recursively isomorphic to $U\times \overline{U}$, where $U$ is ${\Pi }_2$-complete set.

We generalize to the case of arithmetical transfinite induction the following three theorems for PA: the Wainer Theorem, the Paris-Harrington Theorem, and a version of the Solovay-Ketonen Theorem. We give uniform proofs using combinatorial constructions.

We establish the following model-theoretic characterization of the fragment IΔ₀ + Exp + BΣ₁ of Peano arithmetic in terms of fixed points of automorphisms of models of bounded arithmetic (the fragment IΔ₀ of Peano arithmetic with induction limited to Δ₀-formulae). Theorem A. The following two conditions are equivalent for a countable model of the language of arithmetic: (a) satisfies IΔ₀ + BΣ₁ + Exp; (b) $=I_{fix}\left(j\right)$ for some nontrivial automorphism j of an end extension of that satisfies IΔ₀. Here $I_{fix}\left(j\right)$ is the...