Logic Seminar

Thu, 30 March, 2017 8:00pm

Speaker: Michał Godziszewski, University of Warsaw (Philosophy) and CUNY (Mathematics), graduate student and 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.


Share This Event