Wadge hardness in Scott spaces and its effectivization

DOI10.1017/S0960129513000248MaRDI QIDQ5740667zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Verónica Becher, Serge Grigorieff

Publication date 27 July 2016

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.0331

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45) Descriptive set theory (03E15) Continuous lattices and posets, applications (06B35) Linearly ordered topological spaces, generalized ordered spaces, and partially ordered spaces (54F05)

Abstract: We prove some results on the Wadge order on the space of sets of natural numbers endowed with Scott topology, and more generally, on omega-continuous domains. Using alternating decreasing chains we characterize the property of Wadge hardness for the classes of the Hausdorff difference hierarchy (iterated differences of open sets). A similar characterization holds for Wadge one-to-one and finite-to-one completeness. We consider the same questions for the effectivization of the Wadge relation. We also show that for the space of sets of natural numbers endowed with the Scott topology, in each class of the Hausdorff difference hierarchy there are two strictly increasing chains of Wadge degrees of sets properly in that class. The length of these chains is the rank of the considered class, and each element in one chain is incomparable with all the elements in the other chain.

Recommendations

• The Wadge order on the Scott domain is not a well-quasi-order
• Effective wadge hierarchy in computable quasi-Polish spaces
• A Wadge hierarchy for second countable spaces
• Wadge-like reducibilities on arbitrary quasi-Polish spaces
• scientific article; zbMATH DE number 3875282

Cites work

• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 3232606 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Chain properties in Pomega
• Continuous Lattices and Domains
• Domains for Computation in Mathematics, Physics and Exact Real Arithmetic
• From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II
• Hierarchies in?-spaces and applications
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• On the difference hierarchy in countably based \(T_{0}\)-spaces
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations
• The effective theory of Borel equivalence relations
• Topological complexity with continuous operations
• Towards a descriptive set theory for domain-like structures
• Wadge Degrees ofω-Languages of Deterministic Turing Machines

Cited in

(8)

• On the difference hierarchy in countably based \(T_{0}\)-spaces
• The Wadge order on the Scott domain is not a well-quasi-order
• Effective wadge hierarchy in computable quasi-Polish spaces
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)
• A Q-WADGE HIERARCHY IN QUASI-POLISH SPACES
• A Wadge hierarchy for second countable spaces
• Non-collapse of the effective Wadge hierarchy
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces

This page was built for publication: Wadge hardness in Scott spaces and its effectivization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740667)