×

Truth, disjunction, and induction. (English) Zbl 1477.03250

Summary: By a well-known result of H. Kotlarski et al. [Can. Math. Bull. 24, 283–293 (1981; Zbl 0471.03054)], 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 H. Kotlarski [Z. Math. Logik Grundlagen Math. 32, 531–544 (1986; Zbl 0622.03025)] and C. Cieśliński [J. Philos. Log. 39, No. 3, 325–337 (2010; Zbl 1197.03054)]. 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 A. Visser’s original proof [Synth. Libr. 167, 617–706 (1989; Zbl 0875.03030)].

MSC:

03F30 First-order arithmetic and fragments

References:

[1] Boolos, G.S., Burgess, J.P., Jeffrey, R.C.: Computability and Logic, 5th edn. Cambridge University Press, Cambridge (2007) · Zbl 1154.03001 · doi:10.1017/CBO9780511804076
[2] Buss, S.; Buss, S. (ed.), Proof theory of arithmetic, 79-147 (1998), Amsterdam · Zbl 0911.03029 · doi:10.1016/S0049-237X(98)80017-7
[3] Cieśliński, C.: Deflationary truth and pathologies. J. Philos. Logic 39, 325-337 (2010) · Zbl 1197.03054 · doi:10.1007/s10992-010-9128-4
[4] Cieśliński, C.: The Epistemic Lightness of Truth. Deflationism and its Logic. Cambridge University Press, Cambridge (2017)
[5] Enayat, A.; Visser, A.; Achourioti, T. (ed.); Galinon, H. (ed.); Fujimoto, K. (ed.); Martínez-Fernández, J. (ed.), New constructions of full satisfaction classes, 321-325 (2015), Berlin · doi:10.1007/978-94-017-9673-6_16
[6] Engström, F.: Satisfaction classes in nonstandard models of first-order arithmetic (2002). arXiv:math/0209408
[7] Flumini, D., Sato, K.: From hierarchies to well-foundedness. Arch. Math. Log. 54, 855-863 (2014) · Zbl 1338.03011 · doi:10.1007/s00153-014-0392-9
[8] Hájek, P., Pudlák, P.: Metamathematics of First-Order Arithmetic. Springer, Berlin (1993) · Zbl 0781.03047 · doi:10.1007/978-3-662-22156-3
[9] Halbach, V.: Axiomatic Theories of Truth, 2nd edn. Cambridge University Press, Cambridge (2015) · Zbl 1223.03001
[10] Kaye, R.: Models of Peano Arithmetic. Oxford University Press, Oxford (1991) · Zbl 0744.03037
[11] Kotlarski, H.: Bounded induction and satisfaction classes. Zeitschrift für matematische Logik und Grundlagen der Mathematik 32, 531-544 (1986) · Zbl 0622.03025 · doi:10.1002/malq.19860323107
[12] Kotlarski, H., Krajewski, S., Lachlan, A.: Construction of satisfaction classes for nonstandard models. Can. Math. Bull. 24, 283-293 (1981) · Zbl 0471.03054 · doi:10.4153/CMB-1981-045-3
[13] 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) · Zbl 0338.02030
[14] Leigh, G.: Conservativity for theories of compositional truth via cut elimination. J. Symb. Log. 80, 845-865 (2015) · Zbl 1376.03056 · doi:10.1017/jsl.2015.27
[15] Łełyk, M.: Axiomatic theories of truth, bounded induction and reflection principles. Ph.D. disseration, University of Warsaw (2017)
[16] Łełyk, M., Wcisło, B.: Notes on bounded induction for the compositional truth predicate. Rev. Symb. Logic 10, 455-480 (2017) · Zbl 1421.03028 · doi:10.1017/S1755020316000368
[17] Löb, M.H.: Solution of a problem of Leon Henkin. J. Symb. Logic 20, 115-118 (1955) · Zbl 0067.00202 · doi:10.2307/2266895
[18] Pakhomov, F., Walsh, J.: Reflection ranks and ordinal analysis (2018). arXiv:1805.02095 · Zbl 1511.03018
[19] Pudlák, P.; Buss, S. (ed.), The lengths of proofs, 547-637 (1998), Amsterdam · Zbl 0920.03056 · doi:10.1016/S0049-237X(98)80023-2
[20] Visser, A.; Gabbay, D. (ed.); Günthner, F. (ed.), Semantics and the liar paradox, No. 4, 149-240 (1989), Dordrecht
[21] 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 · Zbl 1444.03167
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.