COMPUTABLE QUOTIENT PRESENTATIONS OF MODELS OF ARITHMETIC AND SET THEORY (Mathematical Logic and Its Applications)
Michał Tomasz Godziszewski, Joel David Hamkins · Institutional Repositories DataBase (IRDB) · 2017
We prove various extensions of the Tennenbaum phenomenon to the case of computable quotient presentations of models of arithmetic and set theory. Specifically, no nonstandard model of arithmetic has a computable quotient presentation by a c.e. equivalence relation. No $Sigma$_{1}-sound nonstandard model of arithmetic has a computable quotient presentation by a co-c.e. equivalence relation. No nonstandard model of arithmetic in the language {+, cdot, leq} has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even much weaker set theories has a computable quotient presentation by any equivalence relation of any complexity. And similarly no nonstandard model of finite set theory has a computable quotient presentation.