Varieties of truth definitions (Q6565567)

While some new concepts introduced in the paper are defined in greater generality, the main results are specifically about theories of truth based on the axioms of bounded arithmetic \(\mathrm{I}\Delta_0+\exp\). A theory \(\mathrm{Th}\) extending \(\mathrm{I}\Delta_0+\exp\) is a \emph{theory of truth} for a language \(\mathcal L\) if there is a unary formula \(\Theta\) in the language of \(Th\) such that for each sentence \(\sigma\) of \(\mathcal L\), \(\mathrm{Th}\) proves \(\Theta(\ulcorner \sigma \urcorner)\leftrightarrow \sigma\). A theory of truth \(\mathrm{Th}\) is a \emph{definition of truth} if it is finitely axiomatizable.\N\NThe authors define the structure DEF of definitions of truth ordered by the naturally defined definability relation \(\blacktriangleleft\), in which each theory is represented by its equivalence class of the relation of mutual definability.\N\N\(\mathrm{CT}^-(x)\) is a truth definition stating that Tarski's inductive truth clauses hold for all sentences of logical depth at most \(x\). \(\mathrm{UTB}^-\) is \(\mathrm{I}\Delta_0+\exp\) extended by the axioms of the form \(T(\ulcorner \sigma(\dot{x} \urcorner)\leftrightarrow \sigma(x)\). In the preliminary section, it is shown that for each standard \(n\), \(\mathrm{I}\Delta_0+\exp\) defines \(\mathrm{UTB}^-\) and that \(\{\mathrm{CT}^-(n): n\in \omega\}\) and \(\mathrm{UTB}^-\) define one another. The authors state that their work was motivated by \textit{A. Visser}'s question whether there is a truth definition for the language of arithmetic that does not define \(\mathrm{UTB}^-\) [J. Appl. Log. - IfCoLog J. Log. Appl. 8, No. 7, 2073--2117 (2021; Zbl 1515.03215)]. The question is still open.\N\NcDEF is the subset of DEF consisting of those truth definitions that are conservative over \(\mathrm{I}\Delta_0+\exp\). The main result is that \((\mathrm{cDEF}, \blacktriangleleft)\) is a universal countable distributive lattice. In the proof it is shown that there is a lattice embedding from the countable atomless Boolean algebra \(\mathbb B\) into \((\mathrm{cDEF}, \blacktriangleleft)\), where \(\mathbb B\) is represented in the standard model of arithmetic by elementary formulas such that \(\mathrm{I}\Delta_0+\exp\) proves that \(\mathbb B\) is an atomless Boolean algebra. The codomain of the embedding is the set of special definitions of truth called weakly compositional.\N\NAmong other results, the authors prove that there are no dense \(\Sigma_2\)-definable subsets of DEF and that both \((\mathrm{cDEF}, \blacktriangleleft)\) and \((\mathrm{DEF}, \blacktriangleleft)\) have no minimal elements.\N\NAppendices include detailed proofs of some of the results as well as a proof of an interesting result due to Bartosz Wcisło: if \(M\) is a countable recursively saturated model of PA and \(c\) is a nonstandard definable element of \(M\), then there is a set \(T\subseteq M\) of sentences of logical depth at most \(c\) such that \((M,T)\models \mathrm{CT}^-(c)\) and a full truth predicate for \(M\) is definable in \((M,T)\).