Computable Analysis and Classification Problems

摘要

Suppose we are given a collection of mathematical objects such as the class of connected compact Polish groups or the set of all real numbers which are normal to some base. Is there a reasonable classification of these objects (e.g. by invariants)? One nice property expected from a useful classification is that it makes the classified objects easier to handle algorithmically. Even if the general classification of a class of objects is impossible, sometimes there is a useful hierarchy of objects in this class, e.g., the Cantor-Bendixson rank of a scattered Polish space, the Ulm type of a reduced abelian p-group, etc. We would expect that the algorithmic, algebraic, or topological complexity of objects increase from lower to higher levels of a hierarchy. Can you make this intuition formal? Is it possible to formally measure the algorithmic complexity of a given classification or a hierarchy, or perhaps show that there is no reasonable classification at all? Can algorithmic tools help us to define useful hierarchies?