The classification problem for compact computable metric spaces

Melnikov A; Nies A

The classification problem for compact computable metric spaces

Date

2013

Publisher

Springer, Berlin, Heidelberg

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.

Citation

Lecture Notes in Computer Science, 2013, 7921 pp. 320 - 328

Collections

Conference Papers

Full item page