Wadge hardness in Scott spaces and its effectivization

DOI10.1017/S0960129513000248zbMATH Open1362.54027DBLPjournals/mscs/BecherG15aarXiv1311.0331OpenAlexW3105972993WikidataQ61927010 ScholiaQ61927010MaRDI QIDQ5740667FDOQ5740667

Authors: Verónica Becher, Serge Grigorieff 

Publication date: 27 July 2016

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• The Wadge order on the Scott domain is not a well-quasi-order
• Effective wadge hierarchy in computable quasi-Polish spaces
• Title not available (Why is that?)
• A Q-WADGE HIERARCHY IN QUASI-POLISH SPACES
• Non-collapse of the effective Wadge hierarchy
• A Wadge hierarchy for second countable spaces
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• On the difference hierarchy in countably based \(T_{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)