Ali Enayat had asked whether two halves of Disjunctive Correctness ([Formula: see text]) for the compositional truth predicate are conservative over Peano Arithmetic (PA). In this paper, we show that the principle “every true disjunction has a true disjunct” is equivalent to bounded induction for the compositional truth predicate and thus it is not conservative. On the other hand, the converse implication “any disjunction with a true disjunct is true” can be conservatively added to [Formula: see text]. The methods introduced (...) here allow us to give a direct nonconservativeness proof for [Formula: see text]. (shrink)

The current paper studies the formal properties of the Global Reflection Principle, to wit the assertion “All theorems of$\mathrm {Th}$are true,” where$\mathrm {Th}$is a theory in the language of arithmetic and the truth predicate satisfies the usual Tarskian inductive conditions for formulae in the language of arithmetic. We fix the gap in Kotlarski’s proof from [15], showing that the Global Reflection Principle for Peano Arithmetic is provable in the theory of compositional truth with bounded induction only ($\mathrm {CT}_0$). Furthermore, we (...) extend the above result showing that$\Sigma _1$-uniform reflection over a theory of uniform Tarski biconditionals ($\mathrm {UTB}^-$) is provable in$\mathrm {CT}_0$, thus answering the question of Beklemishev and Pakhomov [2]. Finally, we introduce the notion of a prolongable satisfaction class and use it to study the structure of models of$\mathrm {CT}_0$. In particular, we provide a new model-theoretical characterization of theories of finite iterations of uniform reflection and present a new proof characterizing the arithmetical consequences of$\mathrm {CT}_0$. (shrink)

We introduce a principle of local collection for compositional truth predicates and show that it is arithmetically conservative over the classically compositional theory of truth. This axiom states that upon restriction to formulae of any syntactic complexity, the resulting predicate satisfies full collection. In particular, arguments using collection for the truth predicate applied to sentences occurring in any given (code of a) proof do not suffice to show that the conclusion of that proof is true, in stark contrast to the (...) case of the induction scheme. We analyse various further results concerning end-extensions of models of compositional truth and the collection scheme for the compositional truth predicate. (shrink)

We introduce a tool for analysing models of $\text {CT}^-$, the compositional truth theory over Peano Arithmetic. We present a new proof of Lachlan’s theorem that the arithmetical part of models of $\text {CT}^-$ are recursively saturated. We also use this tool to provide a new proof of theorem from [8] that all models of $\text {CT}^-$ carry a partial inductive truth predicate. Finally, we construct a partial truth predicate defined for a set of formulae whose syntactic depth forms a (...) nonstandard cut which cannot be extended to a full truth predicate satisfying $\text {CT}^-$. (shrink)

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. (shrink)

By a well-known result of Kotlarski et al., first-order Peano arithmetic \ can be conservatively extended to the theory \ 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 \ while maintaining conservativity over \. Our main result shows that conservativity fails even (...) for the extension of \ obtained by the seemingly weak axiom of disjunctive correctness \ that asserts that the truth predicate commutes with disjunctions of arbitrary finite size. In particular, \ implies \\). Our main result states that the theory \ coincides with the theory \ obtained by adding \-induction in the language with the truth predicate. This result strengthens earlier work by Kotlarski and Cieśliński. 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 Gödel’s second incompleteness theorem, rather than by using the Visser–Yablo paradox, as in Visser’s original proof. (shrink)

This paper is a follow-up to [4], in which a mistake in [6] (which spread also to [9]) was corrected. We give a strenghtening of the main result on the semantical nonconservativity of the theory of PT−with internal induction for total formulae${(\rm{P}}{{\rm{T}}^ - } + {\rm{INT}}\left( {{\rm{tot}}} \right)$, denoted by PT−in [9]). We show that if to PT−the axiom of internal induction forallarithmetical formulae is added (giving${\rm{P}}{{\rm{T}}^ - } + {\rm{INT}}$), then this theory is semantically stronger than${\rm{P}}{{\rm{T}}^ - } + (...) {\rm{INT}}\left( {{\rm{tot}}} \right)$. In particular the latter is not relatively truth definable (in the sense of [11]) in the former. Last but not least, we provide an axiomatic theory of truth which meets the requirements put forward by Fischer and Horsten in [9]. The truth theory we define is based on Weak Kleene Logic instead of the Strong one. (shrink)

By a classical result of Kotlarski, Krajewski and Lachlan, pathological satisfaction classes can be constructed for countable, recursively saturated models of Peano arithmetic. In this paper we consider the question of whether the pathology can be eliminated; we ask in effect what generalities involving the notion of truth can be obtained in a deflationary truth theory (a theory of truth which is conservative over its base). It is shown that the answer depends on the notion of pathology we adopt. It (...) turns out in particular that a certain natural closure condition imposed on a satisfaction class—namely, closure of truth under sentential proofs—generates a nonconservative extension of a syntactic base theory (Peano arithmetic). (shrink)

In this paper we prove that the preordering $\lesssim $ of provable implication over any recursively enumerable theory $T$ containing a modicum of arithmetic is uniformly dense. This means that we can find a recursive extensional density function $F$ for $\lesssim $. A recursive function $F$ is a density function if it computes, for $A$ and $B$ with $A\lnsim B$, an element $C$ such that $A\lnsim C\lnsim B$. The function is extensional if it preserves $T$-provable equivalence. Secondly, we prove a (...) general result that implies that, for extensions of elementary arithmetic, the ordering $\lesssim $ restricted to $\Sigma_{n}$-sentences is uniformly dense. In the last section we provide historical notes and background material. (shrink)

In his 1967 paper Vaught used an ingenious argument to show that every recursively enumerable first order theory that directly interprets the weak system VS of set theory is axiomatizable by a scheme. In this paper we establish a strengthening of Vaught's theorem by weakening the hypothesis of direct interpretability of VS to direct interpretability of the finitely axiomatized fragment VS2 of VS. This improvement significantly increases the scope of the original result, since VS is essentially undecidable, but VS2 has (...) decidable extensions. We also explore the ramifications of our work on finite axiomatizability of schemes in the presence of suitable comprehension principles. (shrink)

It is well-known that natural axiomatic theories are well-ordered by consistency strength. However, it is possible to construct descending chains of artificial theories with respect to consistency strength. We provide an explanation of this well-orderedness phenomenon by studying a coarsening of the consistency strength order, namely, the$\Pi ^1_1$reflection strength order. We prove that there are no descending sequences of$\Pi ^1_1$sound extensions of$\mathsf {ACA}_0$in this ordering. Accordingly, we can attach a rank in this order, which we call reflection rank, to any$\Pi (...) ^1_1$sound extension of$\mathsf {ACA}_0$. We prove that for any$\Pi ^1_1$sound theoryTextending$\mathsf {ACA}_0^+$, the reflection rank ofTequals the$\Pi ^1_1$proof-theoretic ordinal ofT. We also prove that the$\Pi ^1_1$proof-theoretic ordinal of$\alpha $iterated$\Pi ^1_1$reflection is$\varepsilon _\alpha $. Finally, we use our results to provide straightforward well-foundedness proofs of ordinal notation systems based on reflection principles. (shrink)

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. 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 ϕ. (shrink)