[bibtex key=GodziszewskiHamkins2017: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,\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.
A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle\newcommand\N{\mathbb{N}}\N,\star,\ast,\dots\rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\N$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle\N,\star,\ast,\dots\rangle/E$ is isomorphic to $\mathcal A$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure. In a language with relations, it is also natural to relax the concept somewhat by considering the computably enumerable quotient presentations, which allow the pre-quotient relations to be merely computably enumerable, rather than insisting that they must be computable.
At the 2016 conference Mathematical Logic and its Applications at the Research Institute for Mathematical Sciences (RIMS) in Kyoto, Bakhadyr Khoussainov outlined a sweeping vision for the use of computable quotient presentations as a fruitful alternative approach to the subject of computable model theory. In his talk (see his slides), he outlined a program of guiding questions and results in this emerging area. Part of this program concerns the investigation, for a fixed equivalence relation $E$ or type of equivalence relation, which kind of computable quotient presentations are possible with respect to quotients modulo $E$.
In this article, we engage specifically with two conjectures that Khoussainov had made at the meeting.
Conjecture. (Khoussainov)
- No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
- Some nonstandard model of arithmetic admits a computable quotient presentation by a co-c.e.~equivalence relation.
We prove the first conjecture and refute several natural variations of the second conjecture, although a further natural variation, perhaps the central case, remains open. In addition, we consider and settle the natural analogues of the conjectures for models of set theory.
Dear Joel,
I’ll ask the same question I asked Michał when he gave the talk at the KGRC, as I’m curious about your views on this:
There’s an argument in the philosophical literature using Tennenbaum-style phenomena that goes roughly as follows:
1. No non-standard model of PA is recursive.
2. Reflecting on our practice of addition and multiplication, we see that these are recursive functions.
C. Therefore, we single out the standard model by using our understanding of a recursive procedure.
The normal response (pretty persuasively argued in Tim Button and Peter Smith’s article on this) is that the notion of recursive presupposes some notion of finiteness in understanding recursive computation, which is precisely what a sceptic about arithmetic would deny.
Now yourself and Michał have shown that something similar to Tennenbaum holds for equivalence relations (in fact, that the problem seems to be with specifically with *relations* rather than any bi-interpretability with set theory or anything of that sort).
My question: Do you think your result tells for or against Tennenbaum-style arguments such as the one presented above?
Best Wishes,
Neil
Thanks for the comment, Neil, and I think I’d have to agree with the reply that you mentioned by Button and Smith. Of course, the people who live in the nonstandard universe believe that their + and * are computable also, even if those outside can see that they have nonstandard arithmetic. I’m not sure whether any part of this exchange is affected by the idea of quotient presentations; indeed, I’m inclined to say that basically the same exchange can be had in the quotient context. The quotient result is stronger than the ordinary Tennenbaum result, since in Tennenbaum’s theorem, one assumes that it is computable to tell whether two representations of a number are equal, but in the quotient context, this has the complexity of the equivalence relation (so it is c.e. or co-c.e. or whatever). The quotient theorem says that even with this relaxed concept of equality, you cannot have computable + and *. I suppose that if the Tennenbaum theorem becomes stronger, then it should strengthen the hand of those who are appealing to it, but nevertheless the reply you mentioned still seems very strong.