Logic Seminar

James WalshNYU
A theory satisfying a strong version of Tennenbaum's theorem

Friday, April 12, 2024 - 2:55pm
Malott 205

Tennenbaum's theorem states that no non-standard model of PA is computable. Hence, no unsound extension of PA has computable models. Pakhomov recently showed that this consequence of Tennenbaum's theorem is fragile; it depends on the signature in which PA is presented. In particular, there is a theory T such that (i) T is definitionally equivalent to PA (this is a strong form of bi-interpretability) and (ii) every consistent r.e. extension of T has a computable model. Pakhomov's techniques yield analogous results for ZF and other canonical systems. He asked whether there is a consistent, r.e. theory T such that no theory which is definitionally equivalent to T has a computable model. We answer this question positively through an ad hoc construction. This is joint work with Patrick Lutz.