The classification problem for compact computable metric spaces

Abstract

We adjust methods of computable model theory to effective analysis. We use index sets and infinitary logic to obtain classification-type results for compact computable metric spaces. We show that every compact computable metric space can be uniquely described, up to isometry, by a computable Π3 formula, and that orbits of elements are uniformly given by computable Π2 formulas. We show that deciding if two compact computable metric spaces are isometric is a Π02Π20 complete problem within the class of compact computable spaces, which in itself is Π03Π30 . On the other hand, if there is an isometry, then ∅ ′′ can compute one. In fact, there is a set low relative to ∅ ′ which can compute an isometry. We show that the result can not be improved to ∅ ′. We also give further results for special classes of compact spaces, and for other related classes of Polish spaces.