Abstract
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).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Boolos, G.S., Burgess, J.P., Jeffrey, R.C.: Computability and Logic, 5th edn. Cambridge University Press, Cambridge (2007)
Buss, S.: Proof theory of arithmetic. In: Buss, S. (ed.) Handbook of Proof Theory, pp. 79–147. Elsevier, Amsterdam (1998)
Cieśliński, C.: Deflationary truth and pathologies. J. Philos. Logic 39, 325–337 (2010)
Cieśliński, C.: The Epistemic Lightness of Truth. Deflationism and its Logic. Cambridge University Press, Cambridge (2017)
Enayat, A., Visser, A.: New constructions of full satisfaction classes. In: Achourioti, T., Galinon, H., Fujimoto, K., Martínez-Fernández, J. (eds.) Unifying the Philosophy of Truth, pp. 321–325. Springer, Berlin (2015)
Engström, F.: Satisfaction classes in nonstandard models of first-order arithmetic (2002). arXiv:math/0209408
Flumini, D., Sato, K.: From hierarchies to well-foundedness. Arch. Math. Log. 54, 855–863 (2014)
Hájek, P., Pudlák, P.: Metamathematics of First-Order Arithmetic. Springer, Berlin (1993)
Halbach, V.: Axiomatic Theories of Truth, 2nd edn. Cambridge University Press, Cambridge (2015)
Kaye, R.: Models of Peano Arithmetic. Oxford University Press, Oxford (1991)
Kotlarski, H.: Bounded induction and satisfaction classes. Zeitschrift für matematische Logik und Grundlagen der Mathematik 32, 531–544 (1986)
Kotlarski, H., Krajewski, S., Lachlan, A.: Construction of satisfaction classes for nonstandard models. Can. Math. Bull. 24, 283–293 (1981)
Krajewski, S.: Nonstandard satisfaction classes. In: Marek, W., et al. Set Theory and Hierarchy Theory: A Memorial Tribute to Andrzej Mostowski. Lecture Notes in Mathematics, vol. 537, pp. 121–144 . Springer, Berlin (1976)
Leigh, G.: Conservativity for theories of compositional truth via cut elimination. J. Symb. Log. 80, 845–865 (2015)
Łełyk, M.: Axiomatic theories of truth, bounded induction and reflection principles. Ph.D. disseration, University of Warsaw (2017)
Łełyk, M., Wcisło, B.: Notes on bounded induction for the compositional truth predicate. Rev. Symb. Logic 10, 455–480 (2017)
Löb, M.H.: Solution of a problem of Leon Henkin. J. Symb. Logic 20, 115–118 (1955)
Pakhomov, F., Walsh, J.: Reflection ranks and ordinal analysis (2018). arXiv:1805.02095
Pudlák, P.: The lengths of proofs. In: Buss, S. (ed.) Handbook of Proof Theory, pp. 547–637. Elsevier, Amsterdam (1998)
Visser, A.: Semantics and the liar paradox. In: Gabbay, D., Günthner, F. (eds.) Handbook of Philosophical Logic, vol. 4, pp. 149–240. Reidel, Dordrecht (1989)
Visser, A.: From Tarski to Gödel. Or, how to derive the second incompleteness theorem from the undefinability of truth without self-reference (2018). arXiv:1803.03937
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The work of Fedor Pakhomov is supported by the Russian Science Foundation under Grant 16-11-10252 and performed at Steklov Mathematical Institute of Russian Academy of Sciences. F. Pakhomov was selected as one of the Young Russian Mathematics award winners, and he would like to thank its sponsors and jury; his work on this particular paper was funded from another source. Sections 2 and 4 of this paper were contributed by A. Enayat; Section 3 was contributed by F. Pakhomov; Sections 1 and 5 were contributed jointly by the authors. The authors are grateful to the anonymous referees for their meticulous and valuable feedback.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Enayat, A., Pakhomov, F. Truth, disjunction, and induction. Arch. Math. Logic 58, 753–766 (2019). https://doi.org/10.1007/s00153-018-0657-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-018-0657-9