CUNY Logic Workshop, New York, April 2010

Abstract: There are a number of interesting classification problems surrounding models of PA. For instance, given a fixed completion $T\supset PA$, one may consider the classification problem for all countable models, finitely generated models, recursively saturated models, and several others. The idea of this talk is to isolate the complexity of these classification problems with respect to the Borel reducibility theory of equivalence relations. Roughly speaking, the isomorphism relation on one collection $X$ of structures is said to be Borel reducible to the isomorphism relation on another collection $Y$ iff there exists a Borel function $f\colon X\to Y$ such that $M\cong M’$ iff $f(M)\cong f(M’)$. In this talk, I’ll introduce the theory of Borel reducibility, and then compare each of the above classification problems for models of PA against one another and also against some of the benchmark classification problems from descriptive set theory.