Kurt Gödel Research Center

2012 seminar talk: Computable Categoricity

Talk held by Dan Turetsky (KGRC) at the KGRC seminar on 2012-12-06.

Abstract

This talk is in the area of computable model theory. A computable model is called "computably categorical" if for every two computable copies, there is a computable isomorphism between them. As defined, this is an external property of the model – the statement does not involve the internal structure of the model. A closely related property is being "relatively computably categorical" (which will be defined in the talk). Goncharov showed that being relatively computably categorical is equivalent to a nice internal property of the model; a model is relatively computably categorical if and only if the realized types of the model are all effectively isolated. We present a pathological collection of models which demonstrate that computable categoricity does not correspond to any internal property of this form. These models also allow us to show that the property of being computably categorical is $\Pi^1_1$-complete.