A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $\mathbf {0}'$ -computable low $_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$, there exists a Polish space $X_n$ such that exactly the high $_{n}$ -degrees are required to present the homeomorphism type of $X_n$. (...) Along the way we investigate the computable aspects of Čech homology groups. We also show that no compact Polish space has a least presentation with respect to Turing reducibility. (shrink)

The Wadge hierarchy was originally defined and studied only in the Baire space. Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski -type theorems in quasi-Polish spaces. In fact, many results hold not (...) only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q. (shrink)

Attempts to extend the classical Hausdorff difference hierarchy to the case of partitions of a space to k > 2 subsets lead to non‐equivalent notions. In a hope to identify the “right” extension we consider the extensions appeared in the literature so far: the limit‐, level‐, Boolean and Wadge hierarchies of k ‐partitions. The advantages and disadvantages of the four hierarchies are discussed. The main technical contribution of this paper is a complete characterization of the Wadge degrees of Δ02‐measurable k (...) ‐partitions of the Baire space. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

The wedge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g. several Hausdorff-Kuratowski-type theorems in quasi-Polish spaces. In fact, (...) many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q. (shrink)

We establish some results on the Borel and difference hierarchies in φ-spaces. Such spaces are the topological counterpart of the algebraic directed-complete partial orderings. E.g., we prove analogs of the Hausdorff Theorem relating the difference and Borel hierarchies and of the Lavrentyev Theorem on the non-collapse of the difference hierarchy. Some of our results generalize results of A. Tang for the space Pω. We also sketch some older applications of these hierarchies and present a new application to the question of (...) characterizing the ω-ary Boolean operations generating a given level of the Wadge hierarchy from the open sets. (shrink)

It is well known that any finitary operation is recursive in a suitable total numeration. A. Orlicki showed that there is an ω-operation not recursive in any total numeration. We will show that any ω-operation is recursive in a partial numeration.

We prove that for any k≥3 each element of the h-quasiorder of finite k-labeled forests is definable in the ordinary first order language and, respectively, each element of the h-quasiorder of countable k-labeled forests is definable in the language Lω1ω, in both cases provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we characterize the automorphism groups of both structures and show that the structure of finite k-forests is atomic. Similar results hold true for two other relevant (...) structures: the h-quasiorder of finite k-labeled trees and of finite k-labeled trees with a fixed label of the root element. (shrink)

We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than (...) the recursive structures. (shrink)