A Survey of Mučnik and Medvedev Degrees

DOI10.2178/bsl/1333560805zbMath1248.03063arXiv1007.2376OpenAlexW2070956093MaRDI QIDQ2893281

Peter G. Hinman

Publication date: 20 June 2012

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

survey paperMedvedev degreeimplicative latticesMuchnik degree\(\Pi^0_1\) sets and classesglobal degree structureslattice logicslocal degree structures

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Related Items (12)

Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism ⋮ Natural factors of the Muchnik lattice capturing IPC ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ First-order logic in the Medvedev lattice ⋮ Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions ⋮ Natural factors of the Medvedev lattice capturing IPC ⋮ Completeness, Compactness, Effective Dimensions ⋮ Unnamed Item ⋮ Highness properties close to PA completeness ⋮ Comparing the degrees of enumerability and the closed Medvedev degrees ⋮ Computability of Subsets of Metric Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• The Medvedev lattice of computably closed sets
• Degrees of difficulty of generalized r.e. separating classes
• Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely
• Mass problems and intuitionism
• Intermediate logics and factors of the Medvedev lattice
• Density of the Medvedev lattice of \(\Pi^0_1\) classes
• Embedding Brouwer algebra in the Medvedev lattice
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Algorithmic Randomness and Complexity
• Degrees of models
• Mass Problems and Randomness
• Some Quotient Lattices of the Medvedev Lattice
• Some remarks on the algebraic structure of the Medvedev Lattice
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• On the structure of the Medvedev lattice
• The First Order Theories of the Medvedev and Muchnik Lattices
• K-Triviality of Closed Sets and Continuous Functions
• A fixed-point-free minimal degree
• A splitting theorem for the Medvedev and Muchnik lattices
• An extension of the recursively enumerable Turing degrees
• Almost everywhere domination
• The definition of random sequences
• Class groups of integral group rings

This page was built for publication: A Survey of Mučnik and Medvedev Degrees