The Tennenbaum phenomenon for computable quotient presentations of models of arithmetic and set theory, Shanghai, August 2021

This will be a talk for the conference Fudan Model Theory and Philosophy of Mathematics, held at Fudan University in Shanghai and online, 21-24 August 2021. My talk will take place on Zoom on 23 August 20:00 Beijing time (1pm BST).

Abstract. Tennenbaum famously proved that there is no computable presentation of a nonstandard model of arithmetic or indeed of any model of set theory. In this talk, I shall discuss the Tennenbaum phenomenon as it arises for computable quotient presentations of models. Quotient presentations offer a philosophically attractive treatment of identity, a realm in which questions of identity are not necessarily computable. Objects in the presentation serve in effect as names for objects in the final quotient structure, names that may represent the same or different items in that structure, but one cannot necessarily tell which. Bakhadyr Khoussainov outlined a sweeping vision for quotient presentations in computable model theory and made several conjectures concerning the Tennenbaum phenomenon. In this talk, I shall discuss joint work with Michał Godziszewski that settles and addresses several of these conjectures.

Computable quotient presentations of models of arithmetic and set theory

[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)

  1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
  2. 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.

Computable quotient presentations of models of arithmetic and set theory, CUNY set theory seminar, March 2017

This will be a talk for the CUNY Set Theory Seminar on March 10, 2017, 10:00 am in room 6417 at the CUNY Graduate Center.

CUNY GC

Abstract.  I shall 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. This is joint work with Michał Tomasz Godziszewski.

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 my talk, I shall engage specifically with two conjectures that Khoussainov had made at the meeting.

Conjecture. (Khoussainov)

  1. No nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
  2. 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.