Computable Quotient Presentations of Models of Arithmetic and Set Theory

Abstract

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 ,\le \}$ 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.

This article is a preliminary report of results following up research initiated at the conference Mathematical Logic and its Applications, held in memory of Professor Yuzuru Kakuda of Kobe University in September 2016 at the Research Institute for Mathematical Sciences (RIMS) in Kyoto. The second author is grateful for the chance twenty years ago to be a part of Kakuda-sensei’s logic group in Kobe, a deeply formative experience that he is pleased to see growing into a lifelong connection with Japan. He is grateful to the organizer Makoto Kikuchi and his other Japanese hosts for supporting this particular research visit, as well as to Bakhadyr Khoussainov for insightful conversations. The first author has been supported by the National Science Centre (Poland) research grant NCN PRELUDIUM UMO-2014/13/N/HS1/02058. He also thanks the Mathematics Program of the CUNY Graduate Center in New York for his research visit as a Fulbright Visiting Scholar between September 2016 and April 2017. Commentary concerning this paper can be made at http://jdh.hamkins.org/computable-quotient-presentations.