Kurt Gödel Research Center

2017 seminar talk: Computable quotient presentations of models of arithmetic and set theory

Talk held by Michał Tomasz Godziszewski (University of Warsaw, Poland) at the KGRC seminar on 2017-03-23.

Abstract

A computable quotient presentation of a mathematical structure $\mathbb{A}$ consists of a computable structure on the natural numbers $(\mathbb{N}, \star, \ast, \ldots)$ (meaning that the operations and relations of the structure are computable) and an equivalence relation $E$ on $\mathbb{N}$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $(\mathbb{N}, \star, \ast, \ldots)_{/E}$ is isomorphic to the given structure $\mathbb{A}$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on, for any kind of mathematical structure.

In 2016 Bakhadyr Khoussainov discussed some questions and results in this area. Part of this 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$.

We address two conjectures that Khoussainov had made and 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. Concluding from that, we indicate how the program of computable quotient presentations has difficulties with purely relational structures (as opposed to algebras).

This is joint work with Joel David Hamkins, GC CUNY.