

Workshop on Proof Theory, Modal Logic and Reflection Principles
October 18, 2017 16:40–17:15, Moscow, Steklov Mathematical Institute






Models of the compositional truth theory with bounded induction
B. Wcisło^{} 
Video records: 

MP4 
812.1 Mb 

MP4 
222.5 Mb 
Number of views: 
This page:  56  Video files:  18 

Abstract:
In [1], it has been shown that $\mathrm{CT}_0$, a compositional truth theory with $\Delta_0$induction for the truth predicate, is not conservative over Peano Arithmetic. Subsequently, Mateusz Łełyk has shown that this theory proves the principle of firstorder closure which states that the set of true sentences is closed under derivations in firstorder logic.
We show how the original proof combined with the refined result by Łełyk shows that in every model $\mathrm{M}$ of $\mathrm{CT}_0$, the truth predicate may be presented as a sum of the predicates $\mathrm{T_c}$ which satisfy full induction scheme and compositional axioms for sentences of logical complexity at most c (i.e., with the syntactic tree of height at most $\mathrm{c}$). The observation that the original argument of nonconservativeness of $\mathrm{CT}_0$ yields this modeltheoretic corollary is due to Ali Enayat.
Using standard arguments, one can show that the theory $\mathrm{CT}_0$ is arithmetically strictly weaker than $\mathrm{CT}$, its counterpart with full induction. In particular, there exist models of $\mathrm{PA}$ which admit an expansion to a model of $\mathrm{CT}_0$ but do not admit an expansion to a model of $\mathrm{CT}$. In such models, there exists a family of compatible fully inductive truth predicates which are compositional for sentences of arbitrarily high logical complexity, but there is no truth predicate which is fully inductive and compositional for all sentences.
The above result is closely related to a problem in the theory of models of Peano Arithmetic which asks whether the existence of inductive satisfaction classes compositional for $\Sigma_{\mathrm{c}}$ sentences for all c implies existence of a fully inductive satisfaction class.
Language: English
References

M. Łełyk, B. Wcisło, “Notes on bounded induction for the compositional truth predicate”, The Review of Symbolic Logic, 10:3 (2017), 455–480

