Michał Tomasz Godziszewski: Computable quotient presentations of models of arithmetic and set theory

KGRC Research Seminar – 2017-03-23 at 4pm

Speaker: Michał Tomasz Godziszewski (University of Warsaw, Poland)

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.

 

Attachments

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.