By a well-known result of Kotlarski et al. (1981), first-order Peano arithmetic \({{\mathsf {P}}}{{\mathsf {A}}}\) can be conservatively extended to the theory \({{\mathsf {C}}}{{\mathsf {T}}}^{-}\mathsf {[PA]}\) of a truth predicate satisfying compositional axioms, i.e., axioms stating that the truth predicate is correct on atomic formulae and commutes with all the propositional connectives and quantifiers. This result motivates the general question of determining natural axioms concerning the truth predicate that can be added to \({{\mathsf {C}}}{{\mathsf {T}}}^{-}\mathsf {[PA]}\) while maintaining conservativity over \( {{\mathsf {P}}}{{\mathsf {A}}}\). Our main result shows that conservativity fails even for the extension of \({{\mathsf {C}}}{{\mathsf {T}}}^{-}\mathsf {[PA]}\) obtained by the seemingly weak axiom of disjunctive correctness \({{\mathsf {D}}}{{\mathsf {C}}}\) that asserts that the truth predicate commutes with disjunctions of arbitrary finite size. In particular, \({{\mathsf {C}}}{\mathsf {T}}^{-}\mathsf {[PA]}+\mathsf {DC}\) implies \(\mathsf {Con}(\mathsf {PA})\). Our main result states that the theory \({\mathsf {C}}{\mathsf {T}}^{-}\mathsf {[PA]}+\mathsf {DC}\) coincides with the theory \({\mathsf {C}}{\mathsf {T}}_{0}\mathsf {[PA]}\) obtained by adding \( \Delta _{0}\)-induction in the language with the truth predicate. This result strengthens earlier work by Kotlarski (1986) and Cieśliński (2010). For our proof we develop a new general form of Visser’s theorem on non-existence of infinite descending chains of truth definitions and prove it by reduction to (Löb’s version of) Gödel’s second incompleteness theorem, rather than by using the Visser–Yablo paradox, as in Visser’s original proof (1989).

Let $\left\langle {{W_n}:n \in \omega } \right\rangle$ be a canonical enumeration of recursively enumerable sets, and supposeTis a recursively enumerable extension of PA (Peano Arithmetic) in the same language. Woodin (2011) showed that there exists an index $e \in \omega$ (that depends onT) with the property that if ${\cal M}$ is a countable model ofTand for some ${\cal M}$ -finite sets, ${\cal M}$ satisfies ${W_e} \subseteq s$ , then ${\cal M}$ has an end extension ${\cal N}$ that satisfiesT+W_e=s.Here we generalize Woodin’s theorem to all recursively enumerable extensionsTof the fragment ${{\rm{I}\rm{\Sigma }}_1}$ of PA, and remove the countability restriction on ${\cal M}$ whenTextends PA. We also derive model-theoretic consequences of a classic fixed-point construction of Kripke (1962) and compare them with Woodin’s theorem.

By classical results of Dedekind and Zermelo, second order logic imposes categoricity features on Peano Arithmetic and Zermelo-Fraenkel set theory. However, we have known since Skolem’s anti-categoricity theorems that the first order formulations of Peano Arithmetic and Zermelo- Fraenkel set theory (i.e., PA and ZF) are not categorical. Here we investigate various categoricity-like properties (including tightness, solidity, and internal categoricity) that are exhibited by a distinguished class of first order theories that include PA and ZF, with the aim of understanding what is special about canonical foundational first order theories.

Let ${\cal T}$ be any of the three canonical truth theories CT⁻ (compositional truth without extra induction), FS⁻ (Friedman–Sheard truth without extra induction), or KF⁻ (Kripke–Feferman truth without extra induction), where the base theory of ${\cal T}$ is PA (Peano arithmetic). We establish the following theorem, which implies that ${\cal T}$ has no more than polynomial speed-up over PA.Theorem. ${\cal T}$ is feasibly reducible to PA, in the sense that there is a polynomial time computable function f such that for every ${\cal T}$ -proof π of an arithmetical sentence ϕ, f (π) is a PA-proof of ϕ.