Alexander Melnikov

A computable topological presentation of a space is given by an effective list of a countable basis of non-empty open sets so that the intersection of the basic sets is uniformly effectively enumerable. We show that every countably-based $T_0$ -space has a computable topological presentation, and that, conversely, every (formal) computable topological presentation represents some Polish space. In the compact case, we give a computable uniform list of computable topological presentations such that every compact Polish space is represented by exactly one presentation from the list. Note that none of these results assume that the Polish (or $T_0$ ) spaces are effective. Quite surprisingly, the effectively compact topological presentations turn out to be rather well behaved. Not only do such presentations allow one to construct a $\Delta ^0_2$ (complete) metric compatible with the topology, but also, under a mild extra condition, they can be turned into a computably compact Polish presentation of the space.

We prove that there exists a left-c.e. Polish space not homeomorphic to any right-c.e. space. Combined with some other recent works (to be cited), this finishes the task of comparing all classical notions of effective presentability of Polish spaces that frequently occur in the literature up to homeomorphism. We employ our techniques to provide a new, relatively straightforward construction of a computable Polish space K not homeomorphic to any computably compact space. We also show that the Banach space $C(K;\mathbb {R})$ has a computable Banach copy; this gives a negative answer to a question raised by McNicholl. We also give an example of a space that has both a left-c.e. and a right-c.e. presentation, yet it is not homeomorphic to any computable Polish space. In addition, we provide an example of a $\Delta ^0_2$ Polish space that lacks both a left-c.e. and a right-c.e. copy, up to homeomorphism.

We prove that for any computable successor ordinal of the form α = δ + 2k there exists computable torsion-free abelian group that is relatively Δα0 -categorical and not Δα−10 -categorical. Equivalently, for any such α there exists a computable TFAG whose initial segments are uniformly described by Σαc infinitary computable formulae up to automorphism, and there is no syntactically simpler family of formulae that would capture these orbits. As far as we know, the problem of finding such optimal examples of Δα0-categorical TFAGs for arbitrarily large α was first raised by Goncharov at least 10 years ago, but it has resisted solution 315–356]). As a byproduct of the proof, we introduce an effective functor that transforms a 0″-computable worthy labeled tree into a computable TFAG. We expect that this techni...

The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We apply this result to show that there is no Turing computable embedding of the class of graphs into the class of "rank-homogeneous" trees. The second main result says that there is a Turing computable embedding of the class of rank-homogeneous trees into the class of torsion-free Abelian groups. The third main result says that there is a "rank-preserving" Turing computable embedding of the class of rank-homogeneous trees into the class of Boolean algebras. Using this result, we show that there is a computable Boolean algebra of Scott rank ${\mathrm{\omega }}_{1}^{\mathrm{C}\mathrm{K}}$