A theory satisfying a strong version of Tennenbaum's theorem

2023/09/20 by Patrick Lutz, James Walsh, Lutz, Patrick +1 · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Advanced Topology and Set Theory #Mathematical and Theoretical Analysis

paper · pdf · doi:10.48550/arxiv.2309.11598

Abstract

We answer a question of Pakhomov by showing that there is a consistent, c.e. theory T such that no theory which is definitionally equivalent to T has a computable model. A key tool in our proof is the model-theoretic notion of mutual algebraicity.

Cited by

• ESCAPING TENNENBAUM’S THEOREM AND A STRONG JUMP INVERSION THEOREM

Related

• How to escape Tennenbaum's theorem
• Computable quotient presentations of models of arithmetic and set theory
• Mutually algebraic structures and expansions by predicates
• A computability theoretic equivalent to Vaught's conjecture
• The theory of tracial von Neumann algebras does not have a model companion