Logic Seminar

Valentina Harizanov, George Washington University

"Arithmetically categorical structures"

 We investigate categoricity of countable structures from the computability-theoretic point of view. A computable structure is computably categorical if for every computable isomorphic structure there is a computable isomorphism. A computable structure A is relatively computably categorical if for every isomorphic B, there is an isomorphism computable relative to the atomic diagram of B or, equivalently, A has a computably enumerable Scott family of existential formulas. Computable categoricity and relative computable categoricity often but not always coincide for structures from natural classes. We similarly define categoricity and relative categoricity corresponding to higher levels in arithmetical hierarchy, and look for their characterizations for structures from natural classes.

MC 5501