Аннотация:
We define and study an effective version of the Wadge hierarchy in computable quasi-Polish spaces which
include most spaces of interest for computable analysis. Along with hierarchies of sets we study hierarchies
of $k$-partitions which are interesting on their own. We show that levels of such hierarchies are preserved
by the computable effectively open surjections, that if the effective Hausdorff-Kuratowski theorem holds
in the Baire space then it holds in every computable quasi-Polish space, and we extend the effective
Hausdorff theorem to $k$-partitions. We establish sufficient conditions for the non-collapse of the
effective Wadge hierarchy and apply them to some concrete spaces like the discrete spaces of intergers,
Baire space and Cantor. We show that the proof of non-collapse in any concrete space is highly non-trivial.
|
