We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
We consider a slightly modified form of the standard Rudin-Keisler order on ideals and demonstrate the existence of complete (with respect to this order) ideals in various projective classes. Using our methods, we obtain a simple proof of Hjorth’s theorem on the existence of a complete Π¹₁ equivalence relation. This proof enables us (under PD) to generalize Hjorth’s result to the classes of equivalence relations.
We consider the Katětov order between ideals of subsets of natural numbers ("") and its stronger variant-containing an isomorphic ideal ("⊑ "). In particular, we are interested in ideals for which for every ideal . We find examples of ideals with this property and show how this property can be used to reformulate some problems known from the literature in terms of the Katětov order instead of the order "⊑ " (and vice versa).
Non-abelian Polish groups arising as countable products of countable groups can be tame in arbitrarily complicated ways. This contrasts with some results of Solecki who revealed a very different picture in the abelian case.