On the Wadge reducibility of k-partitions

DOI10.1016/J.JLAP.2009.02.008MaRDI QIDQ1044675zbMATH OpenOpenAlexFDO

Authors Victor Selivanov

Publication date 18 December 2009

Published in The Journal of Logic and Algebraic Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jlap.2009.02.008

zbMATH Keywords

\(k\)-partitionBaire domainBaire spaceCantor domainCantor spacediscrete weak semilatticehomomorphic preorderWadge reducibility

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55) Descriptive set theory (03E15)

Review text

Let \(X\) be a topological space and let \(\nu,\mu:X\rightarrow k\) be \(k\)-partitions of \(X\) (\(k\geq 2\)). We say that \(\mu\) is Wadge-reducible to \(\nu\) if \(\mu=\nu\circ f\) for some continuous function \(f\) on \(X\). This notion generalizes the well-known notion of the Wadge reducibility of subsets of \(X\). In the article under review the main attention is paid to the Baire and Cantor spaces, Baire and Cantor domains and their close relatives. In the paper the author extends known results on the difference hierarchy of sets in the Baire and Cantor spaces to the case of \(k\)-partitions. Some facts on the Wadge hierarchy of sets are extended to the case of \(k\)-partitions as well. In particular, the structures of Wadge degreees of \(\Delta_2^0\)-measurable \(k\)-partitions are completely characterized. It is also shown that many natural substructures of the structure of Wadge degrees become undecidable for \(k\geq 3\).

Recommendations

• On the Wadge reducibility of \(k\)-partitions
• Extending Wadge theory to \(k\)-partitions
• scientific article; zbMATH DE number 7770056
• On the set of reduced -partitions of a positive integer
• Reduction of \(m\)-regular noncrossing partitions
• On the Kegel-Wielandt -problem for binary partitions
• On the \(k\)-measure of partitions and distinct partitions
• p-partitions revisited
• scientific article; zbMATH DE number 480311
• On the k-partition dimension of graphs

Cites work

• Definability in the Homomorphic Quasiorder of Finite Labeled Forests
• Definability of closure operations in the \(h\)-quasiorder of labeled forests
• Hierarchies in?-spaces and applications
• Hierarchies of function classes defined by the first-value operator
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• scientific article; zbMATH DE number 4210133 (Why is no real title available?)
• scientific article; zbMATH DE number 4053601 (Why is no real title available?)
• scientific article; zbMATH DE number 3685469 (Why is no real title available?)
• scientific article; zbMATH DE number 1500515 (Why is no real title available?)
• scientific article; zbMATH DE number 1759433 (Why is no real title available?)
• scientific article; zbMATH DE number 2154085 (Why is no real title available?)
• scientific article; zbMATH DE number 3997775 (Why is no real title available?)
• On the quasi-ordering of Borel linear orders under embeddability
• On the Wadge reducibility of \(k\)-partitions
• Structure of degrees of generalized index sets
• The quotient algebra of labeled forests modulo h-equivalence
• Topology and descriptive set theory
• Towards a descriptive set theory for domain-like structures
• Undecidability in Some Structures Related to Computation Theory
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• Variations of Wadge reducibility

Cited in

(14)

• Extending Wadge theory to \(k\)-partitions
• The Wadge hierarchy on Zariski topologies
• Reducibility by continuous functions and Wadge degrees
• Monotone Reducibility Over the Cantor Space
• Towards a descriptive theory of cb\(_{0}\)-spaces
• scientific article; zbMATH DE number 2154085 (Why is no real title available?)
• On the difference hierarchy in countably based \(T_{0}\)-spaces
• On the Wadge reducibility of \(k\)-partitions
• A Wadge hierarchy for second countable spaces
• Non-collapse of the effective Wadge hierarchy
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• Variations of Wadge reducibility
• Wadge-like reducibilities on arbitrary quasi-Polish spaces
• On the main scientific achievements of Victor Selivanov

This page was built for publication: On the Wadge reducibility of \(k\)-partitions

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