Logic Seminar-Computable quotient presentations of models of arithmetic and set theory

Thursday, March 30, 2017

4:00–5:00p.m.

Speaker: Michał Godziszewski, University of Warsaw and CUNY (Fulbright Research Scholar)

Place: Rome Hall (801 22nd Street), Room 352

Title: Computable quotient presentations of models of arithmetic and set theory

Abstract: We will discuss two conjectures of Khoussainov and prove various extensions of 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 computably enumerable equivalence relation. No nonstandard model of arithmetic in the language {+, x, ≤} has a computably enumerable quotient presentation by any equivalence relation of any complexity. No model of ZFC or even of much weaker set theory has a computable quotient presentation by any equivalence relation of any complexity. Similarly, no nonstandard model of finite set theory has a computable quotient presentation. We will further discuss the difficulties of computable quotient presentations in the case of purely relational structures.