A splitting theorem for the Medvedev and Muchnik lattices

DOI10.1002/MALQ.200310034zbMATH Open1022.03021OpenAlexW1980030616MaRDI QIDQ4419261FDOQ4419261

Authors: Stephen Binns 

Publication date: 31 July 2003

Published in: MLQ (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310034

Recommendations

• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• On the structure of the Medvedev lattice
• Some remarks on the algebraic structure of the Medvedev Lattice
• Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes
• The finite intervals of the Muchnik lattice

zbMATH Keywords

reducibilitysplittinglattice embeddingMedvedev degree\(\Pi^0_1\) classMuchnik degreededicable theory

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Other degrees and reducibilities in computability and recursion theory (03D30)

Cited In (28)

• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Small \(\Pi^{0}_{1}\) classes
• Mass problems associated with effectively closed sets
• The Medvedev lattice of computably closed sets
• Medvedev degrees of two-dimensional subshifts of finite type
• MASS PROBLEMS AND HYPERARITHMETICITY
• A splitting theorem for blocks
• The finite intervals of the Muchnik lattice
• Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes
• Degrees of difficulty of generalized r.e. separating classes
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• A survey of Mučnik and Medvedev degrees
• Classes of Polish spaces under effective Borel isomorphism
• Medvedev degrees of generalized r.e. separating classes
• Mass problems and measure-theoretic regularity
• Intermediate logics and factors of the Medvedev lattice
• On the structure of the Medvedev lattice
• Mass problems and density
• Intervals of the Muchnik lattice
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Title not available (Why is that?)
• Mass Problems and Randomness
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• Some remarks on the algebraic structure of the Medvedev Lattice
• Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
• Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely
• Degrees of unsolvability: a tutorial
• Immunity for closed sets

This page was built for publication: A splitting theorem for the Medvedev and Muchnik lattices

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