Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes

DOI10.1007/s00153-003-0195-xzbMath1058.03041OpenAlexW2010874076MaRDI QIDQ701736

Stephen G. Simpson, Stephen Binns

Publication date: 16 December 2004

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-003-0195-x

zbMATH Keywords

lattice embeddingMedvedev reducibility\(\Pi^0_1\) classMuchnik reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

The Medvedev lattice of computably closed sets, A Survey of Mučnik and Medvedev Degrees, Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism, Degrees of Unsolvability: A Tutorial, On the structure of the Medvedev lattice, Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes, choice classes, On the order dimension of locally countable partial orderings, Classes of Polish spaces under effective Borel isomorphism, MASS PROBLEMS AND HYPERARITHMETICITY, Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions, Degrees of difficulty of generalized r.e. separating classes, Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely, The finite intervals of the Muchnik lattice, Subsystems of second-order arithmetic between \(\text{RCA}_{0}\) and \(\text{WKL}_{0}\), Medvedev degrees of two-dimensional subshifts of finite type, Medvedev Degrees of Generalized R.E. separating Classes, Small \(\Pi^{0}_{1}\) classes, Computable metrics above the standard real metric, Mass Problems and Randomness, Mass problems associated with effectively closed sets, Mass Problems and Measure-Theoretic Regularity