Abstract:

In this talk, we'll prove that any nonstandard model of Peano arithmetic is not computable (i.e. the binary functions plus and times of a nonstandard model are not recursive functions). Proven in 1959, this result of Stanley Tennenbaum's was one of the first to connect the fields of recursion theory and model theory. Tennenbaum's theorem raises many questions. As time permits, we'll discuss, mostly without proof, just how complicated (or simple) nonstandard models can be. Put more formally, we'll discuss which Turing degrees d are such that there is a nonstandard model having degree d.

The relevant concepts will be introduced so that the talk should be accessible to anyone who knows what a "structure" of first order logic is and who has an intuitive idea of what it means to be "computable" and "computably enumerable." Non-logicians are welcome!