Speaker: Michał Godziszewski, University of Warsaw (Philosophy) and CUNY (Mathematics), graduate student and Fulbright research scholar

Place: Rome Hall (801 22^nd 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.